[Ipopt] Very Slow Convergence

[Uwe Nowak]

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