Résolution d'un problème des moindres carrés avec des contraintes linéaires en Python

12

J'ai besoin de résoudre

minxAxb22,s.t.ixi=1,xi0,i.

Je pense que c'est un problème quadratique qui devrait être résolu avec CVXOPT , mais je ne sais pas comment.

tillsten
la source
J'espère que cette question n'est pas trop spécifique pour compsci.
tillsten
Geoff Oxberry: Juste une curiosité, mais pourquoi avez-vous édité la partie linéaire? Je pense que c'est une partie assez impuissante de la description du problème, la solution serait tout à fait différente pour une optimisation des moindres carrés non linéaire.
tillsten
Btw, les autres modifications sont super!
tillsten
Vous pouvez facilement résoudre ce problème par votre propre code de manière très efficace. Pas besoin de CVXOPT.
Royi

Réponses:

11

J'ai écrit une réponse complète (en dessous de la ligne) avant de découvrir CVXPY , qui (comme CVX pour MATLAB) fait tout le travail difficile pour vous et a un exemple très court presque identique au vôtre ici . Il vous suffit de remplacer la ligne concernée par

 p = program(minimize(norm2(A*x-b)),[equals(sum(x),1),geq(x,0)])

Mon ancienne réponse, le faire de la manière la plus difficile avec CVXOPT:

Suite à la suggestion de Geoff de cadrer votre fonction objectif donne

Axb22=xTATbT,Axb=xTATAxbTAxxTAbbTb

Bien sûr, tous les termes sont des scalaires, vous pouvez donc transposer le troisième et supprimer le dernier (car cela ne dépend pas de et ne changera donc pas quel vous donne un minimum, bien que vous deviez l'ajouter à nouveau en après résolution afin d'obtenir la valeur correcte de votre objectif) pour obtenir Ceci (y compris vos contraintes) a la forme d'un programme quadratique, comme indiqué dans la documentation CVXOPT ici , où il y a aussi un exemple de code pour résoudre un tel problème.xx

xTATAxbT(A+AT)x
David Ketcheson
la source
4

Au lieu du problème que vous avez résolu, résolvez

minxAxb22,s.t.ixi=1,xi0,i.

Ce problème est un problème d'optimisation différentiable, convexe et non linéaire qui peut être résolu dans CVXOPT, IPOPT ou tout autre solveur d'optimisation convexe.

Geoff Oxberry
la source