Método do ponto interior - Interior-point method

Exemplo de busca por uma solução. As linhas azuis mostram restrições, os pontos vermelhos mostram soluções iteradas.

Os métodos de ponto interior (também chamados de métodos de barreira ou IPMs ) são uma determinada classe de algoritmos que resolvem problemas de otimização convexa linear e não linear .

Um método de pontos interiores foi descoberto pelo matemático soviético II Dikin em 1967 e reinventado nos Estados Unidos em meados da década de 1980. Em 1984, Narendra Karmarkar desenvolveu um método para programação linear chamado algoritmo de Karmarkar , que roda em tempo comprovadamente polinomial e também é muito eficiente na prática. Ele permitiu soluções de problemas de programação linear que estavam além das capacidades do método simplex . Ao contrário do método simplex, ele atinge a melhor solução percorrendo o interior da região viável . O método pode ser generalizado para programação convexa com base em uma função de barreira auto-concordante usada para codificar o conjunto convexo .

Qualquer problema de otimização convexa pode ser transformado em minimizar (ou maximizar) uma função linear sobre um conjunto convexo, convertendo para a forma de epígrafe . A ideia de codificar o conjunto viável usando uma barreira e projetar métodos de barreira foi estudada por Anthony V. Yurii Nesterov , e Arkadi Nemirovski propôs uma classe especial de tais barreiras que podem ser usadas para codificar qualquer conjunto convexo. Eles garantem que o número de iterações do algoritmo é limitado por um polinômio na dimensão e precisão da solução.

O avanço de Karmarkar revitalizou o estudo de métodos de pontos interiores e problemas de barreiras, mostrando que era possível criar um algoritmo de programação linear caracterizado pela complexidade polinomial e, além disso, competitivo com o método simplex. O método elipsóide de Khachiyan já era um algoritmo de tempo polinomial; no entanto, era lento demais para ser de interesse prático.

A classe de métodos de ponto interior de seguimento de caminho primal-dual é considerada a mais bem-sucedida. O algoritmo preditor-corretor de Mehrotra fornece a base para a maioria das implementações desta classe de métodos.

Método de ponto interior duplo primário para otimização não linear

A ideia do método primal-dual é fácil de demonstrar para otimização não linear restrita . Para simplificar, considere a versão de todas as desigualdades de um problema de otimização não linear:

minimizar assunto para onde${\ displaystyle f (x)}$${\ displaystyle c_ {i} (x) \ geq 0 ~ {\ text {for}} ~ i = 1, \ ldots, m, ~ x \ in \ mathbb {R} ^ {n},}$${\ displaystyle f: \ mathbb {R} ^ {n} \ to \ mathbb {R}, c_ {i}: \ mathbb {R} ^ {n} \ rightarrow \ mathbb {R} \ quad (1).}$

Este problema de otimização com restrição de desigualdade é então resolvido convertendo-o em uma função objetivo irrestrita cujo mínimo esperamos encontrar de forma eficiente. Especificamente, a função de barreira logarítmica associada a (1) é

${\ displaystyle B (x, \ mu) = f (x) - \ mu \ sum _ {i = 1} ^ {m} \ log (c_ {i} (x)). \ quad (2)}$

Aqui está um pequeno escalar positivo, às vezes chamado de "parâmetro de barreira". Como converge para zero, o mínimo de deve convergir para uma solução de (1). ${\ displaystyle \ mu}$${\ displaystyle \ mu}$${\ displaystyle B (x, \ mu)}$

O gradiente da função de barreira é

${\ displaystyle g_ {b} (x, \ mu): = \ nabla B (x, \ mu) = g (x) - \ mu \ sum _ {i = 1} ^ {m} {\ frac {1} {c_ {i} (x)}} \ nabla c_ {i} (x), \ quad (3)}$

onde é o gradiente da função original e é o gradiente de . ${\ displaystyle g (x): = \ nabla f (x)}$${\ displaystyle f (x)}$${\ displaystyle \ nabla c_ {i}}$${\ displaystyle c_ {i}}$

Além da variável original ("primal") , introduzimos uma variável dupla inspirada no multiplicador de Lagrange${\ displaystyle x}$${\ displaystyle \ lambda \ in \ mathbb {R} ^ {m}}$

${\ displaystyle c_ {i} (x) \ lambda _ {i} = \ mu, \ forall i = 1, \ ldots, m. \ quad (4)}$

