Método do ponto interior

Métodos de ponto interior (também chamados de métodos de barreira ou IPMs ) são algoritmos para resolver problemas de otimização convexa linear e não linear . IPMs combinam duas vantagens de algoritmos previamente conhecidos:
- Teoricamente, seu tempo de execução é polinomial — em contraste com o método simplex , que tem tempo de execução exponencial no pior caso.
- Na prática, eles são executados tão rápido quanto o método simplex, em contraste com o método elipsoide , que tem tempo de execução polinomial em teoria, mas é muito lento na prática.
Em contraste com o método simplex, que atravessa o limite da região viável, e o método elipsoide, que delimita a região viável de fora , um IPM alcança a melhor solução atravessando o interior da região viável — daí o nome.
História
Um método de ponto interior foi descoberto pelo matemático soviético II Dikin em 1967. [1] O método foi 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 , [2] que roda em tempo polinomial comprovadamente ( operações em números de L bits, onde n é o número de variáveis e constantes), e também é muito eficiente na prática. O artigo de Karmarkar criou uma onda de interesse em métodos de ponto interior. Dois anos depois, James Renegar inventou o primeiro método de ponto interior de seguimento de caminho , com tempo de execução . O método foi posteriormente estendido de problemas de otimização linear para convexa, com base em uma função de barreira autoconcordante usada para codificar o conjunto convexo . [3]
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 . [4] : 143 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 da década de 1960. Essas 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 é limitado por um polinômio na dimensão e precisão da solução. [5] [3]
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. [6]
Definições
Recebemos um programa convexo da forma: onde f é uma função convexa e G é um conjunto convexo . Sem perda de generalidade, podemos assumir que o objetivo f é uma função linear . Normalmente, o conjunto convexo G é representado por um conjunto de desigualdades convexas e igualdades lineares; as igualdades lineares podem ser eliminadas usando álgebra linear, então, para simplificar, assumimos que há apenas desigualdades convexas, e o programa pode ser descrito como segue, onde g i são funções convexas: Assumimos que as funções de restrição pertencem a alguma família (por exemplo, funções quadráticas), de modo que o programa pode ser representado por um vetor finito de coeficientes (por exemplo, os coeficientes das funções quadráticas). A dimensão desse vetor de coeficientes é chamada de tamanho do programa. Um solucionador numérico para uma dada família de programas é um algoritmo que, dado o vetor de coeficientes, gera uma sequência de soluções aproximadas x t para t =1,2,..., usando um número finito de operações aritméticas. Um solucionador numérico é chamado convergente se, para qualquer programa da família e qualquer ε positivo >0, houver algum T (que pode depender do programa e de ε ) tal que, para qualquer t > T , a solução aproximada x t seja ε-aproximada, ou seja: onde é a solução ótima. Um solucionador é chamado polinomial se o número total de operações aritméticas nos primeiros T passos for no máximo
poli(tamanho do problema) * log( V / ε ),
onde V é alguma constante dependente de dados, por exemplo, a diferença entre o maior e o menor valor no conjunto viável. Em outras palavras, V / ε é a "precisão relativa" da solução - a precisão wrt o maior coeficiente. log( V / ε ) representa o número de "dígitos de precisão". Portanto, um solucionador é 'polinomial' se cada dígito adicional de precisão requer um número de operações que é polinomial no tamanho do problema.
Tipos
Os tipos de métodos de pontos internos incluem:
- Métodos de redução de potencial : O algoritmo de Karmarkar foi o primeiro.
- Métodos de acompanhamento de caminhos : os algoritmos de James Renegar [7] e Clovis Gonzaga [8] foram os primeiros.
- Métodos primal-duais .
Métodos de acompanhamento de caminho
Ideia
Dado um programa de otimização convexa (P) com restrições, podemos convertê-lo em um programa irrestrito adicionando uma função de barreira . Especificamente, seja b uma função convexa suave, definida no interior da região viável G , tal que para qualquer sequência { x j in interior(G)} cujo limite esteja na fronteira de G : . Também assumimos que b é não degenerado, isto é: é positivo definido para todo x in interior(G). Agora, considere a família de programas:
( P t ) minimizar t * f(x) + b(x)
Tecnicamente o programa é restrito, já que b é definido somente no interior de G . Mas, na prática, é possível resolvê-lo como um programa irrestrito, já que qualquer solucionador tentando minimizar a função não se aproximará do limite, onde b se aproxima do infinito. Portanto, ( P t ) tem uma solução única - denote-a por x *( t ). A função x * é uma função contínua de t , que é chamada de caminho central . Todos os pontos limites de x *, conforme t se aproxima do infinito, são soluções ótimas do programa original (P).
Um método de seguimento de caminho é um método de rastrear a função x * ao longo de uma certa sequência crescente t 1 ,t 2 ,..., isto é: calcular uma aproximação boa o suficiente x i para o ponto x *( t i ), tal que a diferença x i - x *( t i ) se aproxima de 0 conforme i se aproxima do infinito; então a sequência x i se aproxima da solução ótima de (P). Isso requer especificar três coisas:
- A função de barreira b(x).
- Uma política para determinar os parâmetros de penalidade t i .
- O solucionador de otimização irrestrita usado para resolver ( P i ) e encontrar x i , como o método de Newton . Observe que podemos usar cada x i como um ponto de partida para resolver o próximo problema ( P i+1 ).
O principal desafio em provar que o método é politemporal é que, conforme o parâmetro de penalidade cresce, a solução se aproxima do limite, e a função se torna mais íngreme. O tempo de execução de solucionadores como o método de Newton se torna mais longo, e é difícil provar que o tempo de execução total é polinomial.
Renegar [7] e Gonzaga [8] provaram que uma instância específica de um método de seguimento de caminho é o politempo:
- As restrições (e o objetivo) são funções lineares;
- A função de barreira é logarítmica : b(x) := - sum j log( -g j ( x )).
- O parâmetro de penalidade t é atualizado geometricamente, ou seja, , onde μ é uma constante (eles pegaram , onde m é o número de restrições de desigualdade);
- O solucionador é o método de Newton, e uma única etapa de Newton é realizada para cada etapa em t .
Eles provaram que, neste caso, a diferença x i - x *( t i ) permanece no máximo 0,01, e f( x i ) - f* é no máximo 2* m / t i . Assim, a precisão da solução é proporcional a 1/ t i , então para adicionar um único dígito de precisão, é suficiente multiplicar t i por 2 (ou qualquer outro fator constante), o que requer O(sqrt( m )) passos de Newton. Como cada passo de Newton leva O( mn 2 ) operações, a complexidade total é O( m 3/2 n 2 ) operações para o dígito de precisão.
Yuri Nesterov estendeu a ideia de programas lineares para não lineares. Ele observou que a principal propriedade da barreira logarítmica, usada nas provas acima, é que ela é autoconcordante com um parâmetro de barreira finito. Portanto, muitas outras classes de programas convexos podem ser resolvidas em politempo usando um método de seguimento de caminho, se pudermos encontrar uma função de barreira autoconcordante adequada para sua região viável. [3] : Sec.1
Detalhes
Temos um problema de otimização convexa (P) na "forma padrão":
minimizar c T x st x em G ,
onde G é convexo e fechado. Também podemos assumir que G é limitado (podemos facilmente torná-lo limitado adicionando uma restrição | x |≤ R para algum R suficientemente grande ). [3] : Sec.4
Para usar o método do ponto interior, precisamos de uma barreira autoconcordante para G . Seja b uma barreira M -autoconcordante para G , onde M ≥1 é o parâmetro de autoconcordância. Assumimos que podemos calcular eficientemente o valor de b , seu gradiente e seu Hessian , para cada ponto x no interior de G .
Para cada t >0, definimos o objetivo penalizado f t (x) := c T x + b( x ) . Definimos o caminho dos minimizadores por: x*(t) := arg min f t (x) . Aproximamos esse caminho ao longo de uma sequência crescente t i . A sequência é inicializada por um certo procedimento de inicialização não trivial de duas fases. Então, ela é atualizada de acordo com a seguinte regra: .
Para cada t i , encontramos um mínimo aproximado de f ti , denotado por x i . O mínimo aproximado é escolhido para satisfazer a seguinte "condição de proximidade" (onde L é a tolerância do caminho ):
.
Para encontrar x i +1 , começamos com x i e aplicamos o método de Newton amortecido . Aplicamos várias etapas deste método, até que a "relação de proximidade" acima seja satisfeita. O primeiro ponto que satisfaz esta relação é denotado por x i +1 . [3] : Sec.4
Convergência e complexidade
A taxa de convergência do método é dada pela seguinte fórmula, para cada i : [3] : Prop.4.4.1
Tomando , o número de passos de Newton necessários para ir de x i para x i +1 é no máximo um número fixo, que depende apenas de r e L . Em particular, o número total de passos de Newton necessários para encontrar uma solução ε -aproximada (ou seja, encontrar x em G tal que c T x - c* ≤ ε ) é no máximo: [3] : Thm.4.4.1
onde o fator constante O(1) depende apenas de r e L . O número de etapas de Newton necessárias para o procedimento de inicialização de duas etapas é no máximo: [3] : Thm.4.5.1
onde o fator constante O(1) depende apenas de r e L , e , e é algum ponto no interior de G . No geral, a complexidade geral de Newton para encontrar uma solução ε -aproximada é no máximo
, onde V é uma constante dependente do problema: .
Cada passo de Newton requer O( n 3 ) operações aritméticas.
Inicialização: métodos de fase I
Para inicializar os métodos de seguimento de caminho, precisamos de um ponto no interior relativo da região viável G . Em outras palavras: se G é definido pelas desigualdades g i ( x ) ≤ 0, então precisamos de algum x para o qual g i ( x ) < 0 para todo i em 1,..., m . Se não tivermos tal ponto, precisamos encontrar um usando o chamado método de fase I . [4] : 11.4 Um método simples de fase I é resolver o seguinte programa convexo: Denote a solução ótima por x*, s *.
- Se s *<0, então sabemos que x* é um ponto interno do problema original e podemos prosseguir para a "fase II", que é resolver o problema original.
- Se s *>0, então sabemos que o programa original é inviável - a região viável está vazia.
- Se s *=0 e for alcançado por alguma solução x*, então o problema é viável, mas não tem ponto interior; se não for alcançado, então o problema é inviável.
Para este programa é fácil obter um ponto interior: podemos tomar arbitrariamente x =0, e tomar s como qualquer número maior que max( f 1 (0),..., f m (0)). Portanto, ele pode ser resolvido usando métodos de ponto interior. No entanto, o tempo de execução é proporcional a log(1/ s *). Conforme s* se aproxima de 0, fica cada vez mais difícil encontrar uma solução exata para o problema da fase I, e assim mais difícil decidir se o problema original é viável.
Considerações práticas
As garantias teóricas assumem que o parâmetro de penalidade é aumentado na taxa , então o pior caso de número de etapas de Newton necessárias é . Em teoria, se μ for maior (por exemplo, 2 ou mais), então o pior caso de número de etapas de Newton necessárias está em . No entanto, na prática, um μ maior leva a uma convergência muito mais rápida. Esses métodos são chamados de métodos de passo longo . [3] : Sec.4.6 Na prática, se μ estiver entre 3 e 100, então o programa converge dentro de 20-40 etapas de Newton, independentemente do número de restrições (embora o tempo de execução de cada etapa de Newton, é claro, cresça com o número de restrições). O valor exato de μ dentro desse intervalo tem pouco efeito no desempenho. [4] : cap.11
Métodos de redução de potencial
Para métodos de redução de potencial, o problema é apresentado na forma cônica : [3] : Sec.5
minimizar c T x st x em {b+L} ∩ K ,
onde b é um vetor em R n , L é um subespaço linear em R n (então b + L é um plano afim ), e K é um cone convexo pontiagudo fechado com um interior não vazio. Todo programa convexo pode ser convertido para a forma cônica. Para usar o método de redução de potencial (especificamente, a extensão do algoritmo de Karmarkar para programação convexa), precisamos das seguintes suposições: [3] : Sec.6
- A. O conjunto viável {b+L} ∩ K é limitado e intercepta o interior do cone K .
- B. Recebemos de antemão uma solução estritamente viável x ^, ou seja, uma solução viável no interior de K .
- C. Sabemos de antemão o valor objetivo ótimo, c*, do problema.
- D. Recebemos uma barreira autoconcordante M -logaritmicamente homogênea F para o cone K .
As suposições A, B e D são necessárias na maioria dos métodos de ponto interior. A suposição C é específica para a abordagem de Karmarkar; ela pode ser aliviada usando um "valor objetivo deslizante". É possível reduzir ainda mais o programa para o formato de Karmarkar :
minimizar s T x st x em M ∩ K e e T x = 1
onde M é um subespaço linear de em R n , e o valor objetivo ótimo é 0. O método é baseado na seguinte função potencial escalar :
v ( x ) = F ( x ) + M ln ( s T x )
onde F é a barreira M -autoconcordante para o cone viável. É possível provar que, quando x é estritamente viável e v ( x ) é muito pequeno (- muito negativo), x é aproximadamente ótimo. A ideia do método de redução de potencial é modificar x de modo que o potencial em cada iteração caia em pelo menos uma constante fixa X (especificamente, X =1/3-ln(4/3)). Isso implica que, após i iterações, a diferença entre o valor objetivo e o valor objetivo ótimo é no máximo V * exp(- i X / M ), onde V é uma constante dependente de dados. Portanto, o número de passos de Newton necessários para uma solução ε -aproximada é no máximo .
Note que em métodos de seguimento de caminho a expressão é em vez de M , o que é melhor na teoria. Mas na prática, o método de Karmarkar permite dar passos muito maiores em direção ao objetivo, então ele pode convergir muito mais rápido do que as garantias teóricas.
Métodos primal-duais
A ideia do método primal-dual é fácil de demonstrar para otimização não linear restrita . [9] [10] Para simplificar, considere o seguinte problema de otimização não linear com restrições de desigualdade:
Este problema de otimização com restrição de desigualdade é resolvido convertendo-o em uma função objetivo irrestrita cujo mínimo esperamos encontrar eficientemente. 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". À medida que 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 dual inspirada no multiplicador de Lagrange
A equação (4) é algumas 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.
Substituindo (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 abrangido 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 do limite , ou que a projeção do gradiente na normal do componente de restrição deve ser quase zero.
Seja a direção da 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 .
Devido a (1), (4) a condição
deve ser aplicado em cada etapa. Isso pode ser feito escolhendo apropriado :
Trajetória das iterações de x usando o método do ponto interior.
Tipos de programas convexos solucionáveis por meio de métodos de pontos interiores
Aqui estão alguns casos especiais de programas convexos que podem ser resolvidos eficientemente por métodos de ponto interior. [3] : Sec.10
Considere um programa linear da forma: Podemos aplicar métodos de seguimento de caminho com a barreira A função é autoconcordante com o parâmetro M = m (o número de restrições). Portanto, o número de etapas de Newton necessárias para o método de seguimento de caminho é O( mn 2 ), e a complexidade total do tempo de execução é O( m 3/2 n 2 ). [ esclarecimento necessário ]
Dado um programa quadrático quadraticamente restrito da forma: onde todas as matrizes A j são matrizes positivas-semidefinidas . Podemos aplicar métodos de seguimento de caminho com a barreira A função é uma barreira autoconcordante com parâmetro M = m . A complexidade de Newton é O( (m+n)n 2 ), e a complexidade total do tempo de execução é O( m 1/2 (m+n) n 2 ).
eupaproximação de norma
Considere um problema da forma em que cada um é um vetor, cada um é um escalar e é uma norma L p com Após converter para a forma padrão, podemos aplicar métodos de seguimento de caminho com uma barreira autoconcordante com parâmetro M =4 m . A complexidade de Newton é O( (m+n)n 2 ), e a complexidade total do tempo de execução é O( m 1/2 (m+n) n 2 ).
Considere o problema
Existe uma barreira autoconcordante com parâmetro 2 k + m . O método de acompanhamento de caminho tem complexidade de Newton O( mk 2 + k 3 + n 3 ) e complexidade total O(( k+m ) 1/2 [ mk 2 + k 3 + n 3 ]).
Métodos de pontos interiores podem ser usados para resolver programas semidefinidos. [3] : Sec.11
Veja também
- Escala afim
- Método Lagrangiano Aumentado
- Algoritmo de Chambolle-Pock
- Condições de Karush–Kuhn–Tucker
- Método de penalidade
Referências
- ^ Dikin, II (1967). "Solução iterativa de problemas de programação linear e quadrática". Dokl. Akad. Nauk SSSR . 174 (1): 747–748.
- ^ 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. 302. doi : 10.1145/800057.808695 . ISBN 0-89791-133-4. Arquivado do original (PDF) em 28 de dezembro de 2013.
- ^ abcdefghijklm Arkadi Nemirovsky (2004). Métodos de tempo polinomial de ponto interior em programação convexa.
- ^ abc Boyd, Stephen; Vandenberghe, Lieven (2004). Otimização convexa . Cambridge: Cambridge University Press . ISBN 978-0-521-83378-3. SR 2061575.
- ^ Wright, Margaret H. (2004). "A revolução do ponto interior na otimização: História, desenvolvimentos recentes e consequências duradouras". Boletim da Sociedade Matemática Americana . 42 : 39–57. doi : 10.1090/S0273-0979-04-01040-7 . MR 2115066.
- ^ Potra, Florian A.; Stephen J. Wright (2000). "Métodos de ponto interior". Journal of Computational and Applied Mathematics . 124 (1–2): 281–302. doi : 10.1016/S0377-0427(00)00433-7 .
- ^ ab Renegar, James (1 de janeiro de 1988). "Um algoritmo de tempo polinomial, baseado no método de Newton, para programação linear". Programação Matemática . 40 (1): 59–93. doi :10.1007/BF01580724. ISSN 1436-4646.
- ^ ab Gonzaga, Clovis C. (1989), Megiddo, Nimrod (ed.), "Um algoritmo para resolver problemas de programação linear em operações O(n3L)", Progresso em programação matemática: métodos de ponto interior e relacionados , Nova York, NY: Springer, pp. 1–28, doi :10.1007/978-1-4613-9617-8_1, ISBN 978-1-4613-9617-8, recuperado em 22 de novembro de 2023
- ^ 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.
- ^ Wright, Stephen (1997). Métodos de Ponto Interior Primal-Dual . Filadélfia, PA: SIAM. ISBN 978-0-89871-382-4.
- 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. SR 2265882.
- Nocedal, Jorge; Stephen Wright (1999). Otimização Numérica . Nova York, NY: Springer. ISBN 978-0-387-98793-4.
- Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Seção 10.11. Programação Linear: Métodos de Ponto Interior". Numerical Recipes: The Art of Scientific Computing (3ª ed.). Nova York: Cambridge University Press. ISBN 978-0-521-88068-8. Arquivado do original em 11 de agosto de 2011. Recuperado em 12 de agosto de 2011 .