[Coin-ipopt] Help explaining IP/barrier, visualizing solver?

[Frank J. Iannarilli]

Hi All,

I'm a happy IPOPT user, in the throes of writing an applications paper, in 
which I essentially treat IPOPT as a black-box solver. Nevertheless, I feel 
obliged to provide a non-specialist's overview of what it does.

Grrrr!!!  I've been boning up on IP and NLP methods, reading things such as 
Vanderbei's Linear Programming book (the IP sections), Bertsekas's NLP 
book, a recent SIAM Review piece, and of course Andreas' papers. With all 
those swirling in my small mind, here is how I'm ending up nowhere for an 
explanation:


I want to say that the motivation for the barrier formulation is, as common 
for IP methods, to convert a constrained optimization into a sequence of 
unconstrained optimizations, as the barrier function keeps the iterates 
within the feasible region. This best makes sense for inequality 
constraints c_ineq(x)>=0:

    min: f(x) - u*log[c_ineq(x)]


But IPOPT converts inequalities to equality constraints by means of slack 
variables. These, plus intrinsic equality constraints {let's bundle them 
all up into c_eq(x)=0} are handled by employing the Lagrangian (with 
Langrangian multipliers y):

   min: L(x,y) = f(x) + y.c_eq(x)


The set c_eq(x)=0 define a set of manifolds, the mutual intersection of 
which defines the feasible region of possible solutions.  So where do the 
barrier terms in IPOPT come in?...in the bound (inequality) constraints 
(assume x>=0 for simplicity).  So for IPOPT we start with:

  min: f(x) + y.c_eq(x) - u*Sum_i{log[x_i]}

>From there, we look for stationary points, obtain 1st-order optimality 
conditions, treat the primal and dual variables independently, etc etc.


But then, the statement is made in the IPOPT papers, and elsewhere 
regarding primal-dual methods, that in choosing the descent step length, 
the iterate is explicitly checked against each x_i to insure it (the 
iterate) stays within the variable bounds. So then why bother with the 
barrier function on the variables themselves?  The classical motivation for 
the barrier is to apply it to the inequality constraints c_ineq(x), where 
it is less trivial to insure an iterate remains within the feasible region. 



So where I'm now left wondering is:

   (a) the only terms rendering this an "interior point" method **as a 
visual concept** are the bound constraints, which ostensibly don't even 
require a barrier to enforce;

   (b) the notion of a "feasible region", that marries so well with the 
"interior point" concept, is seemingly superfluous, as the infeasible 
primal-dual path-following need not even stay in feasible space until the 
very end;

   (c) with equality constraints captured in the Lagrangian, I envision the 
primal-dual central path "swimming" in, out, and around the feasible region 
defined by the intersection of the manifolds c_eq(x)=0, with it not 
necessarily encountering any feasible region "boundary" at/near 
termination.


Arghh! My earlier simpler IP weltanshung is shattered!

Can anybody suggest how to reconcile what actually occurs with IPOPT's 
primal-dual IP method with a non-specialist's explanation of what an 
interior-point method is all about?  Or explain IPOPT from a differing 
point of view?

Pointers to articles, thoughts, or indications of where my thinking has 
gone awry are all welcome!!

Thanks!



Frank J. Iannarilli, franki at aerodyne.com
Aerodyne Research, Inc., 45 Manning Rd., Billerica, MA 01821 USA
www.aerodyne.com/cosr/cosr.html