Optimization methods in Engineering

MODULE –II

CLASSICAL OPTIMIZATION TECHNIQUES

Background
In the previous module before mid semester we discussed most widely used optimization i.e.
linear programming. The characteristics of linear programming problem (LPP) and also
different techniques to solve LPP were introduced.
The module started with the definition of LPP, underlying assumptions and elementary
operations. Illustration of graphical method helped to conceive the idea behind the solution of
LPP. Once the concept becomes clear, theoretical as well as logical approach of most popularly
used simplex method was explained. Discussion on duality in LPP, and Primal-Dual relation
helped to understand the practical application of LPP.
At the end of the module the students will be able to

1. Formulate the LPP.

2. Conceptualize the feasible region.

3. Solve the LPP with two variables using graphical method.

4. Solve the LPP using simplex method.

5. Formulate the dual problem from primal.

Introduction
In this module the classical optimization techniques are discussed which are useful in
finding the optimum solution or unconstrained maxima or minima of continuous and
differentiable functions. These are analytical methods and make use of differential calculus in
locating the optimum solution. The classical methods have limited scope in practical
applications as some of them involve objective functions which are not continuous and/or
differentiable. Yet, the study of these classical techniques of optimization form a basis for
developing most of the numerical techniques that have evolved into advanced techniques more
suitable to today’s practical problems.
Four main types of problems can be handled by the classical optimization techniques, viz.,
1) A single variable function with no constraint
2) A multivariable function with no constraint

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

3) A multivariable function with equality constraint.

4) A multivariable function with inequality, constraint.
In this module we present the necessary and sufficient conditions in locating the optimum
solution for the above mentioned problem. For problems with equality constraints the Lagrange
multiplier method can be used.
In this module a brief introduction to stationary points is followed by a presentation of
the necessary and sufficient conditions in locating the optimum solution of a single variable
and two variable functions.
Convexity and concavity of these functions are explained. Then the reader is introduced
to the optimization of functions or single and multivariable functions (with and without equality
constraints). A few examples are discussed for each type.
An insight is also given to the Lagrangian function and Hessian matrix formulation.

This module will help the students to know about

1. Stationary points as maxima, minima and points of inflection
2. Concavity and convexity of functions
3. Necessary and sufficient conditions for optimization for both single and multivariable
functions
4. The Hessian matrix
5. Optimization of multivariable function with and without equality constraints.

But before that a quick REVIEW OF BASIC CALCULUS CONCEPT is necessary.

******************************
References:
1. Rao S.S., Engineering Optimization – Theory and Practice, Third Edition, New Age
International Limited, New Delhi, 2000.
2. Taha H.A., Operations Research – An Introduction, Prentice-Hall of India Pvt. Ltd., New
Delhi, 2005.
3. D Nagesh Kumar, IISc, Bangalore (source: Nptel)

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

Lecture Note-1

Review of Basic Calculus Concept

1.1 Introduction

Most of optimization problems involve functions of several variables. For this, it is important
to be comfortable with vector calculus in order to understand the optimality conditions.

1. Here the differential notation for functions of several variables is introduced.

2. The gradient vector of a function as several variables requiring first partial derivatives
of a function is introduced.
3. The Hessian matrix for the function requiring second partial derivatives of the function
is then defined.
4. Taylor's expansion for functions of single and multiple variables are discussed.

The idea of Taylor series is fundamental to the development of optimum design concepts.

1.2 Gradient Vector

Consider a function f(x) of n variables x1, x2, x3, …, xn

The partial derivative of a function with respect to x1 at a given point x* is defined as
𝜕𝑓(𝑥 ∗ )
.
𝜕𝑥1

Let Ci represent the partial derivative of f(x) with respect to xi at point x*

𝜕𝑓(𝑥 ∗ )
𝐶𝑖 = ; i = 1 to n
𝜕𝑥𝑖

For convenience and compactness of notations, we arrange the partial derivatives into a column
vector called the gradient vector. It can be represented as
𝜕𝑓
C, ∇f, or grad f
𝜕𝑥

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

