search

cvanaret / Uno

A next-gen solver for nonconvex optimization. Uno is a Lagrange-Newton solver that 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
257 stars 19 forks source link

Behavior when gradient is undefined at starting point #39

Open odow opened 5 days ago

odow commented 5 days ago

The initial value and gradient is undefined because the start value is y = 0 and there is 1 / y^2

This could be classified as expected behavior?

Ipopt is able to solve the model.

Uno

julia> using JuMP, AmplNLWriter, Uno_jll

julia> begin
           model = Model() do
               return AmplNLWriter.Optimizer(Uno_jll.amplexe; directory = "/tmp/uno")
           end
           set_attribute(model, "preset", "ipopt")
           set_attribute(model, "linear_solver", "MUMPS")
           @variable(model, x >= 0)
           @variable(model, y >= 0)
           @objective(model, Min, x + y)
           @constraint(model, y >= 1 / (x + 0.1) - 0.5)
           @constraint(model, x >= y^(-2) - 0.5)
           @constraint(model, 4 / (x + y + 0.1) >= 1)
           optimize!(model)
           solution_summary(model)
       end
Model /tmp/uno/model.nl
Options:
- AMPL_write_solution_to_file = yes
- BQPD_kmax = 500
- BQPD_print_subproblem = no
- LP_solver = BQPD
- LS_backtracking_ratio = 0.5
- LS_min_step_length = 5e-7
- LS_scale_duals_with_step_length = yes
- QP_solver = BQPD
- TR_activity_tolerance = 1e-6
- TR_aggressive_decrease_factor = 4
- TR_decrease_factor = 2
- TR_increase_factor = 2
- TR_min_radius = 1e-7
- TR_radius = 10.
- TR_radius_reset_threshold = 1e-4
- armijo_decrease_fraction = 1e-8
- armijo_tolerance = 1e-9
- barrier_damping_factor = 1e-5
- barrier_default_multiplier = 1
- barrier_initial_parameter = 0.1
- barrier_k_epsilon = 10
- barrier_k_mu = 0.2
- barrier_k_sigma = 1e10
- barrier_push_variable_to_interior_k1 = 1e-2
- barrier_push_variable_to_interior_k2 = 1e-2
- barrier_regularization_exponent = 0.25
- barrier_small_direction_factor = 10.
- barrier_smax = 100
- barrier_tau_min = 0.99
- barrier_theta_mu = 1.5
- barrier_update_fraction = 10
- constraint_relaxation_strategy = feasibility_restoration
- convexify_QP = false
- dual_regularization_fraction = 1e-8
- enforce_linear_constraints = no
- filter_beta = 0.99999
- filter_capacity = 50
- filter_fact = 1e4
- filter_gamma = 1e-8
- filter_sufficient_infeasibility_decrease_factor = 0.9
- filter_switching_infeasibility_exponent = 1.1
- filter_type = standard
- filter_ubd = 1e4
- function_scaling_factor = 100
- function_scaling_threshold = 100
- funnel_beta = 0.9999
- funnel_fact = 1.5
- funnel_gamma = 0.001
- funnel_kappa = 0.5
- funnel_require_acceptance_wrt_current_iterate = no
- funnel_ubd = 1.0
- funnel_update_strategy = 1
- globalization_mechanism = LS
- globalization_strategy = waechter_filter_method
- hessian_model = exact
- l1_constraint_violation_coefficient = 1000.
- l1_relaxation_decrease_factor = 10.
- l1_relaxation_epsilon1 = 0.1
- l1_relaxation_epsilon2 = 0.1
- l1_relaxation_fixed_parameter = no
- l1_relaxation_initial_parameter = 1.
- l1_relaxation_residual_small_threshold = 1e-12
- l1_small_duals_threshold = 1e-10
- least_square_multiplier_max_norm = 1e3
- linear_solver = MUMPS
- logger = INFO
- loose_tolerance = 1e-6
- loose_tolerance_consecutive_iteration_threshold = 15
- max_iterations = 2000
- nonmonotone_filter_number_dominated_entries = 3
- primal_regularization_decrease_factor = 3.
- primal_regularization_fast_increase_factor = 100.
- primal_regularization_initial_factor = 1e-4
- primal_regularization_lb = 1e-20
- primal_regularization_slow_increase_factor = 8.
- print_solution = no
- progress_norm = L1
- protect_actual_reduction_against_roundoff = yes
- regularization_failure_threshold = 1e40
- regularization_increase_factor = 2
- regularization_initial_value = 1e-4
- residual_norm = INF
- residual_scaling_threshold = 100.
- scale_functions = yes
- scale_residuals = yes
- sparse_format = COO
- statistics_LS_step_length_column_order = 10
- statistics_SOC_column_order = 9
- statistics_TR_radius_column_order = 10
- statistics_barrier_parameter_column_order = 8
- statistics_complementarity_column_order = 105
- statistics_dual_feasibility_column_order = 102
- statistics_funnel_width_column_order = 25
- statistics_major_column_order = 1
- statistics_minor_column_order = 2
- statistics_objective_column_order = 100
- statistics_penalty_parameter_column_order = 5
- statistics_primal_feasibility_column_order = 101
- statistics_print_header_every_iterations = 15
- statistics_regularization_column_order = 21
- statistics_restoration_phase_column_order = 20
- statistics_stationarity_column_order = 104
- statistics_status_column_order = 200
- statistics_step_norm_column_order = 31
- subproblem = primal_dual_interior_point
- switch_to_optimality_requires_linearized_feasibility = no
- switching_delta = 1
- switching_infeasibility_exponent = 2
- threshold_unsuccessful_attempts = 8
- time_limit = inf
- tolerance = 1e-8
- unbounded_objective_threshold = -1e20
A numerical error was encountered while evaluating a gradient

