IAS0031 Modeling and Identification

Lecture 2: Simplex Method. Nelder-Mead

Method. Problems with Bounds and Con-
straints.

Aleksei Tepljakov, Ph.D.

Part III: Simplex Method

Aleksei Tepljakov 2 / 35
Solutions to a Linear Programming Problem

Recall the two forms of the linear programming problem:

z = CX → max(min) z = CX → max(min)
AX 6 B or AX = B
X > 0 X > 0
(standard form) (canonical form)

Aleksei Tepljakov 3 / 35
Solutions to a Linear Programming Problem

Recall the two forms of the linear programming problem:

z = CX → max(min) z = CX → max(min)
AX 6 B or AX = B
X > 0 X > 0
(standard form) (canonical form)

Definition 1. A basic solution is a solution obtained by fixing enough variables

to be equal to zero, so that the equality constraints have a unique solution.

Aleksei Tepljakov 3 / 35
Solutions to a Linear Programming Problem

Recall the two forms of the linear programming problem:

z = CX → max(min) z = CX → max(min)
AX 6 B or AX = B
X > 0 X > 0
(standard form) (canonical form)

Definition 1. A basic solution is a solution obtained by fixing enough variables

to be equal to zero, so that the equality constraints have a unique solution.

Definition 2. A feasible solution to the linear programming problem which is

also the basic solution is called the basic feasible solution. Basic feasible
solutions are of two types: degenerate—if the value of at least one basic
variable is zero,—and non-degenerate—if all values of basic variables are
non-zero and positive.

Aleksei Tepljakov 3 / 35
Simplex Method: Introductory Example

Solve the following linear programming problem.

z = 3x1 + 4x2 → max

2x1 + 4x2 6 120
2x1 + 2x2 6 80
x1 > 0, x2 > 0.

We shall solve this problem using the Simplex method.

Aleksei Tepljakov 4 / 35
Simplex Method: Initial Steps

Step 1: Standard form of a maximum problem

A linear programming problem in which the objective function is to
be maximized is referred to as a maximum linear programming
problem. Such problems are said to be in standard form if the
following conditions are satisfied:
• All the variables are nonnegative;

Aleksei Tepljakov 5 / 35
Simplex Method: Initial Steps

Step 1: Standard form of a maximum problem

A linear programming problem in which the objective function is to
be maximized is referred to as a maximum linear programming
problem. Such problems are said to be in standard form if the
following conditions are satisfied:
• All the variables are nonnegative;
• All other constraints are written as a linear expression, i.e., less
than or equal to a positive constant.

Aleksei Tepljakov 5 / 35
Simplex Method: Initial Steps

Step 1: Standard form of a maximum problem

A linear programming problem in which the objective function is to
be maximized is referred to as a maximum linear programming
problem. Such problems are said to be in standard form if the
following conditions are satisfied:
• All the variables are nonnegative;
• All other constraints are written as a linear expression, i.e., less
than or equal to a positive constant.
Conclusion: The given problem is in standard form.

Aleksei Tepljakov 5 / 35
Simplex Method: Initial Steps (continued)

Step 2: Slack variables and initial simplex table

In order to solve the maximum problem by means of the simplex
method, we need to do the following first:
• Introduce slack variables;

Aleksei Tepljakov 6 / 35
Simplex Method: Initial Steps (continued)

Step 2: Slack variables and initial simplex table

In order to solve the maximum problem by means of the simplex
method, we need to do the following first:
• Introduce slack variables;
• Construct the initial simplex table.

Aleksei Tepljakov 6 / 35
Simplex Method: Initial Steps (continued)

Step 2: Slack variables and initial simplex table

In order to solve the maximum problem by means of the simplex
method, we need to do the following first:
• Introduce slack variables;
• Construct the initial simplex table.
In this problem we have the constraints as linear expressions less
than or equal to some positive constants. That means there is a
slack between the left and right sides of the inequalities. In order
to take up the slack between the left and right sides of the problem
we introduce slack variables.

Aleksei Tepljakov 6 / 35
Simplex Method: Initial Steps (continued)

