Proyección de un punto sobre un poliedro convexo

Question

Sea $x_0 \in \mathbb{R}^n$ et $A \in \mathbb{R}^{n \times n}$ se dará. Definir el conjunto $S$ como $$ S \triangleq \{x \in \mathbb{R}^n: A x \leq 1\}. $$

Quiero calcular la proyección de $x_0$ en $S$ es decir, el punto más cercano a $x_0$ en $S$ . ¿Hay alguna forma eficaz de hacerlo? Por supuesto, esto se puede formular como un problema cuadrático, pero si quiero utilizar el descenso por gradiente para resolver esto necesito el paso de proyecciones como una subrutina. Por ahora estoy tratando de derivar una expresión de forma cerrada, pero parece inútil.

Answer 1

Como se ha mencionado en otras respuestas y comentarios, el problema que tienes que resolver es un QP fuertemente convexo con restricciones de desigualdad:

$$ \begin{aligned} \mathrm{minimize}\ &\tfrac{1}{2}\|x\|^2_2 \\ \mathrm{subject\ to}\ & Ax \leq b. \end{aligned} $$

Hay pocas posibilidades de que pueda utilizar algún método directo aquí (esta posibilidad se discute ici ), por lo que debe recurrir a métodos iterativos (y si necesita esta operación en un exterior rutina iterativa, obtendrá un algoritmo doblemente iterativo).

Hay muchos métodos iterativos que se pueden utilizar para resolver este tipo de problemas. Muchos de ellos se basarán en una proyección: tenga en cuenta que esto será tan simple como proyectar sobre el ortante no negativo (que se puede hacer en forma cerrada) y no en el propio poliedro (que, por supuesto, es el objetivo final).

En método de gradiente proximal rápido es posiblemente la opción más sencilla. En este caso se aplicarían este tipo de algoritmos a los doble de su problema original, que dice

$$ \begin{aligned} \mathrm{minimize}\ &\tfrac{1}{2}\|A^\top y\|^2_2 + \langle b,y \rangle \\ \mathrm{subject\ to}\ & y \geq 0 \end{aligned} $$

(comprueba que todos los signos del problema anterior son correctos). De hecho, el PGM dual (rápido) en este caso es precisamente el método del gradiente proyectado dual (rápido). Es el método más sencillo que puedo ver: sólo productos matriz-vector por $A$ et $A^\top$ aparte de las proyecciones triviales sobre el ortante no negativo y las sumas de vectores.

Alternativamente, puede aplicar el algoritmo de división Douglas-Rachford al dual, que es el método de los multiplicadores en sentido alterno (ADMM). En este caso, probablemente sería necesario resolver sistemas lineales a lo largo de las iteraciones, ya sea con un método directo o con algún procedimiento iterativo (como los métodos de subespacios de Krylov), dependiendo de la forma/estructura de $A$ .

Además, los métodos de conjunto activo y de punto interior también son opciones, dependiendo del tamaño de los problemas que esté tratando (véase también la respuesta superior a esta pregunta similar para ello).

En realidad, no hay una respuesta definitiva: el enfoque más adecuado depende siempre de la estructura concreta del problema y de la precisión de la solución que se necesite. Sin embargo, los métodos que he sugerido más arriba son generales

Answer 2

Se trata de un problema de programación cuadrática : minimizar $(x - x_0)^T (x - x_0)$ sujeto a $A x \le 1$ . La forma cuadrática es definida positiva.

EDIT: También puede observar que cualquier problema de programación cuadrática cuya forma cuadrática es definida positiva es equivalente a su problema por un cambio de variables (diagonalizar la forma cuadrática). Así que realmente no hay nada especial aquí.

Se conocen algoritmos eficientes para resolver problemas de programación cuadrática con formas cuadráticas definidas positivas: véase el enlace de Wikipedia. Programas como Maple y Cplex tienen implementaciones de dichos algoritmos.