Examcrazy Logo
HOME  SITEMAP CONTACT US LOGIN
HOME Engineering AIEEE GATE IES DRDO-SET BSNL-JTO
MBA in India CAT How to Prepare for Exams Technical Freshers Jobs
  Follow us|  twitter  Orkut  facebook
Engineering Mathematics
   Non Linear Programming
Engineering subjects
   Mechanical Engineering
   Electrical Engineering
   Computer Science & Engineering
   Electronics & Comm engg
GATE preparation tips
   GATE Books & How to prepare
   Objective Solving Tricks
   Other GATE links
   IES exam preparation
   All about DRDO-SET
More Engineering Links
   Directory of coaching Institutes
   Govt engg college rankings
   Private engg college rankings
   Admission notifications for Mtech/PhD
   All Engineering Colleges in India
Non Linear Programming - Constrained Optimization Techniques

by Alok Bhargava, RIET, Jaipur

Introduction:- This type of optimization techniques are applicable to constrained problems of type-
  Minimize f(x), subject to
  gj (x) <=0; j =1,2,….m
hk(x) =0; k =1,2,….p
and
x =
 x1 
 x2 
 . 
 . 
 xn 

In the above type of problem, the function f(x), gj(x) and hk(x) are not necessarily linear, they may be Non-Linear. So it is not possible every time that we use the methods of LPP to solve the above problems.

These methods are iterative methods and can be categorized in to two parts namely---
  1. Direct Methods
  2. Indirect Methods

Direct Methods :- In these method the constraints will be handled in a explicit manner. Some of the direct methods are:-

1. Random Search Method
2. Heuristic Search Method
3. Complex Method
4. Objective and Constraint Approximate Method
5. Sequential Linear Programming Method
6. Sequential Quadratic Programming Method
7. Method of Feasible Directions
8. Generalized Reduced Gradient Methods

Complex Method
Mathematician Box has extended the simplex method for unconstrained optimization of type Minimize f(x) ------- (1)
Subject to gj <= 0; j=1,2,….,m ------(2)
xi(l)<=xi<=xi(u); i=1,2,……,n ------- (3)
where xi(l) = Lower bound of xi
xi(l) = upper bound of xi


This method can’t handle the Non-Linear equality constraints. As the basic idea in the simplex method was forming a sequence of geometrical figures, each having (n+1) vertices in an n-dimensional problem, In this method also, a sequence of geometric figures, each having k>=n+1 vertices being formed to find the constrained optimum point.

Working Procedure:-
Step-1 Find k>=n+1 point, each of which satisfies all ‘m’ constraints.
We start with only one feasible point x1 and remaining (k-1) points are found one at a time, by using random numbers, generated between 0 and 1.as-
xi,j = xi(l) + ri,j[xi(u) - xi(l)] ---- (4)
i=1,2,….,n & j = 1,2,….,k
xi,j-> ith component of xj
ri,j -> random number lying between 0 and 1
It is noted that points x2 , x3 ,------xk are generated according to equation (4), satisfies the side constraints (3) but may not satisfy constraints(2).
When the new point xj is found, find it satisfies (2), or not

If xj does not satisfies (2) then the trial point xj is moved half way towards the centroid of remaining already accepted points. x1, x2,-----xj-1
i.e. x0 =
        j-1
 1/(j-1)å Xp ------ (5);
        p=1

If again this point xj does not satisfy (2) then the process of moving half way towards the centroid x0 is continued until a feasible point xj is found.
Ultimately we find a feasible point xj
Example If the trial point xj, violates any one of constraints of (2), then the new point xj=x'j is found as X'j = (X 0 + Xj)/2 => a new point X'j is halfway towards X0
If x’j satisfies (2) then it is accepted to be the jth vertex of the complex.
If xj’ violates any one constraints of (2) then new xj = xj2 can be found as Xj2 = (X0 + Xj')/2


The process of moving halfway towards the centroid x0 continued until a feasible point xj is obtained

Step2….Evaluate f(x) at each of the k points.
If the vertex xn is given largest value of the function, then the process of reflection is used to find a new point xr as:-
Xr = (1+ a)Xn - aX0
where a>=1(initially) and X0 is the centroid of all objects except Xn i.e.
i.e. x0 =
      k
 å Xp/(k-1) ------ (7);
      p=1
      p!=h


Step3... Now check the feasibility of the point xr.
(a)  If xr is feasible and f(xr)  <   f(xn) then xnis replaced by xr and we move on to Step2.
(b)  If f(xr) >=f (xn), a new trial point xn is found by reducing the value of x in (6). by a factor of 2.(i.e. new a = olda/2 ) and now tested for the satisfaction of f(xr)n). This process is continued until we have a xr such that for which f(xr)  <  f(xn) and value of a become smaller then a small value E=10-6 (say)
(c)  If the point xr is not obtained in any case such that f(xr)  <   f(xn)then we discard the whole reflection process and start the new reflection process by taping xn, which gives second largest value of function.