𝜕𝑓(𝑥 ∗ )
𝜕𝑥1
𝜕𝑓(𝑥 ∗ ) 𝑇
∗) 𝜕𝑥 𝜕𝑓(𝑥 ∗ ) 𝜕𝑓(𝑥 ∗ ) 𝜕𝑓(𝑥 ∗ )
𝐶 = ∇𝑓(𝑥 = 2 =[ …… ]
⋮ 𝜕𝑥1 𝜕𝑥2 𝜕𝑥𝑛
⋮
𝜕𝑓(𝑥 ∗ )
[ 𝜕𝑥𝑛 ]
where superscript T denotes transpose of a vector or matrix.
Geometrically, the gradient vector is normal to the tangent plane at point x*. Also, it points in
the direction Maximum increase in the function.

1.3 Hessian Matrix

Differentiating the gradient vector once again we obtain a matrix of record partial derivatives
for the function f(x) called the Hessian Matrix (H). That is, differentiating each component of
the gradient vector with respect to x1, x2, x3, …, xn we obtain

𝜕2 𝑓 𝜕2 𝑓 𝜕2 𝑓
……
𝜕𝑥12 𝜕𝑥1 𝑥2 𝜕𝑥1 𝑥𝑛
𝜕2 𝑓 𝜕2 𝑓 𝜕2 𝑓
𝜕𝑥2 𝑥1 𝜕𝑥2 2…… 𝜕𝑥2 𝑥𝑛
𝐻= All derivatives are calculated at the given Point x*.
⋮
⋮
𝜕2 𝑓 𝜕2 𝑓 𝜕2 𝑓
[𝜕𝑥𝑛 𝑥1 …… 2]
𝜕𝑥𝑛 𝑥2 𝜕𝑥𝑛

As we see Hessian is an n×n matrix, also denoted as H or∇2 𝑓. It is important to note that each
element of the Hessian is a function in itself that is evaluated at the given point x*.
NOTE :- Since f(x) is assured to be twice continuously differentiable, the cross Partial
derivatives are equal i.e.
𝜕 2𝑓 𝜕 2𝑓
= ; i = 1 to n, j = 1 to n
𝜕𝑥𝑖 𝑥𝑗 𝜕𝑥𝑗 𝑥𝑖
Therefore Hessian is always a symmetric matrix.
It plays a important role in the sufficiency conditions for optimality (Discussed Later)

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

1.4 Taylor's Expansion

A function can be approximated by Polynomials in a neighbourhood of any point in terms of

its values and derivatives using Taylor's Expansion

For Single Variable Functions – About Pt x*

∗)
𝜕𝑓(𝑥 ∗ ) ∗)
1 𝜕 2 𝑓(𝑥 ∗ )
𝑓(𝑥) = 𝑓(𝑥 + (𝑥 −𝑥 + 2
(𝑥 − 𝑥 ∗ )2 + 𝑅
𝜕𝑥 2 𝜕𝑥

R = remainder term smaller than the previous from if x is close to x*

Now let
(x-x*) =d (a small change in the point x*)
Then Taylor's Expansion is
𝜕𝑓(𝑥 ∗ ) 1 𝜕 2 𝑓(𝑥 ∗ ) 2
𝑓(𝑥 ∗ + 𝑑) = 𝑓(𝑥 ∗ ) + 𝑑+ 𝑑 +𝑅
𝜕𝑥 2 𝜕𝑥 2

For Functions of Two Variables (x1, x2)

𝜕𝑓 𝜕𝑓
𝑓(𝑥1 , 𝑥2 ) = 𝑓(𝑥1∗ , 𝑥2∗ ) + (𝑥1 − 𝑥1∗ ) + (𝑥 − 𝑥2∗ )
𝜕𝑥1 𝜕𝑥2 2
1 𝜕 2 𝑓(𝑥1 − 𝑥1∗ )2 𝜕 2𝑓 ∗ ∗
𝜕 2 𝑓(𝑥2 − 𝑥2∗ )2
+ [ +2 (𝑥 − 𝑥1 )(𝑥2 − 𝑥2 ) + ]+𝑅
2 𝜕𝑥12 𝜕𝑥1 𝜕𝑥2 1 𝜕𝑥22

Now for notational compactness using summation notation the above equation can be rewritten
as
2 2 2
𝜕𝑓 1 𝜕 2 𝑓(𝑥𝑖 − 𝑥𝑖∗ )(𝑥𝑗 − 𝑥𝑗∗ )
𝑓(𝑥1 , 𝑥2 ) = 𝑓(𝑥1∗ , 𝑥2∗ ) +∑ (𝑥𝑖 − 𝑥𝑖∗ ) + ∑ ∑ +𝑅
𝜕𝑥𝑖 2 𝜕𝑥𝑖 𝜕𝑥𝑗
𝑖=1 𝑖=1 𝑗=1

𝜕𝑓
= grade of f(x) at the given point x*=∇𝑓(𝑥);
𝜕𝑥𝑖

𝜕2 𝑓
= Hessian at the given point x* = H
𝜕𝑥𝑖 𝜕𝑥𝑗

Therefore Taylor's Expansion in matrix Notation

1
𝑓(𝑥) = 𝑓(𝑥 ∗ ) + ∇𝑓 𝑇 (𝑥 − 𝑥 ∗ ) + (𝑥 − 𝑥 ∗ )𝑇 𝐻(𝑥 − 𝑥 ∗ ) + 𝑅
2
H=2x2 Hessian Matrix

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

Generalized Form of Taylor’s Expansion

For n variables ∇𝑓 is a n dimensional vector and H is the n x n Hessian Matrix

1 𝑇
𝑓(𝑥 ∗ + 𝑑) = 𝑓(𝑥 ∗ ) + ∇𝑓 𝑇 𝑑 + 𝑑 𝐻𝑑 + 𝑅
2

****************************

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

Lecture Notes – 2

Stationary points

Definition of Relative and Global Optimum

1.1 Introduction

In this session, stationary points of a function are defined. The necessary and sufficient
conditions for the relative maximum of a function of single or two variables are also discussed.
The global optimum is also defined in comparison to the relative or local optimum.

1.2 Stationary points

*
For a continuous and differentiable function f(x) a stationary point x is a point at which the
* *
slope of the function vanishes, i.e. f ’(x) = 0 at x = x , where x belongs to its domain of
definition. A stationary point may be a minimum, maximum or an inflection point (Fig. 1).

Minimum Maximum Inflection Point

1.3 Relative And Global Optimum

Relative (Local) Minima
A function f(x) of n variables has a local (Relative) minimum at x =x* if
f(x*) ≤ f(x*+h) for all h in the small neighbourhood of x* in the feasible design space

Local (Relative) Maxima

A function f (x) of n variables has a local Relative Maximum at x = x* if
f(x) ≥f(x*+h) for all h in the mall neighbourhood of x* in the feasible design space.

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

Global (Absolute) Minimum

A function f(x) as a variables has global (absolute) Minimum at x* if
f(x*) ≤ f(x) for all x in the feasible Design space

Global (Absolute) Maximum

A function f(x) of n variables has global (obsolete) Maximum at x* it
f(x*)≥f(x) for all x in the feasible Design space.

Note: For unconstrained optimization problems since there are no constraints, the entire
design space is feasible.

**********************************

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

Lecture Notes – 3

Convexity and Concavity of Functions

3.1 Introduction

In the previous class we studied about stationary points and the definition of relative
and global optimum. The necessary and sufficient conditions required for a relative optimum
in functions of one variable and its extension to functions of two variables was also studied. In
this lecture, determination of the convexity and concavity of functions is discussed.
The analyst must determine whether the objective functions and constraint equations are
convex or concave. In real-world problems, if the objective function or the constraints are not
convex or concave, the problem is usually mathematically intractable.

3.2 Definition
Convex Function
A function f (X) is said to be convex if for any pair of points

and all λ, 0 ≤ λ ≤ 1,
f [λX2 + (1 − λ)X1] ≤ λf (X2) + (1 − λ)f (X1)
that is, if the segment joining the two points lies entirely above or on the graph of f (X). Figures
A.1a and A.2a illustrate a convex function in one and two dimensions, respectively. It can be
seen that a convex function is always bending upward and hence it is apparent that the local
minimum of a convex function is also a global minimum.
Concave Function
A function f (X) is called a concave function if for any two points X1 and X2, and for all
0 ≤ λ ≤ 1,
f [λX2 + (1 − λ)X1] ≥ λf (X2) + (1 − λ)f (X1) (A.2)
that is, if the line segment joining the two points lies entirely below or on the graph of f (X).
Figures A.1b and A.2b give a concave function in one and two dimensions, respectively.

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

It can be seen that a concave function bends downard and hence the local maximum will also
be its global maximum. It can be seen that the negative of a convex function is a concave
function, and vice versa. Also note that the sum of convex functions is a convex function and
the sum of the concave functions is a concave function. A function f (X) is strictly convex or
concave if the strict inequality holds in Eqs. (A.1) or (A.2) for any X1 _= X2. A linear function
will be both convex and concave since it satisfies both inequalities (A.1) and (A.2). A function
may be convex within a region and concave elsewhere. An example of such a function is shown
in Fig. A.3.

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

3.3 Testing the Convexity of a Single Variable Function

A function is convex if its slope is non decreasing or
𝜕2 𝑓
≥0
𝜕𝑥 2
It is strictly convex j its slope is continuously increasing i.e
𝜕2 𝑓
> 0 throughout the function.
𝜕𝑥 2

Properties of Convex Function

1. A differentiable function of one variable is convex on an internal if and only if its

derivatives are monotonically non decreasing on that interval.

2. A twice differentiable function of one variable is convex on an interval if and only if

its 2nd derivative is non negative in that interval. If 2nd derivative is +ve then it is
strictly convex but the converse does not hold.

3. More generally, a continuous, twice differentiable function as several variables is

convex on a convex set if and only if its Hessian Matrix is +ve semi definite on the
interior of a convex set.
Note: A strictly convex function will have only one minimum which is also the global minimum

3.4 Testing the Concavity of a Single Variable Function

A differentiable function f is concave on an interval if its derivative function f ′ is

decreasing on that interval: a concave function has a decreasing slope.

A function that is convex is often synonymously called concave upwards, and a function that
is concave is often synonymously called concave downward.
A function is concave if its slope is non increasing or
𝜕2 𝑓
≤0
𝜕𝑥 2
It is strictly concave if its slope is continuously decreasing or
𝜕2 𝑓
< 0 throughout the function.
𝜕𝑥 2

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

If f(x) is twice differentiable, then f(x) is concave if and only if f"(x) is non +ve. then the graph
is convex (or concave upward);
If its 2nd derivative is -ve then it is strictly concave but the opposite is NOT True.
Points, at which concavity changes, are called inflection points.

3.5 Testing the Convexity or Concavity of Multi Variable Function

To determine convexity or concavity of a function of multiple variables, the eigenvalues of its
Hessian matrix are examined and the following rules apply.
1. If all eigenvalues of the Hessian are positive the function is strictly convex.
2. If all eigenvalues of the Hessian are negative the function is strictly concave.
3. If some eigenvalues are positive and some are negative, or if some are zero, the function
is neither strictly concave nor strictly convex.
4. f (X) will be convex if H(X) is positive semidefinite. Further, if H(X) is positive definite,
the function f (X) will be strictly convex. It can also be proved that if f (X) is concave,
the Hessian matrix is negative semidefinite.
5. Any local minimum of a convex function f (X) is a global minimum.

ILLUSTRATIVE EXAMPLE
Ex 2.1 Pg 66 S.S. Rao
Locate the stationary points of the given function and find out if the function is convex, concave
or neither at the points of optima based on the testing rules discussed above.
𝑓(𝑥) = 12𝑥 5 − 45𝑥 4 + 40𝑥 3 + 5
Soln
𝑓 ′ (𝑥) = 60(𝑥 4 − 3𝑥 3 + 2𝑥 2 ) = 60𝑥 2 (𝑥 − 1)(𝑥 − 2)
therefore
𝑓 ′ (𝑥) = 0 𝑎𝑡 𝑥 = 0, 𝑥 = 1, 𝑥 = 2
Now the 2nd derivative
𝑓 ′′ (𝑥) = 60(4𝑥 3 − 9𝑥 2 + 4𝑥)
At x=1;
f'’(x) = - 60 and hence x=1 is a relative maximum therefore
𝑓𝑚𝑎𝑥 = 𝑓(𝑥 = 1) = 12
𝜕2𝑓
As the 2nd derivative is -ve the function at this point is concave because 𝜕𝑥 2 < 0

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

At x =2
f"(x) = 240 and hence x=2 is a relative minima therefore
𝑓𝑚𝑖𝑛 = 𝑓(𝑥 = 2) = −11
𝜕2𝑓
At this point the function is convex since 𝜕𝑥 2 > 0

At x =0
f"(x) = 0 and hence we investigate the next derivative
𝑓 ′′′ (𝑥) = 60(12𝑥 2 − 18𝑥 + 4) = 240 𝑎𝑡 𝑥 = 0
since 𝑓 ′′′ (𝑥) ≠ 0 𝑎𝑡 𝑥 = 0
At this point the function is neither a maximum nor a minimum and hence is an inflection point.
Since the third derivative is non zero hence the function is neither convex on concave at this
point.

ILLUSTRATIVE EXAMPLE
Ex A.1 Pg 782 S.S. Rao

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

************************

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

Lecture Notes – 4

Unconstrained Optimization -I
Optimality Conditions for Functions of Single Variable
Necessary And Sufficient Condition

Introduction
The conditions that must be satisfied at the optimum Point are created necessary
OR
If a point does not satisfy the necessary conditions it cannot be optimal.
Note that necessary conditions does not guarantee optimality of the point i.e. there can be non-
optimum points that also satisfy the same conditions.
So the number of Points satisfying necessary conditions can be more than the number of
optima.
Therefore to distinguish between optimum and non-optimum points, both satisfying the
necessary condition, a sufficient condition must be satisfied.
If any optimum point satisfies the sufficient conditions then it is an indeed Optimum

Summary
1. Optimum point must satisfy the necessary condition
2. A point notifying the necessary conditions need not be optimum, i.e. non optimum
points satisfy the necessary condition.
3. A point which is satisfies necessary condition and Hen Ratio is the sufficient condition
then that point is indeed optimum.
4. If sufficiency condition is not satisfied then no conclusion can be drawn about
optimality of the point satisfying necessary condition.

Optimality Conditions for Functions of Single Variable

Consider the function f(x) defined for a ≤ x ≤ b. A single variable optimization problem is one
in which the value of x=x* is to be found in the interval [a, b] such that x* minimizes f(x).
We have the following theorems to understand the necessary and sufficient conditions for the
relative maximum of a function of a single variable.

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

Necessary Conditions
Also called 1st Order Necessary Condition
For relative local minimum of f (x) at x* if the derivative df(x)/dx=f’(x) exists at a finite number
at x= x* then f’(x) = 0.
This is also true tor Relative Local Maxima.
In general, a point x* at which f’(x)=0 is called a stationary point *
NOTE - The points satisfying f'(x) = 0 can be local Minima, Maxima or neither minimum or
maximum (Inflection points).

Sufficient Condition
For the same function stated above let f'(x*) = f'’(x*) = . ….. .= f(n-1)(x*)=0, but fn(x*)≠0 then
the sufficient condition can be defined as
(1) f(x*) is a minimum value of f(x) if fn(x*)>0 and n is even
(2) f(x*) is a maximum value of f(x) if fn(x*)<0 and n is even
(3) It can never be maximum nor minimum if n is odd

Illustrative Examples
Find the optimum value of the given function and also state if the function attains a maximum
or a minimum.
f(x) = (x-2)4
solution
f’(x) = 4(x-2)3 = 0
Necessary condition
4(x-2)3=0 » x = x*= 2
x* = 2 is stationary point for maxima or minima
Sufficient condition
𝑓 ′′ (𝑥 ∗ )𝑥 ∗=2 = 12(𝑥 − 2)2 = 12(2 − 2)2 = 0
𝑓 ′′′ (𝑥 ∗ )𝑥 ∗=2 = 24(𝑥 − 2)1 = 12(2 − 2)1 = 0
𝑓 ′′′′ (𝑥 ∗ )𝑥 ∗=2 = 24
n is even and f"(x*) is +ve
So, x=x*=2 is a point of Minima and he function attain a minimum value of zero at x = x*= 2.

*****************************

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

Lecture Notes – 5

Unconstrained Optimization -II

Optimality Conditions For Multi Variable Function
Necessary And Sufficient Condition

Introduction
The concept discussed in previous lecture may be easily extended to functions of multiple
variables.
In this lecture functions of multiple variables, which are more difficult to be analyzed owing
to the difficulty in graphical representation and tedious calculations involved in mathematical
analysis, will be studied for unconstrained optimization. This is done with the aid of the
gradient vector and the Hessian matrix. Examples are discussed to show the implementation of
the technique.

Optimality Conditions
Necessary conditions
In case of multivariable functions a necessary condition for a stationary point of the function
f(X) is that each partial derivative is equal to zero. In other words, each element of the gradient
vector defined below must be equal to zero.

𝜕𝑓(𝑥) 𝜕𝑓(𝑥)
=0 ; = 0 at the stationary points i.e.
𝜕𝑓(𝑥1 ) 𝜕𝑓(𝑥2 )

the gradient vector of f(X), ∆𝑥 𝑓 at x= x* = [x1,x2] defined below must be equal to zero.

𝜕𝑓(𝑥)
(𝑋 ∗)
𝜕𝑓(𝑥1 )
∆𝑥 𝑓 = [ 𝜕𝑓(𝑥) ] =0 OR
(𝑋 ∗)
𝜕𝑓(𝑥1 )

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

Sufficient condition

Consider the following second order derivatives:

The Hessian matrix defined by H is made using the above second order derivatives.

For a stationary point X* to be an extreme point, the matrix of second partial derivatives
(Hessian matrix) of f(X) evaluated at X* must be:
a) If H is positive definite then the point X = [x1, x2] is a point of local minima.

b) If H is negative definite then the point X = [x , x ] is a point of local maxima.