For the given problem we introduce slack variables s1 and s2 , such that
s1 , s2 > 0, and

2x1 + 4x2 + s1 = 120

2x1 + 2x2 + s2 = 80.

Aleksei Tepljakov 7 / 35
Simplex Method: Initial Steps (continued)

For the given problem we introduce slack variables s1 and s2 , such that
s1 , s2 > 0, and

2x1 + 4x2 + s1 = 120

2x1 + 2x2 + s2 = 80.

The objective function z can be rewritten as z − 3x1 − 4x2 = 0. Thus,

we now have

z − 3x1 − 4x2 = 0
2x1 + 4x2 + s1 = 120
2x1 + 2x2 + s2 = 80.

Aleksei Tepljakov 7 / 35
Simplex Method: Initial Steps (continued)

For the given problem we introduce slack variables s1 and s2 , such that
s1 , s2 > 0, and

2x1 + 4x2 + s1 = 120

2x1 + 2x2 + s2 = 80.

The objective function z can be rewritten as z − 3x1 − 4x2 = 0. Thus,

we now have

z − 3x1 − 4x2 = 0
2x1 + 4x2 + s1 = 120
2x1 + 2x2 + s2 = 80.

The goal is to find the particular solution (x1 , x2 , s1 , s2 , z) that

maximizes z.

Aleksei Tepljakov 7 / 35
Simplex Method: Initial Simplex Table

We now constuct the initial simplex table.

x1 x2 s1 s2 z b variables
2 4 1 0 0 120 s1
2 2 0 1 0 80 s2
−3 −4 0 0 1 0 z

The coefficients of the objective function are arranged in the

bottom row, which is called the objective row.
From this point on, the simplex method consists of pivoting from
one table to another until the optimal solution is found.

Aleksei Tepljakov 8 / 35
Simplex Method: Pivoting

Pivoting: To pivot a matrix about a given element, called the pivot element, is
to apply row operations, so that the pivot element is replaced by 1 and all
other entries in the same column (called pivot column) become 0.

Aleksei Tepljakov 9 / 35
Simplex Method: Pivoting

Pivoting: To pivot a matrix about a given element, called the pivot element, is
to apply row operations, so that the pivot element is replaced by 1 and all
other entries in the same column (called pivot column) become 0.
Pivot element: The pivot element for the Simplex method is found using the
following rules:

Aleksei Tepljakov 9 / 35
Simplex Method: Pivoting

Pivoting: To pivot a matrix about a given element, called the pivot element, is
to apply row operations, so that the pivot element is replaced by 1 and all
other entries in the same column (called pivot column) become 0.
Pivot element: The pivot element for the Simplex method is found using the
following rules:
• The pivot column is selected by locating the most negative entry in the
objective row. If all the entries in this column are negative, the problem is
unbounded and there is no solution.

Aleksei Tepljakov 9 / 35
Simplex Method: Pivoting

Pivoting: To pivot a matrix about a given element, called the pivot element, is
to apply row operations, so that the pivot element is replaced by 1 and all
other entries in the same column (called pivot column) become 0.
Pivot element: The pivot element for the Simplex method is found using the
following rules:
• The pivot column is selected by locating the most negative entry in the
objective row. If all the entries in this column are negative, the problem is
unbounded and there is no solution.
• Divide each entry in the last column by the corresponding entry from the
same row in the pivot column. Ignore the rows in which the pivot column
entry is less than or equal to 0. The row in which the smallest positive
ratio is obtained is the pivot row.

The pivot element is the entry at the intersection of the pivot row and the
pivot column.

Aleksei Tepljakov 9 / 35
Simplex Method: Locating the Pivot
Element

x1 x2 s1 s2 z b variables ratio
2 4 1 0 0 120 s1
2 2 0 1 0 80 s2
−3 −4 0 0 1 0 z

• Inspect the objective row.

Aleksei Tepljakov 10 / 35
Simplex Method: Locating the Pivot
Element

x1 x2 s1 s2 z b variables ratio
2 4 1 0 0 120 s1
2 2 0 1 0 80 s2
−3 −4 0 0 1 0 z

