Augmented Lagrangian method for equality- and inequality-constrained minimization, with line/util/neldermead.h or line/util/levmar.h as the inner unconstrained solver. More...

#include <cstddef>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/levmar.h"
#include "line/util/neldermead.h"

Include dependency graph for auglag.h:

Classes
struct	line::AugLagOptions< T >
	Tuning of the outer multiplier iteration. More...
struct	line::AugLagResult< T >
	Outcome of a constrained solve. More...
struct	line::NoConstraints< T >
	A constraint map that returns no constraints; the default for h or g. More...

Namespaces
namespace	line

Functions
template<class T>
AugLagOptions< T >	line::auglag_defaults ()
	Defaults: rho0 = 10, growth 10, feasibility 1e-10, 50 outer iterations.
template<class T, class F, class H, class G>
AugLagResult< T >	line::auglag (F f, H h, G g, const std::vector< T > &x0, const std::vector< Bound< T > > &bounds, const AugLagOptions< T > &opt)
	Augmented Lagrangian with a scalar objective and a simplex inner solver.
template<class T, class F, class H, class G>
AugLagResult< T >	line::auglag (F f, H h, G g, const std::vector< T > &x0, const std::vector< Bound< T > > &bounds)
	auglag with the default tuning.
template<class T, class R, class H, class G>
AugLagResult< T >	line::auglag_ls (R r, std::size_t m, H h, G g, const std::vector< T > &x0, const AugLagOptions< T > &opt)
	Augmented Lagrangian with a least-squares objective and levmar as the inner solver.
template<class T, class R, class H, class G>
AugLagResult< T >	line::auglag_ls (R r, std::size_t m, H h, G g, const std::vector< T > &x0)
	auglag_ls with the default tuning.

Detailed Description

Augmented Lagrangian method for equality- and inequality-constrained minimization, with line/util/neldermead.h or line/util/levmar.h as the inner unconstrained solver.

Solves min f(x) s.t. h_i(x) = 0, g_j(x) <= 0, lo <= x <= hi by minimizing, for a sequence of penalty parameters rho and multiplier estimates (lambda, mu),

L_A(x; lambda, mu, rho) = f(x)

sum_i [ lambda_i h_i + (rho/2) h_i^2 ]
(1/(2 rho)) sum_j [ max(0, mu_j + rho g_j)^2 - mu_j^2 ]

which is the Hestenes-Powell-Rockafellar form: the inequality term is the exact penalty of Rockafellar (1973), differentiable once, and is inactive for a constraint that is strictly satisfied with a zero multiplier. After each inner solve lambda_i <- lambda_i + rho h_i, mu_j <- max(0, mu_j + rho g_j) and rho is multiplied by rho_factor whenever the constraint violation did not shrink by at least the factor shrink. This is a first-order multiplier method: it converges to a KKT point without driving rho to infinity, which is what keeps the inner problems well conditioned.

WHY NOT A PENALTY-ONLY LOOP: with lambda held at zero, the minimizer of the penalized problem is offset from the true solution by O(1/rho) and the only way to tighten it is a large rho, whose Hessian is ill conditioned by exactly that factor. The multiplier update removes the offset, so a moderate rho suffices.

ACCEPTANCE CONTRACT. This replaces MATLAB's fmincon (active-set / interior-point), quadprog, patternsearch and PSwarm in the m3a and kpctoolbox fitting routines. It is a different algorithm: it does not reproduce their iterates, their multipliers, or, on a nonconvex problem with several local minima, necessarily their local minimum. Every caller in line/api/mam therefore states its acceptance in terms of the specification (the fitted process reproduces the target characteristics to a stated tolerance, and is a valid MAP) and returns the objective value it achieved, so it can be compared against the reference's.

Deterministic: no random multi-start, no global state, no exit(), no output. Non-convergence is reported through AugLagResult, never thrown.

Gated on transcendental arithmetic through the inner solvers.

Definition in file auglag.h.

Classes

Namespaces

Functions

Detailed Description