40
otimo simplex pontos interiores

simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

Universidade Estadual de CampinasFACULDADE DE ENGENHARIA EL�ETRICA E DE COMPUTAC� �AO

DT�FEEC�UNICAMP

M�etodo de Pontos Interiores em Programa�c�ao Linear

� Introdu�c�ao

��� Pontos Interiores X Simplex

� Ambos e�cientes

� Simplex� muitas itera�c�oes �simples� pelas arestas

� Pontos Interiores� poucas itera�c�oes �caras� pelos pontos inte�

riores�

otimo

simplex

pontos interiores

Figure �� Simplex X Pontos Interiores

Page 2: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

��� Nota�c�ao

� A�B�C��� onde A � faijg � Matrizes

� a� b� c��� onde a � faig � Vetores colunas

��� Programa�c�ao Linear � Formas Padr�oes

Primal �

�������������

min ctx

sa Ax � b

x � �

Dual �

�������������

max bty

sa Aty � c

y livre

ou Dual �

�������������

max bty

sa Aty z � c

z � �� y livre

��� De�ni�c�oes

� Def� �� Ponto interior� xo tal que xo � � e ponto interior

do primal�

� Def� �� Ponto fact��vel� xo tal que Axo � b� xo � � e um

ponto fact�vel do primal�

� Def� �� Ponto interior fact��vel �satisfaz e ��� xo tal que

Axo � b� xo � � e um ponto interior fact�vel do primal�

� Def� � Gap �ou GAP�� diferen�ca entre o valor do primal e

do dual� Ex�� GAP � ctx� bty�

Page 3: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

�� Condi�c�oes de Otimalidade

i� Primal factibilidade� b�Ax � �� x � �

ii� Dual factibilidade� c� Aty � z � �� z � �

iii� Condi�c�ao de Complementaridade� xizi � �

�� Problemas de M��nimos Quadrados

Problema� Minx�R��x� � ��k b� Ax k�

Logo�

��x� � ���b�Ax�t�b�Ax� � �

��btb� btAx� xtAtb xtAtAx�

r��x� � � � x � �AtA���Atb

r���x� � AtA � � � e m�nimo global�

Page 4: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

x0 x1 x2

f(x)

x

Figure �� M�etodo de Newton

�� M�etodo de Newton

� Caso monovariavel�

��x� �� ��x�� r�t�x���x� x��

��x� � � � r�t�x��x � r�t�x��x� � ��x��

x � x� � ��x��r��x��

� Caso Multivariavel�

Metodo de Newton�

��x� �� ��xk� r��xk��x� xk� ���x� xk�tJ�xk��x� xk�

Page 5: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

onde J�xk� � r�r��xk�� �Jacobiana de ��x��

r��x� � � � r��xk� J�xk��x� xk� � �

xk�� � xk � ��J�xk����r��xk�

� Lema �� Uma dire�c�ao d para melhorar a fun�c�ao objetivo e

fact�vel para restri�c�oes de igualdade do tipo Ax � b se Ad � �

�pois A�x d� � b � Ad � ���

� Premissa �� Algoritmos de pontos interiores come�cam em

pontos interiores fact�veis e movem de ponto em ponto interior

fact�vel� em dire�c�ao �a solu�c�ao otima�

Page 6: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

� M�etodo PrimalA�mEscala

��� Base Te�orica

X�nxn� � diag�x� �

��������������

x� � ��� �

� x� ��� �

� � ��� �

� � ��� �

� � ��� xn

�������������

Miny�z��k Xz k� sa z � c�Aty

Miny�z��k Xz k� �Minz

��k X�c�Aty� k

Z � k X�c� Aty� k�

� ctX tXc� ctX tXAty � ytAX tXc ytAX tXAty

X t � X � ryZ � �� �AX�c AX�Aty � �

z � c�At�AX�At���AX�c

Teorema �Dikin � Dados x tal que Ax � b� x � �� z �

c�Aty� y � �AX�At���AX�c� ent�ao a dire�c�ao d � �X�z e uma

dire�c�ao de descida fact��vel�

Assim� d � �X�z minimiza k Xz k��

xk�� � xk �kdk com�

Page 7: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

�k � �min�ki����

xki