• Inspect the objective row.

• The most negative entry is −4 in the objective row, hence the 2nd column
is the pivot column.

Aleksei Tepljakov 10 / 35
Simplex Method: Locating the Pivot
Element

x1 x2 s1 s2 z b variables ratio
2 4 1 0 0 120 s1 120/4 = 30
2 2 0 1 0 80 s2 80/2 = 40
−3 −4 0 0 1 0 z

• Inspect the objective row.

• The most negative entry is −4 in the objective row, hence the 2nd column
is the pivot column.
• Compute the ratios by dividing each entry in the 6th column by the
corresponding entry in the 2nd column.

Aleksei Tepljakov 10 / 35
Simplex Method: Locating the Pivot
Element

x1 x2 s1 s2 z b variables ratio
2 4 1 0 0 120 s1 120/4 = 30
2 2 0 1 0 80 s2 80/2 = 40
−3 −4 0 0 1 0 z

• Inspect the objective row.

• The most negative entry is −4 in the objective row, hence the 2nd column
is the pivot column.
• Compute the ratios by dividing each entry in the 6th column by the
corresponding entry in the 2nd column.
• The smallest ratio is 30, so the element a12 = 4 is the pivot element.

Aleksei Tepljakov 10 / 35
Simplex Method: Row Operations and New
Table
We now divide R1 (the first row) by 4 and then apply the operations
R2 = R2 − 2R1 and R3 = R3 + 4R1 . The new table becomes

x1 x2 s1 s2 z b variables ratio
1 1
2
1 4
0 0 30 x2
1 0 − 12 1 0 20 s2
−1 0 1 0 1 120 z

Aleksei Tepljakov 11 / 35
Simplex Method: Row Operations and New
Table
We now divide R1 (the first row) by 4 and then apply the operations
R2 = R2 − 2R1 and R3 = R3 + 4R1 . The new table becomes

x1 x2 s1 s2 z b variables ratio
1 1
2
1 4
0 0 30 x2
1 0 − 12 1 0 20 s2
−1 0 1 0 1 120 z

• The most negative entry in the objective row is −4, hence the 1st column is
the pivot column.

Aleksei Tepljakov 11 / 35
Simplex Method: Row Operations and New
Table
We now divide R1 (the first row) by 4 and then apply the operations
R2 = R2 − 2R1 and R3 = R3 + 4R1 . The new table becomes

x1 x2 s1 s2 z b variables ratio
1 1
2
1 4
0 0 30 x2 60
1 0 − 12 1 0 20 s2 20
−1 0 1 0 1 120 z

• The most negative entry in the objective row is −4, hence the 1st column is
the pivot column.
• Compute the ratios by dividing each entry in the 6th column by the
corresponding entry in the 1st column.

Aleksei Tepljakov 11 / 35
Simplex Method: Row Operations and New
Table
We now divide R1 (the first row) by 4 and then apply the operations
R2 = R2 − 2R1 and R3 = R3 + 4R1 . The new table becomes

x1 x2 s1 s2 z b variables ratio
1 1
2
1 4
0 0 30 x2 60
1 0 − 21 1 0 20 s2 20
−1 0 1 0 1 120 z

• The most negative entry in the objective row is −4, hence the 1st column is
the pivot column.
• Compute the ratios by dividing each entry in the 6th column by the
corresponding entry in the 1st column.
• The smallest ratio is 20, so the element a21 = 1 is the pivot element.

Aleksei Tepljakov 11 / 35
Simplex Method: Row Operations and Final
Table
We apply the operations R1 = R1 − 12 R2 and R3 = R3 + R2 . The
new table becomes

x1 x2 s1 s2 z b variables
1
0 1 2 − 12 0 20 x2
1 0 − 21 1 0 20 x1
1
0 0 2 1 1 140 z

Aleksei Tepljakov 12 / 35
Simplex Method: Row Operations and Final
Table
We apply the operations R1 = R1 − 12 R2 and R3 = R3 + R2 . The
new table becomes

