Thursday, November 17, 2016

Constrained Least Squares solution times

In this post a somewhat larger linearly constrained least squares problem is solved using R. The problem is simply:

\[\begin{align}\min_P&||P s - f||^2\\ & \sum_i p_{i,j}\le 1\\ & p_{i,j} \ge 0 \end{align}\]

To make things easier for the QP solver I implemented the model (in GAMS) as:

\[\begin{align}\min_{P,e}&\sum_i e_i^2\\ & \sum_j p_{i,j} s_j = f_i + e_i\\ &\sum_i p_{i,j} \le 1 \\ &p_{i,j} \ge 0 \end{align}\]

The timings for a problem with \(39 \times 196\) elements in \(P\) are:

R+constrOptim 15 hours
R+auglag 2 hours
GAMS+IPOPT 1.2 seconds
GAMS+Cplex 0.15 seconds

Cplex uses a specialized convex quadratic solver, while IPOPT is a general purpose NLP (nonlinear programming) solver.

Sometimes it helps to choose the right solver for the problem at hand.

References
  1. Follow-up on this blog detailing the effects on my reformulation is here: http://yetanothermathprogrammingconsultant.blogspot.com/2016/11/constrained-least-squares-solution.html