Main Content

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

$$\underset{x}{\mathrm{min}}f(x)$$

such that

$$\begin{array}{c}{c}_{i}(x)\le 0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}i=1\dots m\\ ce{q}_{i}(x)=0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{}i=m+1\dots mt\\ A\cdot x\le b\\ Aeq\cdot x=beq\\ lb\le x\le ub,\end{array}$$

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.

Each subproblem solution represents one iteration. The number of function evaluations per iteration is therefore much higher when using nonlinear constraints than otherwise.

A subproblem formulation is defined as

$$\Theta (x,\lambda ,s,\rho )=f(x)-{\displaystyle \sum _{i=1}^{m}{\lambda}_{i}}{s}_{i}\mathrm{log}({s}_{i}-{c}_{i}(x))+{\displaystyle \sum _{i=m+1}^{mt}{\lambda}_{i}}ce{q}_{i}(x)+\frac{\rho}{2}{\displaystyle \sum _{i=m+1}^{mt}ce{q}_{i}}{(x)}^{2},$$

where

The components

*λ*of the vector_{i}*λ*are nonnegative and are known as Lagrange multiplier estimatesThe elements

*s*of the vector_{i}*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 minimizes a sequence of subproblems, each of which is an
approximation of the original problem. Each subproblem has a fixed value of
*λ*, *s*, and *ρ*. 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.

Each subproblem solution represents one iteration. The number of function evaluations per iteration is therefore much higher when using nonlinear constraints than otherwise.

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

[1] Kolda, Tamara G., Robert Michael Lewis, and Virginia Torczon. “A generating set direct search augmented Lagrangian algorithm for optimization with a combination of general and linear constraints.” Technical Report SAND2006-5315, Sandia National Laboratories, August 2006.

[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.