Quais são as vantagens / desvantagens dos métodos de pontos interiores sobre o método simplex para otimização linear?

Pelo que entendi, como uma solução para um programa linear sempre ocorre em um vértice de seu conjunto viável poliédrico (se existe uma solução e o valor ótimo da função objetivo é delimitado por baixo, assumindo um problema de minimização), como uma pesquisa no interior da região viável ser melhor? Ele converge mais rápido? Em que circunstâncias seria vantajoso usar o método simplex sobre os métodos de pontos interiores? Um é mais fácil de implementar em um código do que o outro?

Com base na experiência pessoal, eu diria que os métodos simplex são marginalmente mais fáceis de entender como implementar do que os métodos de pontos interiores, com base na experiência pessoal da implementação do método simplex primitivo e de um ponto interior básico no MATLAB como parte de uma aula de programação linear . Os principais obstáculos no primal simplex são garantir que você implementa a Fase I e a Fase II corretamente e também implementa uma regra anticiclagem corretamente. Os principais obstáculos na implementação de um método de ponto interior para programação linear tendem a ser mais sobre como implementar o método iterativo corretamente e dimensionar o parâmetro de barreira de acordo.

Você pode encontrar uma discussão mais completa dos prós e contras de cada algoritmo em um livro sobre programação linear, como Introdução à otimização linear de Bertsimas e Tsitsiklis. ( Isenção de responsabilidade: eu aprendi programação linear com este livro e peguei programação linear no MIT com a esposa de Bertsimas.) Aqui estão alguns dos princípios básicos:

Prós do simplex:

• Dadas variáveis ​​de decisão, geralmente converge em operações com pivôs.$n$$O(n)$$O(n)$
• Aproveita a geometria do problema: visita os vértices do conjunto viável e verifica a otimização de cada vértice visitado. (No simplex primal, o custo reduzido pode ser usado para essa verificação.)
• Bom para pequenos problemas.

Contras de simplex:

• Dadas variáveis ​​de decisão, você sempre pode encontrar uma instância de problema em que o algoritmo requer operações e pivôs para chegar a uma solução.O ( 2 n$n$$O(2^{n})$
• Não é tão bom para problemas grandes, porque as operações de giro se tornam caras. Algoritmos de plano de corte ou algoritmos de geração atrasada de colunas como Dantzig-Wolfe às vezes podem compensar essa falha.

Prós dos métodos de pontos interiores:

• Possui complexidade assintótica no tempo polinomial de , onde L é o número de bits de entrada no algoritmo.$O(n^{3.5}L^2\log{L}\log\log{L})$$L$
• Melhor para problemas grandes e esparsos, porque a álgebra linear necessária para o algoritmo é mais rápida.

Contras dos métodos de pontos internos:

• Não é tão intuitivamente satisfatório porque você está certo, esses métodos não visitam vértices. Eles vagam pela região interior, convergindo para uma solução quando bem-sucedidos.
• Para pequenos problemas, o simplex provavelmente será mais rápido. (Você pode construir casos patológicos, como o cubo Klee-Minty.)

A resposta é fácil. Ambos (métodos de ponto simples e interior) são um campo maduro do ponto de vista algorítmico. Ambos funcionam muito bem na prática. A boa reputação do IPM (métodos de pontos internos) é devida à sua complexidade polinomial no pior dos casos. Esse não é o caso do simplex que possui complexidade combinatória. No entanto, programas lineares combinatórios quase nunca acontecem na prática. Para problemas de escala muito grande, o IP parece ser um pouco mais rápido, mas não é necessária a regra. Na minha opinião, o IP pode ser fácil de entender e implementar, mas com certeza alguém pode discordar, e isso é bom. Agora, no LP, se a solução é única, é definitivamente um vértice (o IP e o Simplex também se saem bem aqui). A solução também pode estar em uma face do poliedro ou em uma aresta. Nesse caso, o vértice adjacente é (ou vértices são) também uma solução (novamente, IP e simplex se saem bem). Então eles são praticamente iguais.