Sunday, September 29, 2013

Ill-posed problem

A client was solving a (large, non-linear) problem and got as message back:

ill-posed problem, solution status is unknown

The manual at http://www.gams.com/dd/docs/solvers/mosek.pdf did not give any help. This message seems to indicate the modeler (me) did something wrong. However I am really sure the model is just fine: smooth and differentiable everywhere and even convex.

Solver messages are really important (they’ll help the user when they are in trouble), and I think many of these messages are not very good; they often seem to be made up after a long day of coding without too much thought. A good message would probably try to answer the obvious question: “And what now?”. If at all possible it should help the user fix the problem (may be even adding some information about which equations and variables are involved).

Instead of fixing the so-called ill-posed problem we used a newer version of the solver, and now we obtained an optimal solution.

Sometimes it can help to have different solvers available. In GAMS you can then automate:

option nlp=minos;
solve
mod1 minimizing z using nlp;
if
(mod1.modelstat > 2,
*   not optimal or locally optimal

  
option nlp=conopt;
  
solve
mod1 minimizing z using nlp;
);

1 comment:

  1. The problem min 1/x, x>=0.0 is ill-posed because the optimal solution x is +infinity and can never be attained. Another example of an ill-posed problem is one that has nonzero duality gap.

    In practice MOSEK may say ill posed for other reasons. A very bad scaling could cause the message for instance. Or if you extremely large bounds or penalty values in the objective. Another reason is that the problem may not convex even though the user thinks it is.

    It is impossible for MOSEK to be precise about what is causing the ill-posedness because there is no single reason causing it.
    Ignoring the message and moving to another optimizer may of course be a fix that solves the issue. The other optimizer may presolve and scale the problem differently and hence be lucky to work around the issue. Of course I can not exclude MOSEK is doing something stupid that the other optimizer does not.

    An alternative route is to provide the problem to MOSEK support for an investigation. Frequently that leads to pinpointing an unfortunate model model formulation.

    Btw the characteristic of an ill-posed problem is a tiny perturbation in the data changes the solution dramatically. This should make it obvious that is very hard to deal with such problems. Note the problem min 1/x, x>=1.0e-10 is not ill-posed.


















    ReplyDelete