15. Non-Linear Programming – Operations Research, 2nd Edition

15

Non-Linear Programming

15.1 INTRODUCTION

One of the important assumptions of linear programming problem is the linear relationship among the decision variables. This means that each decision variable will have an independent effect on the objective and will contribute a constant and proportional amount to it and that each constraint will involve a linear relationship. In many real-world cases, decision variables do not always utilise a constant and independent amount. For instance, expansion programmes of a company forces work groups to specialise in particular tasks. This specialisation, in turn, creates productive efficiencies that can reduce rates of utilisation of resources, as the level of activity increases. For example, tripling production might require only a doubling rather than tripling of resource utilisation. Moreover, decision variables often have interrelated, instead of independent, effects on the system constraint relationships. For instance, consider an electrical service company in which the same personnel are engaged to serve both residential and commercial customers. That is, each customer group utilises joint rather than separate resources and facilities. For this reason, an increase in commercial calls could divert available service personnel from residential customer requests. If such a diversion delays service, the completion time per residential request would depend on the number of commercial calls. Thus, residential and commercial calls have an interrelated effect on the usage of service capacity.

In addition, each decision variable may not always make a constant and independent contribution to the objective function which we seek to optimise. A company, for example, can usually sell a larger quantity by lowering its price. Thus relevance per unit item will decrease as the sales quantity increases. In some other cases manufacturing cost per unit may decline as the output level increases. Thus a product’s per unit contribution to an objective function will fluctuate rather than remain constant as the level of activity changes.

In some situations the decision variables frequently have interrelated, rather than, independent, effects on the objective criterion. For example, consider a company that sells razors and blades. Since these products complement each other in the market, one may expect that a growth in razor sales increases the demand for blades. As a consequence, the profit from blades may depend on razor sales, apart from the number of sales for blades. In other words, razor and blade sales make interrelated contributions to the objective criterion.

When any decision activity makes a variable unit contribution or interrelated contribution to the objective criterion the mathematical model. Objective function will not involve a linear relationship. In such a case a decision variable will have an exponent from one and/or more than one activity will appear in a single term of the function.

A variable utilisation rate or interaction among the decision activities creates a non-linear relationship in the corresponding constraint expression. As a result, the mathematical model consists of a nonlinear objective function and/or at least one non-linear constraint expression, which is offer referred to as a non-linear program.

Thus, in a non-linear programming problem, either the objective function is non-linear or one or more constraints have non-linear relationship or both.

15.2 FORMULATION OF A NON-LINEAR PROGRAMMING PROBLEM (NLPP)

Some of the real-life situations can be formulated as a NLPP.

Example Production Allocation Problem

A manufacturing company produces two products: radios and TV sets. Sales-price relationships for these two products are given below:

 

TABLE 15.1

Product Quantity demanded Unit price
Radios 1,500 − 5p p
TV sets 3,800 − 10q q

The total cost functions for these two products are given by 200x + 0.1x2 and 300y + 0.1y2, respectively. The production takes place on two assembly lines. Radio sets are assembled on Assembly line I and TV sets are assembled on Assembly line II. Because of the limitations of the assembly line capacities, the daily production is limited to no more than 80 radio sets and 60 TV sets. The production of both types of products requires electronic components. The production of each of these sets requires five units and six units of electronic equipment components, respectively. The electronic components are supplied by another manufacturer, and the supply is limited to 600 units per day. The company has 160 employees, that is, the labour supply amounts to 160 man-days. The production of one unit of radio set requires 1 man-day of labour, whereas 2 man-days of labour are required for a TV set. How many units of radio and TV sets should the company produce in order to maximise the total profit? Formulate the problem as a non-linear programming problem.

Solution: Let us assume that whatever is produced is sold in the market. Let x and y stand for the quantities of radio sets and TV sets, respectively, produced by the firm. Then, we are given that

Further, if C1 and C2 stand for the total cost of production of these amounts of radio sets and TV sets, respectively, then we are also given that

 

C1 = 200x + 0.1x2   and   C2 = 300y + 0.1y2

Now, the revenue from radio sets is px and on TV sets is qy. Thus, the total revenue R = px + q y.

That is,

R = (300 − 0.2x)x + (380 − 0.1y)y
= 300x − 0.2x2 + 380y − 0.1y2

The total profit z is measured by the difference between the total revenue R and the total cost C = C1 + C2.

Thus,

z = RC1C2 = 100x − 0.3x2 + 80y − 0.2y2

The objective function thus obtained is a non-linear function.

In the present case, production is influenced by the available resources. The two assembly lines have limited capacity to produce radio and TV sets. Since no more than 80 radio sets can be assembled on assembly line I and 60 TV sets on assembly line II per day, we have the restrictions: x ≤ 80 and y ≤ 60.

There is another constraint in the daily requirement of the electronic components, so that 5x1 + 6x2 ≤ 600. The number of available employees is limited to 160 man-days. Thus, x1 + 2x2 ≤ 160. Also obviously, since the manufacturer cannot produce negative number of units, we must have x1 ≥ 0 and x2 ≥ 0.

Hence, the required NLPP takes the form

 

Maximise Z = 100x − 0.3x2 + 80y − 0.2y2

Subject to the constraints

 

0 ≤ x ≤ 80, 0 ≤ y ≤ 60, 5x + 6y ≤ 600,
x + 2y ≤ 160   and   x, y ≥ 0.

General Non-linear Programming Problem

Let z be a real value function of n variables defined by

 

z = f(x1, …, xn)

Let {b1, b2, …, bm} be a set of constraints such that

 

g1 (x1, x2, …, xn) {≤, ≥ or =} b1
g2 (x1, x2, …, xn) {≤, ≥ or =} b2

gm (x1, x2, …, xn) {≤, ≥ or =}bm

where, gis are real value functions of n variables x1, …, xn. Finally, let xj ≥ 0, j = 1, 2, …, n.

If either f(x1, …, xn) or some gi(x1, …, xn), i = 1, 2, …, m, or both are non-linear, then the problem of determining the n-type (x1, …, xn) which makes z a maximum or minimum and satisfies the constraints is called as a general non-linear programming problem (GNLPP).

In matrix notations, the GNLPP may be written as:

Determine XTRn so as to maximise or minimise the objective function z = f(x), subject to the constraints

 

gi(X) {≤, ≥ or =} bi, X ≥ 0 i = 1, 2, …, m

where, either f(x) or some gi(X) or both are non-linear in X.

Sometimes it is convenient to write the constraints gi(x) {≤, ≥ or =} bi as hi(X) {≤, ≥ or =} for hi(X) = gi(X) − bi.

There is one simplex-like solution procedure for the solution of the general non-linear programming problem. However, numerous solution methods have been developed since the appearance of the fundamental theoretical paper by Khun and Tucker. A few primary types of available solution techniques will be discussed in the subsequent sections.

15.3 UNCONSTRAINED OPTIMISATION

15.3.1 Univariate Optimisation

In this section we deal with the optimisation of a single variable function y = f(x). Figure 15.1, is a plot of a continuous function y = f(x) which illustrates some of the concepts associated with the optimisation theory.

FIGURE 15.1

We have shown some points A, B, C, D, E and F associated with peaks and troughs of the curve.

Point A is called the relative or local maximum of the curve.

Point F is called the relative or local minimum of the curve.

Point E is called absolute or global maximum of the curve.

Point B is called the absolute or global minimum of the curve.

Such maxima or minima are known collectively as extreme points. In the figure, there is a line drawn tangent to the curve y = f(x) at A, B, C, D, E and F. The tangent lines are all flat, that is, they have a slope equal to zero. Such points are called stationary points.

Thus, extreme points are stationary points. But the converse is not true, since C is a stationary point not an extreme point. The point C is an inflection point or saddle point.

Procedure for finding the saddle point:

Step 1: Find the first derivate of f(x) denoted by f′(x) or .

Step 2: Solve f′(x) = 0 for x.

Step 3: Find the second derivative of y = f(x) and determine its value at the stationary points. A negative (positive) value indicates that the stationary point is a maximum (minimum).

Example

Find the extreme points of y = x3 − 12x.

Solution:

y = x3 − 12x

Thus, x = +2 and x = −2 are the stationary points.

Now,

. Hence, x = +2 is a point of minimum.

. Hence, x = −2 is a point of maximum.

15.3.2 Bivariate Optimisation

Let f(x1, x2) be a function of two variables. Let fx1 or (f1) denote the partial derivative of f with respect to x1 and let fx2 or (f2) denote the partial derivative of f with respect to x2. fx1x2 denotes derivative of yf first with respect to x2 and then with respect to x1.

Procedure for obtaining extreme points

