Optimization Techniques

Amrita Vishwa Vidyapeetham

October 13, 2020

Outline

Multivariable Optimization
Optimization Problem
Unconstrained Optimization
Example
Outline

Multivariable Optimization
Optimization Problem
Unconstrained Optimization
Example
STATEMENT OF AN OPTIMIZATION PROBLEM

An optimization or a mathematical programming problem can be stated as

follows.  
x1
 x2 
Find X =  .  which minimizes f (X)
 
 .. 
xn
subject to the constraints

gj (X) ≤ 0, j = 1, 2, . . . , m
(1)
lj (X) = 0, j = 1, 2. . . . , p,

where X is an n-dimensional vector called the design vector, f (X) is termed

the objective function, and gj (X) and lj (X) are known as inequality and
equality constraints, respectively. The number of variables n and the number
of constraints m and/or p need not be related in any way. The problem stated
in Eq. (1) is called a constrained optimization problem.
Unconstrained Optimization

Some optimization problems do not involve any constraints and can be

stated as  
x1
 x2 
Find X =  .  which minimizes f (X).
 
 . .
xn
Unconstrained Optimization

Some optimization problems do not involve any constraints and can be

stated as  
x1
 x2 
Find X =  .  which minimizes f (X).
 
 . .
xn
Such problems are called unconstrained optimization problems.
Graphical Representation
Outline

Multivariable Optimization
Optimization Problem
Unconstrained Optimization
Example
Multivariable Optimization with no Constraints
In this lecture, we consider the necessary and sufficient conditions for
the minimum or maximum of an unconstrained function of several
variables.
Multivariable Optimization with no Constraints
In this lecture, we consider the necessary and sufficient conditions for
the minimum or maximum of an unconstrained function of several
variables.
Necessary Condition:

Theorem
If f (X) has an extreme point (maximum or minimum) at X = X ∗ and if the
first-order partial derivatives of f (X) exist at X ∗ , then

∂f ∂f ∂f
(X ∗ ) = (X ∗ ) = · · · = (X ∗ ) = 0.
∂x1 ∂x2 ∂xn
Multivariable Optimization with no Constraints
In this lecture, we consider the necessary and sufficient conditions for
the minimum or maximum of an unconstrained function of several
variables.
Necessary Condition:

Theorem
If f (X) has an extreme point (maximum or minimum) at X = X ∗ and if the
first-order partial derivatives of f (X) exist at X ∗ , then

∂f ∂f ∂f
(X ∗ ) = (X ∗ ) = · · · = (X ∗ ) = 0.
∂x1 ∂x2 ∂xn

Sufficient Condition:
Theorem
A sufficient condition for a stationary point X ∗ to be an extreme point is that
the matrix of second-order partial derivatives (Hessian matrix) of f (X)
evaluated at X ∗ is (i) positive definite when X ∗ is a relative minimum point,
and (ii) negative definite when X ∗ is a relative maximum point.
Hessian Matrix

The Hessian matrix J of f (x) at X = X ∗ is given by

∂2f ∂2f ∂2f

 
...
 ∂x12 ∂x1 ∂x2 ∂x1 ∂xn 
∂2f ∂2f ∂2f
 
 
 ... 
Jn×n = ∇2 f (X ∗ ) = 
 ∂x1 ∂x2 ∂x22 ∂x2 ∂xn 

 .. .. .. .. 

 . . . . 

 ∂2f ∂2f ∂2f 
...
∂xn ∂x1 ∂xn ∂x2 ∂xn2 X=X ∗

Note that the Hessian Matrix is a symmetry matrix.

