Trustful Nonlinear Programming

Question

Is it possible for an NLP solver to claim that a knowingly feasible problem is infeasible?

Shouldn't the solver be able to provide a solution (of course not necessarily the global optimum but a feasible one)?

Is a wrongly claimed infeasibility a matter of tolerances or are there algorithmic issues?

Edit: Here is the EXIT state of IPOPT

EXIT: Converged to a point of local infeasibility. Problem may be infeasible.

That indicates that the problem is an algorithmic issue.

Answer 1

Local nonlinear optimization solvers, such as IPOPT, are not guaranteed to find a feasible point for problems that are feasible. That is certainly the case for problems with non-convex constraints, and I believe may even occur sometimes for problems having convex nonlinear constraints.

The starting (initial) point is often important in determining whether or not a feasible point is found.

Things are even worse than you might think. I have experienced a number of occasions on which I provided a starting point in the interior of the feasible region, and the solver diverged to an infeasible point.

If you want an (almost) guaranteed determination of feasibility for a non-convex problem, use an (almost) rigorous (branch and bound) global optimization solver, such as BARON, COUENNE, ANTIGONE, BMIBNB (under YALMIP), Octeract or SCIP. Even those solvers can occasionally declare feasible problems as infeasible, generally when the numerics of the problem are bad, such as very bad input data scaling.

The only guaranteed way to make a reliable determination of feasibility is to use a "verified" global solver, such as based on interval (or affine) arithmetic with outward rounding, based on, perhaps, branch and bound interval Newton's method. Unfortunately, there are no hardware implementations I know of to implement interval arithmetic with outward rounding; so that needs to be done in software. Therefore, such solvers tend to take orders of magnitude longer to run than the much more popular almost rigorous (branch and bound) global optimization solvers, which already can have very long run times. Note that for purposes of determining feasibility, it is sufficient to use a nonlinear equation and inequality solver rather than an optimizer.

Answer 2

Oh boy. Adding to Mark's great answer, I'll add some fun facts on what can go wrong with IPOPT and feasibility, and provide us with endless nights of entertainment:

• The linear system solver gets stuck. A timeless classic, especially for MUMPS. It will suddenly slow down to a crawl for no apparent reason. It can also fail outright, which can cascade to reporting infeasibility.
• Iteration limit/timeout can be reached before a feasible point can be found. The exit flag is often, but not necessarily, indicative of this having happened.
• The cryptic "restoration failed" message. Another timeless classic, this can be caused by a number of things, but utterly it means that IPOPT could not bring the solution inside the feasible region within tolerances. The "within tolerances" part we have to guess, as IPOPT has the same umbrella message for any number of different issues that lead to failed restoration.
• The Newton iteration can diverge.
• The Newton iteration can diverge because we didn't provide exact/good/correct derivatives.
• The Newton iteration can diverge because the barrier parameters need tweaking.
• The Newton iteration can diverge/be so slow that iteration limit is reached before feasibility because the line search failed/needs tweaking.
• The starting point is bad.
• The starting point is technically ok, but a tiny numerical flux in the first few iterations derails the iterative process.
• Another great one: the starting point is feasible but far from the optimal solution. IPOPT "tends" to work best with points close to the local solution, even if they are infeasible. "Tends" is the normative word here, as this is often, but not always, true.
• The problem formulation is not numerically stable.
• There is a bug in the automatic differentiation the user provided to IPOPT.
• The user did not define variable bounds properly.
• There is a bug in the interface or .nl file that is passed to IPOPT.
• IPOPT's default tolerances are just marginally too strict for this problem.
• IPOPT was compiled for Windows instead of Linux. Although rare, results can actually be different (including feasibility/infeasibility) depending on OS/architecture.
• Just for fun, we have also seen a single case where the reason was a compiler bug. Compiling with a different version made the problem go away.

IPOPT can be quite cryptic about why things go wrong, so if you know that your model is feasible the reason can be any one of these things. However, IPOPT is damn good and most people will probably never encounter most of these. The most common reasons by far (as in, 99.99% of cases) are that (i) the feasible solution you have has different tolerances than IPOPT's defaults, and (ii) the starting point is bad.