A PROJECT REPORT submitted by

BIJAN KUMAR PATEL for the partial fulfilment for the award of the degree of

Master of Science in Mathematics under the supervision of

Prof. ANIL KUMAR

DEPARTMENT OF MATHEMATICS NIT ROURKELA ROURKELA– 769008

MAY 2014

NATIONAL INSTITUTE OF TECHNOLOGY ROURKELA

DECLARATION

I hereby certify that the work which is being presented in the report entitled “ Solutions Of Some Non-Linear Programming Problems” in partial fulfillment of the requirement for the award of the degree of Master of Science, submitted in the Department of Mathematics, National Institute of Technology, Rourkela is an authentic record of my own work carried out under the supervision of Prof. Anil Kumar.

The matter embodied in this has not been submitted by me for the award of any other degree.

May, 2014

(Bijan Kumar Patel)

CERTIFICATE

This is to certify that the project report entitled ”Solutions Of Some Non-Linear Programming Problems” submitted by Bijan Kumar Patel to the National Institute of Technology Rourkela, Odisha for the partial fulfilment of requirements for the degree of master of science in Mathematics is a bonafide record of review work carried out by his under my supervision and guidance. The contents of this project, in full or in parts, have not been submitted to any other institute or university for the award of any degree or diploma.

May, 2014

ii

ACKNOWLEDGEMENT I would like to warmly acknowledge and express my deep sense of gratitude and indebtedness to my guide Prof. Anil Kumar, Department of Mathematics, NIT Rourkela, Odisha, for his keen guidance, constant encouragement and prudent suggestions during the course of my study and preparation of the final manuscript of this project.

I would like to thank the faculty members of Department of Mathematics NIT Rourkela, who have always inspired me to work hard and helped me to learn new concepts during our stay at NIT Rourkela.

I would like to thanks my family members for their unconditional love and support. They have supported me in every situation. I am grateful for their support.

My heartfelt thanks to all my friends for their invaluable co-operation and constant inspiration during my project work.

Bijan Kumar Patel Rourkela, 769008 May 2014

iii

Abstract The purpose of this dissertation was to provide a review of the theory of Optimization, in particular non-linear and quadratic programming, and the algorithms suitable for solving both convex and non-convex programming problems.Optimization problems arise in a wide variety of fields and many can be effectively modeled with linear equations. However, there are problems for which linear models are not sufficient thus creating a need for nonlinear systems.

This project includes a literature study of the formal theory necessary for understanding optimization and an investigation of the algorithms available for solving of the non-linear programming problem and a special case, namely the quadratic programming problem. It was not the intention of this project to discuss all possible algorithms for solving these programming problem, therefore certain algorithms for solving various programming problems were selected for a detailed discussion in this project. Some of the algorithms were selected arbitrarily, because limited information was available comparing the efficiency of the various algorithms.It was also shown that it is difficult to conclude that one algorithm is better than another as the efficiency of an algorithm greatly depends on the size of the problem, the complexity of an algorithm and many other implementation issues.

Optimization problems arise continuously in a wide range of fields and thus create the need for effective methods of solving them. We discuss the fundamental theory necessary for the understanding of optimization problems, with particular programming problems and the algorithms that solve such problems.

Keywords Non-linear Programming, Convex, Non-convex, Optimization, Fractional Programming, Separable Programming

iv

Contents 1 Non-Linear Programming Problem

2

1.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2

Graphical Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3

Single-Variable Optimization . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.3.1

Bisection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.3.2

Newtons Method . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.4

Multivariable Optimization without Constraints . . . . . . . . . . . . . . .

5

1.5

Multivariable Optimization with Constraints . . . . . . . . . . . . . . . . .

8

1.5.1

Lagrange Multipliers . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.5.2

Kuhn-Tucker Conditions . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Quadratic Programming Problem

13

2.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2

Wolfe’s modified simplex method . . . . . . . . . . . . . . . . . . . . . . . 14

2.3

Beale’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Separable Programming

22

3.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.2

Separable Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1

3.3

Separable Programming Problem . . . . . . . . . . . . . . . . . . . . . . . 24

3.4

Piece-wise Linear Approximation of Non-linear Function:- . . . . . . . . . . 24

3.5

Reduction of separable programming problem to linear programming problem 26

4 Fractional Programming

28

4.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4.2

Computational Procedure Of Fractional Algorithm . . . . . . . . . . . . . 28

5 Future Research

30

Bibliography

31

2

Introduction

Throughout human history, man has always strived to master his physical environment by making the best use of his available resources. These resources are however limited and the optimal use thereof poses potentially difficult problems. Problems of finding the best or worst situation arise constantly in daily life in a wide variety of fields that include science, engineering, economy and management. The theory of optimization attempts to find these solutions.

The theory and application of optimization is sometimes referred to as mathematical programming. Here the term programming does not refer to computer programming.The theory of optimization provides a powerful framework for formulating the general optimization problem. This project work is however, concerned with algorithms for solving various programming problems and comparison of these algorithms, rather than to show how these programming problems are formulated.

