search

cvanaret / Uno

A next-gen Lagrange-Newton solver for nonconvex optimization. It unifies barrier and SQP methods in a modern and generic way, and implements different globalization flavors (line search/trust region and merit function/filter method/funnel method). Competitive against filterSQP, IPOPT, SNOPT, MINOS and CONOPT.
MIT License
297 stars 22 forks source link

Unboundedness detection #58

Closed odow closed 3 weeks ago

odow commented 3 weeks ago

Uno cannot identify even the most trivial cases of unboundedness:

julia> using JuMP, AmplNLWriter, Uno_jll

julia> model = Model(
           () -> AmplNLWriter.Optimizer(Uno_jll.amplexe; directory = "/tmp")
       )
A JuMP Model
├ solver: AmplNLWriter
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

julia> @variable(model, x)
x

julia> @objective(model, Min, x)
x

julia> optimize!(model)
Original model /tmp/model.nl
1 variables, 0 constraints
Reformulated model /tmp/model.nl_scaled_equalityconstrained_boundrelaxed
1 variables, 0 constraints

Used overwritten options:
- LS_backtracking_ratio = 0.5
- LS_min_step_length = 5e-7
- LS_scale_duals_with_step_length = yes
- armijo_decrease_fraction = 1e-8
- barrier_damping_factor = 1e-5
- barrier_tau_min = 0.99
- constraint_relaxation_strategy = feasibility_restoration
- filter_beta = 0.99999
- filter_fact = 1e4
- filter_gamma = 1e-8
- filter_type = standard
- filter_ubd = 1e4
- globalization_mechanism = LS
- globalization_strategy = waechter_filter_method
- l1_constraint_violation_coefficient = 1000.
- linear_solver = MUMPS
- loose_tolerance = 1e-6
- loose_tolerance_consecutive_iteration_threshold = 15
- progress_norm = L1
- protect_actual_reduction_against_roundoff = yes
- residual_norm = INF
- scale_functions = yes
- sparse_format = COO
- subproblem = primal_dual_interior_point
- switch_to_optimality_requires_linearized_feasibility = no
- switching_delta = 1
- tolerance = 1e-8

┌───────┬─────────┬────────────────┬─────────────┬───────┬────────────────┬──────────────┬─────────────┬──────────────┬─────────────────┬────────────────────────┐
│ iter  │ LS iter │ barrier param. │ step length │ phase │ regularization │ step norm    │ objective   │ stationarity │ complementarity │ status                 │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 0     │ -       │ -              │ -           │ OPT   │ -              │ -            │ 0           │ 1            │ 0               │ initial point          │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 1     │ 1       │ 0.02           │ 1           │ OPT   │ 0              │ 1            │ -1          │ 1            │ 0               │ accepted (f-type)      │

├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 2000  │ 1       │ 0.02           │ 1           │ OPT   │ 0              │ 1            │ -2000       │ 1            │ 0               │ accepted (f-type)      │
└───────┴─────────┴────────────────┴─────────────┴───────┴────────────────┴──────────────┴─────────────┴──────────────┴─────────────────┴────────────────────────┘

Uno 1.1.0 (LS feasibility_restoration waechter_filter_method primal_dual_interior_point)
Fri Nov  1 13:31:42 2024
────────────────────────────────────────
Status:                 Failed with suboptimal point
Objective value:            -2000
Primal feasibility:         0
┌ Stationarity residual:        1
└ Complementarity residual:     0
┌ Feasibility stationarity residual:    1
└ Feasibility complementarity residual: 0
┌ Infeasibility measure:        0
│ Objective measure:            -2000
└ Auxiliary measure:            0
Primal solution:            -2000 
┌ Constraint multipliers:       
│ Lower bound multipliers:      0 
└ Upper bound multipliers:      0 
┌ Constraint feasibility multipliers:   
│ Lower bound feasibility multipliers:  0 
└ Upper bound feasibility multipliers:  0 
Objective multiplier:           1
CPU time:               0.221202s
Iterations:             2000
Objective evaluations:          2001
Constraints evaluations:        0
Objective gradient evaluations:     2002
Jacobian evaluations:           0
Hessian evaluations:            2000
Number of subproblems solved:       2000

shell> cat /tmp/model.nl
g3 1 1 0
 1 0 1 0 0 0
 0 1
 0 0
 0 0 0
 0 0 0 1
 0 0 0 0 0
 0 1
 0 0
 0 0 0 0 0
