Module 5

Quadratic Programming

Necessary and Sufficient conditions of QP

Wolfe’s Modified Simplex Method

Example
Quadratic Programming
What is Quadratic Programming (QP)?
Quadratic Programming (QP) is a type of optimization problem where
▶ The objective function is quadratic (contains squared terms like
x12 , x1 x2 )
▶ The constraints are linear (like a1 x1 + a2 x2 ≤ b )

Mathematical model of QP

1
Maximize (or) Minimize f (x) = xT Dx + cT x
2
Subject to Ax ≤ b
x≥0

Dr.R. Sakthivel, VIT Chennai 3 / 31

Quadratic Programming

where:
▶ x → vector of decision variables x = (x1 , x2 , . . . , xn )T
▶ D → [djk ] is an n × n symmetric matrix, i.e [djk = dkj ] (contains
quadratic terms)
▶ c → linear coefficient vector c = (c1 , c2 , . . . , cn )
▶ A → constraint matrix
▶ b → constraint limits b = (b1 , b2 , . . . , bm )T

Dr.R. Sakthivel, VIT Chennai 4 / 31

Necessary and Sufficient conditions of QP

Necessary and Sufficient conditions of Quadratic Programming

Step 1 : Introducing slack variables si and rj to constraints, the QP problem
becomes:
1
Maximize f (x) = cT x − xT Dx
2
Subject to Ax + si = b i = 1, 2, 3, · · · , m
−x + rj = 0 j = 1, 2, 3, · · · , n
Step 2 : Forming the Lagrange function as follows:
m
X n
X
L(x, s, r, λ, µ) = f (x) − λi (Ax + si − b) − µj (−xj + r)
i=1 j=1

Dr.R. Sakthivel, VIT Chennai 5 / 31

Necessary and Sufficient conditions of QP

Step 3 : Differentiate L(x, s, r, λ, µ) partially with respect to the components

of x, s, r, λ and µ. Then equate these derivatives with zero in order to get the
required Kuhn-Tucker necessary conditions. That is,

∂L
(i) = 0 =⇒ c − Dx − AT λ + µ = 0
∂x
∂L
(ii) = 0 =⇒ λi si = 0, i = 1, 2, . . . , m
∂s
∂L
(iii) = 0 =⇒ µj rj = 0, j = 1, 2, . . . , n
∂r
∂L
(iv) = 0 =⇒ Ax + s − b = 0
∂λ
∂L
(v) = 0 =⇒ −x + r = 0
∂µ
(vi) λi ,µj , xj , si , rj ≥0

Dr.R. Sakthivel, VIT Chennai 6 / 31

Necessary and Sufficient conditions of QP

▶ These conditions, except (ii) and (iii), are linear constraints involving
2(n + m) variables.
▶ The condition µj rj = λi si = 0 implies that both rj and µj , as well as si
and λi , cannot be basic variables at the same time in a nondegenerate
basic feasible solution.
▶ The conditions µj rj = 0 and λi si = 0 are also called complementary
slackness conditions.

Dr.R. Sakthivel, VIT Chennai 7 / 31

Wolfe’s Modified Simplex Method

Algorithm
Step 1 : Introduce artificial variables Aj ( j = 1, 2, 3, · · · , n ) in the Kuhn-
Tucker condition (in step - 3 (i)). Then we have

c − Dx − AT λ + µ + Aj = 0

For a starting basic feasible solution we shall have xj = 0, µj = 0, Aj = −cj

and s2j = bi . However, this solution would be desirable if and only if Aj = 0
for all j.
Step 2 : Apply Phase I of the simplex method to check the feasibility of the
constraints Ax ≤ b.
If there is no feasible solution, then terminate the solution procedure, otherwise
get an initial basic feasible solution for Phase II.
To obtain the desired feasible solution solve the following problem:

Dr.R. Sakthivel, VIT Chennai 8 / 31

Wolfe’s Modified Simplex Method

