A quest˜ao do tratamento de restri¸c˜oes n˜ao-lineares gen´ericas ´e uma an- tiga dificuldade que desafia os diferentes m´etodos de otimiza¸c˜ao conhecidos
2De fato, esta ´e a defini¸c˜
Outros m´etodos, tais como aqueles baseados em programa¸c˜ao quadr´atica, ne- cessitam aproximar as suas restri¸c˜oes por fun¸c˜oes afins, o que pode impedir a sua aplica¸c˜ao em determinadas classes de problemas. Em particular, res- tri¸c˜oes n˜ao-diferenci´aveis constituem uma classe de problemas para os quais existem poucos m´etodos dispon´ıveis.
Os m´etodos da categoria de “exclus˜ao de semi-espa¸cos” tˆem em comum ainda a maneira imediata como tratam a quest˜ao das restri¸c˜oes. O me- canismo de tratamento de restri¸c˜oes se baseia no fato de que, dada uma restri¸c˜ao convexa (ou seja, que define uma regi˜ao fact´ıvel convexa), o sub- gradiente dessa restri¸c˜ao num ponto sempre define um semi-espa¸co no qual dever´a estar contida a regi˜ao fact´ıvel. Dessa forma, n˜ao ´e necess´aria nenhuma altera¸c˜ao estrutural no algoritmo para tratar as restri¸c˜oes, basta substituir o subgradiente da fun¸c˜ao objetivo pelos subgradientes dos funcionais que representam as restri¸c˜oes violadas.
A estrutura l´ogica da abordagem de “exclus˜ao de semi-espa¸cos” para o tratamento de m´ultiplas restri¸c˜oes decorre do fato de que a interse¸c˜ao de conjuntos convexos ´e um conjunto convexo. Para ilustrar isso, considere-se o sistema com uma fun¸c˜ao-objetivo e duas fun¸c˜oes de restri¸c˜ao, sendo as trˆes fun¸c˜oes convexas: x∗ = arg min x f (x) sujeito a: g1(x) ≤ 0 g2(x) ≤ 0 (7.18) com f (·) : Rn 7→ R, g 1(·) : Rn 7→ R e g2(·) : Rn 7→ R. A regi˜ao fact´ıvel do
problema ´e dada pela interse¸c˜ao das regi˜oes sub-n´ıvel das duas fun¸c˜oes, para o n´ıvel zero:
F = R(g1, 0) ∩ R(g1, 0) (7.19)
Esta regi˜ao fact´ıvel pode ainda ser interpretada como sendo a regi˜ao sub-n´ıvel para o n´ıvel zero de uma outra fun¸c˜ao, r(·), constru´ıda como:
r(x) = max{g1(x), g2(x)} (7.20)
Dessa forma:
Claramente, a partir da convexidade de g1(·) e g2(·), tem-se a convexidade
de r(·) e de F. Dessa forma, no caso geral, pode-se definir:
r(x) = max{g1(x), g2(x), · · · , gm(x)} (7.22)
A otimiza¸c˜ao de r(x), claramente, resulta em um ponto fact´ıvel, se houver tal ponto. A cada passo antes de se atingir a factibilidade, exclui-se apenas um semi-espa¸co infact´ıvel. Defina-se por fim a fun¸c˜ao s(·) : Rn 7→ R dada
por: s(x) = f (x) , se r(x) ≤ 0 r(x) , se r(x) > 0 (7.23) A otimiza¸c˜ao de s(x) ir´a produzir a cada passo:
• a exclus˜ao do semi-espa¸co em que o ponto de ´otimo n˜ao se encontra, se o ponto corrente for fact´ıvel;
• a exclus˜ao do semi-espa¸co que ´e totalmente infact´ıvel, se o ponto cor- rente for infact´ıvel.
A otimiza¸c˜ao de s(·) leva, portanto, `a convergˆencia para o ´otimo restrito x∗
. Devido a tal estrutura de tratamento de restri¸c˜oes, o m´etodo elipsoidal ´e conhecido como um procedimento particularmente flex´ıvel de otimiza¸c˜ao, que possui convergˆencia garantida para o ´otimo sob a condi¸c˜ao de convexidade da fun¸c˜ao objetivo e das restri¸c˜oes (Akg¨ul 1984). A simplicidade de se tratar com com restri¸c˜oes n˜ao-lineares neste m´etodo ´e uma das principais raz˜oes de sua aplicabilidade.
7.5
Caracter´ısticas de Comportamento
O comportamento dessa categoria de m´etodos frente a algumas dificuldades que ir˜ao surgir com freq¨uˆencia em problemas de otimiza¸c˜ao de tipo geral ´e agora discutido.
7.5.1
Descontinuidades e N˜ao-Diferenciabilidade
As regi˜oes de descontinuidade e n˜ao-diferenciabilidade de funcionais no espa¸co de parˆametros n˜ao constituem problema para a execu¸c˜ao dos m´etodos de “ex- clus˜ao de semi-espa¸cos”. Tais singularidades n˜ao obstruem a determina¸c˜ao de
que o c´alculo do pr´oximo ponto estimado n˜ao ´e feito sobre uma trajet´oria que parte do ponto atual, como no caso dos algoritmos de busca em dire¸c˜oes (isso faz com que que tais algoritmos fiquem presos nessas singularidades). O pr´oximo ponto, ao inv´es disso, ´e obtido por constru¸c˜ao a uma distˆancia finita do ponto anterior, o que impede que a seq¨uˆencia de estimativas fique “aprisionada”.
7.5.2
N˜ao-Convexidade
A principal premissa sobre a qual se assenta a categoria dos m´etodos de “exclus˜ao de semi-espa¸cos” ´e a convexidade de todos os funcionais envolvidos. Se tal premissa for violada, o processo de exclus˜ao passa a ser feito “`as cegas”, de forma que a evolu¸c˜ao do m´etodo torna-se imprevis´ıvel. ´E poss´ıvel que, nessas circunstˆancias, o m´etodo n˜ao convirja para o ponto de ´otimo.
7.5.3
Multimodalidade
A quest˜ao da multimodalidade pode ser entendida como um caso particular da n˜ao-convexidade. Isso poderia levar a an´alise a conclus˜oes semelhantes. No entanto, deve-se observar que uma fun¸c˜ao multimodal pode ser local- mente convexa, de forma que os algoritmos de “exclus˜ao de semi-espa¸cos” podem convergir para m´ınimos locais. ´E poss´ıvel, entretanto, que n˜ao ocorra convergˆencia para nenhum m´ınimo.
7.5.4
Velocidade de Convergˆencia
Deve-se notar inicialmente que as caracter´ısticas de convergˆencia tanto dos m´etodos de “dire¸c˜ao de busca” quanto dos de “exclus˜ao de semi-espa¸cos” po- dem ser muito diferentes dependendo do m´etodo espec´ıfico que estiver sendo referido em cada caso. De uma forma geral, entretanto, ´e poss´ıvel afirmar que h´a uma tendˆencia para que em problemas nos quais s˜ao aplic´aveis tanto os m´etodos do tipo “dire¸c˜ao de busca” quanto os m´etodos de “exclus˜ao de semi-espa¸cos”, os primeiros apresentem maior velocidade de convergˆencia. Os segundos devem ser aplicados, portanto, especificamente nos problemas em que houver n˜ao-diferenciabilidades que impediriam a convergˆencia dos
primeiros. H´a ainda o caso de problemas de factibilidade (que podem cons- tituir a etapa inicial de grande parte dos problemas de otimiza¸c˜ao), em que a eficiˆencia de alguns m´etodos (especificamente os m´etodos do tipo “elip- soidal”) de “exclus˜ao de semi-espa¸cos” pode ser muito aumentada com a aplica¸c˜ao de “deep cuts”.
7.6
Algoritmo Cone-Elipsoidal
Esta se¸c˜ao e as pr´oximas do presente cap´ıtulo pretendem mostrar que a inter- preta¸c˜ao das condi¸c˜oes de Karush-Kuhn-Tucker para otimalidade enquanto uma condi¸c˜ao de “inexistˆencia de um cone”, e seu complemento como uma condi¸c˜ao de “existˆencia” de um cone de dire¸c˜oes fact´ıveis pode fornecer “in- sights” a respeito de problemas de otimiza¸c˜ao em geral. Esses cones oriundos da condi¸c˜ao KKTE ser˜ao utilizados para aperfei¸coar as propriedades de con- vergˆencia do algoritmo elipsoidal.
Nas se¸c˜oes que se seguem, ´e mostrado que: (i) em algumas situa¸c˜oes, a configura¸c˜ao das restri¸c˜oes pode levar a uma convergˆencia arbitrariamente lenta do m´etodo elipsoidal cl´assico para a solu¸c˜ao do problema; e (ii) uma mo- difica¸c˜ao do m´etodo elipsoidal, denominada M´etodo Cone-Elipsoidal (MCE), proposta por este autor e colaboradores (Takahashi, Saldanha, Dias-Filho & Ramirez 2003), restaura as propriedades de convergˆencia do m´etodo, obtendo a mesma taxa de convergˆencia atingida quando o mesmo ´e aplicado a pro- blemas irrestritos. O algoritmo MCE proposto preserva as condi¸c˜oes formais de convergˆencia para o ´otimo em problemas convexos, possibilitando, ainda, tratar uma classe de problemas n˜ao-convexos.
Os dados apresentados a seguir foram, em grande parte, publicados na referˆencia (Takahashi, Saldanha, Dias-Filho & Ramirez 2003) e na tese de doutorado, orientada pelo presente autor, (Dias-Filho 2003). Uma aborda- gem diferente da que est´a sendo proposta aqui foi empregada na referˆencia (Shah, Mitchell & Kupferschmid 2001) para lidar com a mesma dificuldade de convergˆencia do m´etodo elipsoidal em problemas com restri¸c˜oes de igual- dade. Entretanto, tal referˆencia se limita a abordar problemas com restri¸c˜oes lineares, fazendo uso de proje¸c˜oes do elips´oide dentro da variedade linear que define o conjunto fact´ıvel.
Considere-se o problema de otimiza¸c˜ao com restri¸c˜oes de igualdade3 e de
desigualdade, definido no espa¸co dos parˆametros x ∈ Rn:
x∗ = arg min x f (x) sujeito a: qj(x) ≤ 0 ; j = 1, . . . , r hl(x) ≤ 0 ; l = 1, . . . , s −hl(x) ≤ 0 ; l = 1, . . . , s (7.24)
Assume-se que as fun¸c˜oes f (·), q(·) e h(·) devam ser convexas, para permitir a constru¸c˜ao de provas formais de convergˆencia para o ´otimo global. No caso de fun¸c˜oes arbitr´arias, o m´etodo pode convergir para m´ınimos locais ou pode divergir (assim como qualquer outro m´etodo de otimiza¸c˜ao). O vetor de restri¸c˜oes ´e reescrito da seguinte forma:
g(x) = qT(x) hT(x) −hT(x) T
(7.25) Seja F o conjunto de solu¸c˜oes fact´ıveis do problema (7.24), ou seja, o conjunto dos pontos para os quais g(x) ≤ 0.