Chapter 1 gives the detail of general optimization problem and its classification are presented in mathematical context. The conditions for optimality, the identification of local and global optimum points, the convexity of the objective function and the KuhnTucker conditions are described, with particular reference to the quadratic programming problem. In Chapter 2 a selection of algorithms for solving the quadratic programming problem specifically concerned with a convex objective function are discussed.It will be shown that these algorithms do not necessarily produce a global optimum. Chapter 3 deals with such non-linear programming problems in which the objective function as well as all the constraints are separable. In Chapter 4 we solve the problem of maximizing the fraction of two linear function subject to a set of linear equalities and the non-negativity constraints. Chapter 5 will present a summary of the research and the conclusions that have arisen during the research and provide some recommendations for future research.

1

1 1.1

Non-Linear Programming Problem Introduction

The Linear Programming Problem which can be review as to M aximize Z =

n X

cj x j

j=1

subject to

n X

aij xj ≤ bi

f or

i = 1, 2, ..., m

j=1

and xj ≥ 0

f or

j = 1, 2, ..., m

The term ’non linear programming’ usually refers to the problem in which the objective function (1) becomes non-linear, or one or more of the constraint inequalities (2) have non-linear or both. Ex. Consider the following problem M aximize( M inimize ) Z = x21 + x22 + x33 subject to

1.2

x1 + x2 + x3 = 4 and x1 , x2 , x3 > 0

Graphical Solution

In a linear programming, the optimal solution was usually obtained at one of the extreme points of the convex region generated by the constraints and the objective function of the problem. But, it is not necessary to find the solution at extreme points of the feasible region of non-linear programming problem. Here, we take an example below :Example 1. Solve graphically the following problem: M aximize Z = 2x1 + 3x2

(1)

x21 + x22 6 20,

(2)

x1 x2 6 8 and x1 , x2 > 0

(3)

subject to

2

Solution: In this problem objective function is linear and the constraints are non-linear. x21 + x22 = 20 represents circle and x1 x2 = 0 represents hyperbola. Asymptotes are represented by X − axis and Y − axis . Solving eq n (2) and (3) , we get x1 = −2, −4, 2, 4 . But x1 = −2, −4 are impossible (x1 > 0) Take x1 = 2 and 4 in eq n (2) and (3) , then we get x2 = 4 and 2 respectively. So, the points are (2, 4) or (4, 2). Shaded non-convex region of OABCD is called the feasible region. Now, we maximize the objective function i.e 2x1 + 3x2 = K lines for different constant values of K and stop the process when a line touches the extreme boundary point of the feasible region for some value of K . At (2, 4) , K = 16 which touches the extreme boundary point. We have boundary point of like (0, 0), (0, 4), (2, 4), (4, 2), (4, 0). Where the value of Z is maximum at point (2, 4).

∴ M ax. Z = 16

3

1.3

Single-Variable Optimization

A one-variable,unconstrained nonlinear program has the form M aximize(M inimize) Z = f (x) where f (x) is a nonlinear function of the single variable x, and the search for the optimum is conducted over the infinite interval. If the search is restricted to a finite subinterval [a, b] ,then the problem becomes M aximize (M inimize) Z = f (x) subject to

a6x6b

some result (1) If f (x) is continuous in the closed and bounded interval [a,b], then f (x) has global optima (both a maximum and minimum) on this interval. (2) If f (x) has a local optimum at x0 and if f (x) is differentiable on a small interval 0

centered at x0 , then f (x0 ) = 0 Two search-methods to find the optimization in one dimension

1.3.1

Bisection

Assume concave f (x) → all we need to find is the turning point. Steps: 1) Initially search points x1 , x2 , ... 0

0

2) Keep most interior point with f (x) < 0 and most interior point with f (x) > 0 3) Pick a point half way in between them and: 0

if f (xk+1 ) < 0 −→replace xmax 0

if f (xk+1 ) > 0 −→replace xmin 4) Repeat until desired resolution is obtained. 0

Stopping condition:|f (xk+1 )| 6 Only checking if positive or negative ⇒ Values are ignored. 4

Advantages: Known no. of steps until we reach the end. Disadvantages: Doesnt use all available information. Doesnt take into account slope and curvature.

1.3.2

Newtons Method

This method uses information on the curvature of the function but we need to be able to calculate the curvature in order for it to be feasible. By Taylors rule 0

f (xi ) = f (xi ) + (xi+1 + xi )f (x) +

(xi+1 + xi )2 00 f (x) + . . . 2

If we maximize this approximation we use both the first and second derivative information to make a guesses as to the next point to evaluate:

0

xi+1

f (x) = xi − 00 f (x)

In one dimension: 0

f (x) = 0 is necessary for a maximum or minimum. 00

f (x) > 0 is necessary for a minimum. 00

f (x) 6 0 is necessary for a maximum. 0

For strict inequality for this to be a sufficient condition. i.e.f (x) = 0 00

and f (x) > 0 is sufficient to know that x is a minimum.

1.4

Multivariable Optimization without Constraints

A nonlinear multivariable optimization without constraints has the form : M aximize f (x1 , x2 , ..., xn )

with

x1 , x2 , ..., xn > 0 5

