Programación cuadrática cuando la matriz no es positiva definida

8

http://cran.r-project.org/web/packages/quadprog/quadprog.pdf

El paquete R quadprogparece ser capaz de resolver el problema de programación cuadrática solo cuando la matrizD Es positivo definitivo.

Sin embargo, hay un caso cuando la matriz DNo es positivo definido. como

min(x2+y2−6xy)subject tox+y≤1,3x+y≤1.5,x,y≥0.

¿Cómo puedo resolver este tipo de problema?

r optimization usuario67275
fuente
El problema podría estar relacionado con el hecho de que si la cuadrática no es positiva definida, no tiene un mínimo local. En este caso, todavía debería haber un mínimo global, ya que la región está limitada.
Glen_b -Reinstate a Monica el
1
Si D no es PSD, entonces el problema no es convexo. Cualquier algoritmo de descenso de gradiente lo llevará a un mínimo local, más o menos dependiendo de su punto de partida. Es posible que tenga que encontrar una heurística para decidir cuándo detener la búsqueda.
user603
44
No es tan difícil decidir en qué segmento del límite se encuentra el mínimo. Luego, dada esa restricción, es bastante fácil considerarlo como un problema que tiene un mínimo local ... pero la sugerencia de @ user603 de usar un algoritmo de minimización estándar como el descenso de gradiente puede ser bastante útil como enfoque general.
Glen_b -Reinstate a Monica el

Respuestas:

4

Existen rutinas de optimización específicamente para la optimización local o global de problemas de programación cuadrática, ya sea que la función objetivo sea convexa o no.

BARON es un optimizador global de propósito general que puede manejar y aprovechar problemas de programación cuadrática, convexos o no.

CPLEX tiene un solucionador de programación cuadrática que se puede invocar con solutiontarget = 2 para encontrar un óptimo local o = 3 para encontrar un óptimo global. En MATLAB, eso se puede invocar con cplexqp.

Los optimizadores locales de uso general que pueden manejar restricciones lineales también se pueden utilizar para encontrar un óptimo local. Un ejemplo en R es https://cran.r-project.org/web/packages/trust/trust.pdf . Los optimizadores para R se enumeran en https://cran.r-project.org/web/views/Optimization.html .

En MATLAB, la función quadprog en Optimization Toolbox se puede usar para encontrar un óptimo local.

En Julia, hay una variedad de optimizadores disponibles.

"Algún" algoritmo de descenso de gradiente podría no llevarte a nada, y mucho menos lidiar con restricciones. Use un paquete desarrollado por alguien que sepa lo que está haciendo.

El problema de ejemplo proporcionado se resuelve fácilmente con una optimización global demostrable. Quizás con el paso de más de 2 años ya no sea necesario, o tal vez sea un ejemplo que nunca fue, pero en cualquier caso, el óptimo global está en x = 0.321429, y = 0.535714

Mark L. Stone
fuente
1
+1. Los métodos multiplicadores de Lagrange para resolver estos problemas se enseñan de manera rutinaria en las clases de Cálculo de segundo año. Con ellos, uno obtiene fácilmente e (que se alcanza a lo largo del límite ). x=9/28y=15/283x+y=3/2
whuber
1

Se puede construir una solución mediante el uso nearPDdel Matrixpaquete de este modo:
nearPD(D)$mat.

nearPD calcula la matriz definida positiva más cercana.

vonjd
fuente
2
+1 porque es una solución aproximada relativamente sencilla . (No recuerdo haber visto esta pregunta; de lo contrario, la habría hecho yo mismo en un comentario). Dicho esto, uno esencialmente establece los valores propios negativos a cero cuando se usa esta técnica y luego se reconstruye la matriz original; Si los modos de variación correspondientes son significativos, esta aproximación puede ser seriamente defectuosa.
usεr11852
3
De acuerdo con la última oración en el comentario anterior. Esta es una técnica excelente para usar siempre y cuando no le importe en lo más mínimo si su respuesta es correcta, o incluso en el estadio, ciudad o estado correcto. Si su matriz "Hesiana" objetiva está dentro de la "tolerancia" lejos de ser positiva definida, este enfoque podría ser razonable, de lo contrario, no lo sería.
Mark L. Stone