[Coin-ipopt] Help explaining IP/barrier, visualizing solver?
Frank J. Iannarilli
franki at aerodyne.com
Fri Jun 10 16:48:47 EDT 2005
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
More information about the Coin-ipopt
mailing list