The Uno (Unifying Nonconvex Optimization) solver

Specific Domains Optimization (Mathematical)
, , ,
1

Dear all,

For the past 6 years, I have been working (on and off, this year full time) on Uno, a modular C++ solver for nonconvex optimization. It unifies the workflows of most gradient-based iterative methods (such as SQP and barrier methods) and allows the automatic combination of off-the-shelf strategies for step computation, globalization and constraint relaxation. It mimics existing solvers such as IPOPT, filterSQP and SNOPT, but also generates thoroughly novel optimization methods.

hypergraph
hypergraph1858×294 59.5 KB

I have just published the preprint Unifying nonlinearly constrained nonconvex optimization cowritten with Sven Leyffer (Argonne National Laboratory).
The code is available on Github as open-source software under the MIT license.

At the moment, Uno only reads models from .nl files (AMPL). Interfaces to CasADi and Matlab are being independently developed and I’m confident more interfaces will be available soon. Until a Julia/JuMP interface is available, you can dump your JuMP model into an .nl file with the AmplNLWriter.jl library.

Future developments include L-BFGS Hessian approximation, funnel method (with David Kiessling), trust-region barrier method, SLP-EQP method, parameterizable numerical type (double, float, quad precision and so on) and extension to broader classes of problems (problems with complementarity constraints, robust optimization).

Give Uno a try and give us some feedback :slight_smile:

30 Likes
2

I guess we should make a Yggdrasil build so that we can install it automatically.

8 Likes
3

Don’t miss us at ISMP next week!
Sven will give the keynote presentation Unifying nonlinearly constrained optimization on July 23 (Tuesday) at 3pm. I will give the talk Uno, a next-gen solver for unifying nonlinearly constrained nonconvex optimization on July 26 (Friday) at 9am.
See you then :slight_smile:

2 Likes
4

Uno 1.1.0 is out! It now features:

  • an interface to the open-source linear solver MUMPS.
  • a new globalization strategy (a strategy that accepts or rejects trial iterates) called funnel method. According to our tests, it performs at least better than filter methods (IPOPT, filterSQP), while easier to implement.
3 Likes
5

This solver could potentially be useful for Model Predictive Control (MPC), is this something you or any of your colleagues have tried? Do you have any feeling for what kind of overhead the AmplNLWriter interface adds? I have a feeling this would be prohibitive for using UNO for MPC from julia?

6

I haven’t, but Uno’s main beta tester David Kiessling is writing his PhD on MPC. We’ve discussed future Uno developments that would benefit MPC, in particular quasi-Newton Hessian approximations and exploiting the structure of the problem. I’m interested to see how Uno will hold up compared to state-of-the-art solvers!

At the moment, AmplNLWriter is just the easy way between Julia and Uno, but it’s probably not the most efficient way indeed. Ideally, I’d need a JuMP interface. To be developed :slight_smile:

1 Like
7

Here are the latest numerical results (Sept 26, 2024) of Uno against filterSQP, IPOPT, SNOPT, MINOS, LANCELOT, LOQO and CONOPT on 429 small CUTEst test problems. It is a Dolan-Moré performance profile (the higher and the more to the left, the better).

uno_performance_profile
uno_performance_profile1616×997 130 KB

3 Likes
8

I think the blocker for writing a Julia interface was being able to compile it. Did we make any progress since [Uno] add initial build_tarballs.jl by odow · Pull Request #8937 · JuliaPackaging/Yggdrasil · GitHub?

9

Is there any plan to provide IPOPT-like C API for Uno? I think it is the prerequisite for a Julia Interface and I plan to support it in PyOptInterface, too.

10

Yes, I’ll work on that at some point. It might be helpful for other interfaces as well.

1 Like
11

Will more LP/QP solvers like HiGHS, Gurobi, COPT be supported in the future? I see that you have prepared abstractions to support multiple LP/QP solvers in the codebase.

I am also curious about the decision to use BQPD as the primary LP/QP solver. Does it have special advantages compared with other solvers?

1 Like
12

Charlie, do you think that we could be allowed to cross-compile BQPD and get a BQPD_jll.jl with Yggdrasil so that we can use it in Uno_jll.jl?

13