O0 0
n0
x1
0 0
b
3
G0 1
0 1

Ipopt returns

julia> optimize!(model)
Ipopt 3.14.16: 

******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
 Ipopt is released as open source code under the Eclipse Public License (EPL).
         For more information visit https://github.com/coin-or/Ipopt
******************************************************************************

This is Ipopt version 3.14.16, running with linear solver MUMPS 5.7.3.

Number of nonzeros in equality constraint Jacobian...:        0
Number of nonzeros in inequality constraint Jacobian.:        0
Number of nonzeros in Lagrangian Hessian.............:        0

Total number of variables............................:        1
                     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...............:        0
        inequality constraints with only lower bounds:        0
   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  0.0000000e+00 0.00e+00 1.00e+00  -1.0 0.00e+00    -  0.00e+00 0.00e+00   0
   1 -1.0000000e+04 0.00e+00 1.00e+00  -1.7 1.00e+04  -4.0 1.00e+00 1.00e+00f  1
   2 -4.0000000e+04 0.00e+00 1.00e+00  -1.7 3.00e+04  -4.5 1.00e+00 1.00e+00f  1
   3 -1.3000000e+05 0.00e+00 1.00e+00  -1.7 9.00e+04  -5.0 1.00e+00 1.00e+00f  1
   4 -4.0000000e+05 0.00e+00 1.00e+00  -1.7 2.70e+05  -5.4 1.00e+00 1.00e+00f  1
   5 -1.2100000e+06 0.00e+00 1.00e+00  -1.7 8.10e+05  -5.9 1.00e+00 1.00e+00f  1
   6 -3.6400000e+06 0.00e+00 1.00e+00  -1.7 2.43e+06  -6.4 1.00e+00 1.00e+00f  1
   7 -1.0930000e+07 0.00e+00 1.00e+00  -1.7 7.29e+06  -6.9 1.00e+00 1.00e+00f  1
   8 -3.2800000e+07 0.00e+00 1.00e+00  -1.7 2.19e+07  -7.3 1.00e+00 1.00e+00f  1
   9 -9.8410000e+07 0.00e+00 1.00e+00  -1.7 6.56e+07  -7.8 1.00e+00 1.00e+00f  1
iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
  10 -2.9524000e+08 0.00e+00 1.00e+00  -1.7 1.97e+08  -8.3 1.00e+00 1.00e+00f  1
  11 -8.8573000e+08 0.00e+00 1.00e+00  -1.7 5.90e+08  -8.8 1.00e+00 1.00e+00f  1
  12 -2.6572000e+09 0.00e+00 1.00e+00  -1.7 1.77e+09  -9.2 1.00e+00 1.00e+00f  1
  13 -7.9716100e+09 0.00e+00 1.00e+00  -1.7 5.31e+09  -9.7 1.00e+00 1.00e+00f  1
  14 -2.3914840e+10 0.00e+00 1.00e+00  -1.7 1.59e+10 -10.2 1.00e+00 1.00e+00f  1
  15 -7.1744530e+10 0.00e+00 1.00e+00  -1.7 4.78e+10 -10.7 1.00e+00 1.00e+00f  1
  16 -2.1523360e+11 0.00e+00 1.00e+00  -1.7 1.43e+11 -11.2 1.00e+00 1.00e+00f  1
  17 -6.4570081e+11 0.00e+00 1.00e+00  -1.7 4.30e+11 -11.6 1.00e+00 1.00e+00f  1
  18 -1.9371024e+12 0.00e+00 1.00e+00  -1.7 1.29e+12 -12.1 1.00e+00 1.00e+00f  1
  19 -5.8113073e+12 0.00e+00 1.00e+00  -1.7 3.87e+12 -12.6 1.00e+00 1.00e+00f  1
iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
  20 -1.7433922e+13 0.00e+00 1.00e+00  -1.7 1.16e+13 -13.1 1.00e+00 1.00e+00f  1
  21 -5.2301766e+13 0.00e+00 1.00e+00  -1.7 3.49e+13 -13.5 1.00e+00 1.00e+00f  1
  22 -1.5690530e+14 0.00e+00 1.00e+00  -1.7 1.05e+14 -14.0 1.00e+00 1.00e+00f  1
  23 -4.7071589e+14 0.00e+00 1.00e+00  -1.7 3.14e+14 -14.5 1.00e+00 1.00e+00f  1
  24 -1.4121477e+15 0.00e+00 1.00e+00  -1.7 9.41e+14 -15.0 1.00e+00 1.00e+00f  1
  25 -4.2364430e+15 0.00e+00 1.00e+00  -1.7 2.82e+15 -15.5 1.00e+00 1.00e+00f  1
  26 -1.2709329e+16 0.00e+00 1.00e+00  -1.7 8.47e+15 -15.9 1.00e+00 1.00e+00f  1
  27 -3.8127987e+16 0.00e+00 1.00e+00  -1.7 2.54e+16 -16.4 1.00e+00 1.00e+00f  1
  28 -1.1438396e+17 0.00e+00 1.00e+00  -1.7 7.63e+16 -16.9 1.00e+00 1.00e+00f  1
  29 -3.4315189e+17 0.00e+00 1.00e+00  -1.7 2.29e+17 -17.4 1.00e+00 1.00e+00f  1
iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
  30 -1.0294557e+18 0.00e+00 1.00e+00  -1.7 6.86e+17 -17.8 1.00e+00 1.00e+00f  1
  31 -3.0883670e+18 0.00e+00 1.00e+00  -1.7 2.06e+18 -18.3 1.00e+00 1.00e+00f  1
  32 -9.2651009e+18 0.00e+00 1.00e+00  -1.7 6.18e+18 -18.8 1.00e+00 1.00e+00f  1
  33 -2.7795303e+19 0.00e+00 1.00e+00  -1.7 1.85e+19 -19.3 1.00e+00 1.00e+00f  1
  34 -8.3385908e+19 0.00e+00 1.00e+00  -1.7 5.56e+19 -19.7 1.00e+00 1.00e+00f  1
  35 -1.8338591e+20 0.00e+00 1.00e+00  -1.7 1.00e+20 -20.0 1.00e+00 1.00e+00f  1

Number of Iterations....: 35

                                   (scaled)                 (unscaled)
Objective...............:  -1.8338590849833298e+20   -1.8338590849833298e+20
Dual infeasibility......:   1.0000000000000000e+00    1.0000000000000000e+00
Constraint violation....:   0.0000000000000000e+00    0.0000000000000000e+00
Variable bound violation:   0.0000000000000000e+00    0.0000000000000000e+00
Complementarity.........:   0.0000000000000000e+00    0.0000000000000000e+00
Overall NLP error.......:   1.0000000000000000e+00    1.0000000000000000e+00

Number of objective function evaluations             = 36
Number of objective gradient evaluations             = 36
Number of equality constraint evaluations            = 0
Number of inequality constraint evaluations          = 0
Number of equality constraint Jacobian evaluations   = 0
Number of inequality constraint Jacobian evaluations = 0
Number of Lagrangian Hessian evaluations             = 35
Total seconds in IPOPT                               = 0.013

EXIT: Iterates diverging; problem might be unbounded.
cvanaret commented 3 weeks ago

I can reproduce with Uno_jll.jl but not with my local uno_ampl. I'll investigate some more.

cvanaret commented 3 weeks ago

There seems to be a problem with MUMPS_jll.jl the MUMPS options in Uno. My local uno_ampl with MUMPS 5.7.2 reports at the very first iteration with logger=DEBUG3:

Original matrix
Dimension: 1, number of nonzeros: 2
m(0, 0) = 0
m(0, 0) = 0

Testing factorization with regularization factors (0, 0)
Expected inertia (1, 0, 0), got (0, 0, 1)
Number of attempts: 1

Matrix is singular
Testing factorization with regularization factors (0.0001, 3.7606e-09)
Dimension: 1, number of nonzeros: 2
m(0, 0) = 0.0001
m(0, 0) = 0

Factorization was a success

which allows the solver to take large steps and then ultimately to decrease the objective to $< -1e20$. Uno_jll.jl and MUMPS_jll.jl produce:

Original matrix
Dimension: 1, number of nonzeros: 2
m(0, 0) = 0
m(0, 0) = 0

Testing factorization with regularization factors (0, 0)
Inertia is good

which is clearly wrong (the matrix is singular). ~I cannot explain this error at the moment.~ https://github.com/cvanaret/Uno/pull/61 should fix it.