Resolución de la programación cuadrática con restricciones lineales mediante el descenso de coordenadas

Question

¿Alguien tiene alguna idea sobre cómo resolver el siguiente problema con el Descenso de Coordenadas? \begin{align} \min &\quad \mathbf{x}^{\top}P\mathbf{x} + b^{\top}\mathbf{x}\\ \text{Subject to}& \quad A\mathbf{x} \leq c \end{align}

No quiero utilizar la técnica de la Función de Choque y necesito el Descenso de Coordenadas para poder resolverlo en altas dimensiones.

Answer 1

Suponiendo que $P$ sea semidefinido positivo, su problema es simplemente un QP estándar con restricciones lineales. A menos que muestre algunas peculiaridades en las restricciones lineales, la estructura de $P$ o una dimensión enorme, simplemente cogería cualquier solucionador QP establecido (MOSEK, CPLEX, Gurobi...) o incluso simplemente quadprog en MATLAB.

Los documentos a los que se refiere se refieren a algunas situaciones específicas:

• Tseng et al. considera funciones no suaves y este no es su caso.

• Lin et al. se centran especialmente en la aplicación de SVN, que son problemas realmente enormes. Pero en ese caso resuelven el dual que una QP con restricciones de caja que es de alguna manera más fácil .

En general, yo buscaría algoritmos QP antes de implementar los propios.

Answer 2

Creo que el siguiente documento responde en gran medida a mi pregunta:

Tseng, Paul, y Sangwoon Yun. "Un método de descenso de gradiente por coordenadas para la minimización separable no lisa". Programación matemática 117.1-2 (2009): 387-423.