CLASSICAL OPTIMIZATION
Single Variable Optimization
Local (or) Relative minimum and maximum
A function of one variable f(x) is said to have a relative or local minimum at x= x* if f(x*) ≤ f(x*+h) for all sufficiently small positive and negative values of h. Similarly a point x* is called a relative or local maximum if f(x*) ≥ f(x*+h) for all values of h sufficiently close to zero.
Global (or) Absolute minimum and maximum
A function of one variable f(x) is said to have a global or absolute minimum at x= x* if f(x*) ≤ f(x) for all x, and not just for all x close to x*, in the domain over which f(x) is defined. Similarly a point x* will be a global or absolute maximum of f(x) if f(x*)≥ f(x) for all values of x in the domain.

f(x)
A_{1,} A_{2}and A_{3} –Relative maxima
A_{2} –Global maxima
B_{1} and B_{2} –Relative minima
B_{1} –Global minima
C=Relative minimum and also global minimum
Necessary and sufficient conditions for the relative minimum of a function of a single variable 🙁 Two theorems)
Theorem1: If a function(x) is defined in the interval a≤ x ≤b and has a relative minimum at x=x* where a < x* < b and if the derivative exists as a finite number at x=x*, then f′(x*)=0.
Theorem2: Let f′ (x*)=f′′(x*) =……f^{n1}(x*)=0, but if f^{n}(x*)≠0. Then f(x*) is
 A minimum value of f(x) if f ^{n}(x*)>0 and n is even
 A maximum value of f(x) if f ^{n}(x*)<0 and n is even
 Neither a maximum nor a minimum if n is odd. This point is called a stationary (inflection) point.
