Sucedió así que necesito trabajar con un algoritmo para resolver problemas de QP. El principal problema aquí es que no puedo encontrar ninguna referencia a este algoritmo (al menos ninguna referencia en fuentes en inglés). Hay algo en Wikipedia, pero bastante oscuro. He podido encontrar un par de libros donde se hace referencia a este algoritmo como 'Método de los Puntos Sigulares' (traducción exacta del ruso al inglés), pero Quiero saber si hay un nombre globalmente aceptado para este algoritmo, y tal vez las implementaciones existentes en Matlab, Maple o SciPy .
El algoritmo parece una especie de 'Método Simplex', pero para problemas QP, y siempre converge en un número finito de pasos.
Breve descripción del algoritmo:
Tenemos el siguiente problema QP :
\begin{equation} f(x) \to min, \quad x \in D, \tag{1} \end{equation}
\begin{equation} D = \{ x \in R^n \, | \, Ax \leq b \}, \tag{2} \end{equation}
donde $$ f: R^n \to R, \quad f(x) = \frac{1}{2} <Cx, x> + <c, x> $$ $C \in R(n, n)$ es una matriz simétrica semidefinida positiva, $c \in R^n$ , $A \in R(m, n)$ , $b \in R^m$ .
La notación $<a, b>$ significa producto-punto, $R(m, n)$ es un conjunto de todos los $(m \times n)$ -matrices dimensionales.
A continuación, vamos a definir un análogo de los vértices del simplex sobre el que iteramos en el 'Método Simplex'.
Definición 1. Punto $\hat x$ se llama singular para el problema (1), (2), si existe un conjunto $I \subset \{ 1, \ldots, m \} $ como por ejemplo $\hat x$ es una solución para el siguiente problema:
\begin{equation} f(x) \to min, \quad x \in D_I, \tag{3} \end{equation}
\begin{equation} D_I = \{ x \in R^n \, | \, <a_i, x> = b_i, \, i \in I \} \tag{4} \end{equation}
(casos en los que $I = \emptyset$ y $I = \{ 1, \ldots, m \}$ se incluyen ambos).
Bien, ahora vamos a formular un teorema que arroje algo de luz sobre el algoritmo real.
Teorema 1. Para toda matriz simétrica semidefinida positiva $ C \in R(n, n) $ y cada $c \in R^n$ , $A \in R(m, n)$ y $b \in R^m$ sólo hay un conjunto finito de puntos singulares para el problema (1), (2), y la solución de este problema es su punto singular .
En este paso está claro que podríamos iterar sobre puntos singulares y elegir aquella en la que el valor de la función objetivo sea mínimo, y esa punto singular será la solución.
Por supuesto, el proceso de iteración es bastante complejo. Construye una secuencia de puntos singulares $x^1, x^2, \ldots, x^k$ tal que $ f( x^{i+1} ) < f(x^i) $ . El método del gradiente conjugado con algunas modificaciones para las matrices semidefinidas podría utilizarse para resolver el problema (3), (4) (para las funciones cuadráticas converge en un número finito de pasos).
Podría dar aún más detalles, pero estoy bastante seguro de que en este punto se podría identificar el algoritmo.
Editar:
La idea principal del algoritmo:
Supongamos que tenemos algún punto $x_0 \in D$ .
-
Seleccione las restricciones de (2) que se satisfacen como ecuaciones para $x_0$ . Estas restricciones definen algunas caras $D_0$ de un poliedro descrito por (2).
-
Encuentre $\hat x_0 = min f(x), \, x \in D_0$ .
$\hat x_0$ es la solución para el problema (1), (2) o es posible cambiar a otra cara, y comenzar con el paso 1).
Por cierto, no hay restricciones no negativas en las variables del problema