1 2

c) If H is neither then the point X = [x1, x2] is neither a point of maxima nor minima.

NOTE:
1. A square matrix is positive definite if all its eigen values are positive and it is negative
definite if all its eigen values are negative.
2. If some of the eigen values are positive and some negative then the matrix is neither
positive definite or negative definite.
To calculate the eigen values λ of a square matrix then the following equation is solved.
|𝐴 − 𝜆𝐼| = 0
The above rules give the sufficient conditions for the optimization problem of two variables.
NOTE:
To determine convexity or concavity of a function of multiple variables, the eigenvalues of its
Hessian matrix are examined and the following rules apply.
(a) If all eigenvalues of the Hessian are positive the function is strictly convex.
(b) If all eigenvalues of the Hessian are negative the function is strictly concave.
(c) If some eigenvalues are positive and some are negative, or if some are zero, the function is
neither strictly concave nor strictly convex.

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

Illustrative example
Locate the stationary points of f(X) and classify them as relative maxima, relative minima or
neither based on the rules discussed in the lecture.
2𝑥13
𝑓(𝑥) = − 2𝑥1 𝑥2 − 5𝑥1 + 2𝑥22 + 4𝑥2 + 5
3
Solution
Necessary condition
𝜕𝑓(𝑥)
(𝑋 ∗)
𝜕𝑓(𝑥 ) 2𝑥12 − 2𝑥2 − 5 0
∆𝑥 𝑓 = [ 𝜕𝑓(𝑥)1 ]= [ ]= [ ]
(𝑋 ∗) −2𝑥1 + 4𝑥2 + 4 0
𝜕𝑓(𝑥1 )