Example: Determine the maximum and minimum values of the function
f(x) = 12x^{5}45x^{4}+40x^{3}+5
f′(x)=60(x^{4}3x^{3}+2x^{2})=60 x^{2}(x1)(x2)
f′(x)=0 at x=0,1,2
f′′(x)= 60(4x^{3}9x^{2}+4x)
At x=1, f′′(x)=60 x=1 is a relative maximum
f (max) =f(1)= 12
At x=2, f′′(x)=240 x=2 is a relative minimum
f (mini) =f(2)= 11
At x=0, f′′(x)=0 we must investigate the next derivative
f′′′(x)=60(12 x^{2}18x+4)=240 at x=0
Since f′′′(x)≠0 at x=0, x=0 is neither a maximum nor a minimum, and it is an inflection point.
Multivariable optimization with equality constraints (Solution by Lagrange Multipliers)
Consider the problem
Minimize f(x_{1}, x_{2})
Such that g(x_{1}, x_{2}) = 0 (one constraint)
Lagrange function: (Introduction of one more variable, since one constraint is there, otherwise as many variables as the number of constraints should be added
L (x_{1}, x_{2, }λ) = f (x_{1}, x_{2})+ λ g (x_{1}, x_{2})
λ = Lagrange multiplier (a new variable)
Necessary conditions for the function to have a relative minimum:
All the partial derivatives of Lagrange function with respect to each of its argument are set equal to zero.
The values of x*, y* and λ can be obtained
Sufficiency conditions: Each root of the polynomial, Zi, defined by the following determinantal equation, be positive
L_{11}z  L_{12}  L_{13}  ……..  L_{1n}  g_{11}  g_{21}  ……..  g_{m1} 
L_{21}  L_{22}z  L_{23}  ……..  L_{2n}  g_{12}  g_{22}  ……..  g_{m2} 
.
. . 
.
. . 
.
. . 
.
. . 
.
. . 
.
. . 
.
. . 

L_{n1}  L_{n2}  L_{n3}  ……..  L_{nn}z  g_{1n}  g_{2n}  ……..  g_{mn} 
g_{11}  g_{12}  g_{13}  ……..  g_{1n}  0  0  ……..  0 
g_{21}  g_{22}  g_{23}  ……..  g_{2n}  0  0  ……..  0 
.
. . 
.
. . 
.
. . 
.
. . 
.
. . 
.
. . 

g_{m1}  g_{m2}  g_{m3}  ……..  g_{mn}  0  0  ……..  0 
=0
L_{ij}=x_{i}x_{j} (x*, λ)
(x*)
If some of the roots are positive while others are negative, the point X*(x_{1}*, x_{2}*) is not an extreme point.
Example
Find the dimensions of a cylindrical tin (with top and bottom) made up of sheet metal to maximize its volume such that total surface area is equal to A_{o}=24 π
Solution: If x_{1}=radius of base
x_{2}=length of the tin, the problem can be stated as
Maximise f(x_{1,} x_{2}) = π x_{1}^{2} x_{2}
Subject to 2 π x_{1}^{2} + 2π x_{1}x_{2}=Ao=24 π
Lagrange function is L(x_{1}, x_{2, }λ) = π x_{1}^{2} x_{2}+ λ(2 π x_{1}^{2} + 2π x_{1}x_{2}Ao)
Necessary condition
——1
——————2
————3
Equations 1 and 2 lead to
—————————4
Equation 3 and 4 give the solution as
If Ao=24 π (x_{1}^{*}=2 x_{2}^{*}=4 λ^{*}=1)
See that this solution really corresponds to the maximum of f, we apply the sufficiency condition
L_{11}=
L_{12}=
L_{22}=
g_{11}=
g_{12}=
Determinatal equation
L_{11}z  L_{12}  g_{11} 
L_{21}  L_{22}z  g_{12} 
g_{11}  g_{12}  0 
4πz  2π  16π 
2π  0z  4π 
16π  4π  0 
=0=
This gives 272 π^{2}z+192π^{3}=0
Z=12/17 π
Since the value of the polynomial, z is negative the point (x_{1}^{*} ,x_{2}^{*}) corresponds to the maximum of f
Example
Find the maximum of the function f(x)= 2x_{1}+x_{2}+10 subject to g(x)= x_{1}+2x_{2}^{2}=3
Solution: The Lagrange function is given by L(x _{, }λ) = 2x_{1}+ x_{2}+ 10+λ(3 x_{1} – 2x_{2}^{2})
Necessary condition
λ*=2, x_{1}* = 96/33 = 2.97, x_{2}* = 1/8 = 0.13
Sufficiency condition
L_{11}z  L_{12}  g_{11} 
L_{21}  L_{22}z  g_{12} 
g_{11}  g_{12}  0 
z  0  1 
0  4λz  4x_{2} 
1  4x_{2}  0 
=0=
z  0  1 
0  8z  0.52 
1  0.52  0 
=0
z((0.52)^{2}1(8z))=0 → 0.2704z+8+z=0 →z=6.2972
Since z is negative X*=(x_{1}^{*} ,x_{2}^{*})corresponds to maximum of f(x) f*=16.07
Multivariable optimization with no constraints
Necessary and Sufficient conditions (Two Theorems) :
Theorem1: If a function(x) is an extreme point (maximum or minimum)at X=X*and if the first partial derivative of f (X) exist at X* , then
………..
Theorem2: A sufficient condition for a stationary point X* to be an extreme point is that the matrix of second partial derivatives (Hessian matrix) of f(X) evaluated at X* is
 Positive definite when X* is a minimum point, and
 Negative definite when X* is a maximum point
Hessian matrix:It is the matrix of second partial derivatives
J_{X=X* }=
A sufficient condition for the stationery point X* to be a relative minimum is that the Hessian matrix evaluated at the same point be positive definite. The matrix ‘A’ will be positive definite if and only if all the values A_{1}, A_{2}, A_{3}, A_{4},….. A_{n }are positive.
Where A_{1} = [a_{11}], A_{2} = [a_{11 }a_{12 } A_{3} = [a_{11} a_{12} a_{13}
a_{21 }a_{22}] a_{21} a_{22} a_{23}
a_{31} a_{32} a_{33}]
The matrix ‘A’ will be negative definite if and only if the sign of Aj is (1)^{j} for j=1,2,3….n. If some of the Aj are positive and remaining are zero, the matrix will be positive semi definite.
Example
Find the extreme points of the function f(x_{1}, x_{2})= x_{1}^{3}+ x_{2}^{3}+2x_{1}^{2}+4x_{2}^{2}+6
Solution: The necessary conditions for the existence of an extreme point are
These equations are satisfied at points
(0,0), (0, 8/3), (4/3, 0)and (4/3, 8/3). To find the nature of these extreme points, we have to use the sufficiency conditions
0  
0 
The Hessian matrix is given by J =
J_{1}=
0  
0 
J_{2}=
Point X  Value of J_{1}  Value of J_{2}  Nature of J  Nature of X  f(x) 
(0,0)  +4  +32  Positive definite  Relative minimum  6 
(0,8/3)  +4  32  indefinite  Saddle point  418/27 
(4/3,0)  4  32  indefinite  Saddle point  194/27 
(4/3,8/3)  4  32  Negative definite  Relative maximum  50/3 
Multivariable optimization with inequality constraints (Solution by KUHNTUCKER conditions):
For Minimization Problems
λ_{j}g_{j}=0, j=1,2,3…m
g_{j}=0 j=1,2,3…m
λ_{j≤}0 j=1,2,3…m
For maximization problem or if the constraints are of the type g_{j}≥0, then λ_{j≤}0
Example
A manufacturing firm producing refrigerators has given a contract to supply 50 units at the end of the first month, 50 at the end of the second month and 50 at the end of the third. The cost of producing ‘x’ refrigerators in any month is given by x^{2}. The firm can produce more number of refrigerators in any month and carry them to a subsequent month. However holding cost of Rs. 20.00 per unit is charged for any refrigeration carried over from one month to the next. Assuming that there is no initial inventory, determine the number of refrigerators to be produced in each month so as to minimize the total cost.
Solution
Let x_{1},x_{2} and x_{3} represent the number of refrigerators produced in the first, second and third month respectively
The total cost to be minimized is given by
Total cost=production cost+ holding cost
i.e f(x_{1},x_{2}, x_{3})= x_{1}^{2}+ x_{2}^{2}+ x_{3}^{2}+20(x_{1}50)+20(x_{1}+ x_{2}100)
= x_{1}^{2}+ x_{2}^{2}+ x_{3}^{2}+40 x_{1}+20x_{2}3000
The constraints are
g_{1}(x_{1},x_{2}, x_{3})= x_{1}50≥0
g_{2}(x_{1},x_{2}, x_{3})= x_{1}+ x_{2}100≥0
g_{3}(x_{1},x_{2}, x_{3})= x_{1}+ x_{2}+ x_{3}150≥0
The KuhnTucker conditions can be stated as
i=1,2,3…
i.e 2x_{1}+40+ λ_{1}+λ_{2}+ λ_{3}=0 _____________1
2x_{2}+20+λ_{2}+ λ_{3}=0 _____________2
2x_{3}+ λ_{3}=0 _____________3
λ_{j}g_{j}=0 , j=1,2,3
λ_{1}(x_{1}50) =0 _____________4
λ_{2}(x_{1}+ x_{2}100) =0 _____________5
λ_{3}(x_{1}+ x_{2}+ x_{3}150) =0 _____________6
g_{j}≥0 , j=1, 2, 3
x_{1}50≥0 ____________ 7
x_{1}+ x_{2}100≥0 _____________8
x_{1}+ x_{2}+ x_{3}150≥0 _____________9
λ_{j}≤0
λ_{1}≤0 λ_{2}≤0 λ_{3}≤0 __________________10,11,12
Equation 4 shows that either λ_{1}=0 or x_{1}=50
Case 1: If λ_{1}=0 , Equation 1 to 3 give x_{3} = λ_{3}/2
x_{2} =10 λ_{2}/2 λ_{3}/2 _______________13
x_{1} =20 λ_{2}/2 λ_{3}/2
Substituting equation 13 in eq. 5 and 6 we obtain
λ_{2} (130 λ_{3}– λ_{ 2}) =0 _____________14
λ_{3} (λ_{ 2}3/2 λ_{ 3}+ 180) =0
The four possible solutions of this eq. 14 are
1) λ_{2} =0, λ_{ 2}3/2 λ_{ 3}+ 180 =0
i.e λ_{2} =0, λ_{3} =120
so x_{1} =40, x_{2} =50, x_{3} =60
This solution satisfies eq. 10 to 12 but violates eq. 7 and 8
2) λ_{3} =0, 130 λ_{3}– λ_{ 2}=0
i.e λ_{3} =0, λ_{2} =130
so x_{1} =45, x_{2} =55, x_{3} =0
This solution satisfies eq. 10 to 12 but violates eq. 7 and 8
3) λ_{2} =0, λ_{3} =0
so x_{1} =20, x_{2} =10, x_{3} =0
This solution satisfies eq. 10 to 12 but violates eq. 7
4) λ_{ 2}3/2 λ_{ 3}+ 180 =0, 130 λ_{3}– λ_{ 2}=0
i.e λ_{3} =100, λ_{2} =30
so x_{1} =45, x_{2} =55, x_{3} =50
This solution satisfies eq. 10 to 12 but violates eq. 7
Case 2: If x_{1}=50
Eq. 1 and 3 give
λ_{1}=402x_{1}– λ_{2}– λ_{3 }=120+2x_{2}
λ_{2}=202x_{2}λ_{3}=202x_{2}+2x_{3 } _______________15
λ_{3 }= 2x_{3}
Substitutes of equations 15 in 5 and 6 gives
(202x_{2}+2x_{3})(x_{1}+ x_{2}100)=0 ___________________16
(2x_{3})( x_{1}+ x_{2}+ x_{3}150)=0
Again there are four possible solutions to eq. 16 as
1) 202x_{2}+2x_{3}=0, x_{1}+ x_{2}+ x_{3}150=0
x_{1} =50, x_{2} =45, x_{3} =55
This solution violates eq. 8
2) 202x_{2}+2x_{3}=0, 2x_{3}=0
x_{1} =50, x_{2} =10, x_{3} =0
This solution violates eq. 8and 9
3) x_{1}+ x_{2}100=0, 2x_{3}=0
x_{1} =50, x_{2} =50, x_{3} =0
This solution violates eq. 9
4) x_{1}+ x_{2}100=0, x_{1}+ x_{2}+ x_{3}150=0
x_{1} =50, x_{2} =50, x_{3} =50
This solution can be seem to satisfy all the constraints eq. 7 to 9
The values of λ_{1,} λ_{2} and λ_{3 }can be obtained from eq. 15 as
λ_{1 }= 20, λ_{2 }=20, λ_{3 }=100
These satisfy eq. 10 to 12
The optimum solution will be
x_{1}^{*} = 50, x_{2}^{*} = 50, x_{3}^{*} = 50
Total cost = 50^{2}+50^{2}+50^{2}