¿Qué es exactamente un "solucionador" en la optimización?

Question

Estoy realmente confundido por el uso del solucionador en la optimización computacional. He mirado alrededor durante un mes de vez en cuando para ver si puedo tener una buena idea de lo que este término significa, pero todavía no tengo una buena comprensión de él.

Parece que, si quisiera resolver un problema de optimización en el aprendizaje de la máquina o en cualquier otro lugar, me referiría al procedimiento computacional exacto como un algoritmo en lugar de un solucionador. Por ejemplo, si tuviera un programa cuadrático, usaría la función Quadprog de MATLAB para resolver el QP.

Personalmente no me referiría a la función Quadprog como un solucionador de QP, porque es sólo una función de MATLAB, o un script. No me referiría al algoritmo exacto detrás de Quadprog como un solucionador QP, no me importa si es el descenso de gradiente, el método de punto interior, Newton Raphson... todos son algoritmos para mí. Finalmente, no me referiría a MATLAB como solucionador de QP porque ese no es el único propósito de MATLAB. Así que parece que la palabra "solucionador" falta en mi vocabulario diario a pesar de tener que trabajar rutinariamente con la optimización, esto me confunde bastante, simplemente siento que no estoy al día con la jerga.

Así que por mi razonamiento, los algoritmos y MATLAB no son solucionadores. Pero supongamos que he descargado algunos programas como Gurobi o YALMIP para resolver problemas de optimización, ¿se llaman solucionadores? A menudo he oído a la gente referirse a qué "solucionador" estás usando en el mismo tono que qué "software" estás usando. ¿Qué diferencia los softwares de optimización de los solucionadores?

Sé que suena como una pregunta muy rudimentaria, pero sólo he hecho la optimización en MATLAB.

Answer 1

A solucionador es una rutina para encontrar respuestas numéricas exactas para sistemas determinados. Por ejemplo, cuando se utiliza Newton-Raphson para encontrar la(s) raíz(es). Cuando un sistema es sobredeterminado entonces se suelen utilizar soluciones aproximadas, por ejemplo, la regresión. Por lo general, no se habla de la regresión como un solucionador, aunque, como es de esperar, el lenguaje puede ser mal utilizado, y muchas rutinas que son aproximadas se denominan vagamente solucionadores . Por ejemplo, el CUTEr El paquete de software de optimización contiene algoritmos, al menos algunos de los cuales son para sistemas sobredeterminados, y otros son solucionadores, por lo que resulta fácil decir que estoy descargando un "solucionador". Tanto los solucionadores como los métodos de regresión son ejemplos de métodos de optimización.

Answer 2

Sugiero que un solucionador lo sea:

• un paquete de software
• que incorpora uno o más algoritmos
• para encontrar soluciones a una o varias clases del problema

Las clases de problemas son parte de ello. Es un solucionador X.

Así que

• Yo llamaría a Gurobi "un solucionador MIP/LP" .
• Y yo diría "Matlab incorpora un solucionador QP, que expone a través de la función Quadprog". En este caso, el "solucionador QP" real puede o no existir como un producto independiente.
• Concorde es un solucionador de TSP
• Concorde incorpora QSopt, que es un solucionador de LP

Creo que este uso está en consonancia con (por ejemplo) el Documentación de JuMP

JuMP es un lenguaje de modelado específico para la optimización matemática integrado en Julia. Actualmente es compatible con una serie de solucionadores comerciales y de código abierto (véase más abajo) para diversas clases de problemas, como la programación lineal, la programación entera mixta, la programación cónica de segundo orden, la programación semidefinida y la programación no lineal.

Esta es una lista de cosas que JuMP llama a los solucionadores . Ninguno de ellos es un algoritmo, todos son programas específicos

Answer 3

Suelo escuchar que "solucionador" se utiliza para describir el software, lo que significa que se aplica a un aplicación de un algoritmo. Por ejemplo, esto parece aplicarse a la mayoría de los Preguntas de SciComp.SE etiquetadas como solver .

En general, el término parece reservarse para los problemas matemáticos con una "solución bien definida". Una solución única sería lo suficientemente "bien definida", como señala Sycorax en los comentarios. (El Gurobi parecen ser para problemas de esta clase; por si sirve de algo, Gurobi parece un suite o biblioteca de los solucionadores para mí).

