Programmation quadratique lorsque la matrice n'est pas définie positive

8

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

Le package R ne quadprogsemble pouvoir résoudre le problème de programmation quadratique que lorsque la matrice est définie positive.D

Cependant, il existe un cas où la matrice n'est pas définie positive. tel queD

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

Comment puis-je résoudre ce genre de problème?

r optimization user67275
la source
Le problème pourrait être lié au fait que si le quadratique n'est pas positif défini, il n'a pas de minimum local. Dans ce cas, il devrait toujours y avoir un minimum global, car la région est délimitée.
Glen_b -Reinstate Monica
1
Si n'est pas PSD, le problème n'est pas convexe. Tout algorithme de descente de gradient vous atterrira sur un minimum local, plus ou moins en fonction de son point de départ. Vous devrez peut-être trouver une heuristique pour décider quand arrêter la recherche. D
user603
4
Il n'est pas si difficile de décider sur quel segment de la frontière se situe le minimum. Puis, étant donné cette contrainte, il est assez facile de le présenter comme un problème qui a un minimum local ... mais la suggestion de @ user603 d'utiliser un algorithme de minimisation standard comme la descente de gradient peut être très utile comme approche générale.
Glen_b -Reinstate Monica

Réponses:

4

Il existe des routines d'optimisation spécifiquement pour l'optimisation locale ou globale des problèmes de programmation quadratique, que la fonction objectif soit convexe ou non.

BARON est un optimiseur global à usage général qui peut gérer et tirer parti des problèmes de programmation quadratique, convexe ou non.

CPLEX possède un solveur de programmation quadratique qui peut être appelé avec solutiontarget = 2 pour trouver un optimum local ou = 3 pour trouver un optimum global. Dans MATLAB, cela peut être invoqué avec cplexqp.

Des optimiseurs locaux à usage général qui peuvent gérer des contraintes linéaires peuvent également être utilisés pour trouver un optimum local. Un exemple dans R est https://cran.r-project.org/web/packages/trust/trust.pdf . Les optimiseurs pour R sont répertoriés sur https://cran.r-project.org/web/views/Optimization.html .

Dans MATLAB, la fonction quadprog de la boîte à outils d'optimisation peut être utilisée pour trouver un optimum local.

Dans Julia, il existe une variété d'optimiseurs disponibles.

«N'importe quel» algorithme de descente de gradient peut ne pas vous amener sur quoi que ce soit, sans parler des contraintes. Utilisez un package développé par quelqu'un qui sait ce qu'il fait.

L'exemple de problème fourni est facilement résolu en une optimalité globale prouvable. Peut-être qu'avec le passage de plus de 2 ans, il n'est plus nécessaire, ou peut-être un exemple qu'il n'a jamais été, mais en tout cas, l'optimum global est à x = 0,321429, y = 0,535714

Mark L. Stone
la source
1
+1. Les méthodes de multiplication de Lagrange pour résoudre ces problèmes sont systématiquement enseignées dans les classes de calcul de deuxième année. Avec eux, on obtient facilement et (qui est atteint le long de la frontière ). x=9/28y=15/283x+y=3/2
whuber
1

Vous pouvez construire une solution de contournement à l'aide nearPDdu Matrixpaquet comme ceci:
nearPD(D)$mat.

nearPD calcule la matrice définie positive la plus proche.

vonjd
la source
2
+1 car il s'agit d'une solution approximative relativement simple . (Je ne me souviens pas avoir vu cette question, sinon je l'aurais moi-même donnée dans un commentaire.) Cela dit, on met essentiellement les valeurs propres négatives à zéro lors de l'utilisation de cette technique, puis reconstruisez la matrice d'origine; si les modes de variation correspondants sont significatifs, cette approximation peut être gravement erronée.
usεr11852
3
D'accord avec la dernière phrase du commentaire précédent. C'est une excellente technique à utiliser tant que vous ne vous souciez pas du tout de savoir si votre réponse est correcte, ou même dans le bon stade, la ville ou l'État. Si votre matrice objectif "Hessian" est dans la "tolérance" loin d'être définie positive, cette approche pourrait en fait être raisonnable, sinon, non.
Mark L. Stone