JuliaSmoothOptimizers / JuliaSmoothOptimizers/SolverTools.jl

Implement merit functions and make it work with line search and trust region

Open
#143 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Julia
Stars
24
Forks
18
PR merge metrics
No merged PRs in 30d

Description

Short draft on the design of merit functions

Examples of merit functions for equality-constrained problems:
- `l1` and `l2`: `phi(x, eta) = f(x) + eta * |c(x)|_p`, where `p = 1` or `p = 2`.
- `l2` squared (what is the name of this one again?): `phi(x, eta) = f(x) + eta * |c(x)|_2^2 / 2`.
- Fletcher: `phi(x, eta) = f(x) - y(x)' * c(x) + eta * |c(x)|^2 / 2`, where `y(x) = argmin |g(x) + A(x)' * y|^2`
- aug. Lagrangian: `phi(x, y, eta) = f(x) - y' * c(x) + eta * |c(x)|^2 / 2`.

Important features:
- value at given points
- directional derivative
- Memory efficient
- Save evaluations
- Option to update internal values or not (defaults to yes)

Suggested implementation:
- `AbstractMerit`
- `L1Merit <: AbstractMerit`, `AugLagMerit <: AbstractMerit`
- Assume `fx`, `cx`, `gx` and `Ad` are stored internally, where `fx` is the objective, `cx` is the constraints, and `gx` is the gradient at `x` and `Ad` is the Jacobian times the direction `d`.
- The user may decide to keep pointers or new copies. Test will be made to determine that's possible.
- `obj(::AbstractMerit, x::Vector; update=true)`
- `directional(::AbstractMerit, x::Vector, d::Vector; update=true)`

Discussion:
- Line search expects a `LineModel`, which has a lot more liberty and deals with an `nlp` directly.
- For instance, a `LineModel` can compute `grad!` on an `nlp`.
- Trust region expects an `nlp` an also computes `grad!.
- Could we unify these?
- Should `AbstractMerit` be an `NLPModel`? (I think no)
- Should we disallow `grad!` on `nlp` from line search and trust region?

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.