Pero no creo que sea único necesario . Por ejemplo, tanto los problemas de optimización local como los globales pueden tener soluciones bien definidas pero no únicas (por ejemplo, la función $f[x]=\sin[\pi x]^2$ tiene un mínimo global $f[k]=0$ para $k\in\mathbb{Z}$ ).

No estoy de acuerdo con esta respuesta que parece hablar de "solucionadores de sistemas de ecuaciones" más que de "solucionadores de optimización". Por ejemplo, en los mínimos cuadrados lineales, el álgebra lineal problema está sobredeterminado, pero el optimización El problema es convexo con una solución única (en casos no degenerados). Obsérvese también que el Página "solver" de Wikipedia vinculado en esa respuesta enumera "Problemas de optimización lineal y no lineal, problemas del camino más corto, problemas del árbol de extensión mínima" entre sus ejemplos.

---

En respuesta al comentario, aclararé lo que quiero decir en el caso de la "regresión".

Dada una función $F:\mathbb{R}^n\to\mathbb{R}^m$ , a solución del sistema de ecuaciones especificado por $$F[x]=0$$ es un vector $x\in\mathbb{R}^n$ de manera que todos los $m$ componentes de $F[x]$ son cero. Dependiendo de la función $F$ puede no haber soluciones, una única solución, o muchas soluciones (normalmente infinitas), dependiendo de la dimensión del espacio nulo de $F$ . En el caso de que $F$ es lineal, es decir $F[x]=Ax-b$ para algunos $A\in\mathbb{R}^{m\times{n}},b\in\mathbb{R}^m$ entonces no puede existir ninguna solución a menos que $m\leq\mathrm{rank}[A]\leq n$ .

Por otro lado, para un determinado función objetivo $E_F:\mathbb{R}^n\to\mathbb{R}$ y conjunto factible $\Omega_F\subset\mathbb{R}^n$ que dependen de $F$ , a solución al problema de optimización especificado por $$\epsilon=\min_{x\in\Omega_F}E_F[x]$$ es un vector $x\in\Omega_F$ tal que $E_F[x]\leq E_F[y]$ para todos $y\in\Omega_F$ .

En la optimización por "mínimos cuadrados", la función $E_F$ es una suma de cuadrados. Los dos problemas de mínimos cuadrados más comunes son 1) $$E_F[x]=\|F[x]\|^2 \text{ , } \Omega_F=\mathbb{R}^n$$ donde $F$ corresponde a un sobredeterminado sistema de ecuaciones, y 2) $$E_F[x]=\|x\|^2 \text{ , } \Omega_F=\{y\in\mathbb{R}^n\ \mid F[y]=0\}$$ donde $F$ corresponde a un sub-determinado sistema de ecuaciones.

Las plataformas comunes de álgebra lineal, como Matlab, pueden combinar estos tres problemas matemáticos distintos "bajo el capó" en una función de conveniencia como linsolve() . Sin embargo, las bibliotecas de bajo nivel ("solver"), como LAPACK No lo hará.

Dos últimas aclaraciones:

• Un "solucionador" corresponderá normalmente a una solución bien definida pero abstracta matemáticas problema. Por ejemplo, la "inferencia estadística" o la "predicción acertada" no son problemas de este tipo. En el lenguaje de Ciencia computacional , tú verificar un solucionador, usted validar un modelo.

  • Las ideas de único/no único o exacto/aproximado no están del todo claras. Digamos que nos centramos sólo en el caso de los sistemas cuadrados de ecuaciones, lo que debería eliminar la mayoría de los puntos de controversia. En este campo, es habitual hablar de "solucionadores iterativos" (por ejemplo, ~600.000 visitas en Google Scholar ). Por lo tanto, el de facto La definición de "solucionador" debe incluir esta clase de algoritmos, que por definición son esencialmente inexactos.

Answer 4

Creo que la palabra solver viene de la funcionalidad similar de resolver alguna solución factible, ya que existe en el complemento Solver de Excel la opción "valor de", que trata de encontrar $X$ tal que $f(X) = Y$ y algunas restricciones más de igualdad y desigualdad. En mathematica la función resolver hace lo mismo.

El inglés (especialmente gracias a los medios de comunicación de EE.UU.) tiene una tendencia a evolucionar copiando errores como "cracker" ~ "hacker". Solver podría ser similar. Es lo suficientemente abstracto como para ocultar los nombres de los algoritmos de optimización reales. A menudo las implementaciones reales no son tan puramente un algoritmo.