[Ipopt] Very Slow Convergence
Uwe Nowak
uwe.nowak at itwm.fraunhofer.de
Fri Feb 25 13:18:59 EST 2011
Hello!
Your observation are right, in fact all of the 356590 Inequality
constraints are reverse convex and it is likely that at the optimum
quite a few (maybe a thousend) are active. However MFCQ should be
satisfied (probably LICQ is not satisfied). Of cause there are lots of
local minima, but convergence to a local minimum would suffice.
I put some effort in the starting point. The starting point is feasible
(could also make it strictly feasible) but far away from the optimum.
Following the hint of Frank E. Curtis I tried A quasi newton
approximation, but as far as I can see, convergence speed did not
improved so far.
Best Regards,
Uwe
Am 25.02.2011 16:45, schrieb Andreas Waechter:
> Hi Uwe,
>
> I agree with Frank's observation; it appears that the algorithm is
> trying to get out of a nonconvex region (therefore the Hessian
> modifications), but it takes a lot of time. You may also want to try
> what happens if you provide a different starting point (not sure how
> much work you put into your starting point, given that this is probably
> a problem with multiple local minima, the choice of the starting point
> might make a big difference in terms of which local solution Ipopt
> converges to).
>
> Regards,
>
> Andreas
>
> On Fri, 25 Feb 2011, Frank E. Curtis wrote:
>
>> I agree with Ashu that the Hessian may be the issue. Not necessarily
>> that it is being evaluated incorrectly, but your problem appears to be
>> highly nonconvex, requiring Ipopt to modify the Hessian during all
>> iterations. (Note the fourth-to-last column of the output, "lg(rg)";
>> whenever this value is not "-" it means the Hessian is being
>> modified.) You may want to try adjusting the way the Hessian is
>> modified or use Hessian approximation techniques. You may get lucky.
>>
>> Frank E. Curtis
>> P. C. Rossin Assistant Professor
>> Industrial and Systems Engineering
>> Lehigh University
>> 200 W. Packer Ave., Room 322
>> Bethlehem, PA 18015
>> frank.e.curtis at gmail.com
>> +1.646.789.5490
>> http://coral.ie.lehigh.edu/~frankecurtis
>>
>> On Fri, Feb 25, 2011 at 10:11 AM, Ashutosh Mahajan <asm4 at lehigh.edu>
>> wrote:
>>> How do you input your problem: AMPL or your own interface? Slow
>>> convergence is
>>> sometimes a sign of incorrectly evaluated hessian.
>>>
>>> --
>>> regards
>>> Ashutosh Mahajan
>>> http://coral.ie.lehigh.edu/~asm4
>>>
>>> On Fri, Feb 25, 2011 at 01:52:51PM +0100, Uwe Nowak wrote:
>>>> Hello!
>>>>
>>>> I am trying to solve some circle packing related problems with IPOPT.
>>>> For small to medium size problems (up to 400 Circles) everything works
>>>> fine and reasonable fast. However for larger problems the Algorithm
>>>> does
>>>> not converge..
>>>>
>>>>
>>>>> This is Ipopt version 3.9.2, running with linear solver ma27.
>>>>>
>>>>> Number of nonzeros in equality constraint Jacobian...: 0
>>>>> Number of nonzeros in inequality constraint Jacobian.: 1426360
>>>>> Number of nonzeros in Lagrangian Hessian.............: 733017
>>>>>
>>>>> Total number of variables............................: 2535
>>>>> variables with only lower bounds: 0
>>>>> variables with lower and upper bounds: 0
>>>>> variables with only upper bounds: 0
>>>>> Total number of equality constraints.................: 0
>>>>> Total number of inequality constraints...............: 356590
>>>>> inequality constraints with only lower bounds: 356590
>>>>> inequality constraints with lower and upper bounds: 0
>>>>> inequality constraints with only upper bounds: 0
>>>>>
>>>>> iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du
>>>>> alpha_pr ls
>>>>> 0 1.7720393e+06 1.99e-01 6.18e+00 -1.0 0.00e+00 - 0.00e+00
>>>>> 0.00e+00 0
>>>>> 1 1.7719897e+06 1.90e-03 1.97e-01 -1.0 1.99e-01 0.0 9.90e-01
>>>>> 9.90e-01f 1
>>>>> 2 1.7719792e+06 8.17e-07 4.14e-01 -1.0 9.04e-02 -0.5 9.91e-01
>>>>> 1.00e+00f 1
>>>>> 3 1.7719639e+06 1.63e-07 1.90e-02 -1.0 1.74e-01 -1.0 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 4 1.7719359e+06 1.46e-06 1.15e-02 -2.5 3.34e-01 -1.4 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 5 1.7718661e+06 1.31e-05 4.24e-02 -3.8 2.42e+00 -1.9 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 6 1.7718414e+06 1.85e-06 7.36e-03 -3.8 2.30e-01 -1.5 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 7 1.7717680e+06 1.66e-05 5.97e-03 -3.8 5.44e-01 -2.0 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 8 1.7717406e+06 2.34e-06 5.97e-03 -3.8 2.04e-01 -1.5 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 9 1.7716585e+06 2.10e-05 5.97e-03 -3.8 6.12e-01 -2.0 1.00e+00
>>>>> 1.00e+00f 1
>>>>> iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du
>>>>> alpha_pr ls
>>>>> 10 1.7716278e+06 2.96e-06 5.97e-03 -3.8 2.29e-01 -1.6 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 11 1.7715352e+06 2.66e-05 7.90e-03 -3.8 1.10e+00 -2.1 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 12 1.7712588e+06 2.39e-04 1.40e-02 -3.8 2.06e+00 -2.5 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 13 1.7704321e+06 2.15e-03 5.96e-03 -3.8 6.18e+00 -3.0 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 14 1.7679654e+06 1.92e-02 5.94e-03 -3.8 1.85e+01 -3.5 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 15 1.7606816e+06 1.70e-01 7.13e-03 -3.8 5.49e+01 -4.0 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 16 1.7398125e+06 1.45e+00 5.77e-02 -3.8 1.59e+02 -4.4 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 17 1.6839562e+06 2.44e-01 4.15e-01 -3.8 4.34e+02 -4.9 1.00e+00
>>>>> 1.00e+00F 1
>>>>> 18 1.6647120e+06 1.52e+00 5.50e-02 -3.8 1.52e+02 -4.5 1.00e+00
>>>>> 1.00e+00f 1
>>>>> 19 1.6134541e+06 2.81e-01 3.22e-01 -3.8 4.06e+02 -5.0 1.00e+00
>>>>> 1.00e+00F 1
>>>>
>>>>
>>>> Then many hours later...
>>>>
>>>>> iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du
>>>>> alpha_pr ls
>>>>> 8270 3.4629818e+05 3.73e-04 3.03e-01 -5.7 3.05e+00 -5.1 3.40e-01
>>>>> 1.28e-02h 1
>>>>> 8271 3.4629149e+05 2.48e-04 2.48e-01 -5.7 1.14e+00 -4.7 7.40e-01
>>>>> 3.48e-01h 1
>>>>> 8272 3.4627186e+05 3.18e-04 1.68e-01 -5.7 3.48e+00 -5.2 3.53e-01
>>>>> 3.38e-01h 1
>>>>> 8273 3.4627111e+05 3.06e-04 1.62e-01 -5.7 1.29e+00 -4.8 3.95e-02
>>>>> 3.56e-02h 1
>>>>> 8274 3.4626946e+05 3.00e-04 3.55e-01 -5.7 4.43e+00 -5.2 3.53e-01
>>>>> 2.57e-02h 1
>>>>> 8275 3.4626407e+05 2.44e-04 2.17e-01 -5.7 1.45e+00 -4.8 1.64e-01
>>>>> 2.25e-01h 1
>>>>> 8276 3.4626263e+05 2.40e-04 3.19e-01 -5.7 5.92e+00 -5.3 1.53e-01
>>>>> 2.01e-02h 1
>>>>> 8277 3.4625715e+05 2.04e-04 1.82e-01 -5.7 1.64e+00 -4.9 4.42e-02
>>>>> 2.05e-01h 1
>>>>> 8278 3.4624521e+05 2.74e-04 1.60e-01 -5.7 7.71e+00 -5.3 1.65e-01
>>>>> 1.47e-01h 1
>>>>> 8279 3.4624204e+05 2.54e-04 3.19e-01 -5.7 2.29e+00 -4.9 3.28e-01
>>>>> 1.05e-01h 1
>>>>> iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du
>>>>> alpha_pr ls
>>>>> 8280 3.4621935e+05 3.81e-04 1.10e-01 -5.7 5.50e+00 -5.4 3.91e-02
>>>>> 2.53e-01h 1
>>>>> 8281 3.4621741e+05 3.61e-04 3.22e-01 -5.7 2.06e+00 -5.0 3.66e-01
>>>>> 5.74e-02h 1
>>>>> 8282 3.4621398e+05 3.54e-04 3.55e-01 -5.7 6.18e+00 -5.4 1.30e-01
>>>>> 3.39e-02h 1
>>>>> 8283 3.4620558e+05 3.05e-04 2.46e-01 -5.7 2.32e+00 -5.0 1.74e-01
>>>>> 2.22e-01h 1
>>>>> 8284 3.4620029e+05 3.03e-04 2.70e-01 -5.7 6.95e+00 -5.5 2.38e-01
>>>>> 4.65e-02h 1
>>>>> 8285 3.4619775e+05 2.88e-04 3.07e-01 -5.7 2.61e+00 -5.1 2.54e-01
>>>>> 5.98e-02h 1
>>>>> 8286 3.4618951e+05 2.97e-04 3.08e-01 -5.7 7.80e+00 -5.5 8.89e-02
>>>>> 6.48e-02h 1
>>>>
>>>>
>>>>
>>>> I read the 90-minutes-introduction to IPOPT and the implementation
>>>> paper. However I do not really have a feeling, why the algorithm is
>>>> converging that slow.
>>>>
>>>> this run is started with the options
>>>> tol 0.01
>>>> acceptable_tol 0.05
>>>> max_iter 200000
>>>>
>>>> So by default it should by
>>>> dual_inf_tol = 1
>>>> constr_viol_tol = 1e-4
>>>> compl_inf_tol = 1e-4
>>>>
>>>> I see, that dual feasibility is stisfied but primal feasibility is not.
>>>> I do not know, where to read the compl_inf value in the current
>>>> iteration. Further I do not know, if the primal and dual step sizes are
>>>> "small"...
>>>>
>>>> Has anybody some suggestions, why the algorithm is converging that
>>>> slow?
>>>>
>>>> Thank you,
>>>> Uwe
>>>>
>>>> _______________________________________________
>>>> Ipopt mailing list
>>>> Ipopt at list.coin-or.org
>>>> http://list.coin-or.org/mailman/listinfo/ipopt
>>>
>>> _______________________________________________
>>> Ipopt mailing list
>>> Ipopt at list.coin-or.org
>>> http://list.coin-or.org/mailman/listinfo/ipopt
>>>
>>
>>
>> _______________________________________________
>> Ipopt mailing list
>> Ipopt at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/ipopt
>>
>>
>>
>
>
> _______________________________________________
> Ipopt mailing list
> Ipopt at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/ipopt
--
Uwe Nowak
Fraunhofer-Institut für Techno- und Wirtschaftsmathematik
Abteilung Optimierung
Fraunhofer-Platz 1
D-67663 Kaiserslautern
Telefon: +49(0)631/31600-4458
E-Mail: uwe.nowak at itwm.fraunhofer.de
Internet: www.itwm.fraunhofer.de
More information about the Ipopt
mailing list