Tuesday, May 3, 2011

Initial Point for NLP models

This example was introduced to illustrate the need for good initial points in NLP models (see http://amsterdamoptimization.com/pdf/snopt.pdf).

The problem is just a three variable model: find the smallest enclosing circle around n points. GAMS has a default initial point of zero which is often very bad. Only IPOPT can find an optimal solution quickly. But if we add a good starting point, all solvers find the optimal very quickly. Even the performance of IPOPT improves.

For a presentation I cleaned up the example a little bit:





Note: actually the model is easier to solve using a slightly different formulation:


(i.e. minimize the square of the radius r).

1 comment:

  1. Hi,

    first of all: Great Blog, keep it up! :-)

    I just wanted to add that this particular problem can be solved in O(n) with specialized algorithms, see e.g. this book: http://www.cs.uu.nl/geobook/

    Best regards from Germany,