6- Métodos de punto interior en programación lineal (MPI)

2

DEFINICIONES

• Sea (P) el siguiente problema de programación lineal:

(P) Min cTx /

Ax = b

x 0,

donde c Rn, b Rm y A es una matriz de rango completo mxn con n>m.

• Sea la región factible

S = { x Rn, / Ax = b, x 0 }

y su interior relativo:

S0 = { x Rn, / Ax = b, x >0 }

• MPI: obtiene soluciones factibles intermedias en S0

3

• En forma genérica, sea:

Min f0(x) /

(1) fi(x) 0 i=1..m

A.x = b

Con fi convexa, dos veces contínuamente diferenciable,

Am,n, de rango m

• Asumimos que el problema anterior es estrictamente factible, o sea, existe un punto interior al dominio z /

fi(z) < 0 i=1..m , Az=b

• El problema (1) lo podemos reformular como:

bxA

xfIxfMinmi

i

.

/))(()(..1

0

4

Donde:

I-(u) es la una función indicatriz de R-:

Aproximación de I-(u) con barrera logarítmica:

(2)

,0)(,00)( uuIuuI

0-1

bxA

xftxfMinmi

i

.

/))(log(1)(..1

0

5

• Así, (2) es un problema con restricciones de igualdad lineales.

• Para t>0, -1/t. log (-u) es una aproximación diferenciable de I- y la aproximación mejora cuando t

• Propiedades de la barrera logarítmica: convexa, dos veces contínuamente diferenciable

0

-1

6

• Caso particular: prog. Lineal

la función barrera logarítmica es:

xRn, x>0 p(x)= - log xi = - log xi

I=1..n i=1..n

• La barrera penaliza las variables próximas a cero, o sea, la frontera de S. (III)

• DEF: x*=argmin p(x) xS0= es el centro analítico de S (maximiza e producto de las variables)

• Idea principal: en cada paso el costo de (P) disminuye y soluciones intermedias en S0 (no en S).

• A efectos de cumplir con ambos objetivos, se construyen nuevas funciones objetivos penalizadas donde aparece la función barrera, por ejemplo:

R, xR+n f(x)=cTx+p(x)

7

METODOS DE CAMINO CENTRAL (MCC):

• DEF: para cada valor de queda definida una función de la familia f(x), el punto donde se produce el mínimo de esta función se llama punto central y a la curva x() se le llama camino central para el problema (P)

x() = argmin f(x) xS0

• PROPS: x() es diferenciable y x() valor óptimo de (P) cuando crece

• Existen diferentes implementaciones del método de camino central variando la forma en que se parametriza la curva.

• Idea principal: en cada paso el costo de (P) disminuye y soluciones intermedias en S0 (no en S).

8

• A efectos de cumplir con ambos objetivos: mejora de costos y aproximación al centro analítico, se construyen nuevas funciones objetivos penalizadas (funciones auxiliares) donde aparece la barrera:

(a) Frish, Fiacco y McCormick. El parámetro está asociado al gap de dualidad:

R, xR+n f(x)=cTx+p(x)

(b) Huard, Renegar. El parámetro K es una cota superior del costo óptimo y q n es una constante:

xS0 y cTx < K, fK(x)=-qlog(K-cTx)+p(x)

(c) Karmarkar. El parámetro v es una cota inferior del costo óptimo y q n es una constante:

xS0 , fv(x)= qlog(cTx-v)+p(x)

(función potencial)

9

• Parametrizaciones en MCC: cada una de las anteriores funciones auxiliares genera una parametrización diferente x() del camino central:

(a) Primal-dual: R, xR+n , f(x)=cTx+p(x) (convexa)

El nombre de esta parametrización se debe a la estrecha relación entre el parámetro y el gap de dualidad : =n/

(b) Primal: xS0 y cTx < K, fK(x)=-qlog(K-cTx)+p(x) (convexa)

Es llamada primal debido a que el parámetro K es una cota superior de la función objetivo primal.

(c) Dual: xS0 , fv(x)= qlog(cTx-v)+p(x) (no convexa)

Es llamada dual debido a que el parámetro v es una cota inferior del valor óptimo del objetivo, estando asociado al valor de la función objetivo dual, para alguna una solución dual factible

10

Parametrización primal-dual

-5.0000

0.0000

5.0000

10.0000

15.0000

20.0000

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190

p(x)

cx

a1.cx+p(x)

a2.cx+p(x)

a3.cx+p(x)

a4.cx+p(x)

11

Parametrización primal

-100.0000

-50.0000

0.0000

50.0000

100.0000

150.0000

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190

p(x)

cx

-q.log(K1-cx)+p(x)

-q.log(K2-cx)+p(x)

-q.log(K3-cx)+p(x)

-q.log(K4-cx)+p(x)

12

Paramerización dual

-300.0000

-200.0000

-100.0000

0.0000

100.0000

200.0000

300.0000

400.0000

500.0000

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190

p(x)

cx

n.log(cx-v1)+p(x)

n.log(cx-v2)+p(x)

n.log(cx-v3)+p(x)

n.log(cx-v4)+p(x)

13

ALGORITMO MCC GENERAL:

k=0

Repeat1- Calcular k+1=f( k) , según sea la parametrización utilizada

2- Calcular xk+1= x(k+1) con algún algoritmo de optimización

3- k = k +1

Until (k) < 2-L

14

Clasificación según la parametrización ()

Primal Primal-dual Dual

f(x) fK(x)=-qlog(K-cTx)+p(x) f(x)=cTx+p(x) fv(x)=qlog(cTx-v)+p(x)

f(x) q. c -x-1 c -x-1 q. c -x-1

K-cTx cTx-v

() (n/q)(K- cTx) n/ (n/q)(cTx-v)

Act. K’=K+(1- ) cTx ’= / v’= v+(1-) cTx

(0,1) (n/q,1)

15

Actualización del parámetro

A continuación se especifica la forma de actualizar el

parámetro en el paso 1 del algoritmo general de MCC:

(a) Parametrización primal-dual:k+1= k / donde (0,1) es un número arbitrario

La elección de influye sobre la complejidad del algoritmo y depende

si se elige un modelo de “paso” corto o largo.

(b) Parametrización primalKK+1=Kk+(1- ) cTxK

KK es una sucesión decreciente, cTxK+1 < cTxK y (K)=K- cTxk es

decreciente

(c) Parametrización dualvk+1= vk+(1-) cTxk, con q>n para que exista convergencia y (n/q,1)

16

Cálculo de xK+1 (ver I,II)

En el paso 2 del algoritmo general de MCC se hacía referencia al cálculo de xK+1 mediante un algoritmo de optimización. El algoritmo usado más frecuentemente es el “scaling steepest descendent” (SDD).

• Escalado de variables: sea el cambio de variables x=Dy donde D es diagonal positiva. Dado x0S0 se escala respecto a x0 mediante la transformación x=X0y / X0 =(x01,.. X0n) NOTA: el punto x0 se transforma en el e (vector de n unos).

• Descomposición de un vector en espacios ortogonales: sean Am,n y d Rn, d puede ser descompuesto de una única forma en d=dx+dy donde:

dx N(A)={x Rn/ Ax=0} y

dy R(A)={x Rn/ x=Atw, w Rm}

• La operación proyección es una transformación lineal representada por PA

17

ALGORITMO SDD GENERAL:

Sean x0S0 y f: S0 R contínuamente diferencible

k=0

Repeat1- Escalado: A’=AXK, g’=XK f(xK)

2- Dirección de búsqueda: h’=-PA’.g’

3- Búsqueda lineal: y=e+h’ / y’>0

4- Escalado: xK+1=XK.y’

5- k = k +1

Until ||h’(x, )|| <

18

Sean (P) Min cTx / y su dual (D) Max bTw / Ax = b Atw + z = c x 0, z 0,Lema: z Rn es una holgura dual factible de (D)

z 0 y PAz=PAcDemos: sea z 0 , z es holgura dual factible para (D)

para algún wRm, c - z = Atw. Por otro lado, c – z puede descomponerse de forma única en:

c-z = PA(c-z)+ Atw PAz=PAc.

NOTA: Aplicando el lema anterior, dada x1 S, (D) es equivalente a: Min x1

Tz /

PAz = PAc,z 0,

19

Cálculo del gap para la parametrización primal-dual:

Sean x() los puntos del camino central, entonces PAf (x)=0,

o sea: PAc-PAx-1=0 PAc=PAx-1 cp =PAc =PAx-1/ ,

Como x-1/ 0 y PAx-1/ = cp =PAc, aplicando el lema anterior, x-1/ es una holgura dual factible el gap de dualidad será:

= x(). x-1 ()/ = n/

20

ALGORITMO DE KARMARKAR:• Sea el problema (P), presentado de la siguiente forma:

(P) Min cTx / A’x = 0

aTx = 1, x 0,• Este formato se puede obtener directamente introduciendo variables en el

(P) original.• Sea q=n en la función potencial, e inicialmente v=0, entonces:

f0(x)=nlog(cTx)+p(x) ,

esta función es homogénea de grado 0: f0(bx)= f0(x) para cualquier b>0, x>0.

• Sea x>0 / A’x=0 pero aTx>0 1 x/ aTx es factible y tiene el mismo valor potencial

• De acuerdo a lo anterior se puede seguir el siguiente esquema:

1- Eliminar la restricción aTx =1

2- Usar SSD para encontrar f0

3- Calcular x’= xK/ aTxK

• Si v 0, las conclusiones anteriores son válidas, considerando:

v’=v. aTx (sigue siendo factible) y f0(x)=nlog(c-v’a)Tx.p(x)

21

fv(x)=nlog(cTx-v)+p(x) ,

v= valor óptimo conocido (si se desconoce, calcular vkv)

v0v, cota inferior de v

x0S0

k=0

Repeat

1- Escalado: A’=AXK, c’=XKc, a’=XK a

2- Cota inferior: vK+1=max {vK,v(xK)}

3- Dirección de búsqueda: h’=--PA’. ( n (c’-vK+1a’) -e)

(cTx- vK+1)

4- Búsqueda lineal: y=e+h’ / y’>0

5- Volver al conjunto factible: y*=y’/(a’Ty’)

6- Escalado: xK+1=XK.y*

7- k = k +1

Until convergencia ((xK,K) < 2-L