Local and Global Maxima Definition ˆ if there exist an -neighbourhood An objective function f (X) has a local maximum at X ˆ s.t. f (X) 6 f (X) ˆ for all X in this -neighbourhood at which the function is around X defined, If the condition is met for every positive then f (X) has a global maximum at ˆ . X Unconstrained Optimization We have to optimize f (x1 , x2 , ..., xn ) In unconstrained type of function we determine the extreme points. ∂f =0 ∂x1 ∂f =0 ∂x2 .. . ∂f =0 ∂xn For ∂ 2f ∂x2 ∂ 2f ∂x2 ∂ 2f ∂x2

one Variable >0

Then f is minimum.

<0

Then f is maximum.

=0

Then further investigation needed.

For two variable rt − s2 > 0 Then the function is minimum. rt − s2 < 0 Then the function is maximum. rt − s2 = 0 Further investigation needed.

Where r =

∂ 2f ∂ 2f ∂ 2f , s = , t = ∂x1 2 ∂x1 x2 ∂x2 2

For ’n’ Variable Hessian Matrix

6

∂ 2f ∂x1 2 2 ∂ f ∂x1 x2 . .. ∂ 2f ∂x1 xn

∂ 2f ∂x1 x2

...

∂ 2f ... ∂x2 2 .. .. . . 2 ∂ f ... ∂x2 xn

∂ 2f ∂x1 xn 2 ∂ f ∂x2 xn .. . 2 ∂ f ∂xn 2

| H |> 0 at p1 , f is attains minimum at p1 . | H |< 0 at p1 , f is attains maximum at p1 .

Convex Function : A function f (x) is said to be convex function over the region S if for any two points x1 , x2 belongs to S. We have the function f (λx1 + (1 − λ)x2 ) 6 λf (x1 ) + (1 − λ)f (x2 )

where 0 6 λ 6 1

S is strictly convex function if f (λx1 + (1 − λ)x2 ) < λf (x1 ) + (1 − λ)f (x2 ) Concave Function : A function f (x) is said to be concave function over the region S if for any two points x1 , x2 belongs to S. We have the function f (λx1 + (1 − λ)x2 ) > λf (x1 ) + (1 − λ)f (x2 )

where 0 6 λ 6 1

S is strictly concave function if f (λx1 + (1 − λ)x2 ) > λf (x1 ) + (1 − λ)f (x2 ) Result (1) Sum of two convex functions is also a convex function. (2) Let f (x) = X T AX be positive semi definite quadratic form then f (x) is a convex function. (3) Let f (x) be a convex function over convex region S, then a local minima of f (x) is a global minima of f (x) in the region S. (4) If f (x) is a strictly convex function over the convex set S then f (x) has unique global minima. 7

1.5

Multivariable Optimization with Constraints

General Non-linear Programming Problem

Let Z be a real valued function of n variables defined by: (a) Z = f (x1 , x2 , ..., xn ) −→ Objective function.

Let (b1 , b2 , ..., bm ) be a set of constraints, such that: (b) g1 (x1 , x2 , ..., xn ) [ 6 or > or = ] b1

g2 (x1 , x2 , ..., xn ) [ 6 or > or = ] b2

g3 (x1 , x2 , ..., xn ) [ 6 or > or = ] b3

gm (x1 , x2 , ..., xn ) [ 6 or > or = ] bm Where g1 are real valued functions of n variables, x1 , x2 , ..., xn . Finally, let

(c) xj > 0 where j = 1, 2, ..., n. −→Non-negativity constraint.

If either f (x1 , x2 , ..., xn ) or some g1 (x1 , x2 , ..., xn ) or both are non-linear, then the problem of determining the n-type (x1 , x2 , ..., xn ) which makes z a minimum or maximum and satisfies both (b) and (c), above is called a general non-linear programming problem.

Global Minima and Local Minima of a Function It gives optimal solution for the objective function at the point but also optimize the function over the complete solution space. Global Minimum: A function f (x) has a global minimum at a point x0 of a set of points K if an only if f (x0 ) 6 f (x) for all x in K. Local Minimum:

A function f (x) has the local minimum point x0 of a set of points K if

and only if there exists a positive number such that f (x0 ) 6 f (x) for all x in K at which ||x0 − x|| < δ There is no general procedure to determine whether the local minimum is really a global minimum in a non-linear optimization problem. 8

The simplex procedure of an LPP gives a local minimum, which is also a global minimum. This is the reason why we have to develop some new mathematical concepts to deal with NLPP.

1.5.1

Lagrange Multipliers

Here we discussed the optimization problem of continuous functions. The non-linear programming problem is composed of some differentiable objective function and equality side constraints, the optimization may be achieved by the use of Lagrange multipliers. A Lagrange multiplier measures the sensitivity of the optimal value of the objective function to change in the given constraints bi in the problem. Consider the problem of determining the global optimum of Z = f (x1 , x2 , ..., xn ) subject to the gi (x1 , x2 , ..., xn ) = bi , i = 1, 2, ..., m. Let us first formulate the Lagrange function L defined by: L(x1 , x2 , ..., xn ; λ1 , λ2 , ..., λm ) = f (x1 , x2 , ....xn ) + λ1 g1 (x1 , x2 , ..., xn ) + λ2 g2 (x1 , x2 , ..., xn ) + ... + λm gm (x1 , x2 , ..., xn ) where λ1 , λ2 , ..., λm are Lagrange Multipliers. For the stationary points ∂L =0 ∂xj

,

∂L =0 ∂λi

