Programación Cuadrática

Programación Cuadrática
Un problema de Programación Cuadrática es aquél que contiene una función objetivo cuadrática y restricciones lineales
min f (x ) =
n

∑ c j x j + ∑ ∑ q ij x j x i
j =1 i =1 j =1

n

n

n

s.a.

∑ aij x j
j =1

≥ bi

i = 1,K, m

xj ≥ 0

En notación matricial:

min s.a.

f ( x ) = cx + xT Qx g1 ( x) = x ≥ 0 g 2 ( x) = Ax − b ≥ 0

Condicionesde Kuhn-Tucker
min s.a. f ( x ) = cx + xT Qx g1 ( x) = x ≥ 0 g 2 ( x) = Ax − b ≥ 0
Condiciones de KT Problema de Programación Cuadrática

c + x T ( Q + Q T ) − u − yA = 0

∇f ( x) = c + xT (Q + Q T ) ⎡1 ⎤ ∇g1 ( x) = ⎢...⎥ ⎢ ⎥ ⎢1 ⎥ ⎣ ⎦ ∇g 2 ( x ) = A
T

Ax − b ≥ 0 x ≥ 0 ux = 0 u≥ 0 y T ( Ax − b ) = 0 y ≥ 0

Si la función objetivo es convexa, es decir la matriz Q es una matriz cuadrada, ydefinida positiva, y las restricciones son lineales, las condiciones de Kunh-Tucker son necesarias y suficientes para encontrar el óptimo de la función. => Método de Wolfe sólo hay que resolver las condiciones de KT para encontrar el óptimo, como un problema de programación lineal. Otro método más eficiente y simple para resolver las CKT es el método pivote complementario. Para el cual hacemos elsiguiente cambio de variable:

u = (Q + Q T )x − A T y + c T s = Ax − b x,y,u,s ≥ 0 uT x + sT y = 0
⎛u⎞ w =⎜ ⎟ ⎝s ⎠
⎛x⎞ z=⎜ ⎟ ⎜y⎟ ⎝ ⎠

w = Mz + q w, z ≥ 0 w Tz = 0

⎛ Q + QT M =⎜ ⎜ A ⎝

− AT ⎞ ⎟ 0 ⎟ ⎠

⎛ cT ⎞ q=⎜ ⎟ ⎜ − b⎟ ⎝ ⎠

Problema Complementario

Método de Pivote Complementario 1
Consideramos el problema pivote complementario: Encontrar los vectores w y z tales que:

w =Mz + q w, z ≥ 0 w Tz = 0
Una solución (w,z) no negativa al sistema de ecuaciones w=Mz+q se le llama una solución factible al problema complementario Una solución (w,z) factible al problema complementario que también satisface la condición complementaria wTz=0 se le llama solución complementaria

La condición wTz=0 es equivalente a wizi=0 para todas las i. Las variables wi y zi para cada i, sonllamadas un par complementario de variables

Método de Pivote Complementario 2
Supongamos que tenemos que encontrar una solución no negativa a un sistema de ecuaciones de la siguiente forma: Encontrar los vectores w y z tales que:

Problema Complementario

w = Mz + q w≥0 z≥0 w Tz = 0

Sistema de ecuaciones lineales Requiere que la solución al sistema sea no negativa

No hay FunciónObjetivo, solo una restricción no lineal.

Método de Pivote Complementario 3
Solución más sencilla es hacer , z=0 y w=q, válida siempre que q sea nonegativo. Si algún q es negativo el método pivote complementario (Lemke) empieza con una solución no factible, y se suma una variable auxiliar z0 para que el sistema quede siempre positivo, por tanto z0 = - min (qi) => elimino la variable másnegativa. w – Mz = q + z0 w – Mz – z0 = q La tabla inicial queda:
Base w1 w2 w3 w1 1 0 0 w2 0 1 0 w3 0 0 1 z1 -4 2 1 z2 2 -4 1 z3 -1 -1 0 Z0 -1 -1 -1 q -6 0 2

Método de Pivote Complementario 4
W => son variables básicas Z => son variables no básicas. Regla de complementaridad: la variable que entra en la base es la complementaria de la que se eliminó en el paso anterior. Si salió wi entra sucomplementaria zi Regla del radio mínimo: la variable que sale de la base es aquella que cumpla :

⎛ qi ⎞ min ⎜ ⎜m ⎟ m > 0⎝ is ⎟ ⎠
is

Entra en la base
w2 0 1 0 w3 0 0 1 z1 4 6 5 z2 -2 -6 -1 z3 1 0 -1 z0 1 0 0 q 6 6 8

Base

w1 -1 -1 -1

Sale de la base

z0 w2 w3

Método de Pivote Complementario 5
Se sigue iterando hasta que z0 salga de la base.
Base z0 z1 w3 w1 -1/3 -1/6 -1/6 w2 -2/31/6 -5/6 w3 0 0 1 z1 0 1 0 z2 2 -1 4 z3 1 0 1 z0 1 0 0 q 2 1 3

Base z0 z1 z2

w1 -1/4 -5/24 -1/24

w2 -1/4 -1/12 -5/24

w3 -1/2 1/4 1/4

z1 0 1 0

z2 0 0 1

z3 ½ ¼ 1/4

z0 1 0 0

q ½ 7/4 3/4

Método de Pivote Complementario 6

Base z3 z1 z2

w1 -1/2 -1/12 -1/12

w2 -1/2 -1/12 -1/12

W3 -1 ½ ½

z1 0 1 0

z2 0 0 1

z3 1 0 0

Z0 2 -1/2 -1/2

q 1 3/2 1/2...