Método de ponto interior

Exemplo de busca de uma solução. Linhas azuis mostram restrições, pontos vermelhos mostram soluções iteradas.

Métodos de pontos interiores (também conhecidos como métodos de barreira ou IPMs ) são uma certa classe de algoritmos que resolvem problemas de otimização convexa lineares e não lineares .

Um método de pontos interiores foi descoberto pelo matemático soviético II Dikin em 1967 e reinventado nos EUA 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. 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 factível . O método pode ser generalizado para programação convexa com base em uma função de barreira autoconcordante 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 epígrafe . [1] A ideia de codificar o conjunto viável usando uma barreira e projetar métodos de barreira foi estudada por Anthony V. Fiacco, Garth P. McCormick e outros no início dos anos 1960. Estas ideias foram desenvolvidas principalmente para programação não linear geral , mas foram posteriormente abandonadas devido à presença de métodos mais competitivos para esta classe de problemas (por exemplo, programação quadrática sequencial ).

Yurii Nesterov e Arkadi Nemirovski criaram uma classe especial dessas barreiras que podem ser usadas para codificar qualquer conjunto convexo. Eles garantem que o número de iterações do algoritmo seja limitado por um polinômio na dimensão e precisão da solução. [2]

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

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

Método primal-dual de pontos interiores 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 o seguinte problema de otimização não linear com restrições de desigualdade:

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

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).

O gradiente de uma função diferenciável é denotado por . O gradiente da função de barreira é

Além da variável original ("primal"), introduzimos uma variável dupla inspirada no multiplicador de Lagrange

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

Tentamos encontrar aqueles para os quais o gradiente da função de barreira é zero.

Substituindo de (4) em (3), obtemos uma equação para o gradiente:

onde a matriz é o jacobiano das restrições .

A intuição por trás de (5) é que o gradiente de deve estar no subespaço gerado 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 ao limite ou que a projeção do gradiente na normal do componente de restrição deve ser quase zero.

Seja a direção de busca para atualização iterativa . Aplicando o método de Newton a (4) e (5), obtemos uma equação para :

onde é a matriz hessiana de , é uma matriz diagonal de e é a matriz diagonal de .

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

deve ser aplicada em cada etapa. Isso pode ser feito escolhendo apropriado :

Trajetória dos iterados de x usando o método de pontos interiores.

Veja também

Referências

  1. ^ Boyd, Stephen; Vandenberghe, Lieven (2004). Otimização convexa . Cambridge: Cambridge University Press . pág. 143. ISBN 978-0-521-83378-3. MR  2061575.
  2. ^ Wright, Margaret H. (2004). "A revolução do ponto interior na otimização: história, desenvolvimentos recentes e consequências duradouras". Boletim da American Mathematical Society . 42 :39–57. doi : 10.1090/S0273-0979-04-01040-7 . MR  2115066.
  3. ^ Potra, Florian A.; Stephen J. Wright (2000). "Métodos de pontos interiores". Jornal de Matemática Computacional e Aplicada . 124 (1–2): 281–302. doi : 10.1016/S0377-0427(00)00433-7 .

Bibliografia

  • Dikin, II (1967). "Soluçã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 ed. 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 sobre Teoria da Computação – STOC '84 . pág. 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 ponto interior primal-dual". SIAM Journal on Optimization . 2 (4): 575–601. doi : 10.1137/0802028.
  • Nocedal, Jorge; Estevão Wright (1999). Otimização numérica . Nova 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 Interiores". 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 de Pontos Interiores . Filadélfia, PA: SIAM. ISBN 978-0-89871-382-4.
  • Boyd, Stephen; Vandenberghe, Lieven (2004). Otimização Convexa (PDF) . Cambridge University Press.