Considere um problema de otimização convexa no formato
onde são funções convexas. Sem perda de generalidade, podemos assumir que é linear.
Nesterov e Nemirovskii mencionam em seu livro "Algoritmos polinomiais de pontos interiores em programação convexa" que existe um algoritmo capaz de resolver qualquer programa convexo em tempo polinomial no sentido a seguir. Queremos ter uma solução com uma precisão relativa ao custo de cálculos dos valores dos valores e cálculos dos subgradientes. Então, para o método elipsóide, alega-se que
À primeira vista, isso parece implicar que um problema de otimização convexa pode ser resolvido em tempo polinomial usando o método elipsóide (vamos assumir por simplicidade que os oráculos para calcular os valores e os subgradientes requerem tempo para a classe considerada problemas de otimização convexos).
No entanto, eu não entendo totalmente se as expressões dependem de alguma forma das funções , por exemplo, de seus hessianos ou não. Nesse caso, a complexidade pode ter uma explosão exponencial devido às propriedades de curvatura das funções. Além disso, afirma-se misteriosamente que "o método elipsóide não funciona bem na prática". Parece não haver consenso na internet se a resposta à minha pergunta é afirmativa ou negativa; veja, por exemplo, esta discussão no MathOverflow.
Pesquisei todos os livros sobre otimização convexa que encontrei e tive a impressão de que esse realmente depende do problema, mas não consegui encontrar nenhuma confirmação clara dessa suposição. Portanto, minha única esperança é perguntar diretamente às pessoas que estão pesquisando neste campo.
Métodos de pontos interiores que foram desenvolvidos mais tarde parecem explicar explicitamente a curvatura usando a noção de barreiras auto-concordantes. Mas quando as pessoas dizem que esses métodos são eficientes na prática, geralmente não o especificam no nível de complexidade.
fonte
Respostas:
Em 1998, Michel X. Goemans fez uma palestra no ICM, na qual abordou esta questão: "Programas semidefinidos podem ser resolvidos (ou mais precisamente, aproximados) em tempo polinomial, dentro de qualquer precisão específica, pelo algoritmo elipsóide ou de forma mais eficiente algoritmos de ponto interior ... Os algoritmos acima produzem uma solução estritamente viável (ou ligeiramente inviável para algumas versões do algoritmo elipsóide) e, de fato, o problema de decidir se um programa semidefinido é viável (exatamente) ainda está aberto. Um caso especial de viabilidade de programação semidefinida é o problema da soma da raiz quadrada. A complexidade desse problema ainda está aberta. " http://garden.irmacs.sfu.ca/op/complexity_of_square_root_sum
Em 1976, Ron Graham, Michael Garey e David Johnson não conseguiram mostrar alguns problemas de otimização geométrica, como se o Problema do Vendedor Viajante Euclidiano é NP-completo (eles só podem mostrar que o problema é NP-difícil), a razão é que eles não poderiam mostre se o problema da soma da raiz quadrada é solucionável no tempo polinomial ou não. https://rjlipton.wordpress.com/2009/03/04/ron-graham-gives-a-talk/
O problema da soma da raiz quadrada é um problema aberto há muito tempo, que confunde estudiosos da geometria computacional, otimização, complexidade computacional, teoria dos jogos e algumas outras áreas, pois em algum momento elas descobrem que o principal obstáculo para seus problemas é lidar com elas. o problema da soma da raiz quadrada.
O progresso mais notável em relação a esse problema é de Eric Allender e seus coautores, em 2003, eles mostraram que esse problema está no 4º nível da Hierarquia de Contagem. http://ftp.cs.rutgers.edu/pub/allender/slp.pdf
Portanto, com base nos fatos acima, não é possível resolver o problema de otimização convexa no tempo polinomial (verdadeiro) com o método Ellipsoid e o método Point Interior.
A grande notação O é medir o tempo de execução do algoritmo na pior das hipóteses. No entanto, na prática, o pior caso pode ser um evento muito raro, por isso você não pode usá-lo para medir o desempenho prático.
fonte