Pn Pn
Maximize Z = j=1 (−1)Aj =⇒ Minimize Z = j=1 Aj

subject to the constraints

Dx + AT λ − µ + Aj = c
Ax + si = b
and λi , x, µ, si , Aj ≥ 0 for all i and j
µj rj = λi si = 0 {Complementary slackness conditions}

Thus, while deciding for a variable to enter into the basis at each iteration, the
complementary slackness conditions must be satisfied.
This problem has 2(m + n) variables and (m + n) linear constraints, together
with (m + n) complementary slackness conditions.

Dr.R. Sakthivel, VIT Chennai 9 / 31

Wolfe’s Modified Simplex Method

Step 3: Apply Phase II of the simplex method to get an optimal solution to

the problem given in Step 2. The solution, so obtained, will also be an optimal
solution of the quadratic programming problem.

Dr.R. Sakthivel, VIT Chennai 10 / 31

Example

Use Wolfe’s method to solve the quadratic programming problem:

Max Z = 4x1 + 6x2 − 2x12 − 2x1 x2 − 2x22

subject to the constraints

x1 + 2x2 ≤ 2 and
x1 , x2 ≥ 0
Solution
Consider non-negativity conditions x1 , x2 ≥ 0.
Convert this inequality in to xj ≤ 0

−x1 ≤ 0

−x2 ≤ 0

Dr.R. Sakthivel, VIT Chennai 11 / 31

Example

Add slack variables to all inequality constraints in order to express them as

equations.
The standard form of QP problem becomes:

Max Z = 4x1 + 6x2 − 2x12 − 2x1 x2 − 2x22

subject to the constraints

x1 + 2x2 + s1 = 2
−x1 + r1 = 0
−x2 + r2 = 0 and
x1 , x2 , s1 , r1 , r2 ≥ 0

Dr.R. Sakthivel, VIT Chennai 12 / 31

Example

To obtain the necessary conditions, we construct the Lagrange function as fol-

lows:

L(x1 , x2 , s1 , λ1 , µ1 , µ2 , r1 , r2 ) =(4x1 + 6x2 − 2x12 − 2x1 x2 − 2x22 )

− λ1 (x1 + 2x2 + s1 − 2)
− µ1 (−x1 + r1 ) − µ1 (−x2 + r2 )

Dr.R. Sakthivel, VIT Chennai 13 / 31

Example

The necessary and sufficient conditions for the maximum of L and hence of Z
are:
∂L ∂L
= 4 − 4x1 − 2x2 − λ1 + µ1 = 0, = −x2 + r2 = 0
∂x1 ∂µ2
∂L
∂L = λ1 s1 = 0
= 6 − 2x1 − 4x2 − 2λ1 + µ2 = 0 ∂s1
∂x2
∂L
∂L = µ1 r1 = 0,
= x1 + 2x2 + s1 − 2 = 0, ∂r1
∂λ1
∂L
∂L = µ2 r2 = 0
= −x1 + r1 = 0, ∂r2
∂µ1

Dr.R. Sakthivel, VIT Chennai 14 / 31

Example

After simplifying these conditions, we get:

4x1 + 2x2 + λ1 − µ1 = 4
2x1 + 4x2 + 2λ1 − µ2 = 6
x1 + 2x2 + s21 = 2
λ1 s1 = µ1 x1 = µ2 x2 = 0 =⇒ (Complementary conditions)
and x1 , x2 , λ1 , µ1 , µ2 , s1 ≥ 0

Introducing artificial variables A1 and A2 in the first two constraints respec-

tively. Then the modified LP problem becomes:

Dr.R. Sakthivel, VIT Chennai 15 / 31

