12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I hope this question is not too specific for compsci. $\endgroup$ – tillsten Jul 5 '12 at 0:47
  • $\begingroup$ 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. $\endgroup$ – tillsten Jul 5 '12 at 7:49
  • $\begingroup$ Btw, the other edits are great! $\endgroup$ – tillsten Jul 5 '12 at 7:49
  • $\begingroup$ You can easily solve this by your own code in very efficient way. No need for CVXOPT. $\endgroup$ – Royi Jul 9 '18 at 19:05
11
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.