[Coin-ipopt] IPOPT remains dual infeasible

[Peter Carbonetto]

Andreas and Sylvain,

    I will try out your suggestions and let you know about any positive 
developments. Thank you for the illuminating responses!

Peter

On Tue, 13 Feb 2007, Sylvain Miossec wrote:

> Hello Peter,
>
> I used to have the same problem. I send a previous post about it.
>
> I solved it by scaling the problem myself (using additional information of my 
> problem to scale better). But the essential point I think (and Andreas 
> response seems to confirms it) is that I implemented a Quasi-Newton update 
> (not just a limited memory one). I am not a specialist of optimization, but 
> since more histories are used, the hessian must be better approximated. Of 
> course for big problems, more memory will be necessary. Another problem is 
> that my implementation is not very clean. I didn't want to enter IPOPT's 
> code, so I implemented it in the eval_h function, using saved values of 
> objective and constraints gradients when calling eval_f_grad and eval_jac_g. 
> I can send you the piece of code if you want to give it a try.
>
> I guess a quick solution would be to increase the limited_memory_max_history.
>
> Best regards
>
> Sylvain Miossec
>
>
>
> 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
>> 
>