�ki

�� � � � � � dk � f�ki g

��� Algoritmo

� Dados � � ��� � e x� j Ax� � b� x� � �� k � ��

�� Fa�ca ate convergir�

�a� yk � �A�Xk��At���A�Xk��c

�b� zk � c� Atyk

�c� dk � ��Xk��zk

�d� �k � �min�ki��f�

xki

�ki

g

�e� xk�� � xk �kdk

�f� k � k

�� Fim Fa�ca

Page 8: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

� a� Criterios de converg�encias�

� Gap relativo� kXkzkk��kbtyk�ctxkk � �

� Primal factibilidade� kb�Axkk

��kbk � �

� Dual factibilidade� kc�Atyk�zkk

��kck � �

� Varia�c�ao do valor da fun�c�ao objetivo� kctxk���ctxkk��kctxkk � �

� b� Ponto inicial interior fact�vel x�� resolver�

�PM� �

�������������

min ctx M�

sa Ax p� � b

�x� �� � �

onde� p � b� Ax�� Iniciar com �x�� ��

� c� Calculo de yk�

�A�Xk��At�yk � A�Xk��c

� d� a�m� espa�co a�m� escala� �x � X��x�

�P �

�������������

min ctx

sa Ax � b

x � �

� x � X �x � � �P �

�������������

min �ct�x

sa �A�x � b

�x � �

�c � Xc� �A � AX �

Page 9: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

��� Proje�c�ao A�m�Escala

Problema� �������������

max ctx

sa Ax � b

x � �

Dire�c�ao d tal que��������������

max ct�x� d�

sa A�x� d� � b

k d k� �

Lagrangeano�

L�d� y� � � ct�x� d� � � dtd�� yt�A�x� d�� b�

Dual�

Mind�y��L�d� y� ��

Otimalidade�

i� �L�d� c� �d� Aty � �

ii� �L��� � dtd � �

iii� �L�y� A�x� d�� b � �

Page 10: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

iii�� Ax� � b Ad � � � Ad � �

� ���

i�� c� d� Aty � � � d � c� Aty

� y � �AAt���Ac

d � c� At�AAt���Ac � �I � At�AAt���A�c � Pc

P � �I � At�AAt���A� � matriz de proje�c�ao ortogonal

ao espa�co nulo de A�

Figura �� d � da db� da � Atx

Adb � A�d� da� � � �espa�co nulo de A��

Assim�

Ad � Ada � AAtx

x � �AAt���Ad � da � At�AAt���Ad

db � d�At�AAt���Ad � �I �At�AAt���A�d � P �A�d

Page 11: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

d

dd a b

R(A )t

N(A)

Figure � Matriz de projec�ao ortogonal de A

Problema � �P ��

�d � � �P �c � ��I � �At� �A �At��� �A��c

�A � AX� �c � Xc� itera�c�ao k�

�dk � ��I �XkAt�AXkXkAt���AXk�Xkc

� �Xkc XkAt�A�Xk��At���A�Xk��c

Logo�

�����

dk � Xk �dk � ��I � �Xk��At�A�Xk��At���A���Xk��c

xk�� � xk �kdk

Primal�a�m�escala�

Page 12: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

�������������

dk � ��Xk��zk

zk � c�Atyk

yk � �A�Xk��At���A�Xk��c

�����

dk � ��I � �Xk��At�A�Xk��At���A���Xk��c

xk�� � xk �kdk

��� Exemplo �Frannie�s Firewood Problem�

Frannie vende � �cordas� de lenha todo �nal do ano� Pode vender

meia �corda� a U��� ou uma �corda� a U� ��� Como maximizar

o lucro�

Modelo �

�������������

max ��x� ��x�sa �

�x� x� � �

x�� x� � �

x � variavel de folga� � ���� �� � ponto inicial interior fact�vel

Resultado� tabela � �gura ��

Page 13: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

x� x� x ctx

c� � �� c� � �� c � � b � �

��� ���� ���� �����

��� ���� ��� �����

���� � � ���� ������

���� ��� ���� ������

���� �� � ���� ������

���� ���� ��� ������

���� ��� ����� ������

���� ����� ����� ������

���� ���� ����� ������

���� ����� ����� ������

12

34

56

0

0.5

1

1.5150

200

250

300

350

400

450

500

550

x1x2

c’x

Figure �� Evoluc�ao dos pontos interiores do problema de Frannie

Page 14: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

� M�etodo DualA�mEscala

��� Introdu�c�ao

Problema�

�����min �

�k Zx k�

sa Ax � bZ � diag�zi�

Lagrangeano�

L�x� w� � �� k Zx k

� wt�b� Ax� � ���x

tZZx� wt�b�Ax�

Condi�c�oes de otimalidade�

�����

�L�x� � � Z�x� Atw � �

�L�w� � � b�Ax � �

Ou seja�

x � Z��Atw� �AZ��At�w � b� x � Z��At�AZ��At���b

Hessiana�

H �

���Z� �A

�At �

�� � �AAt � �

z � c�Aty � dz � �Atdy

Page 15: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

Dire�c�ao dz � �Z�x�

dz � �Z��Z��At�AZ��At���b�

� �At�AZ��At���b � �Atdy

Assim�

dy � �AZ��At���b

Teorema� Dados �y� z� tais que z � c � Aty� z � �� Ax � b�

x � Z��At�AZ��At���b� a dire�c�ao dada por�

�dy� dz� � �AZ��At���b��Z�x�

e dual fact�vel e e de subida�

��� Algoritmo

� Dados �y�� z�� tal que Aty�z� � c� z� � � e � � ��� �� k �

��

�� Fa�ca ate converg�encia�

�a� dyk � �A�Zk���At�b

�b� dzk � �Atdyk

�c� xk � ��Zk���dzk

Page 16: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

�d� �k � �min�zki��f�

zki

�zki

g

�e� yk�� � yk �kdyk

�f� zk�� � zk �kdzk �ou zk�� � c� Atyk���

�g� k � k

�� Fim Fa�ca

� a� Criterio de converg�encia originalmente utilizado�

kbtyk�btyk��kmax���kbtykk� � ��

� b� Ponto inicial dual fact�vel �y�� z��� resolver o problema�

�������������

max bty �M�

sa Aty z � e� � c

z � �

aplicando o metodo dual�a�m�escala ate � � �� com valor

inicial y� qualquer �livre�� �� � ��minj�cj � Atjy

���

� c� zk�� � c�Atyk�� � c�At�yk �kdyk� �

c�Atyk � �kAtdyk � zk �kdzk

� d� O calculo de xk e dispensavel� a n�ao ser que se utilize no

criterio de converg�encia�

Page 17: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

� e� Como y e livre� n�ao e feito teste de barreira�

� f� Grande custo computacional no calculo de A�Zk���At�

Page 18: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

M�etodo PrimalDualA�mEscala

��� Introdu�c�ao

Condi�c�oes de otimalidade�

F �x� y� z� �

�������

Fp

Fd

Fa

�������

�������

Ax� b

Aty z � c

XZe

������� �

Aproxima�c�ao linear fornece�

�x� y� z� �� �x�� y�� z��� J���x�� y�� z��F �x�� y�� z��

pois�

F �x� y� z� �� F �x�� y�� z�� J�x�� y�� z����x� y� z��

�x�� y�� z���� � �

�F �x�� y�� z�� �

�������

b�Ax�

c�Aty� � z�

�X�Z�e

�������

�������

rprdra

������� r

e�

J�x�� y�� z�� �

�������

rF tp

rF td

rF ta

�������

�������

A � �

� At I

Z� � X�

������

Page 19: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

Assim�

�x� y� z� � �x�� y�� z��

�������

A � �

� At I

Z� � X�

������

�� �������

rprdra

������� �x�� y�� z�� d

onde�

d �

�������

dx

dy

dz

�������

�������

A � �

� At I

Z� � X�

������

�� �������

rprdra

������

Pode�se resolver o sistema�

�������

A � �

� At I

Z� � X�

������

�������

dx

dy

dz

�������

�������

rprdra

������

Considerando�

�������������

Adx � rpAtdy dz � rdZ�dx X�dz � ra

dz � rd �Atdy � �

Z�dx X�dz � Z�dx X��rd � Atdy� � ra

Page 20: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

