[Coin-ipopt] IPOPT remains dual infeasible

[Andreas Waechter]

Hi Peter,

Many thanks for resending your message after the Ipopt mailing list 
"outage"...

Yes, your suspicion is correct:

The reason, why you see such large values of the dual infeasibility is 
most probably that you are using the quasi-Newton option.

Here is why I think this is happening:

When second derivatives are used, then we are truely applying Newton's 
method to the primal-dual first order optimality conditions (or at least a 
perturbed version thereof).  Here, the constraint multipliers enter in the 
KKT matrix (the one that is factorized to compute the step) only in the 
Hessian of the Lagrangian function.

Now, when we use the (limited memory) BFGS method to approximate the 
Hessian of the Lagrangian function, the multipliers have only a small 
effect on the matrix, and there is no reason they would converge quickly 
to the optimal values.  Well, that is not a 100% mathematical explanation, 
but I think this is essentially what is going on.

I have noticed this before, too, and I have tried some tricks to improve, 
but all just being heuristics up to that point.  The main thing I tried is 
to recompute the constraint multipliers in each iteration as least-square 
estimates (for dual infeasibility) instead of relying on the step given 
from the KKT system (which is what we usually use).  Since this requires 
an extra factorization of the KKT system (with identity instead of the 
Hessian), this is somewhat expensive, and I added a heuristic so that this 
is only done when the constraint violation is small.

The options that regular this behavior are:

---------- 8< --------------------------

recalc_y                      ("no")
    Tells the algorithm to recalculate the equality and inequality multipliers
    as least square estimates.
      This asks the algorithm to recompute the multipliers, whenever the
      current infeasibility is less than recalc_y_feas_tol. Choosing yes might
      be helpful in the quasi-Newton option.  However, each recalculation
      requires an extra factorization of the linear system.  If a limited
      memory quasi-Newton option is chosen, this is used by default.
    Possible values:
     - no                      [use the Newton step to update the multipliers]
     - yes                     [use least-square multiplier estimates]

recalc_y_feas_tol                      0 <  (      1e-06) <  +inf
    Feasibility threshold for recomputation of multipliers.
      If recalc_y is chosen and the current infeasibility is less than this
      value, then the multipliers are recomputed.

---------- 8< --------------------------

Usually, the default for the "recalc_y" option is "no", but when you use 
the limited memory BFGS option, it is chosen to be "yes" (unless you 
overwrite the default).  If "recalc_y" is "yes", then the constraint 
multipliers ("y") are recomputed, whenever the current constraint 
violation is less than recalc_y_feas_tol.

In your example, it seems that they are recomputed in every iteration 
(since inf_pr is always less than recalc_y_feas_tol), and here it doesn't 
seem to help :(


I guess your approach to change the termination criterion is a good one. 
But instead of just relaxing the the dual infeasibility, we might want to 
try a more complicated heuristic, that could monitor the progress in the 
objective function and the change in the primal iterates, and maybe the 
step sizes ("alpha").

At the moment, I probably won't have the time to look into actually 
changing the code.  If you want to try something yourself, the file to 
look at would be Ipopt/src/Algorithm/IpOptErrorConvCheck.cpp (the 
CheckConvergence method).

I hope this helps at least a little bit...

Cheers,

Andreas

PS: MATLAB interface, cool!


On Mon, 12 Feb 2007, Peter Carbonetto wrote:

> THE SCENARIO: I have an optimization problem with about 60 variables
> (later this will grow), a nonlinear objective, bound constraints (all
> the variables must lie in the positive quadrant) and a sparse set of
> linear constraints.
>
> [My problem consists of solving inference in a Bayesian model using a
> variational approximation.]
>
> THE GOOD NEWS: IPOPT converges to a very reasonable solution after about 80 
> iterations, and does so using a limited-memory quasi-Newton approximation to 
> the Hessian (limited_memory_max_history = 5) because I haven't bothered to 
> compute the second derivatives. I know the solution is reasonable because 
> there is an existing algorithm tailored to my problem that comes up with the 
> same answer.
>
> THE BAD NEWS: IPOPT fails to converge to a point that is dual
> feasible, or takes an extremely long time to do so. The output from
> IPOPT looks something like this:
>
> iter    objective    inf_pr   inf_du lg(mu)  ||d||
>   0  9.4872744e+01 2.22e-16 4.89e+02   0.0 0.00e+00
>   1  5.4935737e+01 2.22e-16 7.25e+00  -4.0 2.80e+01
>   2  5.3405603e+01 1.11e-16 5.21e+00  -1.3 4.36e-02
>   3  4.6288683e+01 0.00e+00 2.84e+00  -0.8 3.29e-01
>
>                        . . .
>
>  85  2.6698305e+01 2.22e-16 5.84e-02  -2.6 3.35e-02
>  86  2.6698300e+01 2.22e-16 2.42e-02  -2.6 5.99e-02
>  87  2.6658051e+01 2.22e-16 1.91e+00  -3.9 8.45e-03
>  88  2.6669530e+01 2.22e-16 2.75e-01  -3.1 1.11e-02
>
> Notice that the dual variables have failed to converge to the feasible
> region. Currently, I workaround this problem by setting a high
> tolerance for dual infeasibility (dual_inf_tol = 0.9).
>
> I'm wondering if anyone may have some deeper understanding of
> primal-dual methods than myself and may be able to explain why this is
> going on. I suspect that the problem may have something to do with the 
> quasi-Newton approximation, but I can't be sure since I haven't coded
> the exact Hessian.
>
> [By the way, Andreas, I've done all this using a MATLAB interface I've
> developed. There were a few significant obstacles in getting IPOPT to
> interface with MATLAB, but at this point it is working quite
> nicely. More on that in the not-too-distant future.]
>
> Thank you,
>
> Peter Carbonetto
> Dept. of Computer Science
> University of British Columbia
> _______________________________________________
> Coin-ipopt mailing list
> Coin-ipopt at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-ipopt
>