Skip to content
/ Uno Public

A next-gen Lagrange-Newton solver for nonconvex constrained optimization. Unifies barrier and SQP methods in a generic way, and implements various globalization flavors (line search/trust region and merit function/filter method/funnel method). Competitive against filterSQP, IPOPT, SNOPT, MINOS and CONOPT.

License

Notifications You must be signed in to change notification settings

cvanaret/Uno

Folders and files

NameName
Last commit message
Last commit date

Latest commit

bcea64b · Nov 1, 2024
Nov 1, 2024
Oct 29, 2024
Oct 13, 2024
Sep 26, 2024
Jul 28, 2022
Oct 30, 2024
Oct 16, 2024
Jun 19, 2024
Oct 29, 2024
Oct 25, 2024
Jan 6, 2024
Oct 29, 2024
Oct 21, 2024
Sep 13, 2024

Repository files navigation

Uno

A modern, modular solver for nonlinearly constrained nonconvex optimization

Uno (Unifying Nonlinear Optimization) is a C++ library that unifies methods for solving nonlinearly constrained optimization problems of the form:

min x R n   f ( x ) s.t.   c L c ( x ) c U   x L x x U

The theoretical abstract framework for unifying nonlinearly constrained nonconvex optimization was developed by Charlie Vanaret (Argonne National Laboratory & Zuse-Institut Berlin) and Sven Leyffer (Argonne National Laboratory). Uno was designed and implemented by Charlie Vanaret. It is released under the MIT license (see the license file).

The contributors are (in alphabetical order): Oscar Dowson @odow, David Kiessling @david0oo, Alexis Montoison @amontoison, Manuel Schaich @worc4021, Silvio Traversaro @traversaro.

Unit tests on Ubuntu workflow

Unifying nonlinearly constrained nonconvex optimization

We argue that most optimization methods can be broken down into four generic ingredients:

  • a constraint relaxation strategy: a systematic way to relax the nonlinear constraints;
  • a subproblem: a local model of the (possibly relaxed) problem at the current primal-dual iterate;
  • a globalization strategy: an acceptance test of the trial iterate;
  • a globalization mechanism: a recourse action upon rejection of the trial iterate.

Uno 1.0.0 implements the following strategies:

Uno 1.0.0 hypergraph

Any strategy combination can be automatically generated without any programming effort from the user. Note that all combinations do not necessarily result in sensible algorithms, or even convergent approaches. For more details, check out our preprint or my presentation at the ICCOPT 2022 conference.

Uno 1.0.0 implements three presets, that is strategy combinations that correspond to existing solvers (as well as hyperparameter values found in their documentations):

  • filtersqp mimics filterSQP (trust-region feasibility restoration filter SQP method);
  • ipopt mimics IPOPT (line-search feasibility restoration filter barrier method);
  • byrd mimics Byrd's S 1 QP (line-search 1 merit S 1 QP method).

Latest results (September 26, 2024)

Some of Uno combinations that correspond to existing solvers (called presets, see below) have been tested against state-of-the-art solvers on 429 small problems of the CUTEst benchmark. The figure below is a performance profile of Uno and state-of-the-art solvers filterSQP, IPOPT, SNOPT, MINOS, LANCELOT, LOQO and CONOPT; it shows how many problems are solved for a given budget of function evaluations (1 time, 2 times, 4 times, ..., 2 x times the number of objective evaluations of the best solver for each instance).

Performance profile of Uno 1.1.0

All log files can be found here.

How to cite Uno

In an article

We have submitted our paper to the Mathematical Programming Computation journal. The preprint is available on ResearchGate.

Until it is published, you can use the following bibtex entry:

@unpublished{VanaretLeyffer2024,
  author = {Vanaret, Charlie and Leyffer, Sven},
  title = {Unifying nonlinearly constrained nonconvex optimization},
  year = {2024},
  note = {Submitted to Mathematical Programming Computation}
}

On social media

To mention Uno on Twitter, use @UnoSolver.
To mention Uno on LinkedIn, use #unosolver.

Installation instructions

See the INSTALL file.

Solving a problem with Uno

At the moment, Uno only reads models from .nl files. A couple of CUTEst instances are available in the /examples directory.

To solve an AMPL model, type in the build directory: ./uno_ampl model.nl -AMPL [key=value ...]
where [key=value ...] is a list of options.

To use Uno with Julia/JuMP, a solution in the short term is to use the package AmplNLWriter.jl to dump JuMP models into .nl files.

Combination of ingredients

To pick a globalization mechanism, use the argument (choose one of the possible options in brackets): globalization_mechanism=[LS|TR]
To pick a constraint relaxation strategy, use the argument: constraint_relaxation_strategy=[feasibility_restoration|l1_relaxation]
To pick a globalization strategy, use the argument: globalization_strategy=[l1_merit|fletcher_filter_method|waechter_filter_method|funnel_method]
To pick a subproblem method, use the argument: subproblem=[QP|LP|primal_dual_interior_point]
The options can be combined in the same command line.

For an overview of the available strategies, type: ./uno_ampl --strategies

To pick a preset, use the argument: preset=[filtersqp|ipopt|byrd]