𝜕𝑓(𝑥)
=0 𝑥1 = 2𝑥2 + 2
𝜕𝑓(𝑥1 )
𝜕𝑓(𝑥)
=0 2𝑥12 − 2𝑥2 − 5 = 0 substituting for 𝑥1
𝜕𝑓(𝑥2 )

2(2𝑥2 + 2)2 − 2𝑥2 − 5 = 0

8𝑥22 + 14𝑥2 + 3 = 0
(2𝑥2 + 3)(4𝑥2 + 1) = 0
so the two stationary points are
X1 = [-1,-3/2] and X2 = [3/2,-1/4]

Sufficient condition
The Hessian of f(X)
𝜕2 𝑓 𝜕2 𝑓 𝜕2 𝑓 𝜕2 𝑓
= 4𝑥1 ; =4 ; = = −2
𝜕(𝑥1 )2 𝜕(𝑥2 )2 𝜕𝑥1 𝜕𝑥2 𝜕𝑥2 𝜕𝑥1

The hessian matrix can be written as

𝜕2 𝑓 𝜕2 𝑓
𝜕(𝑥1 )2 𝜕𝑥1 𝜕𝑥2 4𝑥 −2
2 2
= [ 1 ]
𝜕 𝑓 𝜕 𝑓 −2 4
(𝜕𝑥2 𝜕𝑥1 𝜕(𝑥2 )2 )