Z�dx�X�Atdy � ra �X�rd

Ou seja�

��X����Z�dx Atdy � ��X����ra rd

que fornece�

���

A �

�D At

��

���dx

dy

�� �

���rprd � �X

����ra

��

onde D � X��Z� Note que�

�������������

Adx � rp�Ddx Atdy � rd �X��radx � D���Atdy � rd X��ra�

e�

D��Atdy � dx D���rd �X��ra�

�AD��At�dy � Adx AD��rd �AD��X��ra

� �AD��At�dy � rp AD��rd �AZ��ra

Page 21: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

��� Algoritmo

� Dados �x�� y�� z�� tal que �x�� z�� � � e � � ��� �� k � ��

�� Fa�ca ate converg�encia�

�a� rkp � b� Axk

�b� rkd � c�Atyk � zk

�c� rka � �XkZke

�d� Dk � ��Xk���Zk�

�e� dyk � �A�Dk���At����rkp A�Dk���rkd �A�Zk���rka �

�f� dxk � �Dk����Atdyk � rkd �Xk���rka �

�g� dzk � �Xk����rka � Zkdxk�

�h� kp � min�xki��f�

xki

�xki

g

�i� kd � min�zki��f�

zki

�zki

g

�j� �kp � min��kp� �

�k� �kd � min��kd� �

�l� xk�� � xk �kpdx

k

�m� yk�� � yk �kddy

k

�n� zk�� � zk �kddz

k

�o� k � k

�� Fim Fa�ca

Page 22: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

� A converg�encia pode ser testada sobre o valor de k F k��

� O ponto inicial �x�� y�� z�� n�ao precisa ser fact�vel� Recomenda�

se�

� Para o primal�

Fazendo x � At�y� Ax � b � AAt�y � b

� �y � �AAt���bAt�y � At�AAt���bx � At�AAt���b�� � max��minixi� ���

kbk���kAk��� onde ��

�� ��

x�i � max�xi� ���

�k b k� �Pmi � j bi j� k A k� � maxj

Pmi � j aij j�

� Para dual�

Aty z � c� y livre e z � � � y� � �� e�

z� �

�������������

zi � se zi � �

�zi se zi � ��� se �� � zi � �

onde � � k c k�� Estes pontos procuram ser bem

posicionados� longe da fronteira �xizi n�ao muito pequenos��

� O tamanho do passo para y e o mesmo de para z ��kd� para

garantir que ocorra c� Atyk � zk � � na converg�encia�

Page 23: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

c�Atdyk�� � zk�� � c�At�yk �kddy

k�� �zk �kddz

k�

� �c�Atyk � zk�� �kd�A

tdyk � dzk�

� Como n�ao precisa de ponto inicial fact�vel� este metodo e mel�

hor que o primal ou dual �n�ao precisa de fase I��

Page 24: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

� M�etodo PrimalDual Cl�assico

�� Introdu�c�ao

Primal�dual a�m�escala permite que x e z aproximem r�apidamente

das fronteiras � ine�ciente�

Primal�Dual Classico acrescenta uma perturba�c�ao na condi�c�ao

de complementariedade�

xizi � �i

Novas condi�c�oes de otimalidade�

�������������

b� Ax � �

ct � Aty � z � �

�e�XZe � �

� tal que limk � ��k � �

Estima�c�ao de �k�

�k � Tr��Xk�tZk� onde� Tr�X � � tra�co de X

Na maioria das implementa�c�oes� adota�se�

�k � �k��k

n�� �k � ��� �

Nota� �k � � � primal�dual a�m�escala� �k � �

Page 25: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

dire�c�ao de centragem pois�

�e�XZe � �

�k

ne�XZe � � � X tZe �

X tZ

ne

A cada itera�c�ao� tem�se o sistema J�xk� yk� zk�dk � rk� ou seja�

�������

A � �

� At I

Zk � Xk

������

�������

dxk

dyk

dzk

�������

�������

rkprkdrkc

�������

�������

b�Axk

c� At � zk

�ke� �Xk�tZke

������

Tem�se assim� duas diferen�cas em rela�c�ao ao metodo primal�dual

a�m�escala�

� a� troca de rka por rkc

� b� calculo de �k

Page 26: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

