importante

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

n

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

n

s.a.

n

∑ aij x j
j =1

≥ bi

i =1 j =1

i = 1,K, m

xj ≥ 0

En notación matricial:

min

f ( x ) = cx + xT Qx

s.a.

g1 ( x) = x ≥ 0
g 2 ( x) = Ax − b ≥ 0Condiciones de Kuhn-Tucker
min
s.a.

f ( x ) = cx + xT Qx
g1 ( x) = x ≥ 0

Problema de
Programación
Cuadrática

g 2 ( x) = Ax − b ≥ 0
Condiciones de KT

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, esdecir la matriz Q es una matriz
cuadrada, y definida 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 elmétodo
pivote complementario. Para el cual hacemos el siguiente cambio de
variable:

u = (Q + Q T )x − A T y + c T

w = Mz + q

s = Ax − b

w, z ≥ 0 w Tz = 0

x,y,u,s ≥ 0
uT x + sT y = 0
⎛u⎞w =⎜ ⎟
⎝s ⎠

⎛x⎞
z=⎜ ⎟
⎜y⎟
⎝ ⎠

⎛ Q + QT
M =⎜
⎜ A
⎝

− AT ⎞
⎟
0 ⎟
⎠

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

Problema
Complementario

Método de Pivote Complementario 1
Consideramos elproblema 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ónfactible 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...