Package minfx :: Module method_of_multipliers
[hide private]
[frames] | no frames]

Module method_of_multipliers

source code

Method of multipliers or augmented Lagrangian method optimization constraint algorithm.

This file is part of the minfx optimisation library.

Classes [hide private]
Method_of_multipliers
Functions [hide private]
 
method_of_multipliers(func=None, dfunc=None, d2func=None, args=(), x0=None, min_options=(), A=None, b=None, l=None, u=None, c=None, dc=None, d2c=None, lambda0=None, init_lambda=10000.0, mu0=1e-05, epsilon0=0.01, gamma0=0.01, scale_mu=0.5, scale_epsilon=0.01, scale_gamma=0.01, func_tol=1e-25, grad_tol=None, maxiter=1000000.0, inner_maxiter=500, full_output=0, print_flag=0)
The method of multipliers, also known as the augmented Lagrangian method.
source code
Variables [hide private]
  __package__ = 'minfx'

Imports: dot, float64, inf, outer, sqrt, zeros, match, print_iter, Min, Constraint_linear


Function Details [hide private]

method_of_multipliers(func=None, dfunc=None, d2func=None, args=(), x0=None, min_options=(), A=None, b=None, l=None, u=None, c=None, dc=None, d2c=None, lambda0=None, init_lambda=10000.0, mu0=1e-05, epsilon0=0.01, gamma0=0.01, scale_mu=0.5, scale_epsilon=0.01, scale_gamma=0.01, func_tol=1e-25, grad_tol=None, maxiter=1000000.0, inner_maxiter=500, full_output=0, print_flag=0)

source code 

The method of multipliers, also known as the augmented Lagrangian method.

Page 515 from 'Numerical Optimization' by Jorge Nocedal and Stephen J. Wright, 1999, 2nd ed. The algorithm is:

  • Given u0 > 0, tolerance t0 > 0, starting points x0s and lambda0
  • while 1:
    • Find an approximate minimiser xk of LA(.,lambdak; uk), starting at xks, and terminating when the augmented Lagrangian gradient <= tk
    • Final convergence test
    • Update Lagrange multipliers using formula 17.58
    • Choose new penalty parameter uk+1 within (0, uk)
    • Set starting point for the next iteration to xk+1s = xk
    • k = k + 1

Three types of inequality constraint are supported. These are linear, bound, and general constraints and must be setup as follows. The vector x is the vector of model parameters. Don't use bound constraints yet as this code is incomplete!

Equality constraints are currently unimplemented.

Linear constraints

These are defined as:

   A.x >= b

where:

  • A is an m*n matrix where the rows are the transposed vectors, ai, of length n. The elements of ai are the coefficients of the model parameters.
  • x is the vector of model parameters of dimension n.
  • b is the vector of scalars of dimension m.
  • m is the number of constraints.
  • n is the number of model parameters.

E.g. if 0 <= q <= 1, q >= 1 - 2r, and 0 <= r, then:

   | 1  0 |            |  0 |
   |      |            |    |
   |-1  0 |   | q |    | -1 |
   |      | . |   | >= |    |
   | 1  2 |   | r |    |  1 |
   |      |            |    |
   | 0  1 |            |  2 |

To use linear constraints both the matrix A and vector b need to be supplied.

Bound constraints

Bound constraints are defined as:

   l <= x <= u,

where l and u are the vectors of lower and upper bounds respectively. E.g. if 0 <= q <= 1, r >= 0, s <= 3, then:

   |  0  |    | q |    |  1  |
   |  0  | <= | r | <= | inf |
   |-inf |    | s |    |  3  |

To use bound constraints both vectors l and u need to be supplied.

General constraints

These are defined as:

   ci(x) >= 0,

where ci(x) are the constraint functions.

To use general constrains the functions c, dc, and d2c need to be supplied. The function c is the constraint function which should return the vector of constraint values. The function dc is the constraint gradient function which should return the matrix of constraint gradients. The function d2c is the constraint Hessian function which should return the 3D matrix of constraint Hessians.

Initial values

These are the default initial values:

   mu0 = 1e-5
   epsilon0 = 1e-2
   gamma0 = 1e-2
   scale_mu = 0.5
   scale_epsilon = 1e-2
   scale_gamma = 1e-2