Note
A point X ∗ is a stationary point if ∇f (X ∗ ) = 0. Furthermore, the point is a
minimum, a maximum, or an inflection point if ∇2 f (X ∗ ) is positive-definite,
negative-definite, or otherwise.
Positive and Negative Definite
I Positive Definite: A matrix A will be positive definite if all its
eigenvalues are positive; that is, all the values of λ that satisfy the
determinantal equation
|A − λI| = 0 (2)
should be positive.
Positive and Negative Definite
I Positive Definite: A matrix A will be positive definite if all its
eigenvalues are positive; that is, all the values of λ that satisfy the
determinantal equation
|A − λI| = 0 (2)
should be positive.
I Negative Definite: Similarly, the matrix [A] will be negative definite if
its eigenvalues are negative.
Positive and Negative Definite
I Positive Definite: A matrix A will be positive definite if all its
eigenvalues are positive; that is, all the values of λ that satisfy the
determinantal equation
|A − λI| = 0 (2)
should be positive.
I Negative Definite: Similarly, the matrix [A] will be negative definite if
its eigenvalues are negative.
I Another test that can be used to find the positive definiteness of a
matrix A of order n involves evaluation of the determinants: A1 = |a11 |,
a11 a12 a13
a a12
A2 = 11 , A3 = a21 a22 a23 , . . . ,
a21 a22
a31 a32 a33
a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
An = 31 a32 a33 ... a3n
a
.. .. .. .. ..
. . . . .
an1 an2 an3 ... ann
Positive and Negative Definite Matrix

B Positive definite : The matrix A will be positive definite if and only if

all the values A1 , A2 , A3 , ..., An are positive.
Positive and Negative Definite Matrix

B Positive definite : The matrix A will be positive definite if and only if

all the values A1 , A2 , A3 , ..., An are positive.
B Negative definite: The matrix A will be negative definite if and only if
the sign of Aj is (−1)j for j = 1, 2, ..., n.
Positive and Negative Definite Matrix

B Positive definite : The matrix A will be positive definite if and only if

all the values A1 , A2 , A3 , ..., An are positive.
B Negative definite: The matrix A will be negative definite if and only if
the sign of Aj is (−1)j for j = 1, 2, ..., n.
B Positive semidefinite: If some of the Aj are positive and the remaining
Aj are zero, the matrix A will be positive semidefinite.
Positive and Negative Definite Matrix

B Positive definite : The matrix A will be positive definite if and only if

all the values A1 , A2 , A3 , ..., An are positive.
B Negative definite: The matrix A will be negative definite if and only if
the sign of Aj is (−1)j for j = 1, 2, ..., n.
B Positive semidefinite: If some of the Aj are positive and the remaining
Aj are zero, the matrix A will be positive semidefinite.
Saddle Point: In the case of a function of two variables, f (x, y), the Hessian
matrix may be neither positive nor negative definite at a point (x∗ , y∗ ) at
which
∂f ∂f
= = 0. (3)
∂x ∂y
In such a case, the point (x∗ , y∗ ) is called a saddle point.
Positive and Negative Definite Matrix

B Positive definite : The matrix A will be positive definite if and only if

all the values A1 , A2 , A3 , ..., An are positive.
B Negative definite: The matrix A will be negative definite if and only if
the sign of Aj is (−1)j for j = 1, 2, ..., n.
B Positive semidefinite: If some of the Aj are positive and the remaining
Aj are zero, the matrix A will be positive semidefinite.
Saddle Point: In the case of a function of two variables, f (x, y), the Hessian
matrix may be neither positive nor negative definite at a point (x∗ , y∗ ) at
which
∂f ∂f
= = 0. (3)
∂x ∂y
In such a case, the point (x∗ , y∗ ) is called a saddle [Link] characteristic of
a saddle point is that it corresponds to a relative minimum or maximum of
f (x, y) with respect to one variable, say, x (the other variable being fixed at
y = y∗ ) and a relative maximum or minimum of f (x, y) with respect to the
second variable y (the other variable being fixed at x∗ ).
Example:

As an example, consider the function f (x, y) = x2 − y2 . For this function,

