Non-linear Programming
Kuhn-tucker condition:
If the constraints of a Non-linear Programming Problem are of inequality form, we can solve them by using Lagrange multipliers, which are slightly modified.
Let us consider a problem.
Maximize Z = f (x1, x2, x3… xn), subject to the constraints
G (x1, x2, x3…xn) ≤ cand x1, x2, ….xn ≥ 0 and c is a constant.
The constraints can be modified to the form h(x1, x2 ….xn) ≤ 0 by introducing a function h (x1, x2 ….xn = g (x1, x2….xn) – c
Maximize Z = f (x)
Subject to h (x) ≤ 0 and x ≥ 0 where, x∈Rn.
This problem can be slightly modified by introducing a new variable S. Define Sr = – h(x) or h (x) S2 = 0, S can be interpreted as slack variable. It appears as its square in the constraint equation so as to ensure its being non-negative.
The problem can be restated as Optimize Z = f (x). x ∈Rn
Subject to constraints h (x) S2 = 0 and x ≥ 0
this is the problem of constrained optimization in (n 1) variables with a single equation constraint and can be solved by Lagrange multiplier method.
To determine the stationary points, consider the Lagrange function as L (x, S, λ ) = f (x) – λ [h (x) S2], where λ is Lagrange multiplier. Necessary conditions for stationary points are:
whenever h (x), 0 from equation 4, we get λ = 0, whenever λ > 0 h (x) = 0. λ is unrestricted in sign whenever h (x) ≤ 0 and the problem reduces to the problem of equation constraint. The necessary conditions for the point x to be a point of maximum are stated as:
f j– λ hj = 0 (j = 1, 2, 3, …n)
λ h = 0 maximum f h ≤ 0 subject to the constraint λ ≥ 0 and h ≤ 0.
(a) General case of the constrained optimization of nonlinear function in n variables under m (< n) inequality constraint:
Consider NLPP Maximize Z = f (x) x ∈Rn Subject to constraint gi (x) ≤ ci i = 1, 2, ….m and x ≥ 0Introducing the function hi(x) = gi (x) – ci for all i = 1, 2, ….m the inequality constraint can bewritten ashi (x) ≤ 0 for i = 1, 2, …m.
By introducing the slack variables Stt = 1, 2, …m defined by hi (x) 2 Si = 0, i = 1, 2, …m.
The inequality constraints are converted to equality ones. The stationary value of x can thus be obtained by Lagrangian multiplier method. The Lagrangian function is
L (x, S, λ ) = f (x) – Σ λ i [hi (x) c Si ]where λ = ( λ1, λ2 …. λm ) Lagrangian multipliers. Necessary conditions for f (x) to be the