Step 1: Find the partial derivative fx1, fx2 of the original function.

Step 2: Set the partial derivatives to zero and solve for x1 and x2. The solution yields stationary points denoted by .

Step 3: Evaluate the second derivative by substituting the stationary points and form a matrix these values called the Hessian matrix at .

Step 4: The stationary point is a minimum if the leading minors of the Hessian matrix

but a maximum if the leading minors of the Hessian matrix

where | | denotes the determinant.

Example

Find the extreme points of the bivariate function f(x1, x2) = 4 + 8x1x2.

Solution: We compute the first partial derivatives

 

fx1 = 8x1 + 8x2
fx2 = 8x1

The second partial derivatives are

 

fx1x1 = 8 + 0 = 8, fx1x2 = fx2x1 = 8; fx2x2 = 0

The Hessian matrix is

Setting the first partial derivatives to zero

 

8x1 + 8x2 = 0
8x1 = 0     we get
x1 = 0, x2 = 0.

Thus the stationary point is = (0, 0). Since the Hessian matrix entries do not involve any variables, the evaluated Hessian matrix is the above matrix itself.

Since

we conclude that the stationary point (0, 0) is neither a minimum point nor a maximum point.

15.3.3 Multivariate Optimisation

Let us consider a function f(x1, x2, x3) of three variables x1, x2 and x3. We shall indicate the natural extension to any number of variables. Here also, we evaluate the first partial derivatives, namely, fx1, fx2, fx3 and the second partial derivatives, namely, fx1x1, fx1x2, fx1x3, fx2x1, fx2x2, fx2 x3, fx3x1, fx3x2 and fx3 x3. To find the optimum of f(x1, x2, x3) we follow the steps given below.

  1. Solve the equations

     

    fx1= 0
    fx2 = 0
    fx3 = 0

    to get the stationary point .

  2. Evaluate the second partial derivatives at and form the following Herssian matrix
  3. Consider the leading minors of H()
  4. If the sign of the above leading minors is positive, the stationary point is a minimum point. On the other hand, if the signs are alternating, with minus sign for the first leading minor, then the stationary point is a maximum point.

Example

Examine the following function for extreme points f(x1, x2, x3) = x1 + 2x3 + x2 x3x3.

Solution: We compute the first partial derivatives

 

fx1 = 1 − 2x
fx2 = x3 − 2x2
fx3 = 2 + x2 − 2x3

Setting these first derivatives equal to zero and solving them, we get the stationary point = (1/2, 2/3, 4/3).

Next, we compute the second partial derivatives,

 

fx1x1 = 0 − 2 = −2
fx1x2 = 0, fx1x3 = 0
fx2x1 = 0, fx2x2 = 0 − 2 = −2
fx2x3 = 1 − 0 = 1, fx3x1 = 0
fx3x2 = 0 + 1 − 0 = 1, fx3x3 = 0 + 0 − 2 = −2

Here also, the second partial derivatives do not involve x1, x2, x3 and evaluating these derivatives at is not necessary.

Thus, the Hessian matrix is

The leading minors whose sign we have to observe are

The exact values of the above quantifiers are −2, + 4 and −6

Since the signs are −, + and −, the stationary point is a maximum point.

15.4 CONSTRAINED OPTIMISATION

15.4.1 Constrained Optimisation with Equality Constraints

If the non-linear programming problem is composed of some differentiable objective function and equality sign constraints, the optimisation may be achieved by the use of Lagrange multipliers (a systematic way of generating the necessary conditions for a stationary point) as illustrated below.

Consider the problem of maximising or minimising z = f(x, x2) subject to the constraints:

 

g (x1, x2) = c   and   x1, x2 ≥ 0, where c is a constant.

We assume that f(x1, x2) and g (x1, x2) are differentiable w.r.t. x1 and x2. Let us introduce a different function h(x1, x2) differentiable w.r.t. x1 and x2 and defined by h(x1, x2) = g (x1, x2) − c. Then, the problem can be restated as follows:

 

Maximise z = f(x1, x2) subject to the constraints
h(x1, x2) = 0   and   x1, x2 ≥ 0.

To find the necessary conditions for a maximum (or minimum) value of Z, a new function is formed by introducing a Lagrange multiplier λ, as

 

L (x1, x2, λ) = f(x1, x2) − λh(x1, x2).

The number λ is an unknown constant, and the function L (x1, x2, λ) is called the Lagrangian function with Lagrange multiplier λ. The necessary conditions for a maximum or minimum (stationary value) of f(x1, x2) subject to h(x1, x2) = 0 are thus given by

Now, these partial derivatives are given by

where L, f and h stand for the functions L(x1, x2, λ), f(x1, x2) and h(x1, x2), respectively, or simply by

 

L1 = f1λh1, L2 = f2λh2   and   Lλ = −h

The necessary conditions for maximum or minimum of f(x1, x2) are thus given by

 

f1 = λh1, f2 = λh2   and   −h(x1, x2) = 0

