¿Qué clases de programas matemáticos pueden resolverse exactamente o aproximadamente, en tiempo polinómico?

Estoy bastante confundido por la literatura de optimización continua y la literatura de TCS sobre qué tipos de programas matemáticos (continuos) (MP) se pueden resolver de manera eficiente y cuáles no. La comunidad de optimización continua parece afirmar que todos los programas convexos se pueden resolver de manera eficiente, pero creo que su definición de "eficiente" no coincide con la definición de TCS.

Esta pregunta me ha estado molestando mucho en los últimos años, y parece que no puedo encontrar una respuesta clara. Espero que puedan ayudarme a resolver esto de una vez por todas: qué clases de MP se pueden resolver exactamente en tiempo polinómico y por qué medios; ¿Y qué se sabe acerca de la aproximación de la solución óptima de MP que no podemos resolver exactamente en el tiempo polinómico?

A continuación, doy una respuesta incompleta a esta pregunta que también es posiblemente incorrecta en algunos lugares, por lo que espero que puedan verificarme y corregirme en los puntos en los que estoy equivocado. También establece algunas preguntas que no puedo responder.

Todos sabemos que la programación lineal se puede resolver exactamente en tiempo polinómico, ejecutando el método elipsoide o un método de punto interior, y posteriormente ejecutando algún procedimiento de redondeo. La programación lineal incluso se puede resolver en el tiempo polinomial en el número de variables cuando se enfrenta a una familia de LP con una cantidad súper grande de restricciones lineales, siempre que se pueda proporcionar un "oráculo de separación": un algoritmo que, dado un punto , determina si ese punto es factible o genera un hiperplano que separa el punto del poliedro de puntos factibles. Del mismo modo, la programación lineal en el tiempo polinomial en el número de restricciones cuando se enfrenta a una familia de LP con cualquier cantidad súper grande de variables, si se proporciona un algoritmo de separación para los duales de estos LP.

El método elipsoide también puede resolver programas cuadráticos en tiempo polinómico, en caso de que la matriz en la función objetivo sea positiva (semi?) Definida. Sospecho que, al usar el truco del oráculo de separación, en algunos casos también podemos hacer esto si nos enfrentamos a un número increíble de restricciones. ¿Es eso cierto?

Últimamente, la programación semidefinida (SDP) ha ganado mucha popularidad en la comunidad TCS. Uno puede resolverlos con una precisión arbitraria mediante el uso de métodos de punto interior, o el método elipsoide. Creo que los SDP no se pueden resolver exactamente debido al problema de que las raíces cuadradas no se pueden calcular exactamente. (?) ¿Sería correcto si digo que hay un FPTAS para SDP? No he visto eso en ningún lado, así que probablemente eso no sea correcto. ¿Pero por qué?

Podemos resolver LPs exactamente y SDPs con precisión arbitraria. ¿Qué pasa con otras clases de programas cónicos? ¿Podemos resolver programas de cono de segundo orden con una precisión arbitraria, utilizando el método elipsoide? No lo sé.

¿En qué clases de MP podemos usar el método elipsoide? ¿Qué propiedades necesita tal MP para satisfacer una respuesta arbitraria, y qué propiedades adicionales necesitamos para poder obtener una solución exacta en el tiempo polinómico? Las mismas preguntas para los métodos de puntos interiores.

Ah, y finalmente, ¿qué es lo que hace que los optimizadores continuos digan que los programas convexos se pueden resolver de manera eficiente? ¿Es cierto que se puede encontrar una respuesta de precisión arbitraria a un programa convexo en tiempo polinómico? Creo que no, entonces, ¿en qué aspectos difiere su definición de "eficiente" de la nuestra?

Cualquier contribución es apreciada! Gracias por adelantado.

Puedo responder esta parte:

¿Sería correcto si digo que hay un FPTAS para SDP? No he visto eso en ningún lado, así que probablemente eso no sea correcto. ¿Pero por qué?

La afirmación es correcta, pero a menudo no la vemos porque una afirmación más fuerte es válida y es más importante que esta más débil.

Un FPTAS es un algoritmo de tiempo polinómico que, dado un problema y un parámetro de precisión 1 ^k , genera una solución aproximada (1 + 1 / k ).

Pero para SDP, el método elipsoide y el método de punto interior proporcionan algoritmos de tiempo polinomial que, dado un problema y un parámetro de precisión 1 ^k , generan una solución aproximada (1 + 2 ^{- k} ). Tenga en cuenta que el factor de aproximación es mucho mejor que el requerido para un FPTAS.

No sé si todos los problemas convexos están en P, pero puedo responder una pregunta relacionada: la optimización no convexa es NP-hard. Consulte "La programación cuadrática con un valor propio negativo es NP-hard" .