Engineering Mathematics 
 Engineering subjects 
 GATE preparation tips 
 More Engineering Links 


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 g_{j} (x) <=0; j =1,2,
.m
h_{k}(x) =0; k =1,2,
.p
and
In the above type of problem, the function f(x), g_{j}(x) and h_{k}(x) are not necessarily linear, they may be NonLinear.
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
 Direct Methods
 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 g_{j} <= 0; j=1,2,
.,m (2)
x_{i}^{(l)}<=x_{i}<=x_{i}^{(u)}; i=1,2,
,n  (3)
where x_{i}^{(l)} = Lower bound of x_{i}
x_{i}^{(l)} = upper bound of x_{i}
This method cant handle the NonLinear equality constraints.
As the basic idea in the simplex method was forming a sequence of geometrical figures, each having (n+1) vertices in an ndimensional 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:
Step1 Find k>=n+1 point, each of which satisfies all m constraints.
We start with only one feasible point x_{1} and remaining (k1) points are found one at a time, by using random numbers, generated between 0 and 1.as
x_{i,j} = x_{i}^{(l)} + r_{i,j}[x_{i}^{(u)}  x_{i}^{(l)}]  (4)
i=1,2,
.,n & j = 1,2,
.,k
x_{i,j}> i^{th} component of x_{j}
r_{i,j} > random number lying between 0 and 1
It is noted that points x_{2} , x_{3} ,x_{k} 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 x_{j} does not satisfies (2) then the trial point x_{j} is moved half way towards the centroid of remaining already accepted points. x_{1}, x_{2},x_{j1}
i.e. x_{0} =

j1
 1/(j1)å X_{p}  (5);
 p=1
 

If again this point x_{j} does not satisfy (2) then the process of moving half way towards the centroid x_{0} is continued until a feasible point x_{j} is found.
Ultimately we find a feasible point x_{j}
Example If the trial point x_{j}, violates any one of constraints of (2), then the new point x_{j}=x'_{j} is found as
X'_{j} = (X _{0} + X_{j})/2
=> a new point X'_{j} is halfway towards X_{0}
If x_{j} satisfies (2) then it is accepted to be the j^{th} vertex of the complex.
If x_{j} violates any one constraints of (2) then new x_{j} = x_{j}^{2} can be found as
X_{j}^{2} = (X_{0} + X_{j}')/2
The process of moving halfway towards the centroid x_{0} continued until a feasible point x_{j} is obtained
Step2
.Evaluate f(x) at each of the k points.
If the vertex x_{n} is given largest value of the function, then the process of reflection is used to find a new point x_{r} as:
X_{r} = (1+ a)X_{n}  aX_{0}
where a>=1(initially) and X_{0} is the centroid of all objects except X_{n} i.e.
i.e. x_{0} =

k
 å X_{p}/(k1)  (7);
 p=1
 p!=h
 

Step3... Now check the feasibility of the point x_{r}.
(a) If x_{r} is feasible and f(x_{r}) < f(x_{n}) then x_{n}is replaced by x_{r} and we move on to Step2.
(b) If f(x_{r}) >=f (x_{n}), a new trial point x_{n} 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(x_{r})n). This process is continued until we have a x_{r} such that for which f(x_{r}) < f(x_{n}) and value of a become smaller then a small value E=10^{6} (say)
(c) If the point x_{r} is not obtained in any case such that f(x_{r}) < f(x_{n})then we discard the whole reflection process and start the new reflection process by taping x_{n}, which gives second largest value of function.
Step4... If at any stage the point x_{r}, does not satisfy (2), then it is moved halfway towards the centroid unit it
becomes feasible i.e.
new X_{r} = (X_{0} + X_{r})/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(x_{j})]^{2}/k]^{1/2} <=e_{2}
 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 cant apply the above procedure to find the new point X_{r}>
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) = (x_{1}1) ^{2} + (x_{2} 1.5) ^{2} 0.25
Subject to x_{1} + x_{2}<=4
1<=x_{2}<=3
0<=x_{1}<=2
by complex method with x1 =
Sol: The problem is of two dimensions so the complex is considered to have k = 2n = 4 vertices. One of its vertices is
and other three vertices are chosen with the help of random numbers distributed between 0 and 1.
Let the chosen numbers are
r_{1,2} = 0.4, r_{1,3} = 0.6, r_{1,4} = 0.8
r_{2,2} = 0.5, r_{2,3}= 0.7, r_{2,4} = 0.9
The six coordinates of these three vertices corresponding to k = 2,3 & 4 are computed by
X_{i,j}= x_{i} ^{(l)} + r_{i,j} [x_{i}^{(u)} x_{i} ^{(l)}] ;
i = 1,2
j = 1,2,3,4
Here x_{1}^{(l)} = 0, x_{1}^{(u)} = 2
And x_{2}^{(l)} = 0, x_{2}^{(u)} = 2
So
x_{1,2} = x_{1}^{(l)} + r_{1,2}[x_{1}^{(u)}  x_{1}^{(l)}] = 0.8
x_{1,3} = x_{1}^{(l)} + r_{1,3}[x_{1}^{(u)}  x_{1}^{(l)}] = 1.2
x_{1,4} = x_{1}^{(l)} + r_{1,4}[x_{1}^{(u)}  x_{1}^{(l)}] = 1.6
x_{2,2} = x_{2}^{(l)} + r_{2,2}[x_{2}^{(u)}  x_{2}^{(l)}] = 2
x_{2,3} = x_{2}^{(l)} + r_{2,3}[x_{2}^{(u)}  x_{2}^{(l)}] = 2.4
x_{2,4} = x_{2}^{(l)} + r_{2,4}[x_{2}^{(u)}  x_{2}^{(l)}] = 2.8
Thus the initial complex consists of the vertices
Because g(x) = x _{1} + x_{2} <= 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 x_{4} 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 =
Hence new x _{4} = x _{4} ^{(l)} = (x _{0} + x _{4})/2 =
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 _{4}^{1}) = 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 _{4}^{1})/3 =
and f(x _{0}) = 0.15
Because f(x _{0}) < f(x _{n}), which means that f(x ) is decreasing on the line x _{3}x _{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} =
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 x_{r}^{1} = 1.1x_{0}  0.1x_{n}
Therefore x_{r}^{1} =
=
F(x_{r}^{(1)}) =  0.17734206
Case II:
Let a = 0.2 then
x_{r}^{(2)} = 1.2 x_{0}  0.2 x_{n}
=
=
And f(x_{r}^{(2)}) = 0.19591584
Similarly,
Case III, a = 0.3 then
f(x_{r}^{(3)}) = 0.20580734
Case IV, a = 0.4 then
f(x_{r}^{(4)}) = 0.20701656
Case V, a = 0.5 then
f(x_{r}^{(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
x_{i+1} = Final point at the end of i^{th} iteration
The value of l is always chosen such that x_{i+1} lies in feasible region.
The search direction S_{i}
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} =
And f(x _{1}) = 0
x _{2} =
and f(x _{2}) = 0.04
x _{3} = x _{r} ^{(4)} =
and f(x _{3}) = 0.207016
x _{4} =
and f(x _{4}) = 0.476725
vBecause f(x_{4}) gives maximum value and f(x_{3}) gives minimum value so let us take
x_{n} = x_{4}=
and f(x _{4}) = 0.476725
x_{l} = x_{3}=
and f(x _{l}) = 0.20701656
Therefore centroid x _{0} = (x _{1} + x _{2} + x _{3})/3
=
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} = S^{T}Ñg_{j}(x_{i}) <= 0  (2)
Where the equality sign holds true only if a constraint is linear or strictly concave