𝜆 + 4𝑥1 2
|𝜆𝐼 − 𝐻| = [ ]
2 𝜆−4

At X = [-1,-3/2],
1

|𝜆𝐼 − 𝐻| = [𝜆 + 4 2
] = (𝜆 + 4)(𝜆 − 4) − 4 = 0
2 𝜆−4

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

𝜆2 − 16 − 4 = 0
𝜆2 = 12 hence 𝜆1 = +√12 and 𝜆2 = −√12
Since one eigen value is positive and one negative, X1 is neither a relative maximum nor a
relative minimum. The function is neither convex nor concave
At X2 = [3/2,-1/4]

2
|𝜆𝐼 − 𝐻| = [𝜆 − 6 ] = (𝜆 − 6)(𝜆 − 4) − 4 = 0
2 𝜆−4

𝜆2 − 10𝜆 + 20 = 0 hence 𝜆1 = 5 + √5 and 𝜆2 = 5 − 5

Since both the eigen values are positive, X is a local minimum. The function is convex at this point.
2

Minimum value of f(x) is -0.375.

Illustrative example

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

Since all eigenvalues are negative the function attains a maximum at the point
*
X =[1/2, 1/2, -2]

******************************

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

Lecture Notes -6
Constrained Optimization-I
Optimization of Functions of Multiple Variables subject to Equality Constraints