* Solver : AmplNLWriter

* Status
  Result count       : 0
  Termination status : OTHER_ERROR
  Message from the solver:
  "Error calling the solver. The solver executed normally, but no `.sol` file was created. This usually means that there is an issue with the formulation of your model. Check the solver's logs for details."

* Candidate solution (result #1)
  Primal status      : NO_SOLUTION
  Dual status        : NO_SOLUTION

* Work counters
  Solve time (sec)   : 5.04861e-02

Ipopt

julia> using JuMP, AmplNLWriter, Ipopt_jll

julia> begin
           model = Model() do
               return AmplNLWriter.Optimizer(Ipopt_jll.amplexe; directory = "/tmp/uno")
           end
           @variable(model, x >= 0)
           @variable(model, y >= 0)
           @objective(model, Min, x + y)
           @constraint(model, y >= 1 / (x + 0.1) - 0.5)
           @constraint(model, x >= y^(-2) - 0.5)
           @constraint(model, 4 / (x + y + 0.1) >= 1)
           optimize!(model)
           solution_summary(model)
       end
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.:        6
Number of nonzeros in Lagrangian Hessian.............:        3

Error in an AMPL evaluation. Run with "halt_on_ampl_error yes" to see details.
Error evaluating Jacobian of inequality constraints at user provided starting point.
  No scaling factors for inequality constraints computed!
Total number of variables............................:        2
                     variables with only lower bounds:        2
                variables with lower and upper bounds:        0
                     variables with only upper bounds:        0
Total number of equality constraints.................:        0
Total number of inequality constraints...............:        3
        inequality constraints with only lower bounds:        3
   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.9999980e-02 1.00e+04 1.00e+00  -1.0 0.00e+00    -  0.00e+00 0.00e+00   0
   1  1.2970166e-01 4.44e+03 1.54e+00  -1.0 3.05e+01    -  6.73e-01 1.00e+00h  1
   2  3.3093968e-01 1.97e+03 5.50e+00  -1.0 7.03e-01    -  9.90e-01 1.00e+00h  1
   3  6.7513596e-01 8.68e+02 2.15e+00  -1.0 3.06e+01    -  5.84e-01 1.00e+00h  1
   4  1.1679898e+00 3.54e+02 7.81e-01  -1.0 8.04e+01    -  8.69e-01 1.00e+00h  1
   5  1.5899014e+00 1.25e+02 5.99e-01  -1.0 1.43e+01  -4.0 1.00e+00 1.00e+00h  1
   6  1.1438428e+00 2.23e+00 2.18e+00  -1.0 1.06e+03    -  1.16e-01 1.00e+00h  1
   7  1.0968948e+00 4.12e+00 1.24e+00  -1.0 1.23e+03    -  4.33e-01 3.41e-02H  1
   8  1.2596142e+00 6.00e+00 6.71e-01  -1.0 1.82e+01    -  1.00e+00 6.48e-01h  1
   9  1.5288200e+00 3.26e-01 2.96e-01  -1.0 1.12e+01    -  5.90e-01 1.00e+00f  1
iter    objective    inf_pr   inf_du lg(mu)  ||d||  lg(rg) alpha_du alpha_pr  ls
  10  1.5175081e+00 6.73e-01 5.20e-02  -1.0 1.19e+01    -  1.00e+00 9.39e-01h  1
  11  1.5389696e+00 8.57e-02 2.72e-01  -1.7 1.95e-01    -  9.43e-01 1.00e+00h  1
  12  1.5530770e+00 3.61e-02 4.23e-02  -1.7 2.67e-01    -  1.00e+00 8.88e-01h  1
  13  1.5512281e+00 0.00e+00 1.20e-02  -2.5 3.89e-02    -  1.00e+00 1.00e+00h  1
  14  1.5452320e+00 0.00e+00 5.49e-05  -3.8 1.50e-02    -  1.00e+00 1.00e+00h  1
  15  1.5449761e+00 0.00e+00 5.00e-08  -5.7 6.09e-04    -  1.00e+00 1.00e+00h  1
  16  1.5449724e+00 0.00e+00 1.96e-11  -8.6 6.17e-06    -  1.00e+00 1.00e+00h  1

Number of Iterations....: 16

                                   (scaled)                 (unscaled)
Objective...............:   1.5449723892994804e+00    1.5449723892994804e+00
Dual infeasibility......:   1.9611753075064438e-11    1.9611753075064438e-11
Constraint violation....:   0.0000000000000000e+00    0.0000000000000000e+00
Variable bound violation:   0.0000000000000000e+00    0.0000000000000000e+00
Complementarity.........:   2.5161366532942358e-09    2.5161366532942358e-09
Overall NLP error.......:   2.5161366532942358e-09    2.5161366532942358e-09

Number of objective function evaluations             = 18
Number of objective gradient evaluations             = 17
Number of equality constraint evaluations            = 0
Number of inequality constraint evaluations          = 18
Number of equality constraint Jacobian evaluations   = 0
Number of inequality constraint Jacobian evaluations = 17
Number of Lagrangian Hessian evaluations             = 16
Total seconds in IPOPT                               = 0.007

EXIT: Optimal Solution Found.
* Solver : AmplNLWriter

* Status
  Result count       : 1
  Termination status : LOCALLY_SOLVED
  Message from the solver:
  "Ipopt 3.14.16: Optimal Solution Found"

* Candidate solution (result #1)
  Primal status      : FEASIBLE_POINT
  Dual status        : FEASIBLE_POINT
  Objective value    : 1.54497e+00
  Dual objective value : 1.54497e+00

* Work counters
  Solve time (sec)   : 3.55769e-01
cvanaret commented 5 days ago

Ah! That's an interesting one :) Uno's ipopt preset performs function scaling (using the gradients at the initial point), THEN perturbs the primal point such that it doesn't sit at its bounds. IPOPT seems to be doing the opposite (perturb the bounds THEN scale), which makes total sense. But it's the kind of things that are not really documented... I will implement the same behavior as IPOPT, which should fix the issue.

odow commented 5 days ago

But it's the kind of things that are not really documented...

Hahahahaha. Yeah. I guess this is why it's helpful to have a fairly comprehensive test suite.

So far, I've run only MINLPTests.jl. Once we fix the dual issue I can run the much larger set of MOI.Test.runtests (I didn't for now, because too many things will fail).