x1 x2 s1 s2 z b variables
1
0 1 2 − 12 0 20 x2
1 0 − 21 1 0 20 x1
1
0 0 2 1 1 140 z

There are no negative entries in the objective row—the optimal

solution has been found. Therefore, zmax (20, 20) = 140.

Aleksei Tepljakov 12 / 35
Simplex Method: Definitions and Theorems

Definition 3. The variables corresponding to the columns of the

identity matrix in the initial simplex table are called basic variables
while the remaining variables are called nonbasic or free variables.

Aleksei Tepljakov 13 / 35
Simplex Method: Definitions and Theorems

Definition 3. The variables corresponding to the columns of the

identity matrix in the initial simplex table are called basic variables
while the remaining variables are called nonbasic or free variables.

Theorem 1. A basic feasible solution to a linear programming

problem corresponds to an extreme point in the convex set of
feasible solutions.

Aleksei Tepljakov 13 / 35
Simplex Method: Definitions and Theorems

Definition 3. The variables corresponding to the columns of the

identity matrix in the initial simplex table are called basic variables
while the remaining variables are called nonbasic or free variables.

Theorem 1. A basic feasible solution to a linear programming

problem corresponds to an extreme point in the convex set of
feasible solutions.

Corollary 1. Each extreme point corresponds to one or more basic

feasible solutions. If one of the basic feasible solutions is
non-degenerate, then an extreme point corresponds to it uniquely.

Aleksei Tepljakov 13 / 35
Simplex Method: Solving Minimum Linear
Programming Problems
Note that in general a minimum problem can be changed to a maximum
problem by realizing that in order to minimize z we must maximize −z. That
is, we multiply the objective by −1 and solve the resulting maximum problem
using the Simplex method.

Aleksei Tepljakov 14 / 35
Simplex Method: Solving Minimum Linear
Programming Problems
Note that in general a minimum problem can be changed to a maximum
problem by realizing that in order to minimize z we must maximize −z. That
is, we multiply the objective by −1 and solve the resulting maximum problem
using the Simplex method.
Consider the following linear programming problem:

z = x1 − 3x2 + 2x3 → min

3x1 − x2 + 2x3 6 7
−2x1 + 4x2 6 12
−4x1 + 3x2 + 8x3 6 10
x1 > 0, x2 > 0, x3 > 0

This is a problem of minimization, so we convert the objective function

z ′ = −x1 + 3x2 − 2x3 → max and solve the obtained maximum problem.

Aleksei Tepljakov 14 / 35
Simplex Method: Solving Minimum Linear
Programming Problems (continued)

After introducing the slack variables s1 , s2 , and s3 the problem can

be expressed as

3x1 − x2 + 2x3 + s1 = 7
−2x1 + 4x2 + s2 = 12
−4x1 + 3x2 + 8x3 + s3 = 10
x1 > 0, x2 > 0, x3 > 0
s1 > 0, s2 > 0, s3 > 0

The objective function can be written as z ′ + x1 − 3x2 + 2x3 = 0.

Aleksei Tepljakov 15 / 35
Simplex Method: Solving Minimum Linear
Programming Problems (continued)

The initial simplex table for this system is

x1 x2 x3 s1 s2 s3 z′ b variables ratio
3 −1 2 1 0 0 0 7 s1
−2 4 0 0 1 0 0 12 s2
−4 3 8 0 0 1 0 10 s3
1 −3 2 0 0 0 1 0 z

Aleksei Tepljakov 16 / 35
Simplex Method: Solving Minimum Linear
Programming Problems (continued)

The initial simplex table for this system is

x1 x2 x3 s1 s2 s3 z′ b variables ratio
3 −1 2 1 0 0 0 7 s1
−2 4 0 0 1 0 0 12 s2 12/4 = 3
10
−4 3 8 0 0 1 0 10 s3 3
1 −3 2 0 0 0 1 0 z

Aleksei Tepljakov 16 / 35
Simplex Method: Solving Minimum Linear
Programming Problems (continued)

The initial simplex table for this system is

x1 x2 x3 s1 s2 s3 z′ b variables ratio
3 −1 2 1 0 0 0 7 s1
−2 4 0 0 1 0 0 12 s2 12/4 = 3
10
−4 3 8 0 0 1 0 10 s3 3
1 −3 2 0 0 0 1 0 z

Row operations: Divide R2 by 4 and apply R1 = R1 + R2 ,

R3 = R3 − 3R2 , and R4 = R4 + 3R2 .

Aleksei Tepljakov 16 / 35
Simplex Method: Solving Minimum Linear
Programming Problems (continued)

We thus obtain the 2nd table:

x1 x2 x3 s1 s2 s3 z′ b variables ratio
5 1
2 0 2 1 4 0 0 10 s1
− 12 1 0 0 1
4 0 0 3 x2
− 52 0 8 0 − 34 1 0 1 s3
− 12 0 2 0 3
4 0 1 9 z

Aleksei Tepljakov 17 / 35
Simplex Method: Solving Minimum Linear
Programming Problems (continued)

We thus obtain the 2nd table:

x1 x2 x3 s1 s2 s3 z′ b variables ratio
5 1
2 0 2 1 4 0 0 10 s1 4
− 12 1 0 0 1
4 0 0 3 x2 ignore
− 52 0 8 0 − 34 1 0 1 s3 ignore
− 12 0 2 0 3
4 0 1 9 z

Aleksei Tepljakov 17 / 35
Simplex Method: Solving Minimum Linear
Programming Problems (continued)

We thus obtain the 2nd table:

x1 x2 x3 s1 s2 s3 z′ b variables ratio
5 1
2 0 2 1 4 0 0 10 s1 4
− 12 1 0 0 1
4 0 0 3 x2 ignore
− 52 0 8 0 − 34 1 0 1 s3 ignore
− 12 0 2 0 3
4 0 1 9 z

Row operations: Divide R1 by 52 and apply the operations

R2 = R2 + 21 R1 , R3 = R3 + 52 R1 , and R4 = R4 + 21 R1 .

Aleksei Tepljakov 17 / 35
Simplex Method: Solving Minimum Linear
Programming Problems (continued)

And then the 3rd table:

x1 x2 x3 s1 s2 s3 z′ b variables
4 2 1
1 0 5 5 10 0 0 4 x1
2 1 3
0 1 5 5 10 0 0 5 x2
0 0 10 1 − 12 1 0 11 s3
12 1 4
0 0 5 5 5 0 1 11 z

Aleksei Tepljakov 18 / 35
Simplex Method: Solving Minimum Linear
Programming Problems (continued)

And then the 3rd table:

x1 x2 x3 s1 s2 s3 z′ b variables
4 2 1
1 0 5 5 10 0 0 4 x1
2 1 3
0 1 5 5 10 0 0 5 x2
0 0 10 1 − 12 1 0 11 s3
12 1 4
0 0 5 5 5 0 1 11 z

Aleksei Tepljakov 18 / 35
Simplex Method: Solving Minimum Linear
Programming Problems (continued)

And then the 3rd table:

x1 x2 x3 s1 s2 s3 z′ b variables
4 2 1
1 0 5 5 10 0 0 4 x1
2 1 3
0 1 5 5 10 0 0 5 x2
0 0 10 1 − 12 1 0 11 s3
12 1 4
0 0 5 5 5 0 1 11 z

In the above table we see that there are no negative entries in the
objective row. Hence, the optimal solution is found. Therefore,
′
zmax = 11 for x1 = 4, x2 = 5, x3 = 0, s1 = 0, s2 = 0, s3 = 11. Hence,
the solution of the original problem is zmin (4, 5, 0) = −11.

Aleksei Tepljakov 18 / 35
Simplex Method: Exercise

Solve the following linear programming problem by means of the

Simplex method.

z = 4x1 + 3x2 → max

3x1 + x2 6 9
−x1 + x2 6 1
x1 + x2 6 6
x1 > 0, x2 > 0

Aleksei Tepljakov 19 / 35
Simplex Method: Summary