Introduction
In the previous lecture we learnt the optimization of functions of multiple variables studied for
unconstrained optimization. This is done with the aid of the gradient vector and the Hessian
matrix. In this lecture we will learn the optimization of functions of multiple variables subjected
to equality constraints using the method of constrained variation and the method of Lagrange
multipliers.

Constrained optimization
A function of multiple variables, f(x), is to be optimized subject to one or more equality
constraints of many variables. These equality constraints, gj(x), may or may not be linear

In this section we consider the optimization of continuous functions subjected to equality

constraints:
Minimize f = f (X)
subject to gj (X) = 0, j = 1, 2, . . . ,m where

Here m is less than or equal to n; otherwise (if m>n), the problem becomes over defined And,
in general, there will be no solution. There are several methods available for the Solution of
this problem. The methods of Lagrange multipliers are discussed in the following sections.
Solution by method of Lagrange multipliers

The problem statement is as follows:

Minimize f(x1,x2), subject to g(x1,x2) = 0

For f(x1,x2) to have a minimum at a point X* = [x1*,x2*], a necessary condition is that the total

derivative of f(x1,x2) must be zero at [x1*,x2*].

……………………………………………………………………………………………..(1)
Continuing with the same specific case of the optimization problem with n = 2 and m = 1 we
define a quantity λ, called the Lagrange multiplier as

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