�� Algoritmo

� Dados �x�� y�� z�� tal que �x�� z�� � �� � � ��� �� � � ��� � e

k � ��

�� Fa�ca ate converg�encia�

�a� �k � Tr�XkZk�

�b� �k � ���k

n�

�c� rkp � b� Axk

�d� rkd � c�Atyk � zk

�e� rkc � �ke�XkZke

�f� Dk � ��Xk���Zk�

�g� dyk � �A�Dk���At����rkp A�Dk���rkd �A�Zk���rkc ��h� dxk � �Dk����Atdyk � rkd �X

k���rkc ��i� dzk � �Xk����rkc � Zkdxk�

�j� kp � min�xki��f�

xki

�xki

g

�k� kd � min�zki��f�

zki

�zki

g

�l� �kp � min��kp� �

�m� �kd � min��kd� �

�n� xk�� � xk �kpdx

k

�o� yk�� � yk �kddy

k

�p� zk�� � zk �kddz

k

�q� k � k

�� Fim Fa�ca

Page 27: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

� O criterio de converg�encia e a inicializa�c�ao deste metodo po�

dem ser os mesmos do metodo primal�dual a�m�escala� E

recomendavel inicializar com �� alto�

� Dependendo dos valores de � e � � obtemos algoritmos de diver�

sas naturezas �complexidade polinomial� converg�encia super�

linear� etc���

� Os valores t�picos de � est�ao entre ������� ���������

� Quando �k � � recomenda�se utilizar �k � ��k��

npara procu�

rar acelerar a converg�encia�

Page 28: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

� M�etodo PreditorCorretor

�� Introdu�c�ao

Baseado em � componentes�

� dire�c�ao a�m�escala �d �dire�c�ao de Newton� preditor��

� dire�c�ao de centragem� de�nido pelo � do primal�dual classico�

� dire�c�ao de corre�c�ao �d� que tenta compensar a aproxima�c�ao

linear de Newton�

Ideia� calcular a dire�c�ao a�m�escala e estudar o progresso ao

longo desta dire�c�ao� atuando na perturba�c�ao � �centragem� e na

corre�c�ao n�ao�linear�

No ponto �x� y� z��

� �

�������������

Ad�x � rpAtd�y d�z � rdZd�x Xd�z � ra � �XZe

Obtem�se� ent�ao� o ponto ��x� �y� �z�� onde�

�������

�x

�y

�z

�������

�������

x d�x

y d�y

z d�z

������

A seguir� determinar a dire�c�ao �d�x� d�y� d�z��

Page 29: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

���

�������������

Ad�x � �

Atd�y d�z � �

Zd�x Xd�z � �e� �D�xD�z�e � rc

onde D�x � diag�d�x� e D�z � diag�d�z�� Finalmente� a dire�c�ao

�nal �dx� dy� dz� e determinada somando � � e �����������������

A�d�x d�x� � rpAt�d�y d�y� �d�z d�z� � rdZ�d�x d�x� X�d�z d�z� � ra rc � rs

onde�

�����ra � �XZe

rc � �e� �D�xD�z�e

Page 30: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

�� Algoritmo

� Dados �x�� y�� z�� tal que �x�� z�� � �� � � ��� � e k � ��

�� Fa�ca ate converg�encia�

�a� rkp � b� Axk

�b� rkd � c�Atyk � zk

�c� rka � �XkZke

�d� Dk � ��Xk���Zk�

�e� d�yk � �A�Dk���At����rkp A�Dk���rkd �A�Zk���rka �

�f� d�xk � �Dk����Atd�yk � rkd �Xk���rka �

�g� d�zk � �Xk����rka � Zkd�xk�

�h� �kp � min��xki��f�

xki

��xki

g

�i� �kd � min��zki��f�

zki

��zki

g

�j� ��kp � min�� �kp� �

�k� ��kd � min�� �kd� �

�l� ��k � �xk ��kpd�x

k�t�zk ��kdd�z

k�� �k � Tr�XkZk�

�m� �k �

���������

���k

�k� se �k �

� �kpn� se �k �

�n� �k � �k��k

n�

�o� rks � rka �ke� �D�xk��D�zk�e