1. Add slack variables to change the constraints into equations and write all
variables to the left of the equal sign and constants to the right.
2. Write the objective function with all nonzero terms to the left of the equal
sign and zero to the right. The variable to be maximized must be positive.
3. Set up the initial simplex table by creating an augmented matrix from the
equations, placing the equation for the objective function last.
4. Determine a pivot element and use matrix row operations to convert the
column containing the pivot element into a unit column.
5. If negative elements still exist in the objective row, repeat Step 4. If all
elements in the objective row are positive, terminate the process.
6. When the final matrix has been obtained, determine the final basic
solution. This will give the maximum value for the objective function and
the values of the variables where this maximum occurs.

Aleksei Tepljakov 20 / 35
Simplex Method: Special Cases

• Alternate optimal solutions. The linear programming

problem has alternative optimal solutions (multiple optimal
solutions) if at least one of the coefficients of the nonbasic
variable in the objective row equals to zero.

Aleksei Tepljakov 21 / 35
Simplex Method: Special Cases

• Alternate optimal solutions. The linear programming

problem has alternative optimal solutions (multiple optimal
solutions) if at least one of the coefficients of the nonbasic
variable in the objective row equals to zero.
• Degeneracy. A situation, when a basic solution has a basic
variable that is equal to zero. The basic solution is then said to
be degenerate. This situation may lead to cycling —a sequence
of pivots that goes through the same tables and repeats itself
indefinitely. Fortunately, cycling is rare, though degeneracy is
frequent.

Aleksei Tepljakov 21 / 35
Simplex Method: Special Cases

• Alternate optimal solutions. The linear programming

problem has alternative optimal solutions (multiple optimal
solutions) if at least one of the coefficients of the nonbasic
variable in the objective row equals to zero.
• Degeneracy. A situation, when a basic solution has a basic
variable that is equal to zero. The basic solution is then said to
be degenerate. This situation may lead to cycling —a sequence
of pivots that goes through the same tables and repeats itself
indefinitely. Fortunately, cycling is rare, though degeneracy is
frequent.
• Unbounded optimum. If an identified pivot column consists
of only negative entries, the problem is unbounded.

Aleksei Tepljakov 21 / 35
Nelder-Mead Simplex Method

• The Nelder-Mead simplex method is used for solving unconstrained

optimization problems of the form

min F (x), x ∈ Rn .
x

• It is a direct search method, and is therefore well-suited to optimize a

function whose derivatives are unknown or non-existent.
• The method typically produces significant improvement of a performance
measure in industrial control applications within the first few iterations.
• It may be applied in cases, when cost function evaluation is relatively
expensive.
• It is difficult to formulate stopping criteria for the method, since the
iterates may enter a local minimum, and very little progress is made in
terms of improving performance over the next iterations. Thus, a limit on
the maximum number of iterations should be established.

Aleksei Tepljakov 22 / 35
Nelder-Mead Simplex Method: Summary

First, an initial simplex is constructed by determining n + 1 vertices

along with corresponding values of F . The kth iteration then consists of
the following steps:
1. Order. Order the n + 1 vertices, so that
F (x1 ) 6 F (x2 ) 6 · · · 6 F (xn+1 ) is satisfied. Apply tie-breaking
rules when necessary.
2. Reflect. Compute the reflection point xr = x̄ + ρ(x̄ − xn+1 ), where
n
X
x̄ = xi /n
i=1

is the centroid of the n best vertices. Evaluate Fr = F (xr ). If

F1 6 Fr < Fn , set xn+1 = xr and terminate the iteration.

Aleksei Tepljakov 23 / 35
Nelder-Mead Simplex Method: Summary
(continued)
3 Expand. If Fr < F1 , calculate the expansion point
xe = x̄ + χ(xr − x̄), and evaluate Fe = F (xe ). If Fe < Fr , set
xn+1 = xe and terminate the iteration. Otherwise, set xn+1 = xr
and terminate the iteration.
4 Contract. If Fr > Fn , perform a contraction between x̄ and the
better of xn+1 and xr :

(a) Contract outside. If Fn 6 Fr < Fn+1 , calculate