…. …………………………………………………………….(2)

…………………………………………………………………(3)

…………………………………………………………………(4)
Also, the constraint equation has to be satisfied at the extreme point

…………………………………………………………………..(5)
Hence equations (3) to (5) represent the necessary conditions for the point [x1*, x2*] to be an

extreme point.

Note that λ could be expressed in terms of 𝜕𝑔⁄𝜕𝑥 as well and 𝜕𝑔⁄𝜕𝑥 has to be non-zero. Thus,
1 1

these necessary conditions require that at least one of the partial derivatives of g (x1, x2) be non-

zero at an extreme point.

The conditions given by equations (3) to (5) can also be generated by constructing a function
L, known as the Lagrangian function, as
𝐿(𝑥1 , 𝑥2 , λ) = 𝑓(𝑥1 , 𝑥2 ) + λ 𝑔(𝑥1 , 𝑥2 )
By treating L as a function of three variables (𝑥1 , 𝑥2 𝑎𝑛𝑑 λ), the necessary condition for its
extreme points can be expressed as
𝜕𝐿 𝜕𝑓 𝜕𝑔
(𝑥1 , 𝑥2 , λ) = (𝑥1 , 𝑥2 ) + λ (𝑥 , 𝑥 ) = 0
𝜕𝑥1 𝜕𝑥1 𝜕𝑥1 1 2
𝜕𝐿 𝜕𝑓 𝜕𝑔
(𝑥1 , 𝑥2 , λ) = (𝑥1 , 𝑥2 ) + λ (𝑥 , 𝑥 ) = 0
𝜕𝑥2 𝜕𝑥2 𝜕𝑥2 1 2
𝜕𝐿
(𝑥 , 𝑥 , λ) = 𝑔(𝑥1 , 𝑥2 ) = 0
𝜕λ 1 2
Necessary condition for general problem with n variables and m equality constraints
Minimize f = f (X)
subject to gj (X) = 0, j = 1, 2, . . . ,m

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

