Metodo de puntos interiores karmarkar

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

Algoritmo de Karmarkar
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.

El Algoritmo de Karmarkar.

Consideremos un problema de la forma 2 : (P ) m´ z = ct x ın

s.a Ax = 0 x ∈ S donde S = Simplex standar en I n R n t = {x ∈ I |1 x = 1, x ≥ 0} R y adem´s a c, x ∈ I n R A ∈ I m×n R 1 ∈ I n un vector con componentes 1 R Supongamos adem´s que: a 1. rango(A)=n
1 1 2. A(1 n ) = 0 ⇒ 1 n es factible para (P)

3. z ∗ = 0

1.1.Proyective Scaling Algorithm (Karmarkar, 1984).

1 1. Inicializaci´n: x1 = 1 n o

2. Definimos: x = diag(xk ) ¯ ¯ A = A¯ x c = xc ¯ ¯ Luego, la matriz asociada a las restricciones activas (que coincide con la region factible porque solo hay restricciones de igualdad)viene dada por: ¯ B = ¯ A 1t

Y por tanto la proyecci´n del gradiente de la funci´n objetivo sobre las restricciones o o activas vienedada por: ¯ ¯ ¯ ¯ ¯ c d = −(I − B t (B t B)−1 B)¯
2

Como veremos mas adelante, todo PL puede ser escrito en la forma exigida por el algoritmo

IN70K: Programaci´n Matem´tica o a 3. Sea xk+1 = ˆ Entonces xk+1 = 4. Criterio de detenci´n: o Si ct xk+1 < ⇒ terminar. Si no, k → k + 1. Ir a 1. 5. Redondear la soluci´n. o
1 n

Pag. 2

·1+

¯ αd ¯ n d

xx ¯ˆ 1t xx ¯ˆ

Observaci´n: α yson parametros de la implementaci´n. α se elige en [0,1] siendo un valor o o ∗ t´ ıpico el de 2/3. se escoge peque˜o (Recordar que z = 0). n

1.2.

Interpretaci´n geom´trica o e

Dado un punto xk se aplica una transformaci´n que nos cambia de espacio a otro en el cual el o k punto x corresponde al centro del simplex standar S 3 . En este nuevo espacio, nos movemos en la direcci´n d en unacantidad α/n. o ¯

T (x) =
3

x−1 x ¯ xy ¯ ⇒ T −1 (y) = t x−1 x 1¯ 1¯y x

En efecto, T () puede descomponerse en otras 2 transformaciones: T = T1 · T2 donde: ¯ diagonal scaling(centrado) T1 : x → z = n−1 x−1 x; radial proyection (proyecci´n sobre simplex standar) o T2 : z → y = 11z z; t

IN70K: Programaci´n Matem´tica o a

Pag. 3

1.3.

Procedimiento para llevar un PL a la formaexigida por Karmarkar
Sabemos que cualquier PL puede llevarse a la forma: m´ ct x ın s.a Ax = b x ≥ 0 x = (x1 ...xn ) Agregamos una restricci´n 1t x ≤ Q, que si el problema es acotado siempre puede o escribirse: m´ ct x ın s.a Ax = b 1x + xn+1 = Q xi ≥ 0 Homogenizamos las restricciones haciendolas iguales variable xn+2 = 1. m´ ct x ın s.a Ax − bxn+2 = 1x + xn+1 − Qxn+2 = 1x + xn+1 + xn+2 = xi ≥ a 0.Para ello agregamos una

0 0 Q+1 0

Necesitamos que la tercera ecuaci´n quede igual a 1, lo que logramos por medio de un o cambio de variable: xi = (Q + 1)yi m´ ct y ın s.a Ay − byn+2 1y + yn+1 − Qyn+2 1y + yn+1 + yn+2 yi = = = ≥ b 0 1 0

1 Necesitamos incorporar que 1 n sea factible. Para ello agregamos variables artificiales yn+3 m´ ct y + M yn+3 ın

s.a

Ay − byn+2 − (A1 − b)yn+3 1y +yn+1 − Qyn+2 − (n + 1 − Q)yn+3 1y + yn+1 + yn+2 + yn+3 yi

= = = ≥

b 0 1 0

Observaci´n: Para que las nuevas restricciones sean equivalentes a las anteriores, o 1). necesitamos que yn+3 = 0. Esto se logra penalizando mucho yn+3 (M Solo nos falta exigir que z ∗ = 0, lo cual se puede hacer de varias maneras. Por ejemplo minimizando la brecha entre los problemas primal y dual como se vera en elProblema 2.

IN70K: Programaci´n Matem´tica o a

Pag. 4

2.
2.1.

Problemas
Problema 1. Winston, secci´n 10.06, pag 599. o

Sea el siguiente problema de programaci´n lineal: o m´ z = x1 + 3x2 − 3x3 ın s.a x 2 − x3 = 0 x1 + x 2 + x 3 = 1 x1 , x2 , x3 ≥ 0

Resuelva utilizando el algoritmo de karmarkar. Hint: Itere un par de veces mejorando la funci´n objetivo. No es necesario...