Optimization does not terminate with G and h matrices - fine with just P, q, A, and b

[Jared Vacanti]

I have an ipython notebook here - complete with data so the example is completely reproducible.

https://gist.github.com/jaredvacanti/62010beda0ccfc20d2eac3c900858e50

Executed Block 17 very clear shows the issue here (the original values that are trying to be fit and the x vector I'm left with.

I have read on other portions of the mailing list that problems occur when h is not scaled properly? Is that possibly the case here?

The purpose of this quadratic programming problem is to fit a natural cubic spline, following the implementation of Green and Silverman (1994 - Nonparametric Regression and Generalized Linear Models), my vector x that I am optimizing for should consist of the observed knot values from 0 ... n-1 and the second derivatives at each point at n..2n-2.

When I only provide A  and b, the resulting vector x has a very good fit from the observed knot points. When I also add G and h, I get no optimal solution found with either MOSEK or the default CVXOPT solver. The conditions G and h are vital to the exercise, otherwise many other approaches would fit a generic spline with no boundary conditions.

Any ideas?

[Martin]

I think CVXOPT fails because of the scaling of the problem. However, MOSEK returns "primal infeasible", so perhaps something is wrong with your model and/or implementation?

[Jared Vacanti]

Thanks Martin - sorry for the cross-post, when I initially submitted I did not realize it was pending approval and thought I was doing something wrong. 

I am not familiar with the scaling requirements on h. The post I am referring to had an h-vector of length 2 scaled to 1.0. My vector has a length of 302 with only four non-zero elements. Should I rework my coefficient matrix to scale h to 1.0? 

[Joachim Dahl]

I would not call it a scaling requirement, rather good practice when experience shows you something is not working well.

--
You received this message because you are subscribed to the Google Groups "CVXOPT" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+unsubscribe@googlegroups.com.
To post to this group, send email to cvx...@googlegroups.com.
Visit this group at https://groups.google.com/group/cvxopt.
For more options, visit https://groups.google.com/d/optout.

[Jared Vacanti]

So - to clarify for myself and for others who will come across these archives - when also providing G and h, the coefficient matrix G should be scaled in such a way that the elements of h are all 1.0 ?

To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+un...@googlegroups.com.

[Joachim Dahl]

No, it's not a hard requirement,  and if we worked in infinite precision it wouldn't matter.  On the other hand, having models with both extremely large and small magnitudes (say 1e10 to 1E-10) is probably not going to work well in practice. Physicists often build such model, and almost always have to rescale their data to get a usable solution. It's very similar to just solving linear systems of equations or linear least-squares problems in finite precision using Matlab; if the data-matrices are too ill-conditioned, the factorization will break down, or the solution will be extremely sensitive to perturbations.

What every user of CVXOPT or other software packages should know is the limitations of computations in double precision floating point.

1) If a model can be represented using data ranging from 1 to 1e-6, rather that 1e10 to 1e-10, then naturally go for the former.

2) Never build models with linear dependencies.

3) If you feel your model is OK, but the solver still stalls, then you need to massage your model to make the solver solve it. Some of the massaging-tricks could be normalization like Martin suggested.  But the solver cannot figure out the best way to massage the data - that's up to the user.

To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+unsubscribe@googlegroups.com.

[Jared Vacanti]

OK. I will try re-centering and rescaling and post my results.

Currently my range of the elements of G are from -1.0 to 66.6 and h are -2264 to 2364. I will try to massage this data further, but these scales do not seem outrageous. 

[Jared Vacanti]

I have tried scaling the data in a few ways and did not get the method to work. Cell 17 of this notebook shows that the spline fit is not a good one, and MOSEK and CVXOPT declare it as an optimal solution... this leads me to believe it is a numerical problem. There is a MATLAB implementation of this algorithm here, which I have gone through line-by-line and inspected the variables at different stages with breakpoints to ensure I'm providing the same variables to the quadratic program. 

What methods should I try to see if this is a numerical error? 

Does anyone know if the MATLAB implementation of quadprog is significantly different than CVXOPT or MOSEK solvers - other than the obvious syntax difference?

[Joachim Dahl]

If CVXOPT and MOSEK declares the solution to be optimal, but you don't like the solution, then it sounds like you have formulated the wrong problem.  It's possible that you require even higher accuracy than the default tolerances will produce, but that's generally not easy to achieve.

I don't know the quadprog implementation, but Matlab's optimization toolbox in general is often considered a little rudimentary.

To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+unsubscribe@googlegroups.com.

[Jared Vacanti]

I'm not familiar with the scale that should be solvable. The x-vector that is solved in MATLAB is around 40 elements, a different data set is around 500. Would this scale difference cause it to tail? It appears to get better / more accurate as I interpolate that number down. Could this mean more elements does need more precision? 

[Joachim Dahl]

I am not sure what you're asking.

If MOSEK or CVXOPT gives an optimal solution status, then the solvers have done their job.  If you don't like the answer they give you, then most likely you have asked the wrong question.

It's well-known and very common that for discretized interpolation problems, filter-design problems, etc., where you discretize continuous constraints, you get more and more ill-conditioned data with finer discretization grids.  I don't think there's much you can do about that - you simply start to introduce near-linear dependencies in the constraints.  That's not a problem with CVXOPT or MOSEK.  

I doubt quadprog will solve problems that CVXOPT or MOSEK can't, but it's certainly fine to experiment with different solvers.  Questions about quadprog should probably be asked on the Mathworks forums, though.

To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+unsubscribe@googlegroups.com.

[Dima Pasechnik]

you might give http://libelemental.org
a try. it can do quadratic optimisation with multiple, and even arbitrary precision, floating point numbers.