Step4... If at any stage the point xr, does not satisfy (2), then it is moved halfway towards the centroid unit it becomes feasible i.e. new Xr = (X0 + Xr)/2

Step5... Each time the worst point xn of current complex is replaced by a new point x, so the complex get modified

Convergence:- Now we will check the convergence of the process. This is said to be converged if the following will be satisfied
a) The distance between any two vertices among x1, x2, …. Xk become smaller than a prescribed small value E1
b) The standard Deviation of the function values become sufficiently smaller i.e.
   k
 [å [f(x) - f(xj)]2/k]1/2 <=e2
   j=1
Where x is the centroid of all k vertices of the current complex and E2>0 is a specified small number.

Important features:

1) As the derivatives of f(x) and gj(x) are not necessary, so computation are simple
2) Box was found the initial value of a = 1.3 satisfactory and also recoment k = 2n for n<=5, a lesser value of k can be taken for n>5.
If k is not sufficiently large then complex collapse and flatten along the first encountered constrained boundary

3) Unless some boundary surface is encountered, the complex roles over and over again with expansion.
4) If the feasible reason is non convex, then there is no guarantee that the centroid of all feasible solutions is also feasible. If the centroid is not feasible, we can’t apply the above procedure to find the new point Xr>
5) If number of variables increases the efficiency of the method decreases
6) Method is not applicable for equality constraints


Example 1: Minimize f(x) = (x1-1) 2 + (x2 – 1.5) 2 – 0.25
Subject to x1 + x2<=4
1<=x2<=3
0<=x1<=2


by complex method with x1 =
 0.7 
 1.1 

Sol: The problem is of two dimensions so the complex is considered to have k = 2n = 4 vertices. One of its vertices is
X1 =
 0.7 
 1.1 

and other three vertices are chosen with the help of random numbers distributed between 0 and 1.
Let the chosen numbers are
r1,2 = 0.4, r1,3 = 0.6, r1,4 = 0.8
r2,2 = 0.5, r2,3= 0.7, r2,4 = 0.9

The six co-ordinates of these three vertices corresponding to k = 2,3 & 4 are computed by –
Xi,j= xi (l) + ri,j [xi(u) – xi (l)] ;
i = 1,2
j = 1,2,3,4
Here x1(l) = 0, x1(u) = 2
And x2(l) = 0, x2(u) = 2
So
x1,2 = x1(l) + r1,2[x1(u) - x1(l)] = 0.8
x1,3 = x1(l) + r1,3[x1(u) - x1(l)] = 1.2
x1,4 = x1(l) + r1,4[x1(u) - x1(l)] = 1.6
x2,2 = x2(l) + r2,2[x2(u) - x2(l)] = 2
x2,3 = x2(l) + r2,3[x2(u) - x2(l)] = 2.4
x2,4 = x2(l) + r2,4[x2(u) - x2(l)] = 2.8
Thus the initial complex consists of the vertices
X1 =
 0.7 
 1.1 
X2 =
 0.8 
 2 
X3 =
 1.2 
 2.4 
X4 =
 1.6 
 2.8 
Because g(x) = x 1 + x2 <= 4
g(x 1) = 1.8 <= 4
g(x 2) = 2.8 <= 4
g(x 3) = 3.6 <= 4
g(x 2) = 4.4 > 4

because g(x) is not satisfied at x4 so it is replaced by a point which lying in the feasible region.
Because the centroid x 0 = (x 1 + x 2 + x 3)/3 =
 0.9 
 1.83 

Hence new x 4 = x 4 (l) = (x 0 + x 4)/2 =
 1.25 
 2.315 