∀ j = 1(1)n

∀ i = 1(1)m

Solving the above equation to get stationary points. Observation Although the Lagrangian method is often very useful in applications yet the drawback is that we can not determine the nature of the stationary point. This can sometimes be determined from physical consideration of the problem. problem.1 A rectangular box open at top is to have volume of 32 cubic meters. Find the dimensions 9

of the box requiring the least material for its construction. solution: Let x1 , x2 , x3 be the sides of the rectangular face with x1 , x3 in the sides of the bottom faces and s be its surface then s = 2x1 x2 + 2x2 x3 + x1 x3 subject to x1 x2 x3 = 32

and

x1 , x2 , x3 > 0

Form the lagrangian function L(x1 , x2 , x3 , λ) = 2x1 x2 + 2x2 x3 + x1 x3 + λ(x1 x2 x3 − 32) The stationary points are the solutions of the followings:

∂L = 2x2 + x3 + λx2 x3 = 0 ∂x1

(4)

∂L = 2x1 + 2x3 + λx1 x3 = 0 ∂x2

(5)

∂L = 2x2 + x1 + λx1 x2 = 0 ∂x3

(6)

∂L = x1 x2 x3 − 32 = 0 ∂λ

(7)

from equation (1) and (2) we get

x1 = 2x2

and from equation (1) and (3) we get

x2 = x 3

putting these value in equation (4) we get

x1 = 4, x2 = 2, x3 = 4

M in.S = 48

1.5.2

Kuhn-Tucker Conditions

Here we developing the necessary and sufficient conditions for identifying the stationary points of the general inequality constrained optimization problems. These conditions are called the Kuhn-Tucker Conditions. The development is mainly based on Lagrangian method. These conditions are sufficient under certain limitations which will be stated in the following . 10

Kuhn-Tucker Necessary Conditions M aximize f (X) , X = (x1 , x2 , ..., xn ) subject to constraints gi (X) 6 bi , i = 1, 2, ..., m,

including the non-negativity constraints X > 0 , the necessary conditions for a local ¯ are maxima at X (i)