Example
Max Z = −A1 − A2 =⇒ Minimize Z ∗ = A1 + A2
subject to the constraints
4x1 + 2x2 + λ1 − µ1 + A1 = 4
2x1 + 4x2 + 2λ1 − µ2 + A2 = 6
x1 + 2x2 + s1 = 2 and
x1 , x2 , λ1 , µ1 , µ2 , A1 , A2 , s1 ≥ 0
The non-basic variables are x1 and x2
Hence the non-basic solutions are
x1 , x2 = 0
The basic variables are A1 , A2 and s1
∴ Initial Basic Feasible Solution (IBFS) are
A1 = 4, A2 = 6 and s1 = 2
Dr.R. Sakthivel, VIT Chennai 16 / 31
Example

Iteration - 1
Cj
0 0 0 0 0 0 1 1
XB
B CB XB x1 x2 λ1 µ1 µ2 s1 A1 A2
xi
4
A1 1 4 (4) 2 1 −1 0 0 1 0 4 = 1→
6
A2 1 6 2 4 2 0 −1 0 0 1 2 = 3
2
s1 0 2 1 2 0 0 0 1 0 0 1 =2
Z = 10
Zj 6 6 3 −1 −1 0 1 1
Zj − Cj 6 ↑ 6 3 −1 −1 0 0 0
Since some Zj − Cj > 0, the current basic feasible solution is not optimal.
Positive maximum Zj − Cj is 6 and its column index is 1. So, the entering
variable is x1 .
Dr.R. Sakthivel, VIT Chennai 17 / 31
Example

Minimum ratio is 1 and its row index is 1. So, the leaving basic variable is A1
∴ The pivot element is 4

Entering = x1 , Departing = A1 , Pivot Element = 4

R1 (New) = R1 (Old) ÷ 4

R1 (Old) = [ 4 4 2 1 − 1 0 0 0 ]
 
1 1 1
R1 (New) = 1 1 − 0 0 0
2 4 4

Dr.R. Sakthivel, VIT Chennai 18 / 31

Example

R2 (New) = R2 (Old) − 2R1 (New)

R2 (Old) = [ 6 2 4 2 0 − 1 0 1 ]
 
1 1
2R1 (New) = 2 2 1 − 0 0 0
2 2
 
3 1
R2 (New) = 4 0 3 −1 0 1
2 2

Dr.R. Sakthivel, VIT Chennai 19 / 31

Example

R3 (New) = R3 (Old) − R1 (New)

R3 (Old) = [ 2 1 2 0 0 0 1 0 ]
 
3 1 1
R3 (New) = 1 0 − 0 1 0
2 4 4

Dr.R. Sakthivel, VIT Chennai 20 / 31

Example

Iteration - 2
Cj
0 0 0 0 0 0 1
XB
B CB XB x1 x2 λ1 µ1 µ2 s1 A2
xi
x1 0 1 1 1/2 1/4 −1/4 0 0 0 2
A2 1 4 0 3 3/2 1/2 −1 0 1 1.333
s1 0 1 0 (3/2) −1/4 1/4 0 1 0 0.66 →
Z=4
Zj 0 3 3/2 1/2 −1 0 1
Zj − Cj 0 3↑ 3/2 1/2 −1 0 0
Since some Zj − Cj > 0, the current basic feasible solution is not optimal.
Positive maximum Zj − Cj is 3 and its column index is 2. So, the entering
variable is x2 .
Dr.R. Sakthivel, VIT Chennai 21 / 31
Example

Minimum ratio is 3 and its row index is 3. So, the leaving basic variable is s1
3
∴ The pivot element is 2

Entering = x2 , Departing = s1 , Pivot Element = 3/2

3
R3 (New) = R3 (Old) ÷
2
3
Since dividing by 2is multiplying by 23 ,
 
3 1 1
R3 (Old) = 1 0 − 0 1 0
2 4 4
 
2 1 1 2
R3 (New) = 0 1 − 0 0
3 6 6 3

Dr.R. Sakthivel, VIT Chennai 22 / 31

Example

1
R1 (New) = R1 (Old) − R3 (New)
2
 
