7/25/2019 Clase_Auxiliar_06__05_05_

1/3

DEPARTAMENTO DE INGENIERIA INDUSTRIAL Curso: IN70K - Programacion Matematica

Facultad de Cs. Fsicas y Matematicas Sem.: Otono 2004

UNIVERSIDAD DE CHILE Profs: P. Rey, R. Weber

P. Aux.: Patricio Hernandez

P. Ay.: Claudio Pena

Clase Auxiliar 5 de Mayo 2004

Metodos de Direcciones Factibles

Que es una direccion factible?

Sea (P):

(P) mn f(x)

s.a x S

un vector d es llamado direccion factible en x S si: un >0 tal que (x+d) S, (0, ).

Ademas se dice que es de mejoramiento si:

un >0 tal que f(x+d)< f(x) y (x+d) S, (0, ).

1. Metodo de Zoutendijk

1.1. Caso Restricciones Lineales

Que hace el metodo?

En cada iteracion genera una direccion factible de mejoramiento y luego optimiza a lo largo de

esa direccion.

Lema

Consideremos un problema de la forma:

(P) mn f(x)

s.a Ax b

Ex = e

Sea x una solucion factible y, A1x = b1 y A2x < b2. Luego un vector d es una direccion factibleenx s y solo sA1d 0 Ed = 0.

Sif(x)d

7/25/2019 Clase_Auxiliar_06__05_05_

2/3

Pasos del Algoritmo

Sea el problema:

(P) mn f(x)

s.a Ax b

Ex = e

Supongamos que se parte con una solucion factible inicialx1:

1. Dadoxk, supongamos queAt ybt se pueden descomponer en (At1, At2) y (b

t1, b

t2) de tal forma

queA1xk =b1 y A2x

k < b2.

Seadk la solucion optima del siguiente problema:

(SD) mn f(x)td

s.a A1d 0Ed = 0

1 dj 1

Sif(x)tdk = 0 Parar, luego xk es un punto KKT. Sino ir a paso 2.

2. Sea k el optimo del siguiente problema:

(LS) mn f(xk+ dk)

s.a 0 max

dondemax se determina de la siguiente forma:

max= mn{bidi :di> 0} d >0

d 0donde:b= b2 A2xk yd= A2dkSea xk+1 = xk +dk, luego hay que identificar el nuevo conjunto de restricciones activas

paraxk+1 y actualizarA1 y A2.

Luegok k+ 1 y volver a Paso 1.

2

7/25/2019 Clase_Auxiliar_06__05_05_

3/3

1.2. Caso Restricciones No Lineales

Lema Sea el problema:

(P) mn f(x)

s.a gi(x) 0 (no todas lineales)

Sea x una solucion factible y sea Iel conjunto de restricciones activas en x, es decir, I = {i :

gi(x) = 0}. Supongamos quef ygi parai I son diferenciables enx y que cada gi, parai / I es

continuo en x.

Luego un vector d es una direccion factible de mejoramiento en x s y solo s f(x)td < 0 y

gi(x)td