Learn more about Genetic Algorithm and Direct Search Toolbox

Description of the Nonlinear Constraint Solver

The pattern search algorithm uses the Augmented Lagrangian Pattern Search (ALPS) algorithm to solve nonlinear constraint problems. The optimization problem solved by the ALPS algorithm is

such that

where c(x) represents the nonlinear inequality constraints, ceq(x) represents the equality constraints, m is the number of nonlinear inequality constraints, and mt is the total number of nonlinear constraints.

The ALPS algorithm attempts to solve a nonlinear optimization problem with nonlinear constraints, linear constraints, and bounds. In this approach, bounds and linear constraints are handled separately from nonlinear constraints. A subproblem is formulated by combining the objective function and nonlinear constraint function using the Lagrangian and the penalty parameters. A sequence of such optimization problems are approximately minimized using a pattern search algorithm such that the linear constraints and bounds are satisfied.

A subproblem formulation is defined as

where

• the components λ_i of the vector λ are nonnegative and are known as Lagrange multiplier estimates

• the elements s_i of the vector s are nonnegative shifts

• ρ is the positive penalty parameter.

The algorithm begins by using an initial value for the penalty parameter (InitialPenalty).

The pattern search algorithm minimizes a sequence of the subproblem, which is an approximation of the original problem. When the subproblem is minimized to a required accuracy and satisfies feasibility conditions, the Lagrangian estimates are updated. Otherwise, the penalty parameter is increased by a penalty factor (PenaltyFactor). This results in a new subproblem formulation and minimization problem. These steps are repeated until the stopping criteria are met.

For a complete description of the algorithm, see the following references:

[1] Lewis, Robert Michael and Virginia Torczon, "A Globally Convergent Augmented Lagrangian Pattern Search Algorithm for Optimization with General Constraints and Simple Bounds", SIAM Journal on Optimization, Volume 12, Number 4, 2002, 1075–1089.

[2] Conn, A. R., N. I. M. Gould, and Ph. L. Toint. "A Globally Convergent Augmented Lagrangian Algorithm for Optimization with General Constraints and Simple Bounds," SIAM Journal on Numerical Analysis, Volume 28, Number 2, pages 545–572, 1991.

[3] Conn, A. R., N. I. M. Gould, and Ph. L. Toint. "A Globally Convergent Augmented Lagrangian Barrier Algorithm for Optimization with General Inequality Constraints and Simple Bounds," Mathematics of Computation, Volume 66, Number 217, pages 261–288, 1997.

How Pattern Search Works

Getting Started with the Genetic Algorithm

© 1984-2009- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS