[Ipopt] Very Slow Convergence
Frank E. Curtis
frank.e.curtis at gmail.com
Fri Feb 25 14:20:06 EST 2011
In fact, it's not too surprising that a quasi-Newton method would not
help convergence in this case, but it was worth a try. I don't know
of any method that can handle well the type of nonconvexity that
appears to be present in your model. Hessian modification strategies
(including quasi-Newton methods, if they could be labeled as such) are
essentially heuristics for attaining global convergence in nonconvex
regions. Not much can be said about a fast convergence rate from
remote points, however. Which is why the starting point can make a
big difference.
I may be wrong, but based on the last iterations that you pasted, a
more aggressive strategy with larger modifications may help
(somewhat). Perhaps you can perturb the update to be larger in some
way. Still, though, progress is likely to be slow unless you can
somehow alter your model to avoid such high convexity.
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 1:18 PM, Uwe Nowak <uwe.nowak at itwm.fraunhofer.de> wrote:
> 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
>
> _______________________________________________
> Ipopt mailing list
> Ipopt at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/ipopt
>
More information about the Ipopt
mailing list