and g(x 4 (l)) = 3.565 <= 4
so x 4 (l) lies in the feasible region. So taking x 4 = x 4 (l) as a vertex. So the initial complex has the points x 1 , x 2, x 3 and x 4 = x 1 1. Now because f(x 1) = 0
F(x 2) = 0.04
F(x 3) 0.60
And f(x 41) = 0.476725
Because f(x 3) gives maximum value and f(x 1) gives minimum value so let us take x n = x 3 and f(x n) 0.60 and x l = x 1 and f(x l) = 0
The centroid x 0 is obtained as -
x 0 (x 1 + x 2 + x 41)/3 =
 0.917 
 1.805 

and f(x 0) = -0.15
Because f(x 0) < f(x n), which means that f(x ) is decreasing on the line x 3x 0. So let us find the point x r by reflection process as
x r = (1+ a)x 0 - ax n
Taking a = 1, so x r = 2x 0 - x n =
 0.634 
 1.21 

And f(x r) = -0.031944
As f(x r) is such that the x r is feasible and f(x r)< f(x n), so let us replace the point x n= x 3 by x r and hence two cases
Case I – Let a = 0.1 then xr1 = 1.1x0 - 0.1xn
Therefore xr1 =
1.1
 0.917 
 1.805 
-0.1
 1.2 
 2.4 
=
 0.8887 
 1.7455 

F(xr(1)) = - 0.17734206

Case II:
Let a = 0.2 then-
xr(2) = 1.2 x0 - 0.2 xn =
1.2
 0.917 
 1.805 
-0.2
 1.2 
 2.4 
=
 0.8604 
 1.686 
And f(xr(2)) = -0.19591584

Similarly, Case III, a = 0.3 then
f(xr(3)) = -0.20580734

Case IV, a = 0.4 then
f(xr(4)) = -0.20701656


Case V, a = 0.5 then
f(xr(5)) = -0.1995435



Method of feasible directions
In the method of feasible direction basically we will choose a starting point, satisfying all the constraints and move to a better point according to iterative scheme
x i+1 = x i + lS i ----(1)

where:
x i = standing point for i th iteration
S i = direction of movement
l = step length of the movement
xi+1 = Final point at the end of ith iteration

The value of l is always chosen such that xi+1 lies in feasible region.
The search direction Si a) A small move in that direction violates no constraints
b) The value of the objective function can be reduced in that direction

As the decreasing trend by values of f continues upto x r (4) so let us replace the vertex x n = x 3 by x r (4). So the new complex will have vertices as-
x 1 =
 0.7 
 1.1 

And f(x 1) = 0
x 2 =
 0.8 
 2 

and f(x 2) = 0.04
x 3 = x r (4) =
 0.8038 
 1.567 

and f(x 3) = -0.207016

x 4 =
 1.25 
 2.315 

and f(x 4) = 0.476725
vBecause f(x4) gives maximum value and f(x3) gives minimum value so let us take-
xn = x4=
 1.25 
 2.315 

and f(x 4) = 0.476725

xl = x3=
 0.8038 
 1.567 

and f(x l) = -0.20701656 Therefore centroid x 0 = (x 1 + x 2 + x 3)/3 =
 0.767 
 1.5557 

and f(x 0) = -0.19303
Because | f(x l) = f(x 0)| = 0.014
If the desired accuracy is above e = 0.01, then the above solution is accepted.

The point x i+1 can be taken as the starting point for (i+1) th iteration and the entire procedure is repeated until a point is obtained such that no direction can be formed which satisfy both properties (a) and (b).

A direction satisfying (a) only is called feasible direction, while a direction satisfying both (a) and (b) is called and usable feasible direction. This is the reason that these methods are known as methods of feasible directions.
There are many ways of choosing usable feasible directions and hence there are a number of methods of feasible directions.
i) A direction S is feasible at a point x i if it satisfies the relation-
{d/d l[g j(x i + lS)]} l=0 = STÑgj(xi) <= 0 --------- (2)
Where the equality sign holds true only if a constraint is linear or strictly concave
  About us | Privacy Policy | Terms and Conditions | Contact us | Email: support@Examcrazy.com  
Copyright © 2014 Extreme Testing House, India. All rights reserved.  24699