¿Problemas de optimización de dificultad NP para los que las aproximaciones serían inútiles?

Question

Los problemas de optimización con los que estoy familiarizado (por ejemplo, el problema del viajante de comercio) son tales que las soluciones aproximadas a estos problemas siguen siendo bastante útiles.

Sin embargo, me pregunto si hay problemas de optimización en el mundo real para los que las soluciones aproximadas son inútiles. O, dicho de otro modo, ¿existen problemas de optimización en el mundo real para los que la sólo ¿la solución que es mejor/más útil que cualquier otra es la solución óptima, y todas las demás son igualmente malas/inútiles?

Answer 1

Después de pensarlo un poco creo que los problemas en PPAD pueden ser interesantes para ti: http://en.wikipedia.org/wiki/PPAD_(complejidad)

Hay algunos problemas completos de PPAD: Equilibrios de Nash, Búsqueda de puntos fijos de Brouwer y Fin de línea. Creo que se puede ver el hilo común entre todos ellos: sabemos que el objeto existe (a diferencia de lo que ocurre en SAT o en la versión de decisión de TSP). La cuestión de aproximar un equilibrio de Nash (digamos un equilibrio mixto en un juego simétrico) es que cualquier solución que no sea el equilibrio exacto dará lugar a un juego continuado o posiblemente incluso a una pérdida si se procede desde el punto de equilibrio aproximado: la mejor estrategia aproximada. Así que, a menos que se pueda hacer que el límite de aproximación sea increíblemente pequeño, la perspectiva de los equilibrios de Nash aproximados parece dudosa. También cabe preguntarse si hay problemas en los que la existencia de algoritmos de aproximación implica algo sobre toda una clase de problemas....

Supongamos que tenemos un $N-$ juego limpio de jugadores con funciones de utilidad simétricas. Sea el espacio de estrategias para el jugador $i$ sea $D_i$ . Estrategias mixtas para el jugador $i$ puede consistir en subconjuntos de $D_i$ . En un $N-$ juego del jugador llamar a un perfil de estrategia $\vec{V} = \{v_i\}_{i=1}^N$ un $\epsilon-$ Equilibrio de Nash aproximado si para todos los jugadores $i \in \{1, \ldots, N\}$ y todas las acciones $a \in v_i$ $$\mathbb{E}\left[ u_i(a | \vec{X})\right] \geq \mathbb{E}\left[ u_i(b | \vec{X})\right] - \epsilon, \; \forall b \in D_i$$ donde $u_i$ es la función de utilidad del jugador $i$ y la expectativa es sobre los pesos que los jugadores restantes ponen en sus estrategias mixtas. Muchos juegos y, de hecho, muchos escenarios del mundo real resultan tener equilibrios mixtos, pero ese no es el objetivo de esta respuesta.

Actualmente el valor más pequeño conocido para el que existe un tiempo parcialmente polinómico $\epsilon-$ aproximación (exponencial en la precisión de la aproximación) es $\approx .333$ para funciones de utilidad normalizadas, es decir $\operatorname{Ran}(u_i) = \left[ 0,1 \right]$ . Además, si existiera un algoritmo de tiempo totalmente polinómico, es decir $O((1/\epsilon)^d P(N))$ más bien que $O(N^{1/\epsilon})$ entonces $PPAD \subset P$ que es un gran problema. Así que, tal y como están las cosas, o las aproximaciones son malas o se produce algún colapso de la jerarquía, e incluso entonces la utilidad de la aproximación es muy cuestionable.

Si sigues convencido de que los equilibrios aproximados de Nash no se ajustan del todo a la realidad, te sugiero que mires el End-of-the-Line (explicado en el artículo de la wiki que he adjuntado).

Para más información sobre este maravilloso tema, sugiero el gran libro de Noam Nisan (y compañía) Algorithmic Game Theory.

Answer 2

Podemos tomar como ejemplo el problema de la regresión lineal dispersa. Dada una variable de respuesta $Y \in \mathbb{R}^n$ y una matriz de diseño $X\in \mathcal{M}_{n,p}(\mathbb{R})$ se quiere estimar estadísticamente un escaso vector $\beta \mathbb{R}^n $ tal que $Y=X\beta+\varepsilon$ donde $\varepsilon$ es un ruido gaussiano isotrópico.

Para mejorar la dispersión, se ofrece un estimador natural que penaliza los mínimos cuadrados con un $\ell_0$ plazo : $$\hat{\beta} \in \operatorname{argmin}{\{ \left \| Y-X\beta \right \|_2^2+\lambda \left \| \beta \right \|_0\}} $$ donde $\left \| \beta \right \|_0$ es el $\ell_0$ pseudonorma de $\beta$ (es decir, el número de coeficientes no nulos en $\beta$ ) y $\lambda >0$ es un parámetro de ajuste fijado de antemano. Este procedimiento es estadísticamente bastante eficiente, pero desgraciadamente es NP-difícil.

Una simple relajación del problema se obtiene sustituyendo el $\ell_0$ término por un $\ell_1$ pena: $$\hat{\beta} \in \operatorname{argmin}{\{ \left \| Y-X\beta \right \|_2^2+\lambda \left \| \beta \right \|_1\}} $$ que se conoce como lazo o búsqueda de la base . Este problema relajado es convexo, se puede resolver en tiempo polinómico y mejora la dispersión de la solución. En los últimos años se han realizado muchos trabajos para demostrar la eficacia estadística de esta relajación (véase, por ejemplo, el este artículo de Candès & Plan).

Sin embargo, como se puede ver en este En el documento de trabajo de Lin, Foster y Ungar, la relajación puede, en ciertos casos (bastante raros), dar resultados infinitamente peores que el problema NP-duro. En otras palabras, La aproximación del problema de optimización puede conducir a soluciones inútiles .

• Candès, E. J., y Plan, Y. (2009). Near-ideal model selection by 1 minimization. The Annals of Statistics, 37(5A), 2145-2177.

• D. Lin, D. P. Foster y L. H. Ungar. Una comparación de la relación de riesgo de las regresiones penalizadas 0 y 1. Informe técnico de report, University of Pennsylvania.