# patternsearch

Find minimum of function using pattern search

## Syntax

`x = patternsearch(fun,x0)x = patternsearch(fun,x0,A,b)x = patternsearch(fun,x0,A,b,Aeq,beq)x = patternsearch(fun,x0,A,b,Aeq,beq,LB,UB)x = patternsearch(fun,x0,A,b,Aeq,beq,LB,UB,nonlcon)x = patternsearch(fun,x0,A,b,Aeq,beq,LB,UB,nonlcon,options)x = patternsearch(problem)[x,fval] = patternsearch(fun,x0, ...)[x,fval,exitflag] = patternsearch(fun,x0, ...)[x,fval,exitflag,output] = patternsearch(fun,x0, ...)`

## Description

`patternsearch` finds the minimum of a function using a pattern search.

`x = patternsearch(fun,x0)` finds a local minimum, `x`, to the function handle `fun` that computes the values of the objective function. For details on writing `fun`, see Compute Objective Functions. `x0` is an initial point for the pattern search algorithm, a real vector.

 Note   To write a function with additional parameters to the independent variables that can be called by `patternsearch`, see the section on Passing Extra Parameters in the Optimization Toolbox™ documentation.

`x = patternsearch(fun,x0,A,b)` finds a local minimum `x` to the function `fun`, subject to the linear inequality constraints represented in matrix form by $Ax\le b$, see Linear Inequality Constraints.

If the problem has `m` linear inequality constraints and `n` variables, then

• `A` is a matrix of size `m`-by-`n`.

• `b` is a vector of length `m`.

`x = patternsearch(fun,x0,A,b,Aeq,beq)` finds a local minimum `x` to the function `fun`, starting at `x0`, and subject to the constraints

$\begin{array}{c}A*x\le b\\ Aeq*x=beq,\end{array}$

where $Aeq\ast x=beq$ represents the linear equality constraints in matrix form, see Linear Equality Constraints. If the problem has `r` linear equality constraints and `n` variables, then

• `Aeq` is a matrix of size `r`-by-`n`.

• `beq` is a vector of length `r`.

If there are no inequality constraints, pass empty matrices, `[]`, for `A` and `b`.

`x = patternsearch(fun,x0,A,b,Aeq,beq,LB,UB)` defines a set of lower and upper bounds on the design variables, `x`, so that a solution is found in the range `LB` ≤ `x` ≤ `UB`, see Bound Constraints. If the problem has n variables, `LB` and `UB` are vectors of length n. If `LB` or `UB` is empty (or not provided), it is automatically expanded to `-Inf` or `Inf`, respectively. If there are no inequality or equality constraints, pass empty matrices for `A`, `b`, `Aeq` and `beq`.

`x = patternsearch(fun,x0,A,b,Aeq,beq,LB,UB,nonlcon)` subjects the minimization to the constraints defined in `nonlcon`, a nonlinear constraint function. The function `nonlcon` accepts `x` and returns the vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. `patternsearch` minimizes `fun` such that C(x) ≤ 0 and Ceq(x) = 0. (Set `LB=[]` and `UB=[]` if no bounds exist.)

`x = patternsearch(fun,x0,A,b,Aeq,beq,LB,UB,nonlcon,options)` minimizes `fun` with the default optimization parameters replaced by values in `options`. The structure `options` can be created using `psoptimset`.

`x = patternsearch(problem)` finds the minimum for `problem`, where `problem` is a structure containing the following fields:

• `objective` — Objective function

• `X0` — Starting point

• `Aineq` — Matrix for linear inequality constraints

• `bineq` — Vector for linear inequality constraints

• `Aeq` — Matrix for linear equality constraints

• `beq` — Vector for linear equality constraints

• `lb` — Lower bound for `x`

• `ub` — Upper bound for `x`

• `nonlcon` — Nonlinear constraint function

• `solver``'patternsearch'`

• `options` — Options structure created with `psoptimset`

• `rngstate` — Optional field to reset the state of the random number generator

Create the structure `problem` by exporting a problem from the Optimization app, as described in Importing and Exporting Your Work in the Optimization Toolbox documentation.

 Note   `problem` must have all the fields as specified above.