�p� dyk � �A�Dk���At����rkp A�Dk���rkd �A�Zk���rks �

�q� dxk � �Dk����Atdyk � rkd �Xk���rks �

Page 31: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

�r� dzk � �Xk����rks � Zkdxk�

�s� kp � min�xki��f�

xki

�xki

g

�t� kd � min�zki��f�

zki

�zki

g

�u� �kp � min��kp� �

�v� �kd � min��kd� �

�w� xk�� � xk �kpdx

k

�x� yk�� � yk �kddy

k

�y� zk�� � zk �kddz

k

�z� k � k

�� Fim Fa�ca

Nota�

� O criterio de converg�encia e a inicializa�c�ao deste metodo po�

dem ser os mesmos do metodo primal�dual a�m�escala�

� Dois sistemas lineares precisam ser resolvidos� utilizando a

mesma rela�c�ao� A�Dk���At � Lk�Lk�t�

� Espera�se que o esf�or�co para resolver dois sistemas lineares seja

recompensado pela redu�c�ao no numero de itera�c�oes�

� Este e o metodo com melhores resultados teoricos e praticos

�tem converg�encia quadratica��

Page 32: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

� M�etodo de Barreira Logar��timica

�� Introdu�c�ao

Seja o problema�

�P � �

�������������

max ctx

sa Ax � b

x � �

Substituindo a restri�c�ao x � � na forma�

� �P � �

�������������������������������������������������

max ctx �tf�x�

sa Ax � b

onde � f�x� � ln�x� �

������������������

ln�x��

ln�x��

ln�xn�

�����������������

� pode ser assumido um escalar �� � R��

Exemplo�

�������������������

min z � �x� �x�sa x� x� � �eq� �

� � x� � � �eq���

� � x� � � �eq���

Page 33: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

����������������

����

����

��������

��������

������������������

������������������

��������������������������������

��������������������������������

���������������������������������������������

���������������������������������������������

�����������������������������������

�����������������������������������

���������������

���������������

���������

���������

����

x1

x2eq. 2

eq. 3eq. 1

1 2

1

2

Figure �� Regi�ao fact��vel do problema

Regi�ao fact�vel na �gura �� Com as variaveis de folga����������������������������

min z � �x� �x�sa x� x� � x �

x� x� � �

x� x� � �

xi � �� i � � �� �� �� �

Com a adi�c�ao da fun�c�ao barreira�

���������������������������

min �z � �x� �x� � ��ln�x�� ln�x�� ln�x�

ln�x�� ln�x���

sa x� x� � x �

x� x� � �

x� x� � �

Vamos analisar duas situa�c�oes�

� a� x� � x� ��� �aproximadamente no meio da regi�ao fact�vel�

z � �x� �x� � �

Page 34: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

�z �� �����

� b� x� � ����� x� � ���� �quase na fronteira�

z � �����

�z �� ����

�P � pode ser colocado como sendo�

�P �� �

�����max f�x� � ctx �lnx

sa Ax � b

e o problema de busca de melhor dire�c�ao fact�vel �em torno do

ponto xk� pode ser colocado como�

�P �� �

�����max f�xk� dxk� �� rf t�xk�dxk �

��dxk�tJ�xk�dxk

sa Adxk � �

Note que����������������������

rf�xk� � c � �xk

J�xk� � faijg

aij �

�������

� �

�xki��

se i � j

� se c�c�

Aplicando o metodo primal a�m�escala ao P ���� obtemos �do

lagrangeano associado��

dxk � ��XkP k�ck �e�

Page 35: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

onde Xk � diag�xk�� ck � cXk e P k e a matriz de proje�c�ao

P k � I � �Ak�t�Ak�Ak�t���Ak com Ak � AXk�

Proximo ponto interior�

xk�� � xk �kdxk� com dxk � XkP k�ck �e�

Melhor tamanho do passo no metodo de Newton � ��� ��

�k � minf ��� �maxg� onde� max � min�

xki

��f�xki

�xki

g

� in!uencia fortemente no fator de converg�encia�

Valor t�pico� � � ���� �����

�� Algoritmo

� Dados � � ��� �� x� � �� �� grande� k � ��

�� Fa�ca ate convergir�

�a� Xk � diagfxkg

�b� ck � Xkc

�c� Ak � AXk

�d� P k � I � �Ak�t�Ak�Ak�t���Ak

�e� dxk � XkP k�ck �ke�

�f� kmax � min�xki��f� xk

i

�xki

g

Page 36: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

�g� �k � minf ��k� �kmaxg

�h� xk�� � xk �kdxk

�i� �k�� � f��k� ctxk�

�j� k � k

�� Fim Fa�ca

Nota�

� a� Criterio de converg�encias� pode ser feito sobre a varia�c�ao do

valor de ctxk � ctxk � �� ou sobre o valor de dxk � dxk � ���

� b� O ponto inicial interior x� pode ser encontrado utilizando o

metodo de M grande� como no caso do primal a�m�escala�

� c� O valor de �k pode ser tal que�

�k �

������ se k ctxk k grande

k ctxk k se k ctxk k pequeno

ou considerando�

�k�� � �k� � � �

O valor de � R� � � de�ne a velocidade de converg�encia�

Page 37: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

� Coment�arios sobre Sistemas Lineares

Nos metodos de pontos interiores� s�ao precisos determinar matrizes

do tipo� B � AD��At� onde A e uma matriz dada e D � � e uma

matriz diagonal que varia a cada itera�c�ao e e tal que�

� Primal A�m�Escala� D � X�� �yk � �A�Xk��At���A�Xk��c�

� Dual A�m�Escala� D � Z� �dyk � �A�Zk���At�b�

� Primal�Dual A�m�Escala�

D � X��Z�dyk � �A�Dk���At����rkp A�Dk���rkd �A�Zk���rkc ��

E uma etapa computacionalmente �cara�� A seguir� vamos anal�

isar alguns aspectos que poder�ao melhorar o comportamento com�

putacional�

Como D � � e diagonal� Dt � � tambem e diagonal e podemos

escrever�

B � AD��At � �A �At � � com �A � AD���

Assim� o elemento ij de B e dado por �ver �gura ���

ij � ��ai�t��aj� �

Pnk � �aik�ajk �

Pni � aikajk�

��kk

onde f�ijg � D� Para cada ij � temos ��� produtos uma

soma�n� � �n opera�c�oes� Como aikajk e constante para todas as

Page 38: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

i j

ai

t ~

aj

Figure �� ��ati���aj�

itera�c�oes� se armazenarmos este produto� o calculo de ij vai exigir

�� produto soma�n� � �n opera�c�oes�

Existem m�m���� elementos diferentes em B �simetrica� portanto�

m �m � � ��� � m��� m�� Assim� o numero de opera�c�oes

s�ao�Sem armazenamento� �nm�m���

� opera�c�oes

Com armazenamento� nm�m � opera�c�oesA matriz B e simetrica e de�nida positiva� Logo� a resolu�c�ao do

sistema�

Bd � b

�ca facilitada� se decompormos na forma�

LUd � b

onde�

�����L � matriz triangular inferior unitario

U � matriz triangular superior unitarioAqui� unitario signi�ca matriz com "s na diagonal principal� A

resolu�c�ao e processada� fazendo�

Page 39: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

=

L w b

=U d w

Figure �� Decomposic�ao LU � Soluc�ao por substituic�ao

L�Ud� � b

�����Lw � b

Ud � w

A decomposi�c�ao LU n�ao e unica mas a decomposi�c�aoB � L U

e unica �onde e diagonal e L e U s�ao matrizes unitarios� E

poss�vel mostrar que� para matrizes simetricas� U � Lt� ou seja�

B � L Lt� Como B � � � � �� podemos escrever que

� ��

�� � o que permite escrever�

B � L ��

��Lt � �L�Lt

que e conhecido como decomposi�c�ao de Cholesky� Isso permite

escrevermos�

Bd � b� �L�Ltd � b�

������Lw � b�Ltd � w

Page 40: simplex otimo - Unicamptiago/courses/otimizacao_linear...primal e do dual Ex GAP c t x b y Condi c oes de Otimalidade i Primal factibilidade b Ax x ii Dual factibilidade c A t y z

FEEC� �� de mar�co de �����

Akebo Yamakami � Orientador

DT�FEEC�UNICAMP