Engineering Optimization: Theory and Practice, Fourth Edition

230 Linear Programming II: Additional Topics and Extensions

reduces to a LP problem. The solution of the quadratic programming problem stated

in Eqs. (4.72) to (4.74) can be obtained by using the Lagrange multiplier technique.

By introducing the slack variablessi^2 , i = 1 , 2 ,... , m, in Eqs. (4.73) and the surplus

variablestj^2 , j = 1 , 2 ,... , n, in Eqs. (4.74), the quadratic programming problem can

be written as

Minimizef (X)=CTX+^12 XTDX (4.72)

subject to the equality constraints

ATiX+si^2 =bi, i= 1 , 2 ,... , m (4.75)

−xj+tj^2 = 0 , j= 1 , 2 ,... , n (4.76)

where

Ai=











ai 1

ai 2

..

.

ain











The Lagrange function can be written as

L(X,S,T,λ,θ)=CTX+^12 XTDX+

∑m

i= 1

λi(ATiX+si^2 −bi)

+

∑n

j= 1

θj(−xj+tj^2 ) (4.77)

The necessary conditions for the stationariness ofLgive

∂L

∂xj

=cj+

∑n

i= 1

dijxi+

∑m

i= 1

λiaij−θj= 0 , j= 1 , 2 ,... , n (4.78)

∂L

∂si

= 2 λisi= 0 , i= 1 , 2 ,... , m (4.79)

∂L

∂tj

= 2 θjtj= 0 , j= 1 , 2 ,... , n (4.80)

∂L

∂λi

=ATiX+si^2 −bi= 0 , i= 1 , 2 ,... , m (4.81)

∂L

∂θj

= −xj+tj^2 = 0 , j= 1 , 2 ,... , n (4.82)

By defining a set of new variablesYias

Yi=si^2 ≥ 0 , i= 1 , 2 ,... , m (4.83)

Equations (4.81) can be written as

ATiX−bi= −si^2 = −Yi, i= 1 , 2 ,... , m (4.84)