∂f ∂f
= 2x and = −2y.
∂x ∂y
These first derivatives are zero at x∗ = 0 and y∗ = 0. The Hessian matrix of
f at (x∗ , y∗ ) is given by  
2 0
J= .
0 −2
Since this matrix is neither positive definite nor negative definite, the point
(x∗ = 0, y∗ = 0) is a saddle point. The function is shown graphically in Fig.
2.5. It can be seen that f (x, y∗ ) = f (x, 0) has a relative minimum and
f (x∗ , y) = f (0, y) has a relative maximum at the saddle point (x∗ , y∗ ).
Saddle points may exist for functions of more than two variables also. The
characteristic of the saddle point stated above still holds provided that x and
y are interpreted as vectors in multidimensional cases.
Graphical Representation
Outline

Multivariable Optimization
Optimization Problem
Unconstrained Optimization
Example
Finding Optimum

Example
Find the extreme points of the function f (x1 , x2 ) = x13 + x23 + 2x12 + 4x22 + 6.

Solution: The necessary conditions for the existence of an extreme point are

∂f
= 3x12 + 4x1 = x1 (3x1 + 4) = 0,
∂x1
∂f
= 3x22 + 8x2 = x2 (3x2 + 8) = 0.
∂x2
These equations are satisfied at the points
8 4 4 8
(0, 0), (0, − ), (− , 0), and (− , − ).
3 3 3 3
Finding Optimum

Example
Find the extreme points of the function f (x1 , x2 ) = x13 + x23 + 2x12 + 4x22 + 6.

Solution: The necessary conditions for the existence of an extreme point are

∂f
= 3x12 + 4x1 = x1 (3x1 + 4) = 0,
∂x1
∂f
= 3x22 + 8x2 = x2 (3x2 + 8) = 0.
∂x2
These equations are satisfied at the points
8 4 4 8
(0, 0), (0, − ), (− , 0), and (− , − ).
3 3 3 3
To find the nature of these extreme points, we have to use the sufficiency
conditions. The second-order partial derivatives of f are given by
Finding Optimum

∂2f
= 6x1 + 4,
∂x12
∂2f
= 6x2 + 8,
∂x22
∂2f ∂2f
= = 0.
∂x1 x2 ∂x2 x1
The Hessian matrix of f is given by
 
6x1 + 4 0
J= .
0 6x2 + 8
Finding Optimum

∂2f
= 6x1 + 4,
∂x12
∂2f
= 6x2 + 8,
∂x22
∂2f ∂2f
= = 0.
∂x1 x2 ∂x2 x1
The Hessian matrix of f is given by
 
6x1 + 4 0
J= .
0 6x2 + 8

6x1 + 4 0
If J1 = |6x1 + 4| and J2 = the values of J1 and J2 and
0 6x2 + 8
the nature of the extreme point are given in the next slide:
Finding Optimum
Exercise:

F Answer whether each of the following quadratic forms is positive

definite, negative definite, or neither:
I f = x12 − x22
I f = 4x1 x2
I f = x12 + 2x22
I f = −x12 + 4x1 x2 + 4x22
I f = −x12 + 4x1 x2 − 9x22 + 2x1 x3 + 8x2 x3 − 4x32
Exercise:

F Answer whether each of the following quadratic forms is positive

definite, negative definite, or neither:
I f = x12 − x22
I f = 4x1 x2
I f = x12 + 2x22
I f = −x12 + 4x1 x2 + 4x22
I f = −x12 + 4x1 x2 − 9x22 + 2x1 x3 + 8x2 x3 − 4x32
F Express the function

f (x1 , x2 , x3 ) = −x12 − x22 + 2x1 x2 − x32 + 6x1 x3 + 4x1 − 5x3 + 2

in matrix form as
1 T
f (X) = X [A]X + BT X + C
2
and determine whether the matrix [A] is positive definite, negative
definite, or indefinite.
Exercise:

F The ultimate strength attained by concrete is found to be based on a

certain empirical relationship between the ratios of cement and concrete
used. Our objective is to maximize strength attained by hardened
concrete, given by
3
f (X) = 20 + 2x1 − x12 + 6x2 − x22
2
, where x1 and x2 are variables based on cement and concrete ratios.
Exercise: