JuliaSmoothOptimizers / JuliaSmoothOptimizers/SolverTools.jl
Implement merit functions and make it work with line search and trust region
- 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
Assessment
This issue has not been assessed yet.