[Coin-ipopt] Convergence and BFGS Hessian computation
Andreas Waechter
andreasw at watson.ibm.com
Thu Oct 5 12:15:38 EDT 2006
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
>
>
More information about the Coin-ipopt
mailing list