Documentation

This is machine translation

Mouseover text to see original. Click the button below to return to the English version of the page.

Linear and Nonlinear Constrained Minimization Using `patternsearch`

Linearly Constrained Problem

Problem Description

This section presents an example of performing a pattern search on a constrained minimization problem. The example minimizes the function

`$F\left(x\right)=\frac{1}{2}{x}^{T}Hx+{f}^{T}x,$`

where

`$\begin{array}{c}H=\left[\begin{array}{cccccc}36& 17& 19& 12& 8& 15\\ 17& 33& 18& 11& 7& 14\\ 19& 18& 43& 13& 8& 16\\ 12& 11& 13& 18& 6& 11\\ 8& 7& 8& 6& 9& 8\\ 15& 14& 16& 11& 8& 29\end{array}\right],\\ f=\left[\begin{array}{cccccc}20& 15& 21& 18& 29& 24\end{array}\right],\end{array}$`

subject to the constraints

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

where

`$\begin{array}{c}A=\left[\begin{array}{cccccc}-8& 7& 3& -4& 9& 0\end{array}\right],\\ b=7,\\ Aeq=\left[\begin{array}{cccccc}7& 1& 8& 3& 3& 3\\ 5& 0& -5& 1& -5& 8\\ -2& -6& 7& 1& 1& 9\\ 1& -1& 2& -2& 3& -3\end{array}\right],\\ beq=\left[\begin{array}{cccc}84& 62& 65& 1\end{array}\right].\end{array}$`

Performing a Pattern Search on the Example

To perform a pattern search on the example, first enter

`optimtool('patternsearch')`
to open the Optimization app, or enter `optimtool` and then choose `patternsearch` from the Solver menu. Then type the following function in the Objective function field:
`@lincontest7`
`lincontest7` is a file included in Global Optimization Toolbox software that computes the objective function for the example. Because the matrices and vectors defining the starting point and constraints are large, it is more convenient to set their values as variables in the MATLAB® workspace first and then enter the variable names in the Optimization app. To do so, enter

```x0 = [2 1 0 9 1 0]; Aineq = [-8 7 3 -4 9 0]; bineq = 7; Aeq = [7 1 8 3 3 3; 5 0 -5 1 -5 8; -2 -6 7 1 1 9; 1 -1 2 -2 3 -3]; beq = [84 62 65 1];```

Then, enter the following in the Optimization app:

• Set Start point to `x0`.

• Set the following Linear inequalities:

• Set A to `Aineq`.

• Set b to `bineq`.

• Set Aeq to `Aeq`.

• Set beq to `beq`.

The following figure shows these settings in the Optimization app. Since this is a linearly constrained problem, set the Poll method to `GSS Positive basis 2N`. For more information about the efficiency of the GSS search methods for linearly constrained problems, see Compare the Efficiency of Poll Options. Then click to run the pattern search. When the search is finished, the results are displayed in Run solver and view results pane, as shown in the following figure. To run this problem using command-line functions:

```x0 = [2 1 0 9 1 0]; Aineq = [-8 7 3 -4 9 0]; bineq = 7; Aeq = [7 1 8 3 3 3; 5 0 -5 1 -5 8; -2 -6 7 1 1 9; 1 -1 2 -2 3 -3]; beq = [84 62 65 1]; options = optimoptions('patternsearch',... 'PollMethod','GSSPositiveBasis2N'); [x,fval,exitflag,output] = patternsearch(@lincontest7,x0,... Aineq,bineq,Aeq,beq,[],[],[],options);```

View the solution, objective function value, and number of function evaluations during the solution process.

`x,fval,output.funccount`
```x = 8.5165 -6.1094 4.0989 1.2877 -4.2348 2.1812 fval = 1.9195e+03 ans = 758```

Nonlinearly Constrained Problem

Suppose you want to minimize the simple objective function of two variables `x1` and `x2`,

`$\underset{x}{\mathrm{min}}f\left(x\right)=\left(4-2.1{x}_{1}{}^{2}-{x}_{1}{}^{4/3}\right){x}_{1}{}^{2}+{x}_{1}{x}_{2}+\left(-4+4{x}_{2}{}^{2}\right){x}_{2}{}^{2}$`

subject to the following nonlinear inequality constraints and bounds

Begin by creating the objective and constraint functions. First, create a file named `simple_objective.m` as follows:

```function y = simple_objective(x) y = (4 - 2.1*x(1)^2 + x(1)^4/3)*x(1)^2 + x(1)*x(2) + (-4 + 4*x(2)^2)*x(2)^2;```

The pattern search solver assumes the objective function will take one input `x` where `x` has as many elements as number of variables in the problem. The objective function computes the value of the function and returns that scalar value in its one return argument `y`.

Then create a file named `simple_constraint.m` containing the constraints:

```function [c, ceq] = simple_constraint(x) c = [1.5 + x(1)*x(2) + x(1) - x(2); -x(1)*x(2) + 10]; ceq = [];```

The pattern search solver assumes the constraint function will take one input `x`, where `x` has as many elements as the number of variables in the problem. The constraint function computes the values of all the inequality and equality constraints and returns two vectors, `c` and `ceq`, respectively.

Next, to minimize the objective function using the `patternsearch` function, you need to pass in a function handle to the objective function as well as specifying a start point as the second argument. Lower and upper bounds are provided as `LB` and `UB` respectively. In addition, you also need to pass a function handle to the nonlinear constraint function.

```ObjectiveFunction = @simple_objective; X0 = [0 0]; % Starting point LB = [0 0]; % Lower bound UB = [1 13]; % Upper bound ConstraintFunction = @simple_constraint; [x,fval] = patternsearch(ObjectiveFunction,X0,[],[],[],[],... LB,UB,ConstraintFunction)```
```Optimization terminated: mesh size less than options.MeshTolerance and constraint violation is less than options.ConstraintTolerance. x = 0.8122 12.3122 fval = 9.1324e+004```

Next, plot the results. Create options using `optimoptions` that selects two plot functions. The first plot function `psplotbestf` plots the best objective function value at every iteration. The second plot function `psplotmaxconstr` plots the maximum constraint violation at every iteration.

Note

You can also visualize the progress of the algorithm by displaying information to the Command Window using the `'Display'` option.

```options = optimoptions('patternsearch','PlotFcn',{@psplotbestf,@psplotmaxconstr},'Display','iter'); [x,fval] = patternsearch(ObjectiveFunction,X0,[],[],[],[],LB,UB,ConstraintFunction,options) ```
``` Max Iter Func-count f(x) Constraint MeshSize Method 0 1 0 10 0.8919 1 28 113580 0 0.001 Increase penalty 2 105 91324 1.776e-07 1e-05 Increase penalty 3 192 91324 1.185e-11 1e-07 Increase penalty Optimization terminated: mesh size less than options.MeshTolerance and constraint violation is less than options.ConstraintTolerance. x = 0.8122 12.3122 fval = 9.1324e+04```

Best Objective Function Value and Maximum Constraint Violation at Each Iteration Watch now