Linear and Nonlinear Constrained Minimization Using patternsearch

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 (x) = \frac{1}{2} x^{T} H x + f^{T} x,$

where

$\begin{matrix} H = [\begin{matrix} 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{matrix}], \\ f = [\begin{matrix} 20 & 15 & 21 & 18 & 29 & 24 \end{matrix}], \end{matrix}$

subject to the constraints

$\begin{matrix} A \cdot x \leq b, \\ A e q \cdot x = b e q, \end{matrix}$

where

$\begin{matrix} A = [\begin{matrix} - 8 & 7 & 3 & - 4 & 9 & 0 \end{matrix}], \\ b = 7, \\ A e q = [\begin{matrix} 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{matrix}], \\ b e q = [\begin{matrix} 84 & 62 & 65 & 1 \end{matrix}] . \end{matrix}$

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 Start 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,

$\min_{x} f (x) = (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}$

subject to the following nonlinear inequality constraints and bounds

$\begin{array}{l} x_{1} x_{2} + x_{1} - x_{2} + 1.5 \leq 0 & (nonlinear constraint) \\ 10 - x_{1} x_{2} \leq 0 & (nonlinear constraint) \\ 0 \leq x_{1} \leq 1 & (bound) \\ 0 \leq x_{2} \leq 13 & (bound) \end{array}$

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.782e-07        1e-05   Increase penalty
    3       192        91324    1.188e-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

Documentation