[Ipopt] Optimality guarantees for convex problems?

[Andreas Waechter]

Hi Lasse,

If you write your optimization problem in the form

min  f(x)
s.t. c(x) = 0
      d(x) <= 0

and f(x) and d(x) are convex, and c(x) is linear, then any first order 
optimal point (those are the points found my Ipopt) is a global solution. 
Therefore, in that case Ipopt will find the global optimum.

However, if any of the functions is not convex (or the equality 
constraints c(x) are nonlinear), this is no longer true, and Ipopt is 
guarateed by theory only to find a first order optimal point, which might 
not be the global solution.  So, if you objective function is non-convex, 
Ipopt is not guaranteed to find a global solution.  (Ipopt has measures 
that attempt to steer it towards a local minimizer, though.)

But if your objective function is for some reason of a form so that every 
first order optimal point is a global solution (e.g., if it is 
pseudo-convex), then Ipopt will find the global solution.  However, this 
can be a rather special case.

Hope this helps,

Andreas

On Sat, 31 Oct 2009, Lasse Kliemann wrote:

> Greetings,
>
> I have questions concerning the behavior of Ipopt on convex
> problems. The documentation reads:
>
>   It is important to keep in mind that the algorithm is only
>   trying to find a local minimizer of the problem; if the
>   problem is nonconvex, many stationary points with different
>   objective function values might exist, and it depends on the
>   starting point and algorithmic choices which particular one
>   the method converges to.
>
> Now, assume I have a problem expressed with smooth functions
> (say, polynomials) and an objective function that is convex on
> all R^n. Can I expect Ipopt to deliver a globally optimal
> solution then (probably up to small inaccuracies)?
>
> If so, my second question concerns the case when the objective
> function is not convex on R^n, but at least the set K of feasible
> points is convex and the objective function is convex on K. Can I
> expect Ipopt to deliver a globally optimal solution ("globally"
> meaning: on K) then (probably up to small inaccuracies)?
>
> The latter occurs frequently in my application, so it would be
> interesting to know.
>
> By the way, thank you for your work on Ipopt!
>
> Kind regards
> Lasse
>