where

In this case the Lagrange function, L, will have one Lagrange multiplier λj for each constraint
gj (X) as

𝐿(𝑥1 , 𝑥2 , … … … . 𝑥𝑛 ; λ1 , λ2 , … … . . λ𝑚 )
= 𝑓 (𝑋 ) + λ1 𝑔1 (𝑋 ) + λ2 𝑔2 (𝑋 ) + ⋯ + λ𝑚 𝑔𝑚 (𝑋 )

L is now a function of n + m unknowns, 𝑥1 , 𝑥2 , … … … . 𝑥𝑛 ; λ1 , λ2 , … … … … … . . λ𝑚 and the

necessary conditions for the problem defined above are given by
𝑚
𝜕𝐿 𝜕𝑓 𝜕𝑔𝑗
= (𝑋) + ∑ λ𝑗 (𝑋) = 0
𝜕𝑥𝑖 𝜕𝑥𝑖 𝜕𝑥𝑖
𝑗=1

𝜕𝐿
= 𝑔𝑗 (𝑋) = 0
𝜕λ𝑗
Where i = 1, 2, …….,n and j = 1, 2, …….,m

The solution to this set of equations gives us

The vector X corresponds to the relative constrained minimum of f(X) (subject to the
verification of sufficient conditions).

Sufficient conditions for a general problem

A sufficient condition for f(X) to have a relative minimum at X* is that each root of the
polynomial in ∈, defined by the following determinant equation be positive.

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

………………………[A]
Where

𝜕2 𝐿
𝐿𝑖𝑗 = (𝑋 ∗ , 𝜆∗ ) for i = 1, 2, …….,n and j = 1, 2, …….,m
𝜕𝑥𝑖 𝜕𝑥𝑗

𝜕𝑔𝑝
𝑔𝑝𝑞 = (𝑋 ∗ ) for p = 1, 2, …….,m and q = 1, 2, …….,n
𝜕𝑥𝑞

Similarly, a sufficient condition for f(X) to have a relative maximum at X* is that each root of
the polynomial in ∈, defined by equation (A) be negative. If equation (A), on solving yields
roots, some of which are positive and others negative, then the point X* is neither a maximum
nor a minimum.

ILLUSTRATIVE EXAMPLE
Example 2.11; PG:92; SS RAO

Find the maximum of the function f (X) = 2x1 + x2 + 10 subject to g(X) = x1 + 2𝑥22 = 3 using
the Lagrange multiplier method.
SOLUTION
The Lagrange function is given by

L(X, λ) = 2x1 + x2 + 10 + λ(3 − x1 − 2𝑥22 )

The necessary conditions for the solution of the problem are

Dr. Baboo Rai | National Institute Of Technology Patna

 Optimization methods in Engineering

The application of the sufficiency condition yields

0.2704z + 8 + z = 0
z = −6.2972

Hence X∗ will be a maximum of f with f ∗ = f (X∗) = 16.07.

********************************

Dr. Baboo Rai | National Institute Of Technology Patna