[Ipopt] Optimality guarantees for convex problems?

[Lasse Kliemann]

Hi Andreas,

thank you for the reply. My question is partly answered. Let me 
emphasize one point that I am not sure about yet.

Given your formulation of the minimization problem below, define
the _feasible set_ by

  F := { x | c(x) =0 and d(x) <= 0 }

Let c be linear and d be convex, so F is a convex set.

Let furthermore be the objective f convex on F. But we do not 
know how f behaves outside of F. Maybe we only know how f is 
defined outside, and that it is differentiable. Assume this if 
necessary.

A _local minimizer_ is a point x_0 in F such that there exists a 
real number R>0 such that for all x in F 

   ||x-x_0|| <= R  --->  f(x_0) <= f(x).

(I presume "first order optimal point" means exactly that?)

Now, it is clear that a local minimizer is a global minimizer, 
i.e., a point x_0 such that f(x_0) = min {f(x) | x in F}. This 
follows from convexity of f on F.

But would Ipopt need convexity or some other nice properties 
*outside the feasible set F*, in order to find a local minimizer?  
I could imagine that the behavior of f close to the boundary of F 
might play at least a role. But I am not sure.

Thank you
Lasse

* Message by -Andreas Waechter- from Tue 2009-11-03:
> 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
> >
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 835 bytes
Desc: not available
Url : http://list.coin-or.org/pipermail/ipopt/attachments/20091104/cc1b04fb/attachment.bin