xc = x̄ + γ(xr − x̄) and evaluate Fc = F (xc ). If Fc 6 Fr , set
xn+1 = xc and terminate the operation. Otherwise, go to
Step 5 (perform a shrink).
(b) Contract inside. If Fr > Fn+1 , perform an inside
contraction: calculate x′c = x̄ − γ(x̄ − xn+1 ) and evaluate
Fc′ = F (x′c ). If Fc′ <Fn+1 set xn+1 = x′c and terminate the
iteration. Otherwise, go to Step 5 (perform a shrink).

Aleksei Tepljakov 24 / 35
Nelder-Mead Simplex Method: Summary
(continued)

5 Shrink. Define n new vertices from

xi = x1 + σ(xi − x1 ), i = 2, . . . , n + 1,

and evaluate F at these points.

In the algorithm described above four scalar coefficients are used,

i.e., the coefficients of reflection, expansion, contraction, and
shrinkage, denoted by ρ, χ, γ, and σ, respectively. According to
the original paper, these coefficients should satisfy

ρ > 0, χ > 1, 0 < γ < 1, 0 < σ < 1.

Aleksei Tepljakov 25 / 35
Nelder-Mead Simplex Method: Examples

• Rosenbrock function
fR (x1 , x2 ) = (1 − x1 )2 + 100(x2 − x21 )2 .

It has a global minimum at f (1, 1) = 0.

Aleksei Tepljakov 26 / 35
Nelder-Mead Simplex Method: Examples

• Rosenbrock function
fR (x1 , x2 ) = (1 − x1 )2 + 100(x2 − x21 )2 .

It has a global minimum at f (1, 1) = 0.

• Himmelblau’s function
fH (x1 , x2 ) = (x21 + x2 − 11)2 + (x1 + x22 − 7)2 .

It has four local minima:

◦ f (3, 2) = 0,
◦ f (−2.805118, 3.131312) = 0,
◦ f (−3.779310, −3.283186) = 0,
◦ f (3.584428, −1.848126) = 0.

Aleksei Tepljakov 26 / 35
General Nonlinear Optimization Problem

Recall that the single objective optimization problem can be

written as

 c ne (x) = 0, i ∈ I ,
 i
minn f (x) subject to cni j (x) 6 0, j ∈ E , (1)
x∈R 
 L
xk 6 xk 6 xU k, k∈K,

where f , cne
i and c ni are scalar-valued functions of the variables x,
j
xL
k and x U are lower and upper scalar bounds, respectively, and
k
I ,E , and K are sets of indices.

Aleksei Tepljakov 27 / 35
Problems with Bounds and Constraints for
Unconstrained Optimization Algorithms

• While certain optimization algorithms, such as the Nelder-Mead

method, are designed to solve unconstrained problems
unbounded in the search space, it is possible to introduce both
variable search space bounds and constraints in terms of
coordinate transformations and penalty functions.

Aleksei Tepljakov 28 / 35
Problems with Bounds and Constraints for
Unconstrained Optimization Algorithms

• While certain optimization algorithms, such as the Nelder-Mead

method, are designed to solve unconstrained problems
unbounded in the search space, it is possible to introduce both
variable search space bounds and constraints in terms of
coordinate transformations and penalty functions.
• For search variable bounds coordinate transformations may be
used. We use quadratic and trigonometric transformations.

Aleksei Tepljakov 28 / 35
Problems with Bounds and Constraints for
Unconstrained Optimization Algorithms

• While certain optimization algorithms, such as the Nelder-Mead

method, are designed to solve unconstrained problems
unbounded in the search space, it is possible to introduce both
variable search space bounds and constraints in terms of
coordinate transformations and penalty functions.
• For search variable bounds coordinate transformations may be
used. We use quadratic and trigonometric transformations.
• For introducing constraints we use penalizing terms (through
the use of penalty functions) which are added to the cost
function.