`[x,fval] = patternsearch(fun,x0, ...)` returns the value of the objective function `fun` at the solution `x`.

`[x,fval,exitflag] = patternsearch(fun,x0, ...)` returns `exitflag`, which describes the exit condition of `patternsearch`. Possible values of `exitflag` and the corresponding conditions are

Exit FlagMeaning

`1`

Without nonlinear constraints — Magnitude of the mesh size is less than the specified tolerance and constraint violation is less than `TolCon`.

With nonlinear constraints — Magnitude of the complementarity measure (defined after this table) is less than `sqrt(TolCon)`, the subproblem is solved using a mesh finer than `TolMesh`, and the constraint violation is less than `TolCon`.

`2`

Change in `x` and the mesh size are both less than the specified tolerance, and the constraint violation is less than `TolCon`.

`3`

Change in `fval` and the mesh size are both less than the specified tolerance, and the constraint violation is less than `TolCon`.

`4`

Magnitude of step smaller than machine precision and the constraint violation is less than `TolCon`.

`0`

Maximum number of function evaluations or iterations reached.

`-1`

Optimization terminated by an output function or plot function.

`-2`

No feasible point found.

In the nonlinear constraint solver, the complementarity measure is the norm of the vector whose elements are ciλi, where ci is the nonlinear inequality constraint violation, and λi is the corresponding Lagrange multiplier.

`[x,fval,exitflag,output] = patternsearch(fun,x0, ...)` returns a structure `output` containing information about the search. The output structure contains the following fields:

• `function` — Objective function.

• `problemtype` — String describing the type of problem, one of:

• `'unconstrained'`

• `'boundconstraints'`

• `'linearconstraints'`

• `'nonlinearconstr'`

• `pollmethod` — Polling technique.

• `searchmethod` — Search technique used, if any.

• `iterations` — Total number of iterations.

• `funccount` — Total number of function evaluations.

• `meshsize` — Mesh size at `x`.

• `maxconstraint` — Maximum constraint violation, if any.

• `rngstate` — State of the MATLAB® random number generator, just before the algorithm started. You can use the values in `rngstate` to reproduce the output when you use a random search method or random poll method. See Reproduce Results, which discusses the identical technique for `ga`.

• `message` — Reason why the algorithm terminated.

 Note   `patternsearch` does not accept functions whose inputs are of type `complex`. To solve problems involving complex data, write your functions so that they accept real vectors, by separating the real and imaginary parts.

## Examples

Given the following constraints

the following code finds the minimum of the function, `lincontest6`, that is provided with your software:

```A = [1 1; -1 2; 2 1]; b = [2; 2; 3]; lb = zeros(2,1); [x,fval,exitflag] = patternsearch(@lincontest6,[0 0],... A,b,[],[],lb) Optimization terminated: mesh size less than options.TolMesh. x = 0.6667 1.3333 fval = -8.2222 exitflag = 1 ```

## References

[1] Audet, Charles and J. E. Dennis Jr. "Analysis of Generalized Pattern Searches." SIAM Journal on Optimization, Volume 13, Number 3, 2003, pp. 889–903.

[2] 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, 1997, pp. 261–288.

[3] Abramson, Mark A. Pattern Search Filter Algorithms for Mixed Variable General Constrained Optimization Problems. Ph.D. Thesis, Department of Computational and Applied Mathematics, Rice University, August 2002.

[4] Abramson, Mark A., Charles Audet, J. E. Dennis, Jr., and Sebastien Le Digabel. "ORTHOMADS: A deterministic MADS instance with orthogonal directions." SIAM Journal on Optimization, Volume 20, Number 2, 2009, pp. 948–966.

[5] Kolda, Tamara G., Robert Michael Lewis, and Virginia Torczon. "Optimization by direct search: new perspectives on some classical and modern methods." SIAM Review, Volume 45, Issue 3, 2003, pp. 385–482.

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

[7] Lewis, Robert Michael, Anne Shepherd, and Virginia Torczon. "Implementing generating set search methods for linearly constrained minimization." SIAM Journal on Scientific Computing, Volume 29, Issue 6, 2007, pp. 2507–2530.