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

J'ai besoin de résoudre

\begin{aligned} min_{x} ‖ A x - b ‖_{2}^{2}, \\ s . t . & \sum_{i} x_{i} = 1, \\ x_{i} \geq 0, \forall i . \end{aligned}

$\begin{alignat}{1} & \min_{x}\|Ax - b\|^2_{2}, \\ \mathrm{s.t.} & \quad\sum_{i}x_{i} = 1, \\ & \quad x_{i} \geq 0, \quad \forall{i}. \end{alignat}$

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

optimization python convex-optimization least-squares quadratic-programming 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:

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

‖ A x - b ‖_{2}^{2} = ⟨ x^{T} A^{T} - b^{T}, A x - b ⟩ = x^{T} A^{T} A x - b^{T} A x - x^{T} A b - b^{T} b

$\|Ax-b\|^2_2 = \langle x^TA^T - b^T,Ax-b\rangle = x^TA^TAx - b^TAx - x^TAb - b^Tb$

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. $x$ $x$

x^{T} A^{T} A x - b^{T} (A + A^{T}) x

$x^TA^TAx - b^T(A + A^T)x$

David Ketcheson
la source

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

\begin{aligned} min_{x} ‖ A x - b ‖_{2}^{2}, \\ s . t . & \sum_{i} x_{i} = 1, \\ x_{i} \geq 0, \forall i . \end{aligned}

$\begin{alignat}{1} & \min_{x}\|Ax - b\|^{2}_{2}, \\ \mathrm{s.t.} & \quad\sum_{i}x_{i} = 1, \\ & \quad x_{i} \geq 0, \quad \forall{i}. \end{alignat}$

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