Remark: The necessary conditions become sufficient conditions for a maximum (minimum) if the objective function is concave (convex) and the constraints are in the form of equalities. (We recall that, a function f(x) on a non-empty subset of R″ is said to be convex if for any two vectors x1 and x2 is S,

 

f [λx1 + (1 − λ)x2] ≤ λ f (x1), + (1 − λ) f(x2), 0 ≤ λ ≤ 1.

A function f(x) is said to be concave if − f(x) is convex.

Example 1

Obtain the necessary and sufficient conditions for the optimum solution of the following NLPP:

 

Minimise Z = 3e2x1 + 1 + 2ex2 + 5

subject to

x1 + x2 = 7, x1, x2 ≥ 0.

Solution: Let us introduce a new differentiable Lagrangian function L(x1, x2, λ) defined by

 

L(x1, x2, λ) = f(x1, x2) − λ(x1 + x2 − 7)
= 3e2x1 + 1 + 2ex2 + 5λ(x1 + x2 − 7)

where, λ is the Lagrangian multiplier.

Since the objective function Z = f(x1, x2) is convex and the side constraint an equality one, the necessary and sufficient conditions for the minimum of f(x1, x2) are given by

These imply,

6e2x1 + 1 = 2ex2 + 5 = 3e7−x1 + 5

or,

log 3 + 2x1 + 1 = 7 − x1 + 5   or   x1 = 1/3 (11 − log 3)

Thus,

x1 = 7 − 1/3 (11 − log 3).

Example 2

Find the dimension of rectangular parallelopiped with largest volume whose sides are parallel to the coordinate planes to be inscribed in the ellipsoid

Solution: Let the dimensions of a rectangular parallelopiped be x, y, and z. Its volume is then given by u (x, y, z) = xyz

Forming the Lagrangian function L, we have

 

L(x, y, z, λ) = u (x, y, z) − λg (x, y, z)

Now, differentiating the above equation with respect to each variable and setting the result equal to zero, we obtain

Multiplying first three equations by x, y, z, respectively, adding, and then making use of the last equation, we obtain,

 

3v(x, y, z) − 2λ = 0

Thus,

Now, with this value of λ substituted in first three equations, we have

which is the required answer.

Generalised Lagrangian Method to n-Dimensional Case

Consider the general NLPP

Maximise (or minimise) Z = f(x1, x2, …, xn) subject to the constraints

 

gi(x1, …, xn) = ci   and   xi ≥ 0, i = 1, 2, …, m (m < n)

The constraints can be written as

 

hi(x1, …, xn) = 0   for   i = 1, 2, …, m

where,

hi(x1, …, xn) = gi (x1, …, xn) − ci

The problem can be written in the matrix form as

Maximise (or minimise) Z = f(x), xRn subject to the constraints hi(x) = 0, x ≥ 0.

To find the necessary conditions for a maximum of minimum of f(x), the Lagrangian function L(x, λ) is formed by introducing m Lagrangian multipliers λ = (λ1, λ2, …, λm). This function is defined by

Assuming that L, f and hi are all partially differentiable w.r.t. x1, x2 …, xn and λ1, λ2, …, λm, the necessary conditions for a maximum (minimum) of f(x) are

These m + n necessary conditions can be represented in the following abbreviated form:

j = 1, 2, …, n
j = −hi = 0   or   hi = 0,     i = 1, 2, …, n

where

Note: These necessary conditions also become sufficient for a maximum (minimum) of the objective function if the objective function is concave (convex) and the side constraints are equality ones.

Example

Obtain the set of necessary conditions for the non-linear programming problem

 

Maximise

subject to the constraints

 

x1 + x2 + 3x3 = 2
5x1 + 2x2 + x3 = 5
x1, x2, x3 ≥ 0

Solution: In this problem we are given that

 

x = (x1, x2, x3), f(x) = ,
h1(x) = x1 + x2 + 3x2 − 2 = 0   h2(x) = 5x1 + 2x2 + x3 − 5 = 0

We construct the Lagrangian function for maximising f(x)

 

L(x, λ) = f(x) − λ1 h1(x) − λ 2h2(x).

This gives the following necessary conditions:

Sufficient Conditions for Maximum (Minimum) of Objective Function (with Single Equality Constraint)

Let the Lagrangian function for a general NLPP involving n variables and one constraint be:

 

L(x, λ) = f(x) − λh(x).

The necessary conditions for a stationary point to be a maximum or minimum are

and

The value of λ is obtained by

The sufficient conditions for a maximum or minimum require the evaluation at each stationary point of n − 1 principal minors of the determinant given below:

If Δ3 > 0, Δ4 < 0, Δ5 > 0, …, the sign pattern being alternate, the stationary point is a local maximum.

If Δ3 < 0, Δ4 < 0,… Δn + 1 < 0, the sign being always negative, the stationary point is a local minimum.

Example

Solve the non-linear programming problem

Minimise

subject to the constraints

x1 + x2 + x3 = 1
x1, x2, x3 ≥ 0.

Solution: The Lagrangian function can be formulated as follows:

The necessary conditions for the stationary point are:

By solving these simultaneous equations, we get the stationary point x = (x1, x2, x3) = (6, 2, 3), λ = 0. The sufficient condition for the stationary point

 

x = (x1, x2, x3) = (6, 2, 3); λ = 0.

The sufficient condition for the stationary point to be a minimum is that minors Δ3 and Δ4 both be negative. Now,

Thus, x = (6, 2, 3) is the solution to the given LPP.

Sufficient Conditions for Maximum (Minimum) of Objective Function (with More than One Equality Constraints)

Introducing the m Lagrangian multipliers λ = (λ1, λ2, …, λm), let the Lagrangian function for a general NLPP with more than one constraint be

The reader may verify that the equations

yield the necessary conditions for stationary points of f(x) Thus, the optimisation of f(x) subject to h(x) = 0 is equivalent to the optimisation of L(x, λ).

We state here the sufficiency conditions for the Lagrange multiplier method of stationary point of f(x) to be a maxima or minima without proof. For this, we assume that the function L(x, λ), f(x) and h(x) all possess partial derivative of order one and two w.r.t. the decision variables.

Let

Be the matrix of the second order partial derivatives of L(x, λ) w.r.t. O decision variables

U = [hij(x)]m×n

where

Define the square matrix

Where, O is a m × n null matrix. The matrix HB is called the bordered Hessian matrix. Then, the sufficient conditions for maximum and minimum stationary point are given below.

Let (x0, λ0) for the function L(x, λ) be its stationary point. Let be the corresponding bordered Hessian matrix computed at this satisfactory point. Then, x0 is a

  1. Maximum point, if starting with principal minor of order (2m + 1) the last (nm) principal minors of form an alternating sign pattern starting with (−1)mn; and
  2. Minimum point, if starting with principal minor of order (2m + 1), the list (nm) principal minors of have the sign of (−1)m.

Note: It may be observed that the above conditions are only sufficient for identifying an extreme point, but not necessary condition. That is, a stationary point may be an extreme point without satisfying the above conditions.

Example

Solve the non-linear programming problem

Optimise subject to the constraints x1 + x2 + x3 = 15, 2x1x2 + 2x3 = 20

Solution: Now

 

f(x) =
h1(x) = x1 + x2 + x3 − 15
h2(x) = 2x1x2 + 2x3 − 20

Construct the Lagrangian function

 

L(x, λ) = f(x) − λ1h1(x) − λ2h2(x)
= λ1(x1 + x2 + x3 − 15) − λ2(2x1x2 + 2x3 − 20)

The stationary point (x0, λ0) has thus given the following necessary conditions:

The solution to these simultaneous equations yields

 

x0 = (x1, x2, x3) = (33/9, 10/3, 8) and
λ0 = (λ1,λ2) = (40/9, 52/9).

The bordered Hessian matrix at this solution (x0, λ0) is given by

Hence, since n = 3 and m = 2 therefore nm = 1, (2m + 1 = 5). This means one needs to check the determinant only; it must have the sign of (−1)2.

Now, since det = 72 > 0, x0 is a minimum point.

15.4.2 Constrained Optimisation with Inequality Constraints

We now derive the Kuhn-Tucker conditions (necessary and sufficient) for the optimal solution of general NLPP. Consider the general NLPP:

Optimise Z = f(x1, x2, …, xn), subject to the constraints.

g (x1, …, xn) ≤C and x1, x2 …, xn ≥ 0

where, C is a constant.

Introducing the function h(x1, …, xn) = gC, the constraint reduces to h(x1, …, xn) ≤ 0. The problem thus can be written as

 

Optimise Z = f(x) subject to h(x) ≤ 0 and x ≥ 0 where xRn.

We now slightly modify the problem by introducting 9 new variable S, defined by S2 = −h(x) or h(x) + S2 = 0.

The new variables S is called slack variable and appears as its square in the constraint equation so as to ensure its being non-negative. This avoids an additional constraints S ≥ 0. Now, the problem can be restated as

 

Optimise Z = f(x), xRn subject to the constraints h(x) + S2 = 0 and x ≥ 0.

This is a problem of constrained optimisation in n + 1 variables and a single equality constraint and can thus be solved by the Lagrangian multiplier method

To determine the stationary points, we consider the Lagrangian function defined by

 

L (x, s, λ) = f(x) − λ[ h(x) +S2],

where λ is the Lagrange multiplier. The necessary conditions for stationary points are

requires either λ = 0 or S = 0. If S = 0, (2) implies that h(x) = 0. Thus, we have λ h(x) = 0.

The variable S was introduced merely to convert the inequality constraints into an equality one, and therefore may be discarded. Moreover, since S2 ≥ 0, (2) gives h(x) ≤ 0. Whenever h(x) 0. We get λ = 0 and whenever λ < 0, h(x) = 0. However, λ is unrestricted in sign whenever h(x) = 0.

The necessary conditions for the point x to be a point of maximum are thus restated as (in the abbreviated From):

The set of such necessary conditions is called Kuhn-Tucker condition.

A similar argument holds for the minimisation non-linear programming problem:

 

Minimise Z = f(x) subject to the constraints g(x) ≥ C and x ≥ 0.

Introduction of h(x) = g(x) − C reduces the first constraint to h(x) ≥ 0. The new surplus variable so can be introduced h(x) ≥ 0 so that we may have the equality constraint h(x) − = 0. The appropriate Lagrangian function is

 

L(x, S0, λ) = f(x)−[h(x) − ]

The following set of Kuhn-Tucker conditions is obtained:

Theorem (Sufficiency of Kuhn-Tucker Conditions)

The Kuhn-Tucker conditions for a maximisation NLPP of maximising f(x) subject to the constraints h(x) ≤ 0 and x ≥ 0 are sufficient conditions for a maximum of f(x), if f(x) is concave and h(x) is convex.

Proof: The result follows if we are able to show that the Lagrangian function

 

L(x, S, λ) = f(x) − [h(x) + S2],

where, S is defined by h(x) + S2 = 0, is concave in x under the given conditions.

In that case the stationary point obtained from the Kuhn-Tucker conditions must be the global maximum point.

Now, since h(x) + S2 = 0, it follows from the necessary conditions that λS2 = 0. Since h(x) is convex and λ ≥ 0, it follows that λ h(x) is also convex and −λh(x) is concave. Thus, we conclude that f(x) −λh(x) and hence

 

f(x) − λ[h(x) + S2] = L (x, S, λ) is concave in x.

Note: By a similar argument it can be shown that for the minimisation of NLPP, Kuhn-Tucker conditions are also the sufficient conditions for the minimum of the objective function, if the objective function f(x) is convex and the function h(x) is concave.

Example 1

Use the Kuhn-Tucker conditions to solve the NLPP

subject to

3x1 + 2x2 ≤ 6, x1 ≥, x1 ≥ 0

Solution: Here,


g(x) = 3x1 + 2x2, C = 6
h(x) = g(x) − C = 3x1 + 2x2 − 6

The Kuhn-Tucker conditions are

λh(x) = 0, h(x) ≤ 0, λ ≥ 0 Where λ is the Lagrangian multiplier.

That is,

From equation (15.4.3) either

 

λ = 0

or,

3x1+ 2x2 − 6 = 0

Let λ = 0 then from (15.4.1) and (15.4.2), we get x1 = 4 and x2 = 5. With these values of x1 and x2, (15.4.4) cannot be satisfied. Thus, optimal solution cannot be obtained here for λ = 0. Let then λ ≠ 0 and so 3x1 + 2x2 − 6 = 0. This, together (15.4.1) and (15.4.2) yield the stationary value

Now, it is esay to observe that h(x) is convex in x and f(x) is concave in x. Thus, Kuhn-Tucker conditions are the sufficient conditions for the maximum. Hence, x0 = is the solution to the given LPP NLPP. The maximum value of Z (corresponding to x0) is given by Z0 = 21.3.

Kuhn-Tucker Conditions for General NLPP with m (< n) Constraints

Introducing S = (S1, S2, …, Sm), let the Lagrangian function for a general NLPP with m (< n) constraints be

where, λ = (λ1…, λm) are the Lagrangian multipliers,

The necessary conditions for f(x) to be a maximum are:

where

L = L(x, s, λ), f = f(x)   and   hi = hj(x)

Equation (15.4.8) states that either λi = 0 or Si = 0. By an argument parallel to that considered in the case of single constraint, the conditions (15.4.8) and (15.4.7) together are replaced by conditions (15.4.9), (15.4.10) and (15.4.11) below:

The Kuhn-Tucker conditions for a maximum thus may be restated as

where,

Theorem (Sufficiency of Kuhn-Tucker Conditions)

For the NLPP of maximising, f(x), xRn subject to the inequality constraints hi(x) ≤ 0 (i = 1, 2…, m), the Kuhn-Tucker conditions are also the sufficient conditions for a maximum if f(x) is concave and all hi(x) a convex function f(x).

The Kuhn-Tucker conditions for a minimisation non-linear programming problem may be obtained in a similar manner. These conditions in that case come out to be

It can be shown that for this minimisation problem, Kuhn-Tucker conditions are also sufficient conditions for the minima if f(x) is convex and all hi(x) are concave in x, that is, −hi (x) is also convex.

Note:

  1. If f(x) is strictly concave (convex), the Kuhn-Tucker conditions are sufficient conditions for an absolute maximum (minimum).
  2. We may consider x ≥ 0 or −x ≤ 0 to have been included in the inequality constraint hi (x) ≤ 0.
  3. In both maximisation and minimisation NLPP, the Lagrange multipliers λi corresponding to the equality constraints hi(x) = 0 must be unrestricted in sign.
  4. A general NLPP may contain the constraints of the ‘≥’ or ‘=’ or ‘≤’ type. In the case of maximisation NLPP, all constraints must be converted into those of ‘≤’ type and in the case of minimisation NLPP, into those of ‘≥’ type by suitable multiplying by −1.

Example

Determine x1, x2, x3 so as to

Maximise

Subject to the constraints:

 

x1 + x2 ≤ 2
2x1 + 3x2 ≥12
x1, x2 ≥ 0

Solution: Here,

First, we decide about the concavity−convexity of f(x). For this, we compute the bordered Hessian matrix

The objective function f(x) is concave if the principal minors of matrix HB alternate in sign, starting with the negative sign. If the principal minors are positive, the objective function is convex. So, in this case f(x) is concave. Clearly, h1(x) and h2(x) are convex in x. Thus, the Kuhn-Tucker conditions will be the necessary and sufficient conditions for a maximum. These conditions are obtained by partial derivatives of Lagrangian function:

 

L(x, λ, s) = f(x)λ1 [ g1(x) + ] −λ2[ g2(x) + ]

Where, S = (s1, s2), λ = (λ1, λ2), s1 and s2 being slack variables, and λ1, λ2 are Lagrangian multipliers.

The Kuhn-Tucker conditions are given by

  1. (i) −2x1 + 4 = λ1 + 2λ2     (ii) −2x2 + 6 = λ1 + 3λ2     (iii) −2x2 = 0
  2. (i) l1(x1 + x2 − 2) = 0     (ii) λ 2(2x1 + 3x2 − 12) = 0
  3. (i) x1 + x2 − 2 ≤ 0     (ii) 2 x1 + 3x2 − 12 ≤ 0
  4. λ1 ≥ 0, λ2 ≥ 0

Now, four different cases may arise:

Case 1: λ1 = 0 and λ2 = 0 (i), (ii) and (iii) of 1 yield x1 = 2, x2 = 3, x3 = 0. However, this solution violates both the inequalities of (3).

Case 2: λ1 = 0 and λ2 ≠ 0. In this case (ii) of 2 will give 2x1 + 3x2 = 12 and (i) and (ii) of 1 give −2x1 + 4 = 2λ2 − 2x2 + 6 = 3λ2. The solution to these simultaneous equations gives x1 = 2/13, x2 = 3/13 λ2 = 24/13 > 0, also (iii) of 1 gives x3 = 0. However, this solution violates (i) of 3. So, this solution is discarded.

Case 3: λ1 ≠ 0, λ2 ≠ 0. In this case, (2) (i) and (ii) give x1 + x2 = 2 and 2x1 + 3x2 = 12. These equations give x1 = −6 and x2 = 8. Thus, 1 (i), (ii) and (iii) yield x3 = 0, λ1 = 68, λ2 = −26. Since λ2 = −26 violates the condition (4), so this solution is also discarded.

Case 4: λ1 ≠ 0, λ2 = 0. In this case 2 (i) gives x1 + x2 = 0. This together with 1(i) and (ii) give x1 = 1/2, x2 = 3/2, λ = 3 > 0. Further, from 3 (iii) x3 = 0. This solution does not violate any of the Kuhn-Tucker conditions.

Hence, the optimum (maximum) solution to the given problem is x1 = 1/2, x2 = 3/2, = 0 with λ1 = 3, λ2 = 0, the maximum value of the objective function is Z* = 17/2.

15.5 GRAPHICAL METHOD OF SOLVING A NON-LINEAR PROGRAMMING PROBLEM

In a linear programming problem the optimal solution was usually obtained at one of the corner (extreme) points of the convex region generated by the constraints and the objective function of the problem. But, it not necessary to find the solution at a corner or edge of the feasible region of a non-linear programming problem. The graphical method of solving an NLPP involving only two variables is best illustrated by the following samples problems.

Example 1 Non-Linear Objective Function and Linear Constraints

Minimise the distance of the origin from the convex region bounded by the constraints.

x1 + x2 ≥ 4, 2x1 + x2 ≥ 5 and x1 ≥ 0, x2 ≥ 0. Verify that the Kuhn-Tucker necessary conditions hold at the point of minimum distance.

Solution: The problem of minimising the distance of the origin from the convex region is equivalent to minimising the radius of a circle with centre as origin, say . Such that it touches (passes through) the convex region bounded by the given constrains. Thus, the problem is formulated as

Minimise subject to the constraints x1 + x2 ≥ 4, 2x1 + x2 ≥ 5, x1, + x2 ≥ 0.

Consider a set of rectangular cartesian axis OX1 X2 in the plane. Each point has the coordinates of the type (x1, x2) and conversely every ordered pair (x1, x2) of real numbers determine a point in the plane.

FIGURE 15.2

Clearly, any point which satisfies the condition x1 ≥ 0 and x2 ≥ 0 lies in the first quadrant and conversely for any point (x1, x2) in the first quadrant, x1 ≥ 0 and x2 ≥ 0. Since x1, x2 ≥ 0, consider the first quadrant only. Since x1 + x2 ≥ 4 and 2x1, x2 ≥ 5, the desired point must be somewhere in the unbounded convex region ABC shown in Fig. 15.2. Since our search for such a pair (x1, x2) which gives a minimum value of and lies in the convex region the desired point will be that point of the region at which a side of the convex region is tangent to the circle.

Differenting , we have 2x1dx1 + 2x2dx2 = 0, which gives,

Considering the equalities 2x1 + x2 = 5 and x1 + x2 = 4, we have on differentiation

 

2dx1 + dx2= 0   and   dx1 + dx2 = 0

The yield

From (15.5.1) and (15.5.2) we obtain

This shows that the circle has a tangent to it

  1. the line x1+ x2 = 4 at the point (2, 2)
  2. the line 2x1 + x2 = 5 at the point (2, 1)

The point (2, 1) dose not lie in the convex region and hence is to be discarded. Thus, the minimum distance from the origin to the convex region bounded by the constraints is Z0 = 22 + 22 = 8 is given by the point (2, 2).

verification of the Kuhn-Tucker Conditions

We now verify that the above minima satisfy the Kuhn-Tucker conditions also. Here we have, f(x) = , h′(x) = x1 + x2 − 4, h2(x) = 2x1 + x2 − 5 and the problem is that of maximising f(x) subject to the constraints h′(x) ≥ 0, h2(x) ≥ 0 and x ≥ 0. The Kuhn-Tucker conditions for this minimisation NLPP are:

 

  fj(x) = λ1hij (x) + λ2h2j(x) j = 1, 2
  λ1hi(x) = 0 i = 1, 2
  hi(x) ≥ 0 i = 1, 2
  λ1 ≥ 0 i = 1, 2

where, , (j = 1, 2) and λ1, λ2 are Lagrangian multipliers.

These conditions thus are as given below:

(a)

(b)

(c)

(d) (λ1 ≥ 0, λ2 ≥ 0)

If the point (2, 2) satisfies these conditions, then we must have from (a), λ1 = 4, λ2 = 0. With these values, (x1, x2) = (2, 2) and (λ1, λ2) = (4, 0), it is clear that the conditions (b), (c) and (d) are satisfied. Hence, the minima obtained by graphical method satisfies the Kuhn-Tucker conditions for a minima.

15.6 QUADRATIC PROGRAMMING

Quadratic programming is concerned with the NLPP of maximising (or minimising) the quadratic objective function, subject to a set of linear inequality constraints. In solving LPPs, because of linearity we were able to develop a very efficient algorithm (simplex method). Unlike the linear programing case, no such general algorithms exist for solving all non-linear programming problems. However, for problems with certain suitable structures, efficient algorithms have been developed. Also, it is often possible to convert the given non-linear problem into one in which these structures become visible.

Unlike linear programming, the optimal solution to a NLPP can be found anywhere on the boundary of the feasible region and even at some interior point of it. In recent years, several solution methods of NLPP have been developed. But, an efficient-like technique for a GNLPP is still required to be developed. A few available techniques for some particular cases of GNLPP shall be discussed in the subsequent sections.

Kuhn-Tuker Conditions with Non-Negative Constraints

In the Section 15.4, we obtained the necessary conditions for a point x0Rn to be a relative maximum of f(x) subject to the constraints hi(x) ≤ 0, i = 1, 2, …, m, x ≥ 0. These conditions called Kuhn-Tucker conditions were found by converting each inequality constraint to an equation through the addition of a squared slack variable , imposing the first-order conditions for maxima, on the first partial derivative of the Lagrangian function, and then simplifying the outcome. The following conditions resulted:

(a)   j = 1, 2, …, n
(b) −λihi(x) = 0   i = 1, 2, …, m
(c) hi(x) ≤ 0 and i = 1, 2, …, m
(d) λi ≥ 0   i = 1, 2, …, m

The reader may have observed that in obtaining these conditions, the non-negativity constraints x ≥ 0 were completely ignored. However, we always had in mind to discard all such solutions of (a) to (d) that violate x ≥ 0.

Now, we shall consider the non-negativity constraint x ≥ 0 as one the constraints, namely, h(x) ≥ 0, where h(x) = x, and derive the Kuhn-Tucker conditions for the resulting problem.

We restate the problem as

Maximise Z = f(x), xRn subject to the constraints hi(x) ≥ 0, −x ≤ 0, i = 1, 2, …, m. Clearly, there are m + n inequality constraints, and thus we add the squares of (m + n)slack variables S1, …, Sm, Sm + 1, …, Sm + n in the inequalities so as to convert them into equations.

To find the necessary conditions for maximum of f(x), we construct the associated Lagrangian function

where, S = (S1, S2, …, Sm + n), and λ = (λ1, …, λm + n)

are the Lagrangian multipliers. The Kuhn-Tucker conditions are: and,

and,

The Kuhn-Tucker conditions, as obtained from these, upon simplification are

(a) i = 1, 2, …, n  
(b) λi[hi(x) = 0] i = 1, 2, …, m  
(c) −λm + jxj = 0 j = 1, 2, …, n Maximise of
(d) hi(x) ≤ 0 i = 1, 2, …, m subject hi(x) ≥ 0
(e) λi, λm + j, xj ≥ 0 i = 1, 2, …, m x ≥ 0
  j = 1, 2, …, n  

Note: As before these conditions are sufficient also if f(x), is concave and all hi(x), are convex in x. Similarly, the Kuhn-Tucker conditions for GNLPP minimisation case are sufficient also if f(x) is convex and all hi(x) are concave in x.

Definition (Quadratic Programming Problem)

Let xT and CRn. Let Q be a symmetric m × n real matrix. Then, the problem of maximising (determining x so as to maximise)

Axb and x ≥ 0.

where, bTRn and A is an m × n real matrix is called a general quadratic programming problem.

Note: xT Qx represents a quadratic form. We recall that a quadratic form xT Qx is said to be positive-definite (negative definite) if xTQx > (< 0) for x ≠ 0 and positive semi-definite (negative semi-definite) if xTQx ≥ 0 (≤0) for all x such that there is one x ≠ 0 satisfying xT Qx = 0

It may be easily verified that

  1. If xT Qx is positive semi-definite (negative semi-definite), then it is convex (concave) in x over all of Rn, and
  2. If xT Qx is positive definite (negative definite) then it is strictly convex (strictly concave) in x over all of Rn

These results help in determining whether the quadratic objective function f(x) is concave (convex) and the implication of the same on the sufficiency of the Kuhn-Tucker conditions for constrained maxima (minima) of f(x).

Now, let us consider a QPP written in the form

subject to the constraints

where, djk = dkj for all j and k, and where bi ≥ 0. The Kuhn-Tucker conditions for maximum are:

Thus, the Kuhn-Tucker necessary conditions for an optimal solution to be QPP are:

These expressions can be simplified by introducing some additional notation. Let ≥ 0 be the slack variable introduced in the ith constraint (d) so that

and, let uj = λm+j for j = 1, 2, …,n. Then, (b) and (c) after simplification become

 

(b)′ λj = 0   for   j = 1, 2, …, m
(c)′ xjuj = 0   for   j = 1, 2, …, n

Further, since from (e) , λi, xi, uj must be all non-negative for i = 1, 2, …, m, j = 1, 2, …, n (b)′ and (c)′ can be expressed by a single constraint:

(complementary slackness)

Using the newly defined variables uj, we can rewrite (a) as

If we assume that the quadratic form is negative semi-definite, then f(x) is concave in x and hence the conditions (a) to (e) above become necessary and sufficient conditions for an optimal solution to QPP. Thus, under such assumption if we are able to find non-negative λi, , xj and uj such that, (d)′, (b)″ and (a)′ are satisfied, then such xj determines an optimal solution to the given QPP.

15.6.1 Wolfe’s Modified Simplex Method

The iterative procedure for the solution of a quadratic programming problem by Wolfe’s modified simplex method can be summarised as follows:

Step 1: Convert the inequality constraints into equations by introducing the slack variable in the ith constraint i = 1, 2, …, m, and the slack variables in the jth non-negativity constraint j = 1, 2, …, n.

Step 2: Construct the Lagrangian function

where x = (x1, …, xn), s = (s1, …, sm+n), λ = (λ1, …λm+1).

Differentiate L (x, s, λ) partially w.r.t. the components of x, s, and λ and equate the first order partial derivatives equal to zero. Derive the Kuhn-Tucker conditions from the resulting equations.

Step: 3: Introduce the non- negative artificial variables Aj, j = 1, 2, …, n in the Kuhn −Tucker condition for j = 1, 2, …, n and construct an objective function Z = A1 + A2 + … + An

Step 4: Obtain an initial basic feasible solution to the LPP:

Minimise Z = A1 + … + An subject to

where xn + 1 = , i = 1, 2, …, m, and satisfying the complementary slackness conditions:

Step 5: Use two phase simplex method to obtain an optimum solution to the LPP of step 4, solution satisfying the complementary slackness condition.

Step 6: The optimum solution obtained in step 5 is an optimum solution to the given QPP also.

Important Remarks on Wolfe’s Method

  1. If the quadratic programing problems is given in the minimisation form, then covert it into maximisation one by suitable modifications, in f(x) and the ‘≥’ constraints.
  2. With the exceptional condition of complementary slackness, the problem constructed in step 4 is exactly a linear programmer problem. So, we only need to modify the simplex algorithm to include the complementary slackness condition Thus, while deciding to introduce we must first ensure that : (i) either λi is not in the solution (or) (ii) λi will be removed when si enters. This additional check is not difficult to perform within the simplex routine.
  3. The solution to the above system is obtained by using phase I of the simplex method. Since our aim is to obtain a feasible solution, it does not require the consideration of phase II. The only necessary thing is to maintain the condition λisi = 0 = μj xj all the time. This implies that if λi is in the basic solution with positive value, then si cannot be basic with positive value. Similarly, μj and xj cannot be positive simultaneously.
  4. It should be observed that phase I will end in the usual manner with the sum of all artificial variables equal to only if the feasible solution to the problem exists.

Example 1

Use Wolfe’s method solve the QPP

Maximise subject x1 + 4x2 ≤ 4, x1 + x2 ≤ 2, x1, x2 ≥ 0.

Solution:

Step 1: First, convert the inequality constraints into equations by using slack variables and respectively. Thus, the problem becomes

subject to

Step 2: Construct the Lagrangian function

 

L(x1, x2, s1, s2, s3, s4, λ1, λ2, λ3, λ4)

Step 3: As − represents a negative semi-definite quadratic form Z = 2x1 + 3x2 − 2 is concave in x1, x2. Thus, maxima of L will be maxima of Z = 2x1 + 3x2 − 2 and vice versa. To derive the necessary and sufficient conditions for maxima of L (and hence of z) we equate the first order partial derivatives of L with respect to the variables x1, x2, si′s and λis. Thus, we have

Upon simplification and necessary manipulations these yield:

A solution xj, j = 1, 2, to (15.6.1) and satisfying (15.6.2) shall necessarily be an optimal one for maximising L. To determine the solution to the above simultaneous equation (1), we introduce the artificial variables A1 ≥ 0 and A2 ≥ 0 in the first two constraints of (15.6.1).

Step 4: The modified LPP problem becomess.

Maximise

Z = A1A2

Subject to

4x1 + λ1+ λ2λ3 + A1 = 2
4λ 1+ λ2λ4 + A2 = 3
x1 + 4x2 + x3 = 4 x1+ x2 + x4 = 2
x1, x2, x3, x4 ≥ 0 A1, A2, λ1, λ2, λ3, λ4, ≥ 0

satisfying the complementary slackness condition , where we replaced and by x3 and by x4. An initial basic feasible solution to the LPP is clearly given by

Step 5: Initial Table of Phase I

 

TABLE 15.2

From the Table 15.2 we observe that x1, λ1 or λ2 can enter the basis. But λ1 and λ2 will not enter the basis, because x3 and x4 are in the basis. This is in view of the complementary slackness conditions λ1x3 = 0 and λ2x4 = 0.

First Iteration: Introduce x1 and drop A1.

 

TABLE 15.3

Here, we observe that either λ1 or λ2 can enter the basis. But x3 and x4 are still in the basis, therefore, these cannot enter the basis because of the complementary slackness conditions. However, since λ4 is not in the basis, can enter the basis (because of λ4 x2 = 0).

Second Iteration: Introduce x2 and drop x3.

 

TABLE 15.4

Since x4 is in the basis, λ2 cannot enter and hence λ1 enter the basis.

Final Iteration:

 

TABLE 15.5

Hence, the optimum solution is

 

x1 = 5/16, x2 = 59/64 and
Maximum of Z = 3.19.

Example 2

Apply Wolfe’s method for solving the quadratic programming problem

  Minimise
  subject to x1 + 4x2 ≤ 5
2x1 + 3x2 ≤ 6   and   x1, x2 ≥ 0

Step 1: Converting the problem into maximisation and the inequalities into ‘≤’, the LPP becomes

  Maximise
  subject to x1 + 4 x2 ≤ 5; 2x1 + 3x2 ≤ 6; − x1 ≤ 0   and   −x2 ≤ 0

Step 2: Introducing the slack variables , our problem takes the form Max.

  Max.
  subject to

Step 3: Construct the Lagrangian function

The necessary and sufficient conditions are

Step 4: Introducing artificial variables A1, A2 ≥ 0, the modified linear programming problem is

  Max. Z = −A1A2
  subject to 2x1 + λ1 + 2λ2λ3 + A1 = 2
2x2 + 4λ1 + 3λ2λ4 + A2 = 4
x1+ 4x2 +x3 = 5
2x1 + 3x2 + x4 = 6
  where,

All the variables are non-negative and

 

λ1 x3 = 0, λ2 x4 = 0, λ3 x1 = 0   and   λ4 x2 = 0

Step 5: Initial table of Phase I

 

TABLE 15.6

Since x3 and x4 are in the basis we cannot introduce λ1 and λ2. Introduce x1 and drop A1.

Step 6: First Iteration—Introduce x2 and drop A1.

 

TABLE 15.7

Since x3 and x4 are in the basis, we cannot select λ1 and λ2. Introduce x2 and drop A2.

Step 7: Second Iteration

 

TABLE 15.8

Since x3 and x4 occur in the solution with negative values, they must be eliminated. Hence, introduce λ1 and drop x3.

Step 8: Third Iteration

 

TABLE 15.9

Since all zj − cj ≥ 0 and all xBi ≥ 0 the current solution is optimum. The optimum solution is x1 = 13/17, x2 = 18/17

with,

15.7 SEARCH PROCEDURE FOR UNCONSTRAINED OPTIMISATION

15.7.1 One-variable Unconstrained Optimisation

Suppose the objective function has only one variable x(n = 1) and there is no constraint. The differentiable function f(x) is to be maximised and is concave. The necessary and sufficient condition for a particular solution x = x* to be optimal, that is, global maximum is

15.7.2 One-dimensional Search Procedure

The procedure generates a sequence of trial solutions that lead towards the optimal solution. To start the search, the lower and upper bounds on the value of the variable are estimated and the first trial solution is determined. Depending upon whether f′(x) is positive or negative at the trial solution, the direction of incrementing the variable in determined. If f′(x) is positive, then x* must be larger than the current value and it becomes the lower bound for the next trial solution. If f′(x) is negative, the optimal value x* must be less than the present x, and it becomes the upper bound for the next trial solution. At each iteration, the distance between the upper bound and the lower bound decreases and the trial solution converges towards x*. For efficient convergence of trials, appropriate rules for selecting the trial solution between the two bounds should be applied. Moreover, stopping rule, which determines the error tolerance, must be clearly specified.

Algorithm:

Let x′ = Current trial solution

   x = Current lower bound on x*

    = Current upper bound on x*

   ɛ = Error tolerance for x*

According to Bolzeno search plan or mid-point rule, the mid-point of the current lower and upper bounds is selected as the next trial solution.

Step 1: Determine the lower and upper bounds and initialise the current trial solution. The lower and upper bounds have to be estimated either by making a rough plot of the given function, by simple inspection or by determining the value of x at which the derivative is negative, by hit and trial.

Step 2: Evaluate at x = x′.

If , set x = x′.

If , set = x′.

Step 3: Apply the stopping rule.

It x ≤ 2ɛ, stop; otherwise, determine the next trial solution and perform the new iteration; that is, go to step 2. The accuracy of the result will depend upon the value of ɛ, the error tolerance, and the minimum error will be x* − x′.

Example 1

By using one-dimensional search procedure, maximise f(x) = 20x − 3x2x4.

Solution: Given function f(x) is a one-variable non-linear function.

Now

Since the second derivative is negative everywhere, one-dimensional search procedure can be applied. The rough plot of f(x) is shown in Fig. 15.3.

FIGURE 15.2

Figure 15.3 shows that f(x) is negative for x < 0 or x > 2.5. Hence, set x = 0 and = 2.5.

Let the error of tolerance ɛ be 0.01.

The search starts with x = 0, = 2.5 and x′ = 1.25.

At

Since the value of derivative at x′ = 1.25 is positive, x′ becomes the lower bound for the next trial solution. Hence,

 

x = 1.25, = 2.5   and   x ≤ 2ɛ

Now at 1.875 = −17.624219. Since it is negative, this value of x′ becomes the upper bound for the next trial solution.

The iterations are continued until x becomes less than or equal to 2ɛ. The sequence of solutions obtained in this search is given in Table 15.10.

 

TABLE 15.10

The optional solution is obtained as

 

x* = 1.4160157

Example 2

Using the one-dimensional search procedure, solve the following non-linear problem. Maximise f(x) = 6xx2 by taking the initial upper and lower bounds at = 4.8 and x = 0 and error tolerance ɛ = 0.04.

Solution:

Since the second derivative is non-positive, function f(x) is concave everywhere and hence search can be employed. The starting solution is x = 0 and = 4.8.

The value of at x = 2.4 is 6 − 4.8 = 1.2.

Since is positive, x′ becomes the lower bound for the next trial solution.

Now

Since is negative, x′ becomes the upper bound for the next trial solution.

Derivative at x = 3.0 is neither negative nor positive. Thus, we reach the exact solution at x* = 3.0.

Example 3

Solve the following convex programming problem with lower and upper bounds at x = 0 and = 2 and an error tolerance ɛ = 0.01.

 

Minimise z = x4x2 − 4x

Solution:

This is a convex programming problem of the minimisation type. The one-dimensional search procedure remains the same; only the conditions for selecting the lower and upper bounds change. If the derivative of the function at a solution point is positive, the solution becomes the upper bound for the next trial solution and if the derivative is negative, the solution becomes the lower bound for the next trial solution.

The convex function is f(x) = x4x2 − 4x

For every value of x > 0.45, the second derivative is positive; hence, the function is convex and the search procedure can be applied.

Starting solution is x = 0, = 2, which gives

 

x′ = 1

and

Since the derivative is negative, the present solution x′ = 1 will become the lower bound for the next trial solution. Now,

and

Since the derivative is positive, x′ = 1.5 becomes the upper bound on the next trial solution, that is, = 1.5. The iterations are continued till the difference between the bounds is less than or equal to 2ɛ.

The computations are given in Table 15.11.

 

TABLE 15.11

The solution point x′ = 1.1640625 is well within the tolerance error of 0.01 since x = 0.015625 is less than 2ɛ, that is, less than 0.02.

 

zmin = (1.1640625)4 − (1.1640625)2 − 4(1.1640625)
zmin = −4.175153

15.7.3 Multivariable Unconstrained Optimisation

The multivariable function should either be a concave or convex function in the specified region or a unimodal function. In the case of concave function, the objective is to maximise, whereas in the case of convex function, the objective is to minimise.

Let us consider a multivariable concave function f(X), X = x1, x2, …, xn without any constraints on the feasible values. The function is to be maximised. One method of solving this problem is by setting the respective partial derivatives to be equal to zero and solving the equations analytically.

In the case of a multivariable problem, there are a number of variables and hence a number of directions in which the solution can move. The goal is to reach a point where all the partial derivatives are nearly zero. The value of each variable of this point is nearly optimal.

In the case of a multivariable problem, the objective function f(x) is assumed to be differentiable and hence possess a gradient. This gradient is used to determine whether the variable is to be increased or destroyed.

Let ∇f(x) be the gradient at point x. At any point X = X′, the gradient is the vector of partial derivatives corresponding to various variables.

15.7.4 The Gradient Search Procedure

Step 1: Estimate the trial solution.

Step 2: Evaluate the gradient ∇ f(X′) and set for j = 1, 2, …, n.

Substitute the expressions in f(X) to obtain f(X′ + tf(X′)) as a function of t.

Step 3: By differentiating the above function with respect to t, find the value of t* that maximises f(X′ + tf(X′)) over t ≥ 0.

The value of t* can also be determined by one-dimensional search procedure.

Step 4: Find the next trial solution X′ = X′ + tf(X′).

Step 5: Apply the stopping rule. To do this, evaluate ∇f(X′) at X = X′ and check if for all j = 1, 2, …, n. If it is so, stop the iteration. The current trial solution is the derived near-optional solution.

Example 1

Show three iterations of the solution of the following two-variable problem by the gradient search procedure. Maximise . Take X = (1/2, 1/2) as the starting trial solution. Draw the path of the trial solutions by solving the systems of linear equations by setting ∇f(X) = 0.

Solution: The partial derivatives of function f(X) with respect to x1 and x2 are

The starting solution is , for which

Thus, the gradient .

Now set

Substituting the values in f(X),

Because

or

Now reset the value of trial solution

For the new trial solution, the gradients

and

Now set for j = 1, 2

Substituting these values,

or

2 − 4t = 0 or t* = 1/2

Reset the value of the trial solution.

For this new trial solution, the gradient ∇f(3/4, 3/4) = (0, 5/2).

Now

Substituting these values,

or

The next trial solution is thus

The computations carried out so for are shown in Table 15.12.

The solution moves from to . The solution is gradually moving towards the exact solution (1, 1), which can determined by setting

 

f(X) = 0.

which gives x1 = x2 = 1.

In the trial solution, the increment has gradually decreased. It can be estimated that the next iterations will result in and and so on and converge to (1, 1).

The desired optimal solution will depend upon the tolerance error.

The zigzag path of the trial solution is shown in Fig. 15.4.

FIGURE 15.4

15.7.5 Fibonacci Search Technique

This is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. Compared to binary search, Fibonacci search examines locations whose addresses have lower dispersion. Therefore, when the elements being searched have non-uniform access memory storage, that is, the time needed to access a storage location varies depending on the location previously accessed, the Fibonacci search has an advantage over binary search in slightly reducing the average time needed to access a storage location. Fibonacci search has a complexity of O(log x).

Algorithm:

Let k be defined as an element in F, the array of Fibonacci numbers. n = Fm is the array size. If the array is not of Fibonacci numbers, let Fn be the smallest number in F that is greater than n. The array of Fibonacci numbers is defined where

 

Fk−2 = Fk−1 + Fk,

when

k ≥ 0, F1 = 1   and   F0 = 0.

To test whether an item is in the list of ordered numbers, follow these steps.

  1. Set k = m.
  2. If k = 0, stop. There is no match, and the item is not in the array.
  3. Compare the item against element in Fk−1.
  4. If the item matches, stop.
  5. If the item is less than entry Fk−1, discard the elements from positions Fk−1 + 1 to n. Set k = k − 1 and return to step 2.
  6. If the item is greater than entry Fk−1, discard the elements from positions 1 to Fk−1. Renumber the remaining elements from 1 to Fk−2, set k = k − 2, and return to step 2.

Automotive Implementation:

Given a table of records R1, R2, …, RN whose keys are in increasing order k1 < k2 <…< kN, the algorithm searches for a given argument k. Assume N + 1 = Fk + 1.

Step 1: [Initialise] iFk, pFk−1, qFk−2 (throughout the algorithm, p and q will be consecutive Fibonacci numbers).

Step 2: [Compare.] If k < ki, go to step 3, if k > ki go to step 4, and if k = ki the algorithm terminates successfully.

Step 3: [Decrease i.] If q = 0, the algorithm terminates unsuccessfully. Otherwise, set iiq, and set (p, q) ← (q, pq); then return to step 2.

Step 4: [Increase i.] If p = 1, the algorithm terminates unsuccessfully. Otherwise, set ii + p, pp + q, and qpq, and return to step 2.

15.7.6 Golden Section Search

The golden section search is a technique for finding the extremum (minimum or maximum) of a strictly unimodal function by successively removing the range of values inside which the extremum is known to exist. The technique derives its name from the fact that the algorithm maintains the function values for triplets of points whose distances form a golden ratio. The algorithm is the limit of Fibonacci search for a large number of function evaluations.

FIGURE 15.5

Figure 15.5 illustrates a single step in the technique for finding a minimum. The functional values of f(x) are on the vertical axis, and the horizontal axis is the x parameter. The value of f(x) has already been evaluated at the three points x1 x2 and x3. Since f2 is smaller than either f1 or f3, it is clear that a minimum lies inside the interval from x1 to x3 ( f is unimodal).

The next step in the minimisation process is to ‘probe’ the function by evaluating it at a new value of x, namely x4. It is most efficient to choose x4 somewhere inside the largest interval, that is, between x2 and x3. It is clear that if the function yields f4a then the minimum lies between x1 and x4 and the new triplet of points will be x1, x2 and x4. However, if the function yields the value f4b then the minimum lies between x2 and x3. Thus, in either case, we can construct a new narrower search interval that is guaranteed to contain the function’s minimum.

Probe Point Selection

From Fig. 15.5, it is seen that the new search interval will be either between x1 and x4 with a length of a + c or between x2 and x3 with a length b. The golden search requires that these intervals be equal. If they are not, a run of ‘bad luck’ could lead to the wider interval being used many times, thus slowing down the rate of convergence. To ensure that b = a + c, the algorithm should choose x4 = x1 + (x3x2). However, there still remains the question where x2 should be placed in relation to x1 and x3. The golden section search chooses the spacing between these points in such a way that these points have the same proportion of spacing after evaluating f(x4) is proportional to the spacing prior to that evaluation. If f(x1) is f4a and our new triplet of points is x1, x2 and x4, then we want

However, if f(x4) is f4b and our new triplet of points is x2, x4 and x3, then we want

or

where ϕ is the golden ratio

Termination Condition:

|x3x1| < τ |x2| + |x4| where τ is the tolerance parameter and |x| is the absolute value of x.

EXERCISES

Section 15.1

1. A company manufactures two products A and B. It takes 30 minutes to process one unit of product A and 15 minutes for each unit of B and the maximum machine time available is 35 hours per week. Products A and B require 2 kg and 3 kg of raw material per unit, respectively. The available quantity of raw material is considered to be 180 kg per week. The products A and B which have unlimited market potential sell for 200 and 500 per unit, respectively. If the manufacturing for products A and B are 2x2 and 3y2, respectively, find how much of each product should be produced per week, where

 

x = quantity of product A to be produced
y = quantity of product B to be produced

[Answer: Max. Z = (200 − 2x2) + (500 − 2 y2); subject to 0.5x + 0.25y ≤ 35, 2x + 3y ≤ 180 and x ≥ 0, y ≥ 0.]

2. One-potato, two-potato problem: A frozen-foods company processes potatoes into packages of french fries, hash browns and flakes (for mashed potatoes). At the beginning of the manufacturing process, the raw potatoes are sorted by length and quality and then allocated to separate product lines.

The company can purchase potatoes from two sources which differ in their yields of various sizes and quality. Each source yields different fractions of the products french fries, hash browns and flakes. Suppose that it is possible, at different costs, to alter these yields somewhat. Let f1, f2 and f3 be the fractional yield per unit of weight of source 1 potatoes made into three products, Similarly, let g1, g2, g3 be the yields of source 2. Suppose that each fi and gi can vary within ± 10% of the yields shown below.

Let Ci (f1, f2, f3) and C2 (g1, g2, g3) be the expense associated with obtaining these yields. The problem is to determine how many potatoes should the company purchase from each source? Formulate the problem as NLPP.

[Answer: Minimise subject to 6x1 + x2 ≥ 35, x1 ≥ 01 and x2 ≥ 0.]

3. A manufacturing concern operates its two available machines to polish metal products. The two machines are equally efficient, although their maintenance costs are different. The daily maintenance and operation cost of the machines given in rupees as the non-linear function:

 

f(x, y) = 100 − 1.2x − 1.5y + 0.3x2 + 0.4y2

Where, x and y are the number of hours of operation of machine I and machine II, respectively. The past records of the firm indicate that the combined operating hours of two machines should be at lead 35 hours a day in order to perform a satisfactory job. However, the production manager wishes to operate machine I at least 6 hours more than machine II because of the higher repair cost of the latter. Find the optimal hours of operating the two machines and the minimum daily cost. Formulate the problem as a NLPP.

4. The ABC Investment Company’s manager is trying to create a portfolio of two stocks that promise annual returns of 16 and 20%, respectively. Additionally, he estimates that the risk of each investment will vary directly with twice the square of the size of investment. Each lot (100 shares) of the first stock costs 3,000 and exact lot (100 shares) of the second stock cost 2,000. The total amount of cash available for investment is 6,000 Formulate and solve this problem as an NLPP to maximise return and minimise risk.

5. The operations research team of the ABC Company has come up with the mathematical data (daily basis) needed for two products which the firm manufactures. It has also determined that this is a non- linear programming problem having linear constraints and objective function which is the sum of a linear and a quadratic form. The pertinent data, gathered by the OR team, is

 

Maximise Z = 12x+ 21y + 2xy − 2x2 − 2y2
Subject to the constraints
8 − y ≥ 0
10 − xy ≥ 0
x, y ≥ 0

Find the maximum contribution and number of units that can be expected from these two products which are a part of the firm’s total output, where x and y represent the number of units of the two products.

Section 15.2

6. Find the extreme points of the function

7. Find the maximum and minimum of the function

8. Find the maximum and minimum of the function

Section 15.3

9. (a) Examine z = 6x1 x2 for maxima and minima under the requirement 2x1 + x2 = 10.

(b) What happens if the problem becomes that of maxima Z = 6x1x2 − 10x3 under the constraint equation 3x1 + x2 + 3x3 = 10?

10. Verify that the function

has the stationary points (0, 3, 1), (2, 1, 1,), (2, 3, −1), (0, 1, −1) and (1, 2, 0) use the sufficiency condition to check for the extreme points.

Solve the following non-linear programming problems using the method of Lagrangian multipliers:

11. Minimise subject to

x1 + x2 = 3, x1, x2 ≥ 0

[Answer: x1 = 3/31, x2 = 18/31; Minimum z = 54/31.]

12. Minimise

subject to x1 + x2 + x3 = 20, x1, x2, x3 ≥ 0

[Answer: x1 = x2 = 11 and x3 = 4; minimum of z = 281.]

13. Minimise subject to

 

x1 + x2 + 3x3 = 2, 5x1 + 2x2 + x3 = 5, x1, x2, x3 ≥ 0

[Answer: x1 = 0.81, x2 = 0.35, x3 = 0.28; minimum of z = 0.857.]

14. Write the Kuhn-Tucker necessary conditions for the following problems:

  1. Max.

    subject to

  2. Min.

    subject to

15. Use the Kuhn-Tucker conditions to solve the following non-linear programming problems:

  1. Max.

    subject to

    2x1 + 5x2 ≤ 98
    x1, x2 ≥ 0

    [Answer: x1 = 44, x2 = 2; max Z = 4,900.]

  2. Max.

    subject to

    2x1 + 3x2 ≤ 6

    2x1 + x2 ≤ 4,     x1, x2 ≥ 0

    [Answer: x1 = 2/3, x2 = 14/9; max. Z = 22/9.]

  3. Min. z = −log x1 − log x2

    subject to

    x1 + x2 ≤ 2
    x1 ≥ 0

    [Answer: x1 = 1, x2 = 1; min, z = 0]

  4. Max.

    subject to


    x1 ≤ 0
    x1, x2 ≥ 0

    [Answer: x1 = 2, x2 = ; max z = 42.]

  5. Maximise subject to

    2x1 + 3x2 ≤ 6, 2x1 + x2 ≤ 4   and   x1, x2 ≥ 0

    [Answer: x1 = 2/3, x2 = 14/9, maximum of z = 22/9.]

  6. Max. z = 3x1 + x2 +subject to

    [Answer: x = 1.43, x2 = 0.48 maximum of z = 0.77.]

  7. Minimise f(x, x2) = (x1 − 1)2 + (x2 − 5)2

    subject to

    [Answer: x = 1, x2 = 5; minimum of f(x1, x2 = 0.]

    Solve the following non-linear programming problem graphically:

16. Maximise subject to

 

x1 + x2 ≤ 12, x1x2 ≥ 4   and    x1, x2 ≥ 0

[Answer: x1 = 6, x2 = 2; maximumof z = 24.]

17. Maximise z = −(2x1 − 5)2 − (2x2 − 1)2 subject to

 

x1 + 2x2 ≤ 1, x1 ≥ 0   and   x2 ≥ 0

[Answer: x1 = 0, x2 =0..5; maximum of z = −25.]

18. Maximise z = x1, subject to

 

(1 − x1)3x2 ≥ 0, x1, x2 ≥ 0

Also show that the Kuhn-Tucker necessary conditions for the maxima do not hold. What do you conclude?

[Answer: x1 = 1, x2 = 0; maximum of z = 1. Constraint qualification is not satisfied.]

19. Maximise

subject to

20. Minimise subject to

 

0 ≤ x1 ≥ 2, 0 ≤ x2 ≥ 1

[Answer: x1 = 0, x2 = 1; min. z = 2.]

Section 15.4

21. Apply Wolfe’s method to solve the quadratic programming problem

Maximise

subject to

2x1 + 3x2 ≤ 6
2x1 + x2 ≤ 4
x1, x2 ≥ 0

[Answer: x1 = 2/3, x2 = 14/9 with max z = 22/9.]

22. Use Wolfe’s method to solve the following problems:

  1. Minimise

    subject to

    x1 + x2 + 3x3 = 2
    5x1 + 2x2 + x3 = 5
    x1, x2, x3 ≥ 0

    [Answer: x1 = 0.81, x2 = 0.35, x3 = 0.35; min. z = 0.857.]

  2. Min.

    subject to

    x1 + x2x3 ≤ 0
    4x1 + 2x2 − 7/2 ≤ 0
    x1, x2, x3 ≥ 0

    [Answer: x1 = x2 = x3 = 1/3; min. z = −15/18.]

  3. Max.

    subject to

    3x1 + 2x2 ≤ 6
    x1, x2 ≥ 0

    [Answer: x1 = 4/13, x2 = 33/13; max z = 267/13.]

  4. Maximise

    subject to x1 + x2 ≤ 1, 2x1 + 3x2 ≤4, x1, x2 ≥ 0

    [Answer: x1 = 1, x2 = 0; maximum z = 4.]

  5. Maximise

    subject to

    x1 + 48x2 ≤ 8
    x1 + x2 ≤ 4
    x1, x2 ≥ 0

    [Answer: x1 = 0, x2 = 1; maximum z = 3.]