Quais classes de programas matemáticos podem ser resolvidas exatamente ou aproximadamente, em tempo polinomial?

Estou um pouco confuso com a literatura de otimização contínua e a literatura do TCS sobre quais tipos de programas matemáticos (contínuos) (MPs) podem ser resolvidos com eficiência e quais não. A comunidade de otimização contínua parece afirmar que todos os programas convexos podem ser resolvidos com eficiência, mas acredito que sua definição de "eficiente" não coincide com a definição do TCS.

Essa pergunta me incomodou muito nos últimos anos, e não consigo encontrar uma resposta clara. Espero que você possa me ajudar a resolver isso de uma vez por todas: Quais classes de deputados podem ser resolvidas exatamente em tempo polinomial e por quais meios; e o que se sabe sobre a aproximação da solução ideal de MPs que não conseguimos resolver exatamente no tempo polinomial?

Abaixo, dou uma resposta incompleta a esta pergunta que também está possivelmente incorreta em alguns lugares, por isso espero que você possa me verificar e me corrigir nos pontos em que estou errado. Ele também afirma algumas perguntas que não posso responder.

Todos sabemos que a programação linear pode ser resolvida exatamente em tempo polinomial, executando o método elipsóide ou um método de ponto interior e, posteriormente, executando algum procedimento de arredondamento. A programação linear pode até ser resolvida no polinômio do tempo no número de variáveis ​​ao enfrentar uma família de LPs com qualquer quantidade super grande de restrições lineares, desde que se possa fornecer um "oráculo de separação" para ela: um algoritmo que, dado um ponto , determina se esse ponto é viável ou gera um hiperplano que separa o ponto do poliedro de pontos possíveis. Da mesma forma, a programação linear em polinômio de tempo no número de restrições ao enfrentar uma família de LPs com uma quantidade super grande de variáveis, se houver um algoritmo de separação para os duais desses LPs.

O método elipsóide também é capaz de resolver programas quadráticos em tempo polinomial, caso a matriz na função objetivo seja positiva (semi?) Definida. Suspeito que, usando o truque do oráculo de separação, em alguns casos, também possamos fazer isso se estivermos lidando com um número incrível de restrições. Isso é verdade?

Ultimamente a programação semidefinida (SDP) ganhou muita popularidade na comunidade do TCS. Pode-se resolvê-los com precisão arbitrária usando métodos de pontos interiores, ou o método elipsóide. Penso que os SDPs não podem ser resolvidos exatamente devido ao problema de que raízes quadradas não podem ser calculadas exatamente. (?) Seria correto se eu disser que existe um FPTAS para SDP? Eu não vi isso declarado em lugar algum, então provavelmente não está certo. Mas por que?

Podemos resolver exatamente LPs e SDPs com precisão arbitrária. E quanto a outras classes de programas cônicos? Podemos resolver programas de cone de segunda ordem com precisão arbitrária, usando o método elipsóide? Eu não sei.

Em quais classes de deputados podemos usar o método elipsóide? Que propriedades esse MP precisa satisfazer para que uma resposta possa ser dada com precisão arbitrária e que propriedades adicionais precisamos para poder obter uma solução exata em tempo polinomial? Mesmas perguntas para métodos de pontos interiores.

Ah, e finalmente, o que faz com que os otimizadores contínuos digam que os programas convexos podem ser resolvidos com eficiência? É verdade que uma resposta de precisão arbitrária a um programa convexo pode ser encontrada em tempo polinomial? Eu acredito que não, então em que aspectos sua definição de "eficiente" difere da nossa?

Qualquer contribuição é apreciada! Desde já, obrigado.

Eu posso responder a esta parte:

Seria correto se eu disser que existe um FPTAS para SDP? Eu não vi isso declarado em lugar algum, então provavelmente não está certo. Mas por que?

A afirmação está correta, mas geralmente não a vemos porque uma afirmação mais forte é válida e é mais importante do que essa afirmação mais fraca.

Um FPTAS é um algoritmo de tempo polinomial que, dado um problema e um parâmetro de precisão 1 ^k , gera uma solução aproximada (1 + 1 / k ).

Mas para o SDP, o método elipsóide e o método do ponto interior fornecem algoritmos de tempo polinomial que, dados um problema e um parâmetro de precisão 1 ^k , produzem uma solução aproximada (1 + 2 ^{- k} ). Observe que o fator de aproximação é muito melhor do que o necessário para um FPTAS.

Não sei se todos os problemas convexos estão em P, mas posso responder a uma pergunta relacionada: a otimização não-convexa é difícil para NP. Consulte "A programação quadrática com um valor próprio negativo é difícil para NP" .