CLASSICAL OPTIMIZATION

September 26, 2017 No Comments »
CLASSICAL OPTIMIZATION
Please follow and like us:

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.

 

A2

f(x)

A1, A2and A3 –Relative maxima

A2 –Global maxima

B1 and B2 –Relative minima

B1 –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)

Theorem-1: 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.

Theorem-2: Let f′ (x*)=f′′(x*) =……fn-1(x*)=0, but if fn(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) = 12x5-45x4+40x3+5

f′(x)=60(x4-3x3+2x2)=60 x2(x-1)(x-2)

f′(x)=0 at x=0,1,2

f′′(x)= 60(4x3-9x2+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 x2-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.

Multi-variable optimization with equality constraints (Solution by Lagrange Multipliers)

Consider the problem

Minimize f(x1, x2)

Such that  g(x1, x2) = 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 (x1, x2, λ) = f (x1, x2)+ λ g (x1, x2)

λ = 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

L11-z L12 L13 …….. L1n g11 g21 …….. gm1
L21 L22-z L23 …….. L2n g12 g22 …….. gm2
.

.

.

.

.

.

.

.

.

  .

.

.

.

.

.

.

.

.

  .

.

.

Ln1 Ln2 Ln3 …….. Lnn-z g1n g2n …….. gmn
g11 g12 g13 …….. g1n 0 0 …….. 0
g21 g22 g23 …….. g2n 0 0 …….. 0
.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

gm1 gm2 gm3 …….. gmn 0 0 …….. 0

 

 

 

 

=0

 

 

 

 

 

 

Lij=xixj           (x*, λ)

(x*)

If some of the roots are positive while others are negative, the point X*(x1*, x2*) 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 Ao=24 π

Solution:  If x1=radius of base

x2=length of the tin,       the problem can be stated as

Maximise    f(x1, x2) = π x12 x2

Subject to    2 π x12 + 2π x1x2=Ao=24 π

   Lagrange function is L(x1, x2, λ) = π x12 x2+ λ(2 π x12 + 2π x1x2-Ao)

Necessary condition

——-1

——————2

————3

Equations 1 and 2 lead to

—————————-4

 

Equation 3 and 4 give the solution as

 

 

 

If Ao=24 π   (x1*=2      x2*=4         λ*=-1)

See that this solution really corresponds to the maximum of f, we apply the sufficiency condition

L11=

L12=

L22=

g11=

g12=

Determinatal equation

L11-z L12 g11
L21 L22-z g12
g11 g12 0
4π-z 16π
0-z
16π 0

 

=0=

 

 

This gives 272 π2z+192π3=0

Z=-12/17 π

Since the value of the polynomial, z is negative the point (x1* ,x2*) corresponds to the maximum of f

 

Example

Find the maximum of the function f(x)= 2x1+x2+10 subject to g(x)= x1+2x22=3

Solution:  The Lagrange function is given by L(x , λ) = 2x1+ x2+ 10+λ(3- x1 – 2x22)

Necessary condition

λ*=2,   x1* = 96/33 = 2.97,  x2* = 1/8 = 0.13

Sufficiency condition

L11-z L12 g11
L21 L22-z g12
g11 g12 0
-z 0 -1
0 -4λ-z -4x2
-1 -4x2 0

 

=0=

 

 

-z 0 -1
0 -8-z -0.52
-1 -0.52 0

 

=0

 

-z((-0.52)2-1(-8-z))=0   →   0.2704z+8+z=0    →z=-6.2972

Since z is negative X*=(x1* ,x2*)corresponds to maximum of f(x)  f*=16.07

Multi-variable optimization with no constraints

Necessary and Sufficient conditions (Two Theorems) :

Theorem-1: 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

………..

Theorem-2: 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

JX=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 A1, A2, A3, A4,….. An are positive.

Where    A1 =  [a11],  A2 = [a11    a12           A3  =    [a11      a12       a13

a21     a22]                     a21      a22       a23

a31      a32       a33]

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(x1, x2)= x13+ x23+2x12+4x22+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 =

J1=

0
0

J2=

 

 

Point X Value of J1 Value of J2 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

 

Multi-variable optimization with inequality constraints (Solution by KUHN-TUCKER conditions):

For Minimization Problems

λjgj=0,                     j=1,2,3…m

gj=0                        j=1,2,3…m

λj≤0                         j=1,2,3…m

For maximization problem or if the constraints are of the type gj≥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 x2. 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 x1,x2 and x3 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(x1,x2, x3)= x12+ x22+ x32+20(x1-50)+20(x1+ x2-100)

= x12+ x22+ x32+40 x1+20x2-3000

The constraints are

g1(x1,x2, x3)= x1-50≥0

g2(x1,x2, x3)= x1+ x2-100≥0

g3(x1,x2, x3)= x1+ x2+ x3-150≥0

The Kuhn-Tucker conditions can be stated as

i=1,2,3…

i.e  2x1+40+ λ12+ λ3=0    _____________1

2x2+20+λ2+ λ3=0         _____________2

2x3+ λ3=0                   _____________3

λjgj=0    , j=1,2,3

λ1(x1-50) =0                     _____________4

λ2(x1+ x2-100) =0             _____________5

λ3(x1+ x2+ x3-150) =0       _____________6

gj≥0    , j=1, 2, 3

x1-50≥0                           ____________ 7

x1+ x2-100≥0                   _____________8

x1+ x2+ x3-150≥0             _____________9

λj≤0  

λ1≤0  λ2≤0  λ3≤0   __________________10,11,12

Equation 4 shows that either λ1=0  or x1=50

Case 1: If λ1=0 , Equation 1 to 3 give x3 =- λ3/2

x2 =-10- λ2/2- λ3/2        _______________13

x1 =-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 x1 =40, x2 =50, x3 =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 x1 =45, x2 =55, x3 =0

This solution satisfies eq. 10 to 12 but violates eq. 7 and 8

3) λ2 =0,        λ3 =0

so x1 =-20, x2 =-10, x3 =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 x1 =45, x2 =55, x3 =50

This solution satisfies eq. 10 to 12 but violates eq. 7

Case 2: If x1=50

Eq. 1 and 3 give

λ1=-40-2x1– λ2– λ3 =-120+2x2

λ2=-20-2x23=-20-2x2+2x            _______________15

λ3 = -2x3

Substitutes of equations 15 in 5 and 6 gives

(-20-2x2+2x3)(x1+ x2-100)=0     ___________________16

(-2x3)( x1+ x2+ x3-150)=0

Again there are four possible solutions to eq. 16 as

1) -20-2x2+2x3=0,        x1+ x2+ x3-150=0

x1 =50, x2 =45, x3 =55

This solution violates eq. 8

2) -20-2x2+2x3=0,        -2x3=0

x1 =50, x2 =-10, x3 =0

This solution violates eq. 8and 9

3) x1+ x2-100=0,        -2x3=0

x1 =50, x2 =50, x3 =0

This solution violates eq. 9

4) x1+ x2-100=0,        x1+ x2+ x3-150=0

x1 =50, x2 =50, x3 =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

x1* = 50, x2* = 50, x3* = 50

Total cost = 502+502+502

 

Please follow and like us:

Leave A Response

Follow by Email
Facebook
Google+
http://www.madakasira.in/classical-optimization/