# Solving a least squares problem with linear constraints in Python

I need to solve

\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}

I think it is a quadratic problem which should be solvable with CVXOPT, but I can't work out how.

• I hope this question is not too specific for compsci. – tillsten Jul 5 '12 at 0:47
• Geoff Oxberry: Just a curiosity, but why did you edit out the linear-part? I think it is quite a impotent part of the problem description, the solution would be quite different for a non-linear least squares optimization. – tillsten Jul 5 '12 at 7:49
• Btw, the other edits are great! – tillsten Jul 5 '12 at 7:49
• You can easily solve this by your own code in very efficient way. No need for CVXOPT. – Royi Jul 9 '18 at 19:05

## 2 Answers

I wrote a full answer (below the line) before discovering CVXPY, which (like CVX for MATLAB) does all the hard stuff for you and has a very short example almost identical to yours here. You only need to replace the relevant line with

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


My old answer, doing it the harder way with CVXOPT:

Following Geoff's suggestion to square your objective function gives

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

Of course, all terms are scalars, so you can transpose the third one and drop the last one (as it doesn't depend on $x$ and therefore won't change which $x$ gives you a minimum, though you will need to add it back in after solving in order to get the correct value of your objective) to obtain $$x^TA^TAx - b^T(A + A^T)x$$ This (including your constraints) has the form of a quadratic program, as given in the CVXOPT documentation here, where there is also example code for solving such a problem.

Instead of the problem you solved, solve

\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}

This problem is a differentiable, convex, nonlinear optimization problem that can be solved in CVXOPT, IPOPT, or any other convex optimization solver.