Optimizacion

Programaci´ n Cuadr´ tica y el m´ todo de Conjuntos o a e Activos.
V´ctor Mu˜ iz S. ı n
Optimizaci´ n II o Centro de Investigaci´ n en Matem´ ticas o a Email: victor m@cimat.mx

Abstract— En este reporte se inicia el estudio de los m´ todos de e optimizaci´ n para problemas cuya funci´ n objetivo es cuadr´ tica. o o a Un problema de este tipo se le llama Programaci´ n Cuadr´ tica o a (QP) yel m´ todo abordado en este reporte es el de Conjuntos e Activos, el cual se implementa para resolver el conocido problema de optimizaci´ n para M´ quinas de Soporte Vectorial (SVM), que o a ´ consiste en encontrar el hiperplano separador optimo para la clasificaci´ n de un conjunto de datos artificiales. o

(multiplicadores de Lagrange) tal que el siguiente sistema de ecuaciones se satisfaga: G−AT A 0 x∗ λ∗ = −d b (6)

I.

´ I NTRODUCCI ON

El problema general de programaci´ n cuadr´ tica se expresa o a como m´ q(x) = ın
x

El sistema (6) puede escribirse en una forma m´ s util para a ´ fines computacionales, expresando x∗ = x + p, donde x es alguna estimaci´ n de la soluci´ n y p es el paso deseado. o o Introduciendo esta notaci´ n y reacomodando las ecuaciones o obtenemos: G A −AT0 −p λ∗ = g c (7)

subject to

aT x i aT x i

= ≥

1 T x Gx + xT d 2 bi , i ∈ E bi , i ∈ I

(1) (2) (3)

donde G es una matriz sim´ trica de n × n, E e I son e conjuntos finitos de ´ndices, y d, x y {ai }, i ∈ E ∪ I, son ı vectores con n elementos. Los problemas de programaci´ n cuadr´ tica pueden ser resuelo a tos (o puede mostrarse que son infactibles) en un n´ mero finito u deiteraciones, pero el esfuerzo requerido para encontrar una soluci´ n depende fuertemente en las caracter´sticas de la funo ı ci´ n objetivo y en el n´ mero de restricciones de desigualdad. o u Si el Hessiano G es semidefinida positiva, se dice que 1 es un problema QP convexo. En este reporte el problema cuadr´ tico a que se trata es convexo. II. QP CON RESTRICCIONES DE IGUALDAD

donde c = Ax − b, g = d+ Gx y p = x∗ − x. La matriz de (7) es llamada matriz Karush-Kuhn-Tucker (KKT). Puede mostrarse que, si A es de rango completo por renglones y el Hessiano reducido Z T GZ es positivo definido, entonces la ´ matriz KKT es no-singular y existe un unico vector (x∗ , λ∗ ) que satisface (6). Aqu´, Z es la matriz de n × (n − m) cuyas ı columnas son una base para el espacio nulo de A, es decir, AZ = 0.III. R ESOLVIENDO EL SISTEMA KKT Aunque existen otros m´ todos para resolver el sistema (6) e o (7) (soluci´ n directa, m´ todo del espacio de rango, por o e ejemplo), el que se utiliz´ en este reporte es el m´ todo del o e espacio nulo, que es de gran aplicaci´ n ya que no requiere o que G sea no-singular, y se describe a continuaci´ n. o III-A. El m´ todo del espacio nulo (Null-Space) eSupongamos que particionamos el vector p en (7) en dos componentes: p = Y pY + ZpZ (8)

Consideremos un problema de programaci´ n cuadr´ tica con o a m restricciones, y asumiendo que m ≤ n, el QP se escribe mediante m´ q(x) ın
x def

=

subject to Ax

=

1 T x Gx + xT d 2 b

(4) (5)

donde A de m × n es el Jacobiano de las restricciones defiT nido por A = [ai ]i∈E . Asumimos tambi´ n que A esde rango e completo por renglones (rango m), y que las restricciones (4) son consistentes. Las condiciones necesarias de primer orden para que x∗ sea una soluci´ n de (4) implican que exista un vector λ o

donde Z es la matriz del espacio nulo de n × (n − m), Y es cualquier matriz de n × m tal que (Y |Z) es no-singular, pY ∈ Rm y pZ ∈ R( n − m). En este m´ todo, pY ypZ se obtienen de lasiguiente forma (los e detalles se encuentran en [1]): (AY )pY = −c donde AY es no-singular, (9)

(Z GZ)pZ = −(Z GY pY + Z g) .

T

T

T

(10)

ˆ conjunto activo actual W. Es f´ cil reconocer este punto porque a el subproblema (12) tendr´ entonces soluci´ n p = 0, y los a o multiplicadores de Lagrange se calculan entonces resolviendo ˆ ai λi = g = Gˆ + d x
ˆ i∈W

Los multiplicadores...