[Coin-ipopt] Convergence and BFGS Hessian computation

[Andreas Waechter]

Hi Sylvain,

I had a look at the output files you attached.

One thing I noticed is that it seems quite difficult to decrease the 
constraint violation (inf_pr).  Are your constraints very nonlinear?  Or 
are there very large elements in the constraint Jacobian?

What I usually see when I work with the L-BFGS option is that towards the 
end of the optimization, the primal infeasibility gets very small, and the 
objective function essentially has reached its optimal value, but the dual 
infeasibility is decreasing only slowly (as you observed).  There are 
theoretical reasons for this, but I have tried to add some heuristics to 
overcome this and try to bring down dual infeasibility.  Since in your 
case primal infeasibility is not getting small, this heuristic is not 
activated.

It seems that you got a better value of the objective function with the 
long history (131), but of course this is rather long.  A value like 20 
might already work fine.  As Carl pointed out, only the L-BFGS option is 
implemented in the C++ version of Ipopt, and at this point there are no 
plans to implement a full-space or reduced-space regular BFGS method.

Some other things you might want to play with are the obj_scaling_factor 
(try some values larger than 1, e.g. 10 or 100 or even more to see if that 
brings down the objective function faster).  Also, if you want to try if 
my heuristic for the slowly decreasing dual inf in the L-BFGS mode helps, 
you can use the 'recalc_y_feas_tol' and set it to a value larger than its 
default 1e-6 (looking at your output, you might want to try 1e-1...?)

I don't know if that would really help, but you can give it a try.

Finally, you write that implementing second derivatives is difficult in 
your case.  So, I assume that you wrote a C++ (or C or Fortran) program to 
compute the NLP model functions (like constraint Jacobian...)?  Did you do 
this because you actually call some complicated other code (such as a 
solver for differential equations) to get the constraint values?  (That 
probably means that your constraint function values are only computed to 
some limited accuracy, which might explain why the constraints are not 
getting really feasible?)

Otherwise, if you are implementing analytic expressions for the formulas, 
and you would like to experiment if providing explicit second order 
information would help, you could write your model in the modeling 
language AMPL (see www.ampl.com), which computes derivatives (first and 
second) for you.  Your problem is rather small, so that you could use the 
free student version of AMPL.

I hope this helps,

Andreas

On Thu, 5 Oct 2006, Sylvain Miossec wrote:

> Hi all,
>
> I am using IPOPT for a year now and I found it quite fast for the type
> of problems I solve (robot motion optimization). Thanks a lot for the
> good job.
>
> But I have one problem is the proper convergence of the optimization.
> Now I used to stop the optimization by reaching the maximum number of
> iterations. And then checking that the criteria is not changing a lot
> during the last iterations, and that the constraints are well satisfied.
> The motions I obtain for the robot look also optimal.
>
> Does anyone would have an idea why I don't obtain proper convergence ?
>
> I provide two files (in a zip compressed file) of some runs of optimization 
> for two different history of BFGS approximation.
>
> Since the Hessian computation is very complicate to program in my case,
> I use the limited-memory BFGS approximation. I tried a history of 6 for
> the BFGS computation and 131 (the size of my problem).  The BFGS
> computation is slower with a 131 history but the convergence is better.
> I have another question then : would it be better for my problem size to
> use a BFGS approximation (not limited-memory one) ?
>
> the parameters I used for IPOPT are the following :
> tol : 1e-3
> acceptable tol : 3e-3
> max_iter : 300/500
> expect_infeasible_problem : yes
> hessian_approximation : yes
> limited_memory_max_history : 131/6
> dual_inf_tol : 1e-6
> compl_inf_tol : 1e-6
> acceptable_dual_inf_tol : 3e-3
> acceptable_compl_inf_tol : 3e-3
> check_derivatives_for_naninf : yes
> derivative_test : first-order
> alpha_for_y : full
>
> During the optimization, the dual infeasibility is not really decreasing
> (and not reaching the stopping tolerance) while the criteria seems to
> converge. Is it normal ? Could it be due to a scaling problem (I scaled
> the problem myself by trial and error). Could it be due to the Hessian
> approximation ? Perhaps it is another reason for using BFGS
> approximation instead of limited-memory one. Or perhaps I should try the
> real hessian computation ? (but I would like to be sure it would solve
> my problem, since it will take lots of time to implement).
>
> An help on this point would be greatly appreciated.
>
> Best regards
>
> Sylvain Miossec
>
>