Investigacion de Operaciones

Universidad de Chile
Facultad de Ciencias F´
ısicas y Matem´ticas
a
Departamento de Ingenier´ Industrial
ıa

IN70K: Clase Auxiliar

Programaci´n Cuadr´tica
o
a
Marcel Goic F.1

1Esta es una versi´n bastante preliminar por lo que puede contar con numerosas faltas de ortografia y
o
errores no forzados. Si encuentran alguno favor de denunciarlo a mgoic@ing.uchile.cl

IN70K:Programaci´n Matem´tica
o
a

1.

Pag. 1

Una breve introducci´n.
o

Consideremos un problema de la forma
1
m´ f (x) = ct x + xt Hx
ın
2

(P )

s.a A · x ≤ b
x≥0
R
R
R
donde x, c ∈I n , A ∈ I m×n , H ∈ I n×n , b ∈ I m
R
Recordar que la ptimalidad de un punto x puede verificarse con las condiciones de Karush
¯
Khun Tucker:
µi ∇gi (¯) = 0
x

∇f (¯) +
x
i∈I(¯)
x

xgi (¯) ≥ 0

µi ≥ 0

donde I(¯) = {i|gi (x) = 0}.
x
Apliquemos las condiciones de KKT al problema (P ). Para ello, notamos que (P ) puede
escribirse como:
1
m´ f (x) = ct x + xt Hx
ın
2

(P)

Ax − b
−x

s.a

0
0

≤

Denotemos por (v, w) los ponderadores de la condici´n de KKT con v asociados a las reo
stricciones Ax − b ≤ 0 y w los asociados a x ≥ 0. Con esto:
∇f (x) = c+ xt H


∇g(x) =

A
−e


1
 . 
con e =  .  ∈ I n
R
.
1

Luego las condiciones de KKT pueden expresarse como:
−(c + xt H) = −v t A + w
v t (Ax − b) = 0

IN70K: Programaci´nMatem´tica
o
a

Pag. 2
wt x = 0

v, w ≥ 0

Ax − b ≤ 0

x≤0

Sea −y = Ax − b. As´ KKT queda
ı
−(c + xt H) = −v t A + w
vty = 0

wt x = 0

v, w ≥ 0

(∗)

x, y ≥ 0

De estamanera, minimizar el problema (P ) es equivalente a resolver el sistema de ecuaciones
de KKT. Requerimos una soluci´n para este sistema de ecuaciones, para lo que distinguimos
o
entre 2 casos:
Si c ≥ 0tenemos una soluci´n factible sencilla:
o
w=c

v=0

x=0

y=b

Si c ≤ 0 no tenemos una soluci´n factible sencilla y por lo tanto debemos resolver un
o
problema auxiliar (P A) similar a...