¯ s¯) ¯ λ, ∂L(X, = 0, j = 1, 2, ..., n, ∂xj ¯ i [ gi (X) ¯ − bi ] = 0, (ii) λ

¯ 6 bi , (iii) gi (X)

(iv) λ¯i > 0 , i = 1, 2, ..., m.

Kuhn-Tucker Sufficient Conditions The Kuhn-Tucker conditions which are necessary conditions are also sufficient if f (x) is concave and the feasible space is convex, i.e. if f (x) is strictly concave and gi (x), i = 1, ..., m are convex. Problem.1

M ax.Z = 10x1 + 4x2 − 2x1 2 − 3x2 2 , subject to 2x1 + x2 ≤ 5 x1 , x2 ≥ 0 . Solution: We have, f (X) = 10x1 + 4x2 − 2x1 2 − x2 2 h(X) = 2x1 + x2 − 5 The Kuhn-Tucker condition are

11

∂f ∂h −λ =0 ∂x1 ∂x1 ∂f ∂h −λ =0 ∂x2 ∂x2 λh(X) = 0, h(X) ≤ 0,

λ ≥ 0.

Applying these condition , we get

10 − 4x1 − 2λ = 0

(i)

4 − 2x2 − λ = 0

(ii)

λ(2x1 + x2 − 5) = 0

(iii)

2x1 + x2 − 5 ≤ 0

(iv)

λ≥0

(v)

From (iii) either λ = 0 or 2x1 + x2 − 5 = 0 When λ = 0, the solution of (i) and (ii) gives x1 = 2.5 and x2 = 2 which does not satisfy the equation (iv). Hence λ = 0 does not yield a feasible solution. 11 When 2x1 + x2 − 5 = 0 and λ 6= 0, the solution of (i),(ii) and (iii) yields, x1 = , x2 = 6 4 4 , λ = , which satisfy all the necessary conditions. 3 3 It can be verified that the objective function is concave in X, while the constraint is convex in X. Thus these necessary conditions are also the sufficient conditions of maximization of f (X). Therefore the optimal solution is x1 ∗ =

91 11 ∗ 4 , x2 = , which gives Zmax = 6 3 6

12

.

2

Quadratic Programming Problem

2.1

Introduction

Quadratic programming deals with the non-linear programming problem of maximizing(or minimizing) the quadratic objective function subject to a set of linear inequality constraints. The general quadratic programming problem can be defined as follows: 1 M aximize Z = CX + X T QX 2 subject to AX 6 B and X > 0 where X = (x1 , x2 , ..., xn )T

C = (c1 , c2 , ..., cn )

a11 .. A= .

, B = (b1 , b2 , ..., bm )T ... .. .

a1n .. .

am1 . . . amn q11 . . . q1n .. .. Q = ... . . qn1 . . . qnn

The function X T QX is said to be negative-definite in the maximization case, and positive definite in the minimization case. The constraints are to be linear which ensures a convex solution space. In this algorithm, the objective function is convex (minimization) or concave(maximization) and all the constraints are linear.

13

2.2

Wolfe’s modified simplex method

Let the quadratic programming problem be : n X

n

n

1 XX M aximize Z = f (X) = cj x j + cjk xj xk 2 j=1 k=1 j=1 subject to the constraints : n X

aij xj 6 bi , xj > 0(i = 1, ..., m, j = 1, ..., n)

j=1

Where cjk = ckj for all j and k, bi > 0 for all i = 1,2,...,m. Also, assume that the quadratic form n X n X

cjk xj xk

j=1 k=1

be negative semi-definite. Then, the Wolfe’s iterative procedure may be outlined in the following steps: Step 1. First, convert the inequality constraints into equation by introducing slackvariable qi2 in the ith constraint (i = 1, ..., m) and the slack variable rj2 the jth non-negative constraint (j = 1, 2, ..., n).

Step 2. Then, construct the Lagrangian function L(X, q, r, λ, µ) = f (X) −

m X i=1

λi [

n X

aij xj − bi +

qi2 ]

−

j=1

n X

µj [−xj + rj2 ]

j=1

2 ), r = (r12 , r22 , ..., rn2 ), and µ = (µ1 , µ2 , ..., µn ), Where X = (x1 , x2 , ..., xn ), q = (q12 , q22 , ..., qm

λ = (λ1 , λ2 , ..., λm ), Differentiating the above function ’L’ partially with respect to the components of X,q,r,λ, µ and equating the first order partial derivatives to zero, we derive Kuhn-Tucker conditions from the resulting equations. Step 3. Now introduce the non-negative artificial variable vj , Kuhn-Tucker conditions cj +

n X k=1

cjk xk −

m X i=1

14

λi aij + µj = 0

j = 1, 2, ..., n in the

for j = 1, 2, ..., n and to construct an objective function Zv = v1 + v2 + ... + vn

Step 4. In this step, obtain the initial basic feasible solution to the following linear programming problem :

M inimize Zv = v1 + v2 + ... + vn .

Subject to the constraints : n X

cjk xk −

m X

λi aij + µj + vj = −cj (j = 1, ...n)

i=1

k=1

n X

aij xj + qi2 = bi (i = 1, ..., m)

j=1

vj , λj µj , xj > 0 (i = 1, ..., m; j = 1, ..., n)

and satisfying the complementary slackness condition:

n X j=1

µ j xj +

m X

λi si = 0, (where si = qi2 )

i=1

or

λi si = 0

and µj xj = 0

(f or i = 1, ..., m; j = 1, ..., n).

Step 5. Now, apply two-phase simplex method in the usual manner to find an optimum solution to the LP problem constructed in Step 4. The solution must satisfy the above complementary slackness condition. 15

Step 6. The optimum solution thus obtained in Step 5 gives the optimum solution of given QPP also. Important Remarks: 1.If the QPP is given in the minimization form, then convert it into maximization one by suitable modifications in f (x) and the ’>’ constraints. 2. The solution of the above system is obtained by using Phase I of simplex method. The solution does not require the consideration of Phase II . Only maintain the condition λi si = 0 = µj xj all the time. 3. It should be observed that Phase I will end in the usual manner with the sum of all artificial variables equal to zero only if the feasible solution to the problem exists.

problem.2 M aximize 2x1 + x2 − x1 2 subject to 2x1 + 3x2 ≤ 6 2x1 + x2 ≤ 4

and x1 , x2 ≥ 0

solution: Since the given objective function is convex and each constraint is convex therefore the given NLPP is a CNLPP.

Now L(X, λ) = (−2x1 − x2 + x1 2 ) + λ1 (2x1 + 3x2 − 6) + λ2 (2x1 + x2 − 4) Therefore the khun-tucker condition are

∴

∂L ≥ 0 ⇒ −2 + 2x1 + 2λ1 + 2λ2 ≥ 0 ∂xj ⇒ −2 + 2x1 + 2λ1 + 2λ2 − µ1 = 0 −1 + 3λ1 + λ2 ≥ 0 ⇒ −1 + 3λ1 + λ2 − µ2 = 0

∴

∂L ≤ 0 ⇒ 2x1 + 3x2 − 6 ≤ 0 ∂λi ⇒ 2x1 + 3x2 − 6 + S1 = 0 16

2x1 + x2 − 4 ≤ 0 ⇒ 2x1 + x2 − 4 + S2 = 0 ∂L = 0 ⇒ x1 µ1 = 0, x2 µ2 = 0 ∂xj ∂L = 0 ⇒ λ1 S1 = 0, λ2 S2 = 0 ∴ λi ∂λ The above system of equation can be written as ∴ xj

(1) (2)

2x1 + 2λ1 + 2λ2 − µ1 = 2 3λ1 + λ2 − µ2 = 1 2x1 + 3x2 + S1 = 6 2x1 + x2 + S2 = 4

(3)

x1 , x2 , λ1 , λ2 , S1 , S2 , µ1 , µ2 ≥ 0 x1 µ1 = 0, x2 µ2 = 0, λ1 S1 = 0, λ2 S2 = 0. This equation (3) is a LPP with out an objective function. To find the solution we can write (3) as the following LPP. max.Z = −R1 − R2 subject to 2x1 + 2λ1 + 2λ2 − µ1 = 2 3λ1 + λ2 − µ2 = 1 2x1 + 3x2 + S1 = 6 2x1 + x2 + S2 = 4 Now solve this by the two phase simplex method. The end of the phase (1) gives the feasible solution of the problem The optimal solution of the QPP is 14 1 10 2 x1 = , x2 = , λ1 = , S2 = . 3 9 3 9

2.3

Beale’s Method

In Beale’s method we solve Quadratic Programming problem and in this method we does not use the Kuhn-Tucker condition. At each iteration the objective function is expressed in terms of non basic variables only.

Let the QPP be given in the form 17

1 M aximize f (X) = CX + X T QX 2 subject to AX = b, X ≥ 0.

Where X = (x1 , x2 , ..., xn+m ) c is 1 × n A is m × (n + m) and Q is symmetric and every QP P with linear constraints. Algorithm Step 1 First express the given QPP with Linear constraints in the above form by introducing slack and surplus variable. Step 2 Now select arbitrary m variables as basic and remaining as non-basic. Now the constraints equation AX = b can be written as

BXB + RXN B = b ⇒ XB = B −1 b − B −1 RXN B where XB -basic vector

XN B -non-basic vector

and the matrix A is partitioned to submatrices B and R corresponding to XB and XN B respectively. Step 3 Express the basis XB in terms of non-basic XN B only, using the given additional constraint equations, if any. Step 4 Express the objective function f (x) in terms of XN B only using the given and additional constraint , if any . Thus we observe that by increasing the value of any of the non-basic variables, the value of the objective function can be improved. Now the constraints on

18

the new problem become B −1 RXN B 6 B −1 b

(since XB > 0)

Thus, any component of XN B can increase only until

∂f becomes zero or one or more ∂xN B

components of XB are reduced to zero. Step 5 Now we have m + 1 non-zero variables and m + 1 constraints which is a basic solution to the extended set of constraints. Step 6 We go on repeating the above procedure until no further improvement in the objective function may be obtain by increasing one of the non-basic variables.

problem.1: Use Beale’s Method to solve following problem M aximize Z = 4x1 + 6x2 − 2x1 2 − 2x1 x2 − 2x2 2 subject to x1 + 2x2 ≤ 2 and x1 , x2 ≥ 0 Solution: Step:1 M ax. Z = 4x1 + 6x2 − 2x1 2 − 2x1 x2 − 2x2 2

(1)

subject to x1 + 2x2 + x3 = 2

(2)

and x1 , x2 , x3 ≥ 0 taking XB = (x1 ); XN B =

x2 x3

and x1 = 2 − 2x2 − x3

(3)

Step:2 put (3) in (1), we get M ax. f (x2 , x3 ) = 4(2 − 2x2 − x3 ) + 6x2 − 2(2 − 2x2 − x3 )2 − 2(2 − 2x2 − x3 )x2 − 2x2 2 ∂f = −2 + 8(2 − 2x2 − x3 ) + 8x2 − 4x2 − 2(2 − x3 ) ∂x2 ∂f = −4 + 4(2 − 2x2 − x3 ) + 2x2 ∂x3 19

Now

∂f = 10 ∂x2 (0,0)

∂f =4 ∂x3 (0,0) ∂f indicates that the objective function will increase if xi increased ∂xi ∂f . Similarly ’-ve’ value of indicates that the objective function will decrease if xi is ∂xi decrease . Thus, increase in x2 will give better improvement in the objective function. Here ’+ve’ value of

Step:3 f (x) will increase if x2 increased . If x2 is increased to a value greater then 1, x1 will be negative. Since x1 = 2 − 2x2 − x3 ∂f =0 x3 = 0; ∂x2 ⇒ 10 − 12x2 = 0 ⇒ x2 =

5 6

5 5 M in. (1, ) = 6 6 The new basic variable is x2 . Second Iteration: Step:1 let XB = (x2 ),

XN B =

x1 x3

1 x2 = 1 − (x1 + x3 ) 2 Step:2 Substitute (4) in (1) 1 1 1 M ax. f (x1 , x3 ) = 4x1 + 6(1 − (x1 + x3 )) − 2x1 2 − 2x1 (1 − (x1 + x3 )) − 2(1 − (x1 + x3 ))2 2 2 2 ∂f ∂f = 1 − 3x1 , = −1 − x3 ∂x1 ∂x2 ∂f =1 ∂x1 (0,0) ∂f = −1 ∂x3 (0,0) This indicates that x1 can be introduce to increased objective function. Step:3 1 x2 = 1 − (x1 + x3 ) and x3 = 0 2 If x1 is increased to a value greater then 2, x2 will become negative. 20

∂f =0 ∂x1 ⇒ 1 − 3x1 = 0 1 ⇒ x1 = 3 1 1 M in. (2, ) = 3 3 1 Therefore x1 = 3 1 5 Hence x1 = , x2 = , 3 6 25 and M ax. f (x) = 6

x3 = 0

21

3 3.1

Separable Programming Introduction

This programming deals with such non-linear programming problems in which the objective function as well as constraints are separable. A Non-linear programming problem can be reduced to a Linear Programming Problem and the usual simplex method can be used to get an optimal solution.

3.2

Separable Function

Definition: A Function f (x1 , x2 , ..., xn ) is said to be separable if it can be expressed as the sum of n single valued functions f1 (x1 ), f2 (x2 ), ..., fn (xn ), i.e.

f (x1 , x2 , ..., xn ) = f1 (x1 ) + f2 (x2 ) + ... + fn (xn ) .

Example: g(x1 , x2 , ..., xn ) = c1 x1 + ... + cn xn where c 0 s are constants, is a separable function. g(x1 , x2 , x3 ) = x1 3 + x2 2 sin(x1 ) + log(x61 ) is not a separable function. Reducible to Separable Form: Sometimes the functions are not directly separable but can be made separable by simple substitutions. Example: M ax. Z = x1 x2 Let y = x1 x2 Then log y = log x1 + log x2 Hence the problem becomes M ax. Z = y, subject to log y = log x1 + logx2 which is separable.

22

Reducible to separable form: (1) M ax. Z = x1 x2 x3

Let y = x1 x2 x3 ⇒ log y = log x1 + log x2 + log

3

Hence, the problems are M ax. Z = y subject to log y = log x1 + log x2 + log x3

f or

(x1 , x2 , x3 > 0)

(2) If x1 , x2 , x3 > 0 then

Let

y = u1 u2 u3

u1 = x1 + v1

⇒ x1 = u1 − v1

u2 = x2 + v2

⇒ x2 = u2 − v2

u3 = x3 + v3

⇒ x3 = u3 − v3

{x1 x2 x3 = (u1 − v1 )(u2 − v2 )(u3 − v3 ) = u1 u2 u3 − u3 v2 u1 − v1 u2 u3 + v1 v2 u3 − u1

then; M ax. Z = y − u1 u2 u3 − u3 v2 u1 − v1 u2 u3 + v1 v2 u3 − u1 u2 v3 + u1 v2 v3 + v1 u2 v3 − v1 v2 v3 subject to log y = log u1 + log u2 + log u3

23

which is separable.

3.3

Separable Programming Problem

A Non-linear programming problem in which the objective function can be expressed as a linear combination of several different single variable functions, of which some or all are non-linear, is called a separable programming problem.

Non-linear programming which has the problem of minimizing a convex objective function(or maximizing a concave objective function) in the convex set of points is called Convex Programming. In general, we take non-linear constraints.

Separable Convex Programming Problem

A separable programming problem in which the separate functions are all convex can be defined as a separable convex programming problem with separable objective function. i.e If

f (x) = f1 (x1 ) + f2 (x2 ) + ... + fn (xn )

where f1 (x1 ), f2 (x2 ), ..., fn (xn ) are all convex example: f (x) = 3x31 + 2x23 − x1 − 3x3

So, let

3.4

f1 (x1 ) = 3x31 − x1

and f2 (x2 ) = 2x23 − 3x3

Piece-wise Linear Approximation of Non-linear Function:-

Consider the non-linear objective function M aximizez =

n X

fj (xj )

j=1

subject to constraints: n X

aij xj = bi ,

i = 1, 2, ..., m and xj > 0 ; f or all j

j=1

24

where fj (xj )= nonlinear function in xj . The points (ak , bk ) , k = 1, 2, ..., K are called the breaking points joining the linear segments which approximate the function f (x) . Let wk denote the non-negative weight associated with the kth breaking point such that K X

wk = 1

k=1

wk0 = (ak0 , bk0 ) and wk0 +1 = (ak0 +1 , bk0 +1 )

then

f (x) =

k X

bk wk , where x =

k=1

k X

ak w k

k=1

subject to the necessary additional constraints are:

0 6 w1 6 y1 0 6 w2 6 y1 + y2 .. .

.. .

0 6 wk−1 6 yk−1 + yk−2 0 6 wk 6 yk−1

k X k=1

wk = 1,

k−1 X

yk = 1,

yk = 0 or 1 f or all k

k=1

Suppose

yk 0 = 1

Above all other yk = 0 0 6 wk 0 6 yk 0 0 6 wk0 +1 6 yk0 = 1 Thus, the remaining constraints should be wk 6 0 . Therefore; all other wk = 0 as desired.

25

3.5

Reduction of separable programming problem to linear programming problem

Let us consider the separable programming problem M ax.(or M in.) Z =

n X

fj (xj )

j=1

subject to the constraints : n X

gij (xj ) 6 bi

j=1

xj > 0 (i = 1, 2, ..., m; j = 1, 2, ..., n) where some or all gij (xj ), fj (xj ) are non-linear. Equivalent mixed problem is M ax.(or M in.)z =

Kj n X X

fj (ajk )wjk ,

j=1 k=1

subject to the constraints: Kj n X X

gij (ajk )wjk 6 bi , i = 1, 2, ..., m

j=1 k=1

0 6 wj1 6 yj1 0 6 wjk 6 yj.k−1 + yjk

, k = 2, 3, ..., Kj−1 0 6 wjkj 6 yj.kj−1

kj X

kj−1

wjk = 1,

k=1

yjk = 0 or 1 ;

k = 1, 2, ..., Kj ,

X

yjk = 1

k=1

j = 1, 2, ..., n

The variables for the approximating problem are given by wjk and yjk . We can use the regular simplex method for solving the approximate problem under the additional constraints involving yjk .

Algorithm Step-1 If the objective function is of minimization form; convert it into maximization. 26

Step-2 Test whether the functions fj (xj ) and gij (xj ) satisfy the concavity (convexity) conditions required for the maximization(minimization) of non-linear programming problem. If the condition are not satisfied, the method is not applicable, otherwise go to next step. Step-3 Divide the interval 0 6 xj 6 tj

(j = 1, 2, ..., n) into a number of mesh points

ajk (k =

1, 2, ..., Kj ) such that aj1 = 0, aj1 < aj2 < ... < ajk = tj .

Step-4 For each point ajk , compute piecewise linear approximation for each fj (xj ) and gij (xj ) where j = 1, 2, ..., n; i = 1, 2, ..., m. Step-5 Using the computations of step − 4,write down the piece-wise linear approximation of the given NLPP. Step-6 Now solve the resulting LPP by two-phase simplex method. For this method consider wi1

(i = 1, 2, ..., m) as artificial variables. Since, the costs associated with them are

not given, we assume them to be zero. Then,Phase-I of this method is automatically complete., the initial simplex table of Phase-I is optimum and hence will be the starting simplex table for Phase-II. Step-7 Finally, we obtain the optimum solution x∗j of the original problem by using the relations: x∗j

=

Kj X

ajk wjk

(j = 1, 2, ..., n)

k=1

27

4

Fractional Programming

4.1

Introduction

In various applications of nonlinear programming a ratio of two functions is to be maximized or minimized. In other applications the objective function involves more than one ratio of functions. Ratio optimization problems are commonly called fractional programs. Linear Fractional Programming technique is used to solve the problem of maximizing the function of two linear functions subject to a set of linear equalities and the non-negativity constraints. This method can be directly solved by starting with a basic feasible solution and showing the conditions for improving the current basic feasible solution. The fractional Programming method is useful in solving the problem in Economics whenever the different economic activities utilize the fixed resources in proportion to the level of their values. These types of problems play an important role in 0 f inance0 .

Mathematical Formulation The Linear Fractional Programming Problem can be formulated as follows : 0

(c x + α) M ax.Z = 0 (d x + β)

(8)

Ax = b ,

(9)

Subject to the constraints: X>0

Where x, c and d are n × 1 column vectors A is an m × n column vectors 0

0

c , d is transpose of vectors α, β are some scalars The constraints set is always non-empty and bounded.

4.2

Computational Procedure Of Fractional Algorithm

We consider a example can better demonstrate the computational procedure of linear fractional programming algorithm. 28

Example: Solve the fractional programming problem M ax. Z =

x1 − 2x2 5x1 + 3x2 + 2

subject to: 3x1 + 6x2 6 8 5x1 + 2x2 6 10

and

x1 , x2 > 0

Solution. First, Introducing the slack variables s1 > 0 and s2 > 0 We write the problem in standard form becomes: M ax. Z =

x1 − 2x2 5x1 + 3x2 + 2

subject to 3x1 + 6x2 + s1 = 0 5x1 + 2x2 + s2 = 10 and x1 , x2 , s1 , s2 > 0 Here, α = 0 and β = 2 (1)

(2)

The method to determine the leaving variable and also the new values of xij , XB , ∆j , ∆j corresponding to improved solution will be the same as for ordinary simplex method.

B.V

dB

s1 s2

0 0

Table 1: Starting Table cB XB x1 x2 s1 (β1 ) s2 (β2 ) M in.(xB /x1 ) 0 0

8 10

z (1) = cB xB + α = 0 z (2) = dB xB + β = 0 z = z (1) /z (2) = 0

3 5

6 2

1 0

0 1

8/3 10/5←−

-1 -5 -5 ↑

2 -2 2

0 0 -

0 0 -

4j (2) 4j 4j

(1)

Introducing x1 and dropping s2 (β2 ), we get the first Iteration table. Again, Introducing X2 and dropping s1 (β1 ) , then we construct the second Iteration table. Now, Introducing X4 and removing s1 β(2) After this table we observe that all 4j > 0 So, the optimum solution is x1 = 3, , x2 = 1 , s2 = 2 ∴ M ax. Z = 1/16 29

5

Future Research

Some of the possible projects for future research include the following: Conduct a study on the genetic algorithms for solving quadratic programming problems. Compare the efficiency of these algorithms with respect to the algorithms mentioned in this project, for solving quadratic programming problems and other algorithms for solving general non-linear programming problems. Comparing the efficiency of these algorithms to other algorithms that may or may not have been mentioned in this project, for solving non-convex quadratic programming problems.

There are many more methods that have not been discussed in this project and therefore it could be extended to incorporate other algorithms available for quadratic programming and fractional programming.

30

References [1] F. S. Hillier, G. J. Lieberman. Introduction to Operations Research, Seventh Edition. The McGraw-Hill Companies, Inc., New York 2001. [2] D.S. Hira, P. K. Gupta. Operation Research. S.chand Publication, 2007-08. [3] P. R. Murthy. Operation Research, New age international(P) Limited., New Delhi, 2007. [4] S.D. Sharma Operation Research. Kedar Nath Ram Nath, Meerut, Delhi 2010. [5] H. A. Taha. Operation Research An Introduction. Pearson Education, Inc., Upper Saddle River, New Jersey, 2007. [6] M. Vankova. Algorithms for the Solution of the Quadratic Programming Problem. University of Port Elizabeth, January 2004.

31