Aleksei Tepljakov 28 / 35
Problems with Bounds and Constraints:
Coordinate Transformation
• Let x denote the vector of search variables of size N × 1. For bound
constraints, a coordinate transformation may be applied to each
individual search variable. Let xL
i and x U
i denote the lower bound and
upper bound on the ith search parameter, respectively, and denote by
z the new search variable vector. Let ϕ : R → R denote a coordinate
transformation function, such that x = ϕ(z) and z = ϕ−1 (x).

Aleksei Tepljakov 29 / 35
Problems with Bounds and Constraints:
Coordinate Transformation
• Let x denote the vector of search variables of size N × 1. For bound
constraints, a coordinate transformation may be applied to each
individual search variable. Let xL
i and x U
i denote the lower bound and
upper bound on the ith search parameter, respectively, and denote by
z the new search variable vector. Let ϕ : R → R denote a coordinate
transformation function, such that x = ϕ(z) and z = ϕ−1 (x).
• For problems with lower bounds we have

xi = xL 2
i + zi ,

from which it follows that xi > xL 2

i , since zi > 0. Initial estimates
zi,0 are obtained from original initial estimates xi,0 > xLi as
q
zi,0 = xi,0 − xL i .

Aleksei Tepljakov 29 / 35
Problems with Bounds and Constraints:
Coordinate Transformation (continued)

• For problems with upper bounds we have

xi = xU 2
i − zi ,

from which it follows that xi 6 xUi , since −z 2 6 0. Initial

i
estimates zi,0 are obtained from original initial estimates
xi,0 6 xU
i as q
zi,0 = xU
i − xi,0 .

Aleksei Tepljakov 30 / 35
Problems with Bounds and Constraints:
Coordinate Transformation (continued)

• For problems with lower and upper bounds, we have

L sin(zi ) +1
xi = xL
i + (xU
i − xi ) ,
2
from which it follows that xL U
i 6 xi 6 xi , since the values of the
function f (zi ) = (sin(zi ) + 1)/2 are always inside of the interval
[0, 1] and xi is therefore bounded by f (zi ) = 0 ⇒ xi = xL i ,
f (zi ) = 1 ⇒ xi = xU i . Initial estimates zi,0 are obtained from
original initial estimates xLi 6 x i,0 6 x U as
i
  
−2xi,0 + xL
i + xU
i
zi,0 = ℜ arcsin ,
xLi − x U
i

where ℜ(·) denotes the real part.

Aleksei Tepljakov 31 / 35
Problems with Bounds and Constraints:
Penalty Functions
To introduce constraints, a modification of the cost function

κ(·) = κ∗ ,

where κ∗ denotes the cost for the original optimization problem, is necessary.
Let us define a function fnz : R → R+ such that
(
x, x > 0
fnz (x) :=
0, x 6 0.

Let us also define a penalty function ρ : R → R such that

(
eγ − 1 + x, x > γ
ρ(x) :=
ex − 1, x 6 γ,

where γ > 0 is some predefined constant.

Aleksei Tepljakov 32 / 35
Problems with Bounds and Constraints:
Penalizing Nonlinear Equality Constraints

For general nonlinear equality constraints of the form cne (·) 6 0,

where cne : Rq×r → RNne ×Mne , we define the penalty function
κne : RNne ×Mne → R as

κne (cne (·)) := ρ(cne

Σ (·)),

where
Nne M
X X ne

cne
Σ (·) = fnz (|cne
i,k (·)|),
i=1 k=1

where | · | denotes the absolute value.

Aleksei Tepljakov 33 / 35
Problems with Bounds and Constraints:
Penalizing Nonlinear Inequality Constraints

For general nonlinear inequality constraints of the form cni (·) 6 0, where
cni : Rq×r → RNni ×Mni , we define the following penalty function
κni : RNni ×Mni → R as

κni (cni (·)) := ρ(cni

Σ (·)),

where
Nni M
X X ni

cni
Σ (·) = fnz (cni
i,k (·)).
i=1 k=1

Thus, taking both equality and inequality constraints into account, the
new cost function is

κ(·) = κ∗ + |κne {z
+ κni} .
Penalizing terms

Aleksei Tepljakov 34 / 35
Questions?

Thank you for your attention!

Aleksei Tepljakov 35 / 35