Yes, the abstractions are here, only time is missing :smile: I plan to interface at least HiGHS in the near future.

We started with BQPD because originally, Uno was meant to be a modern version of filterSQP (which uses BQPD). It is a nonconvex QP solver (it accommodates indefinite Hessians) and is matrix-free (it requires only Hessian-vector products, even though in practice we do form the explicit Hessian).
@amontoison that’s a good idea. Let me ask Sven when we meet on Thursday.

Uno’s development is a one-person endeavor, so my to-do list tends to grow faster than it shrinks. If you know someone who would be willing to invest a bit of time and energy into Uno, please have them reach out :slight_smile:

4 Likes
14

Just to update this thread:

Uno can now be installed automatically via Uno_jll.jl, and used via AmplNLWriter.jl.

Here’s an example:

julia> using AmplNLWriter, JuMP, Uno_jll

julia> model = Model(() -> AmplNLWriter.Optimizer(Uno_jll.amplexe));

julia> @variable(model, x);

julia> @variable(model, y);

julia> @objective(model, Min, (1 - x)^2 + 100 * (y - x^2)^2);

julia> optimize!(model)
Original model /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_bVsNQH/model.nl
2 variables, 0 constraints
Reformulated model /var/folders/bg/dzq_hhvx1dxgy6gb5510pxj80000gn/T/jl_bVsNQH/model.nl_scaled_equalityconstrained_boundrelaxed
2 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   │ -              │ -            │ 1           │ 2            │ 0               │ initial point          │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 1     │ 1       │ 0.1            │ 1           │ OPT   │ 0              │ 1            │ 100         │ -            │ -               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -     │ 2       │ -              │ 0.5         │ -     │ -              │ 0.5          │ 6.5         │ -            │ -               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -     │ 3       │ -              │ 0.25        │ -     │ -              │ 0.25         │ 0.953125    │ 12.5         │ 0               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 2     │ 1       │ 0.1            │ 1           │ OPT   │ 0              │ 0.0902778    │ 0.483206    │ 1.01166      │ 0               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 3     │ 1       │ 0.1            │ 1           │ OPT   │ 0              │ 0.429389     │ 3.46968     │ -            │ -               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -     │ 2       │ -              │ 0.5         │ -     │ -              │ 0.214695     │ 0.457088    │ 9.5274       │ 0               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 4     │ 1       │ 0.1            │ 1           │ OPT   │ 0              │ 0.0950542    │ 0.188942    │ 0.415353     │ 0               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 5     │ 1       │ 0.02           │ 1           │ OPT   │ 0              │ 0.349223     │ 0.901785    │ -            │ -               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -     │ 2       │ -              │ 0.5         │ -     │ -              │ 0.174612     │ 0.139187    │ 6.5051       │ 0               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 6     │ 1       │ 0.02           │ 1           │ OPT   │ 0              │ 0.092873     │ 0.054941    │ 0.451043     │ 0               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 7     │ 1       │ 0.02           │ 1           │ OPT   │ 0              │ 0.248802     │ 0.0720927   │ -            │ -               │ rejected (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ -     │ 2       │ -              │ 0.5         │ -     │ -              │ 0.124401     │ 0.0291446   │ 2.26614      │ 0               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 8     │ 1       │ 0.02           │ 1           │ OPT   │ 0              │ 0.11047      │ 0.00985865  │ 1.15467      │ 0               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 9     │ 1       │ 0.02           │ 1           │ OPT   │ 0              │ 0.100021     │ 0.00232375  │ 1.00373      │ 0               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ iter  │ LS iter │ barrier param. │ step length │ phase │ regularization │ step norm    │ objective   │ stationarity │ complementarity │ status                 │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 10    │ 1       │ 0.02           │ 1           │ OPT   │ 0              │ 0.0509267    │ 0.000237972 │ 0.218984     │ 0               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 11    │ 1       │ 0.02           │ 1           │ OPT   │ 0              │ 0.0253247    │ 4.92674e-06 │ 0.0595169    │ 0               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 12    │ 1       │ 0.00282843     │ 1           │ OPT   │ 0              │ 0.00319684   │ 2.81895e-09 │ 0.000831455  │ 0               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 13    │ 1       │ 1.84491e-06    │ 1           │ OPT   │ 0              │ 9.78057e-05  │ 8.88178e-16 │ 8.67623e-07  │ 0               │ accepted (f-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 14    │ 1       │ 2.5059e-09     │ 1           │ OPT   │ 0              │ 4.65423e-08  │ 0           │ 2.46136e-13  │ 0               │ accepted (f-type)      │
└───────┴─────────┴────────────────┴─────────────┴───────┴────────────────┴──────────────┴─────────────┴──────────────┴─────────────────┴────────────────────────┘

Uno 1.1.0 (LS feasibility_restoration waechter_filter_method primal_dual_interior_point)
Mon Oct 28 19:21:41 2024
────────────────────────────────────────
Status:					Converged with feasible KKT point
Objective value:			0
Primal feasibility:			0
┌ Stationarity residual:		2.461364e-13
└ Complementarity residual:		0
┌ Feasibility stationarity residual:	2.461364e-13
└ Feasibility complementarity residual:	0
┌ Infeasibility measure:		0
│ Objective measure:			0
└ Auxiliary measure:			0
Primal solution:			1 1 
┌ Constraint multipliers:		
│ Lower bound multipliers:		0 0 
└ Upper bound multipliers:		0 0 
┌ Constraint feasibility multipliers:	
│ Lower bound feasibility multipliers:	0 0 
└ Upper bound feasibility multipliers:	0 0 
Objective multiplier:			1
CPU time:				0.00863s
Iterations:				14
Objective evaluations:			20
Constraints evaluations:		0
Objective gradient evaluations:		16
Jacobian evaluations:			0
Hessian evaluations:			14
Number of subproblems solved:		14

julia> solution_summary(model)
* Solver : AmplNLWriter

* Status
  Result count       : 1
  Termination status : LOCALLY_SOLVED
  Message from the solver:
  "Uno 1.1.0: Converged with feasible KKT point"

* Candidate solution (result #1)
  Primal status      : FEASIBLE_POINT
  Dual status        : NO_SOLUTION
  Objective value    : 4.43734e-29
  Dual objective value : 4.43734e-29

* Work counters
  Solve time (sec)   : 3.24550e-01
14 Likes
15

I’m really grateful to @odow and @amontoison for their time (and their patience)!
Note that at the moment, the ipopt preset (whose strategy combination mimics IPOPT) is the only available preset in Uno_jll.jl (it invokes the linear solver MUMPS_jll.jl).

If you add constraints to Oscar’s model, you get my favorite problem hs015.mod:

julia> using AmplNLWriter, JuMP, Uno_jll

julia> model = Model(() -> AmplNLWriter.Optimizer(Uno_jll.amplexe));

julia> @variable(model, x <= 0.5, start = -2);

julia> @variable(model, y, start = 1);

julia> @objective(model, Min, 100 * (y - x^2)^2 + (1 - x)^2);

julia> @constraint(model, x*y >= 1);

julia> @constraint(model, x + y^2 >= 0);

julia> optimize!(model)
Original model /tmp/jl_cyAI59/model.nl
2 variables, 2 constraints
Reformulated model /tmp/jl_cyAI59/model.nl_scaled_equalityconstrained_boundrelaxed
4 variables, 2 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   │ primal feas.  │ stationarity │ complementarity │ status                 │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼───────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 0     │ -       │ -              │ -           │ OPT   │ -              │ -            │ 37.7805     │ 4.02          │ 39.2084      │ 2.5             │ initial point          │
│ 1     │ 1       │ 0.1            │ 1           │ OPT   │ 0              │ 0.0233907    │ 35.6959     │ 3.955         │ 107.546      │ 1.52938         │ accepted (h-type)      │
│ 2     │ 1       │ 0.1            │ 1           │ OPT   │ 0              │ 1.98766      │ 1.04159     │ 1.24585       │ 178.176      │ 0.262071        │ accepted (h-type)      │
│ 3     │ 1       │ 0.1            │ 1           │ OPT   │ 0              │ 0.553065     │ 0.40318     │ 1.53048       │ 185.734      │ 0.107792        │ accepted (h-type)      │
│ 4     │ 1       │ 0.1            │ 1           │ OPT   │ 10000          │ 0.00125483   │ 0.39945     │ 1.52798       │ 179.337      │ 0.0780677       │ accepted (h-type)      │
│ 5     │ 1       │ 0.1            │ 1           │ OPT   │ 0              │ 2.07556      │ 15.8289     │ 4.80884       │ -            │ -               │ rejected (filter)      │
│ -     │ 2       │ -              │ 0.5         │ -     │ -              │ 1.03778      │ 2.9258      │ 1.9662        │ -            │ -               │ rejected (filter)      │
│ -     │ 3       │ -              │ 0.25        │ -     │ -              │ 0.518889     │ 0.314168    │ 1.44654       │ 369.218      │ 0.120012        │ accepted (h-type)      │
│ 6     │ 1       │ 0.1            │ 1           │ OPT   │ 3333.33        │ 0.00264217   │ 0.314141    │ 1.44304       │ 362.915      │ 0.0110483       │ accepted (h-type)      │
│ 7     │ 1       │ 0.1            │ 1           │ OPT   │ 1111.11        │ 0.000795601  │ 0.314547    │ 1.44252       │ 363.966      │ 0.0110967       │ accepted (h-type)      │
│ 8     │ 1       │ 0.1            │ 1           │ OPT   │ 2962.96        │ 0.18222      │ 0.339671    │ 1.33278       │ 20376.9      │ 15.7265         │ accepted (h-type)      │
│ 9     │ 1       │ 0.1            │ 1           │ OPT   │ 0              │ 0.00395733   │ 0.342921    │ 1.33029       │ 18813.5      │ 14.5924         │ accepted (h-type)      │
│ 10    │ 1       │ 0.1            │ 1           │ OPT   │ 0              │ 2.16096      │ 12.7717     │ 2.15844       │ -            │ -               │ rejected (filter)      │
│ -     │ 2       │ -              │ 0.5         │ -     │ -              │ 1.08048      │ 4.31384     │ 1.20475       │ 16589.6      │ 12.6198         │ accepted (h-type)      │
│ 11    │ 1       │ 0.1            │ 1           │ OPT   │ 0              │ 0.630084     │ 5.8819      │ 0.952354      │ 1007.7       │ 0.463586        │ accepted (h-type)      │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼───────────────┼──────────────┼─────────────────┼────────────────────────┤
│ iter  │ LS iter │ barrier param. │ step length │ phase │ regularization │ step norm    │ objective   │ primal feas.  │ stationarity │ complementarity │ status                 │
├───────┼─────────┼────────────────┼─────────────┼───────┼────────────────┼──────────────┼─────────────┼───────────────┼──────────────┼─────────────────┼────────────────────────┤
│ 12    │ 1       │ 0.1            │ 1           │ OPT   │ 0              │ 2.28896      │ 12.7534     │ 0.316297      │ 969.044      │ 0.206543        │ accepted (h-type)      │
│ 13    │ 1       │ 0.1            │ 1           │ OPT   │ 0              │ 0.318652     │ 12.763      │ 4.01388e-07   │ 0.237094     │ 0.107368        │ accepted (h-type)      │
│ 14    │ 1       │ 0.02           │ 1           │ OPT   │ 0              │ 0.00351111   │ 12.779      │ 1.01312e-06   │ 0.000127402  │ 0.0200148       │ accepted (f-type)      │
│ 15    │ 1       │ 0.000150424    │ 1           │ OPT   │ 0              │ 0.00955038   │ 12.7393     │ 6.68257e-06   │ 5.06342e-05  │ 0.000192227     │ accepted (f-type)      │
│ 16    │ 1       │ 1.84491e-06    │ 1           │ OPT   │ 0              │ 7.29582e-05  │ 12.739      │ 4.68065e-10   │ 3.49192e-09  │ 1.848e-06       │ accepted (f-type)      │
│ 17    │ 1       │ 2.5059e-09     │ 1           │ OPT   │ 0              │ 8.86474e-07  │ 12.739      │ 5.82867e-14   │ 4.13891e-13  │ 2.50627e-09     │ accepted (f-type)      │
└───────┴─────────┴────────────────┴─────────────┴───────┴────────────────┴──────────────┴─────────────┴───────────────┴──────────────┴─────────────────┴────────────────────────┘

Uno 1.1.0 (LS feasibility_restoration waechter_filter_method primal_dual_interior_point)
Thu Oct 31 14:46:55 2024
────────────────────────────────────────
Status:					Converged with feasible KKT point
Objective value:			306.5
Primal feasibility:			5.240253e-14
┌ Stationarity residual:		4.138911e-13
└ Complementarity residual:		2.506267e-09
┌ Feasibility stationarity residual:	4.138911e-13
└ Feasibility complementarity residual:	2.506267e-09
┌ Infeasibility measure:		5.828671e-14
│ Objective measure:			12.73898
└ Auxiliary measure:			1.146775e-07
Primal solution:			0.5 2 1 4.5 
┌ Constraint multipliers:		700 1.339957e-08 
│ Lower bound multipliers:		0 0 29.09393 5.569483e-10 
└ Upper bound multipliers:		-1751 0 0 0 
┌ Constraint feasibility multipliers:	0 0 
│ Lower bound feasibility multipliers:	0 0 0 0 
└ Upper bound feasibility multipliers:	0 0 0 0 
Objective multiplier:			1
CPU time:				0.00495s
Iterations:				17
Objective evaluations:			21
Constraints evaluations:		22
Objective gradient evaluations:		19
Jacobian evaluations:			19
Hessian evaluations:			17
Number of subproblems solved:		17
3 Likes
16

Uno 1.3.0 now features:

  • an interface to the LP solver HiGHS, available via the option LP_solver=HiGHS (QP coming soon!);
  • a new preset filterslp (a trust-region restoration filter Sequential Linear Programming), available via the option preset=filterslp.

Here’s the same example (hs015.mod) as in the previous message solved with the filterslp preset:

using JuMP, AmplNLWriter, Uno_jll

function Optimizer()
   # pass options here
   options = String["preset=filterslp", "LP_solver=HiGHS"]
   return AmplNLWriter.Optimizer(Uno_jll.amplexe, options)
end
       
model = Model(() -> Optimizer());
@variable(model, x <= 0.5, start = -2);
@variable(model, y, start = 1);
@objective(model, Min, 100 * (y - x^2)^2 + (1 - x)^2);
@constraint(model, x*y >= 1);
@constraint(model, x + y^2 >= 0);
optimize!(model)

Original model /tmp/jl_EMUrZq/model.nl
2 variables, 2 constraints
Reformulated model /tmp/jl_EMUrZq/model.nl
2 variables, 2 constraints

Used overwritten options:
- LP_solver = HiGHS
- TR_min_radius = 1e-8
- TR_radius = 10
- constraint_relaxation_strategy = feasibility_restoration
- filter_type = standard
- globalization_mechanism = TR
- globalization_strategy = fletcher_filter_method
- l1_constraint_violation_coefficient = 1.
- loose_tolerance = 1e-4
- progress_norm = L1
- protect_actual_reduction_against_roundoff = no
- residual_norm = L2
- sparse_format = CSC
- subproblem = LP
- switch_to_optimality_requires_linearized_feasibility = yes
- tolerance = 1e-5

─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
 iter   TR iter  TR radius    phase  step norm   objective   primal feas  stationarity  complementarity  status          
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
 0      -        1.0000e+01   OPT    -           9.0900e+02  4.0000e+00   2.4797e+03    0.0000e+00       initial point   
 1      1        1.0000e+01   OPT    2.5000e+00  2.5250e+01  6.2500e-01   2.3805e+03    1.8750e+02       ✔ (f-type)      
 2      1        1.0000e+01   OPT    1.2500e+00  3.0650e+02  0.0000e+00   5.5902e+02    0.0000e+00       ✔ (h-type)      
 3      1        1.0000e+01   OPT    0.0000e+00  3.0650e+02  0.0000e+00   0.0000e+00    0.0000e+00       0 primal step   
─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

Uno 1.3.0 (TR feasibility_restoration fletcher_filter_method LP)
Mon Nov 18 10:12:16 2024
────────────────────────────────────────
Status:					                   Converged with feasible KKT point
Objective value:			               306.5
Primal feasibility:			               0
┌ Stationarity residual:		           0
└ Complementarity residual:		           0
┌ Feasibility stationarity residual:	   0
└ Feasibility complementarity residual:	   0
┌ Infeasibility measure:		           0
│ Objective measure:			           306.5
└ Auxiliary measure:			           0
CPU time:				                   0.003727s
Iterations:				                   3
Objective evaluations:			           4
Constraints evaluations:		           4
Objective gradient evaluations:            4
Jacobian evaluations:			           4
Hessian evaluations:			           0
Number of subproblems solved:		       3
3 Likes
17

This is really interesting. I’ve been watching Uno for a long time because the problems I work on (Gaussian process MLE computation) really seem to benefit from the trust region paradigm, and an open-source library that mimics filtersqp seems like a really great new tool.

How distant is the feature of direct access to Uno in the sense of not needing to go through AMPL? I have always assumed that AMPL really was for settings where people could write their problem pretty simply in closed form like the hs* examples. But my code applications often look like this:


using StaticArrays, LinearAlgebra, BesselK, JuMP, AmplNLWriter, Uno_jll, Ipopt, ForwardDiff

Optimizer() = AmplNLWriter.Optimizer(Uno_jll.amplexe, String["preset=ipopt"])

# Generate some fake data to fit a GP model to.
const pts = rand(SVector{2,Float64}, 100)
const sim = let K = [matern(x, y, (1.0, 0.1, 0.75)) for x in pts, y in pts]
  L = cholesky(Symmetric(K)).L
  L*randn(length(pts))
end

# negative log-likelihood for GP data with three-parameter Matern model.
function _nll(pv)
  K  = [matern(x, y, pv) for x in pts, y in pts]
  Kf = cholesky!(Symmetric(K))
  (logdet(Kf) + sum(abs2, Kf.U'\sim))/2
end

# If the optimizer steps somewhere infeasible or just takes the range param. to a huge
# number, the Cholesky will fail. So this try-catch is necessary to avoid a hard
# crash that the optimizer doesn't recover from.
nll(p...) = (try; return _nll(p); catch; return NaN; end)

# MLE computation:
function mle()
  model = Model(Ipopt.Optimizer) # Model(()->Optimizer())
  @variable(model, 0.0  <= scale,             start=1.0)
  @variable(model, 0.0  <= range,             start=0.01)
  @variable(model, 0.25 <= smoothness <= 5.0, start=1.0)
  @operator(model, op_nll, 3, nll)
  @objective(model, Min, op_nll(scale, range, smoothness))
  optimize!(model)
  JuMP.is_solved_and_feasible(model) || throw(error("Optimization failed!"))
  value.([scale, range, smoothness])
end

As you can see I did out of curiosity try the AMPL interface, but predictably this setting where my objective function sort of requires carrying around a ton of information doesn’t work. I have no idea how much additional work it is to allow users to access the solver by providing objective/constraint, objective grad/constraint jacobian, and Lagrangian Hessian (like Ipopt and I’m sure many others). But as soon as that is possible, I will probably migrate a lot of workflows over!

Also, off-topic, but this @operator syntax is pretty nice! Thanks @odow.

18

How distant is the feature of direct access to Uno in the sense of not needing to go through AMPL?

I assume, distant. It requires someone to write a C API a la Ipopt.

Using @operator with AmplNLWriter is not on the roadmap. In theory it is possible, but it requires being able to compile a C shared library on the user’s machine. Perhaps we could revisit once static compilation with Julia is trivial.

Finally, note that you cannot use filtersqp through Uno_jll because we cannot distribute the non-free BQPD, which Uno uses to solve QPs.

1 Like
19

Oof. Brutal, brutal, and brutal. I’d still love to find a way to use this somehow, but I suppose I’ll have to stay patient. Just dreaming of the day I stop paying for KNITRO…

20

Thanks @cgeoga! As @odow said, we’ll need a proper C API. It’s of course on my to-do list (like many other things :sweat_smile:).

Good news: we started discussions about extending the HiGHS QP solver to indefinite quadratic optimization. This would be a great open-source alternative to BQPD and we could finally run the filtersqp preset in Uno the way it was meant to be.

4 Likes