(4) às vezes é chamada de condição de "complementaridade perturbada", por sua semelhança com a "folga complementar" nas condições KKT .

Tentamos encontrar aqueles para os quais o gradiente da função de barreira é zero. ${\ displaystyle (x _ {\ mu}, \ lambda _ {\ mu})}$

Aplicando (4) a (3), obtemos uma equação para o gradiente:

${\ displaystyle gA ^ {T} \ lambda = 0, \ quad (5)}$

onde a matriz é o Jacobiano das restrições . ${\ displaystyle A}$${\ displaystyle c (x)}$

A intuição por trás de (5) é que o gradiente de deve estar no subespaço estendido pelos gradientes das restrições. A "complementaridade perturbada" com pequeno (4) pode ser entendida como a condição de que a solução deve estar próxima da fronteira , ou que a projeção do gradiente no componente de restrição normal deve ser quase zero. ${\ displaystyle f (x)}$${\ displaystyle \ mu}$${\ displaystyle c_ {i} (x) = 0}$${\ displaystyle g}$${\ displaystyle c_ {i} (x)}$

Aplicando o método de Newton a (4) e (5), obtemos uma equação para atualização : ${\ displaystyle (x, \ lambda)}$${\ displaystyle (p_ {x}, p _ {\ lambda})}$

${\ displaystyle {\ begin {pmatrix} W & -A ^ {T} \\\ Lambda A&C \ end {pmatrix}} {\ begin {pmatrix} p_ {x} \\ p _ {\ lambda} \ end {pmatrix}} = {\ begin {pmatriz} -g + A ^ {T} \ lambda \\\ mu 1-C \ lambda \ end {pmatriz}},}$

onde é a matriz Hessiana de , é uma matriz diagonal de e é uma matriz diagonal com . ${\ displaystyle W}$${\ displaystyle B (x, \ mu)}$${\ displaystyle \ Lambda}$${\ displaystyle \ lambda}$${\ displaystyle C}$${\ displaystyle C_ {ii} = c_ {i} (x)}$

Por causa de (1), (4) a condição

${\ displaystyle \ lambda \ geq 0}$

deve ser aplicada em cada etapa. Isso pode ser feito escolhendo apropriado : ${\ displaystyle \ alpha}$

${\ displaystyle (x, \ lambda) \ to (x + \ alpha p_ {x}, \ lambda + \ alpha p _ {\ lambda}).}$

Tocar mídia

Trajetória das iterações de x usando o método do ponto interior.

Veja também

• Escala afim
• Método Lagrangiano Aumentado
• Método de penalidade
• Condições de Karush – Kuhn – Tucker

Referências

Bibliografia

• Dikin, II (1967). “Resolução iterativa de problemas de programação linear e quadrática” . Dokl. Akad. Nauk SSSR . 174 (1): 747–748.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Otimização numérica: Aspectos teóricos e práticos . Universitext (segunda edição revisada da tradução da edição francesa de 1997). Berlim: Springer-Verlag. pp. xiv + 490. doi : 10.1007 / 978-3-540-35447-5 . ISBN 978-3-540-35445-1. MR  2265882 .
• Karmarkar, N. (1984). "Um novo algoritmo de tempo polinomial para programação linear" (PDF) . Anais do décimo sexto simpósio anual da ACM em Teoria da Computação - STOC '84 . p. 302. doi : 10.1145 / 800057.808695 . ISBN 0-89791-133-4. Arquivado do original (PDF) em 28 de dezembro de 2013.
• Mehrotra, Sanjay (1992). "Sobre a implementação de um método de pontos interiores primários e duplos". SIAM Journal on Optimization . 2 (4): 575–601. doi : 10.1137 / 0802028 .
• Nocedal, Jorge; Stephen Wright (1999). Otimização numérica . New York, NY: Springer. ISBN 978-0-387-98793-4.
• Pressione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Seção 10.11. Programação linear: métodos de pontos internos" . Receitas Numéricas: A Arte da Computação Científica (3ª ed.). Nova York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Wright, Stephen (1997). Métodos Primal-Dual Interior-Point . Filadélfia, PA: SIAM. ISBN 978-0-89871-382-4.
• Boyd, Stephen; Vandenberghe, Lieven (2004). Otimização convexa (PDF) . Cambridge University Press.