1 1 1 1 1 1
R3 (New) = 0 − 0 0
2 3 2 12 12 3
 
2 1 1 1
R1 (New) = 1 0 − 0 − 0
3 3 3 3

Dr.R. Sakthivel, VIT Chennai 23 / 31

Example

R2 (New) = R2 (Old) − 3R3 (New)

 
1 1
3R3 (New) = 2 0 3 − 0 2 0
2 2

R2 (New) = [2 0 0 2 0 − 1 − 2 1]

Dr.R. Sakthivel, VIT Chennai 24 / 31

Example

Iteration - 3
Cj
0 0 0 0 0 0 1
XB
B CB XB x1 x2 λ1 µ1 µ2 s1 A2
xi
x1 0 2/3 1 0 1/3 −1/3 0 −1/3 0 2
A2 1 2 0 0 (2) 0 −1 −2 1 1→
x2 0 2/3 0 1 −1/6 1/6 0 2/3 0 −
Z=2
Zj 0 0 2 0 −1 −2 1
Zj − Cj 0 0 2↑ 0 −1 −2 0
Since some Zj − Cj > 0, the current basic feasible solution is not optimal.
Positive maximum Zj − Cj is 2 and its column index is 3. So, the entering
variable is λ1 .
Dr.R. Sakthivel, VIT Chennai 25 / 31
Example

Minimum ratio is 2 and its row index is 2. So, the leaving basic variable is A2
∴ The pivot element is 2

Entering = λ1 , Departing = A2 , Pivot Element = 2

R2 (New) = R2 (Old) ÷ 2

R2 (Old) = [ 2 0 0 2 0 − 1 − 2 ]

1
R2 (New) = [ 1 0 0 1 0 − 2 − 1]

Dr.R. Sakthivel, VIT Chennai 26 / 31

Example

R1 (New) = R1 (Old) − 13 R2 (New)

1
3 R2 (New) = [ 13 0 0 1
3 0 − 1
6 − 13 ]

R1 (New) = [ 13 1 0 0 − 1
3
1
6 0]

Dr.R. Sakthivel, VIT Chennai 27 / 31

Example

R3 (New) = R3 (Old) + 16 R2 (New)

1
6 R2 (New) = [ 16 0 0 1
6 0 − 1
12 − 16 ]

R3 (New) = [ 65 0 1 0 1
6 − 1
12
1
2 ]

Dr.R. Sakthivel, VIT Chennai 28 / 31

Example

Iteration - 4

Cj
0 0 0 0 0 0
XB
B CB XB x1 x2 λ1 µ1 µ2 s1
xi
x1 0 1/3 1 0 0 −1/3 1/6 0
λ1 0 1 0 0 1 0 −1/2 −1
x2 0 5/6 0 1 0 1/6 −1/12 1/2
Z=0
Zj 0 0 0 0 0 0
Zj − Cj 0 0 0 0 0 0
Since all Zj − Cj ≤ 0, the current basic feasible solution is optimal.

Dr.R. Sakthivel, VIT Chennai 29 / 31

Example

From iteration 4 all Zj − Cj = 0 an optimal solution for Phase I is reached.

Hence, the optimal solution is at
1 5
x1 = , x2 = , λ1 = 1, µ1 = µ2 = 0, s1 = 0
3 6
This solution also satisfies the complementary conditions:

λ1 s1 = 0, µ1 x1 = µ2 x2 = 0

Further, as Z = 0, this implies that the current solution is also feasible.

Dr.R. Sakthivel, VIT Chennai 30 / 31

Example

Thus, the maximum value of the given quadratic programming problem is:

Max Z = 4x1 + 6x2 − 2x12 − 2x1 x2 − 2x22

     2     2
1 5 1 1 5 5
=4 +6 −2 −2 −2
3 6 3 3 6 6
25 1 5
Max Z = . at x1 = , x2 = .
6 3 6

Dr.R. Sakthivel, VIT Chennai 31 / 31