Por que os métodos de pontos interiores são difíceis de aquecer?

10

Costumo encontrar o ditado geral de que métodos de pontos interiores são difíceis de aquecer. Existe uma explicação intuitiva por trás desse conselho? Existem situações em que se pode esperar benefícios com o início quente em um método de ponto interior? Alguém pode recomendar algumas referências úteis sobre o assunto?

optimization constrained-optimization Christopher Johnson
fonte

Respostas:

11

Os métodos de pontos interiores funcionam seguindo o caminho central para uma solução ideal. Quando você altera a função objetivo, a solução ideal da versão anterior do problema está longe do caminho central para o novo problema; portanto, são necessárias várias iterações para retornar ao caminho central e, além disso, deve retornar a um local bem centralizado. solução. Então você precisa trabalhar no caminho para uma nova solução ideal. Você também pode iniciar o método do ponto interior a partir de um ponto arbitrário.

Em comparação, o método simplex (primal ou duplo) move-se de vértice para vértice do conjunto viável. No caso típico, uma mudança razoavelmente pequena no objetivo resultará em uma nova solução ideal que está apenas a alguns giros simples.

... adicionado à explicação intuitiva acima para fornecer mais detalhes ...

Na prática computacional, a experiência simplesmente não demonstrou nenhum benefício substancial em métodos de ponto interior primitivo-duplo quente. Não é um recurso de códigos amplamente usados ​​como CPLEX e Gurobi (as empresas que produzem esses pacotes adicionariam esse recurso, se valesse a pena), e há relativamente poucos artigos discutindo estratégias para métodos de pontos interiores iniciais quentes .

Duas referências que recomendo são:

EA Yildirim e S. Wright. Estratégias de inicialização a quente em métodos de ponto interior para programação linear. Jornal SIAM on Optimization 12: 782-810, 2002. Este artigo fornece alguns bons limites teóricos sobre algumas estratégias de partida quente. Veja http://pages.cs.wisc.edu/~swright/papers/YilW02a.pdf

Um artigo posterior, co-autor de Yildirim, fornece alguns resultados computacionais, mas os autores admitem que a partida a frio é geralmente mais rápida em seus testes do que a partida a quente:

E. John e EA Yildirim. Implementação de estratégias de arranque a quente em métodos de ponto interior para programação linear em dimensão fixa. Otimização Computacional e Aplicações. 41: 151-183, 2008. Ver http://link.springer.com/article/10.1007/s10589-007-9096-y

Brian Borchers
fonte
Devo dizer que sinto que sua explicação está um pouco ausente. Para um problema que está um pouco mal condicionado, encontrar um ponto viável já é um problema por si só e a maioria dos métodos usa os métodos da "Fase I" para encontrar esse primeiro ponto possível. Ainda não está claro para mim o motivo pelo qual você não pode usar um ponto viável para pelo menos pular essa fase, se não para realmente garantir o sucesso do método.
Olamundo
Na verdade, a maioria das implementações de métodos de pontos interiores primários e duplos usa um ponto de partida inviável (com relação às restrições de igualdade) e trabalha simultaneamente em viabilidade e otimização. Não existe uma fase separada I.
Brian Borchers