Programacion cuadratica

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

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

IN70K: Clase Auxiliar

Esta 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

1

IN70K: Programaci´nMatem´tica o a

Pag. 1

1.

Una breve introducci´n. o

Consideremos un problema de la forma (P ) 1 m´ f (x) = ct x + xt Hx ın 2 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: ∇f (¯) + x
i∈I(¯) x

µi ∇gi (¯) = 0 x µi ≥ 0

x gi (¯) ≥ 0 donde I(¯) = {i|gi(x) = 0}. x

Apliquemos las condiciones de KKT al problema (P ). Para ello, notamos que (P ) puede escribirse como: (P ) s.a 1 m´ f (x) = ct x + xt Hx ın 2 Ax − b −x ≤ 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´n Matem´tica o a wt x = 0 v, w ≥ 0 Sea −y = Ax − b. As´ KKT queda ı −(c + xt H) = −v t A + w vty = 0 v, w ≥ 0 wt x = 0 x, y ≥ 0 (∗) Ax − b ≤ 0 x≤0

Pag. 2

De esta manera, minimizar el problema (P ) es equivalente a resolver el sistema de ecuaciones de KKT. Requerimos una soluci´npara este sistema de ecuaciones, para lo que distinguimos o entre 2 casos: Si c ≥ 0 tenemos una soluci´n factible sencilla: o w=c x=0 v=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 la Fase I del algoritmo simplex: (P A) m´ ın
i

hi

s.a c = −xt H − v t A + w − h wt x = 0 vty = 0 v, w ≥ 0 x, y ≥ 0

(∗)Resoluci´n de (P A) o
Las restricciones (∗) hacen que el problema (P A) sea no lineal lo que dificulta su resoluci´n. o Sin embargo, existen al menos dos enfoques para resolver de manera sencilla este problema. Sea (P A ) un problema como (P A), pero sin las restricciones (∗). Claramente (P A ) es un problema lineal y por tanto podemos resolverlo con simplex (karmarkar u otro) internalizando dealguna manera las restriciones (∗).

IN70K: Programaci´n Matem´tica o a M´todo de Wolfe: modificaci´n de criterio de entrada e o Resolvemos (P A ) con simplex utilizando la siguiente soluci´n b´sica factible inicial: o a w=c x=0 Y en cada iteraci´n: o v=0 y=b hi = −ci ci < 0 0 ci ≥ 0

Pag. 3

Una variable no b´sica vi puede entrar a la base si yi es no b´sica o sale al entrar vi . a a Unavariable no b´sica yi puede entrar a la base si vi es no b´sica o sale al entrar yi . a a Una variable no b´sica wi puede entrar a la base si xi es no b´sica o sale al entrar wi . a a Una variable no b´sica xi puede entrar a la base si wi es no b´sica o sale al entrar xi . a a Introducci´n de variables binarias o Sean: αi = 1 vi > 0 0 vi ≤ 0 i = 1...n βj = 1 wj > 0 0 wj ≤ 0 j = 1...m

Entoncesagregamos las siguientes restricciones a (P A ): vi ≤ αi M wi ≤ βi M y resolvemos el problema lineal mixto. yi ≤ (1 − αi )M xi ≤ (1 − βi )M

2.
2.1.

Problemas
Problema 1. Programaci´n cuadr´tica o a

Considere el siguiente problema de programaci´n no lineal: o 1 m´ f (x) = ct x + xt Hx ın 2 s.a x1 + x2 ≤ 10 x1 − 2x2 ≤ 8 x1 ≥ 0 x2 ≥ 0

IN70K: Programaci´n Matem´tica o a en que H = 4 8 . 6 2Pag. 4

1. Suponga que ct = (3, 4). Formule un sistema de ecuaciones que permita encontrar puntos de KKT. ¿C´mo lo resolver´ o ıa?. 2. Suponga que ct = (−3, −4). Formule un sistema de ecuaciones que permita encontrar puntos de KKT. ¿C´mo lo resolver´ o ıa?. Soluci´n: o Haciendo el cambio de variables y = Ax − b tenemos el siguiente sistema de ecuaciones: −(c + xt H) = −v t A + w vty = 0 v, w...