Quadratic Programming

Download as ppt, pdf, or txt
Download as ppt, pdf, or txt
You are on page 1of 38

QUADRATIC

PROGRAMMING

Quadratic Programming
A quadratic programming problem is a non-linear
programming problem of the form

Maximize
Subject to

z c X X DX
T

A X b, X 0

Here

x1

2
X . , b

xn

a11 a12
a
a
21
22

A .

.
am1 am 2

.
.

b1
b2

. , c c1 c2 . . . cn

.
bm

. a1n
. a2 n

. amn

d11 d12
d d
21 22
D .

.
d n1 d n 2

.
.

. d1n
. d 2 n

. d nn

We also assume that the nn matrix D is


symmetric and negative-definite.
This means that the objective function is
strictly concave.
Since the constraints are linear, the feasible
region is a convex set.

In scalar notation, the quadratic programming


problem reads:
Maximize z

c x d
j 1

Subject to

j j

j 1

x 2

2
jj j

d x x

1i j n

ij i j

a11 x1 a12 x2 . . . a1n xn b1


a21 x1 a22 x2 . . . a2 n xn b2
.
.
am1 x1 am 2 x2 . . . amn xn bm
x1 , x2 ,. . . , xn 0

The solution to this problem is based on the


KKT conditions. Since the objective function is
strictly concave and the solution space is
convex, the KKT conditions are also sufficient
for optimum.
Since there are m+n constraints, we have m+n
Lagrange multipliers; the first m of them are
denoted by 1, 2, , m; and the last n of them
are denoted by 1, 2, , n.

The KKT (necessary) conditions are:

1. 1 , 2 , . . . , m , 1 , 2 , . . . , n 0
n

i 1

i 1

2. c j 2 d ij xi i aij j 0
j 1, 2, . . . , n
(continued )

3. i aij x j b
0, i 1, 2,. . ., m
i
j 1

j x j 0, j 1, 2,. . ., n
n

4.

a
j 1

ij

x j bi , i 1, 2,. . ., m

x j 0, j 1, 2,. . ., n

Denoting the (non-ve) slack variable for the


n
ith constraint

a
j 1

ij

x j bi

by Si, the 3rd condition(s) can be written in


an equivalent form as:

3. i S i 0,

i 1, 2, . . . , m

j x j 0 , j 1, 2, . . . , n
Referred to as " Restricted Basis " conditions.

Also condition(s) (2) can be rewritten as:


n

i 1

i 1

2. 2 dij xi i aij j c j
j 1, 2,. . ., n
And condition(s) (4) can be rewritten as:
n

4.

a x
j 1

ij

Si bi , i 1, 2,. . ., m

x j 0, j 1, 2,. . ., n

Thus we find the optimal solution

*
1

*
1

x , x , . . ., x

*
n

is a solution of the system of m+n linear


equations in the n+m+n unknowns x j , i , j
n

i 1

i 1

2 d ij xi i aij j c j , j 1, 2, . . . , n
n

a
j 1

ij

x j S i bi , i 1, 2, . . . , m

along with the " Restricted Basis " conditions


i S i 0, i 1, 2, . . . , m,
j x j 0 , j 1, 2, . . . , n

Since we are interested only in a "


feasible solution " of the above system
of linear equations, we use Phase-I
method to find such a feasible solution.
By the sufficiency of the KKT
conditions, it will be automatically the
optimum solution of the given
quadratic programming problem.

Problem
Maximize
subject to

z 8 x1 x 2 x2 x3
2
1

x1 3 x2 2 x3 12
x1 , x2 , x3 0

Denoting the Lagrange multipliers by


1,1, 2, and 3, the Lagrangean is:

L 8 x1 x 2 x2 x3
2
1

1 ( x1 3 x2 2 x3 12)
1 ( x1 ) 2 ( x2 ) 3 ( x3 )
i.e. L 8 x1 x 2 x2 x3
2
1

1 ( x1 3 x2 2 x3 12)
1 x1 2 x2 3 x3

Hence the KKT conditions are:

1. 1 , 1 , 2 , 3 0
L
2.
8 2 x1 1 1 0
x1
L
2
x2

31 2 0

L
1
x3

21

i.e. 2 x1 1 1

3 0
8

31 2 2
21

3 1

(Continued)

3. x1 3 x2 2 x3 S1 12,

1S1 0
1 x1 2 x2 3 x3 0
All variables 0.
Solving this by " Modified Simplex Algorithm ",
the optimal solution is:

11
25
x1 , x2 , x3 0
3
9

193
and the optimal z =
9

Basic r

x1 x2 x3 1 1 2 3 R1 R2 R3 S1 Sol

r 1
R1 0

2
0
2

0
0
0

0
0
0

6 -1
0 0
1 -1

-1 -1
0 0
0 0

0 0 0
-1 -1 -1
1 0 0

0
0
0

11
0
8

R2 0

-1

0 1

R3 0 0
S1 0 1

0
3

0
2

2
0

0
0

0 -1
0 0

0 0
0 0

1
0

0
1

1
12

x2

Now if 1 enters, R3 will only leave.


Since 1 S1 = 0 and S1 is in the basis, 1 cannot enter.
So we allow x1 to enter the basis and of course by
minimum ratio test R1 leaves the basis.

Basic r

x1 x2 x3 1 1 2 3 R1 R2 R3 S1 Sol

r 1

x1 0

R2 0

R3 0 0
S1 0 0

5 0

-1 0

0 1/2 -1/2 0

0 1/2 0

0
3

0 2 0 0 -1 0 0
2 -1/2 1/2 0 0 -1/2 0

1
0

0
1

1
8

-1 -1

-1

Since 1 S1 = 0 and S1 is in the basis, 1 cannot enter.


So we allow x2 to enter the basis and of course by
minimum ratio test S1 leaves the basis.

Basic r

x1 x2 x3 1 1 2 3 R1 R2 R3 S1 Sol

r 1

5 0

x1 0

R2 0

-1 0

0 1/2 -1/2 0

0 1/2 0

0 1

R3 0
x2 0

0
0

0 0 2 0
1 2/3 -1/6 1/6

0 -1 0 0
0 0 -1/6 0

1
0

0
1
1/3 8/3

-1 -1

-1

As S1 is not in the basis, now 1 enters the basis .


And by minimum ratio test R3 leaves the basis.

Basic r

x1 x2 x3 1 1 2 3 R1 R2 R3 S1 Sol

r 1

0 0 0 0

x1 0

0 0 0 -1/2 0 1/4 1/2 0 -1/4 0 15/4

R2 0

0 0 0

1 0
x2

0
0 0

0 0 1 0
1 2/3 0 1/6

-1 3/2

-1 3/2

-1 0

0 1

-5/2 0

1/2

-3/2 0 1/2

0 -1/2 0 0 1/2 0 1/2


0 -1/12 -1/6 0 1/12 1/3 11/4

Now 3 enters the basis .


And by minimum ratio test R2 leaves the basis.

Basic r

x1 x2 x3 1 1 2 3 R1 R2 R3 S1 Sol

r 1

0 0 0 0

x1 0

0 0 0 -1/2 1/6

3 0
1 0
x2

0
0
0 0

-1 -1 -1

1/2 -1/6 0

0 11/3

0 0 0 0 -2/3 1
0 2/3 -1 0 1/3
0 0 1 0 -1/3 0
0 1/3 0 0 2/3
1 2/3 0 1/6 -1/18 0 -1/6 1/18 0 1/3 25/9

This is the end of Phase I.

Thus the optimal solution is: Thus the optimal


value z is: 193
11
25

x1

, x2

, x3 0

Problem

Maximize
Subject to

z 8 x1 4 x2 x x
2
1

x1 x2 2
x1 , x2 0

2
2

Denoting the Lagrange multipliers by 1, 1,


and 2, the KKT conditions are:

1. 1 , 1 , 2 0

2. 8 2 x1 1 1 0
4 2 x2 1 2 0
i.e. 2 x1 1 1
2 x2 1

2 4

3. x1 x2 S1 2, 1S1 1 x1 2 x2 0
All variables 0.

Introducing artificial variables R1, R2, we thus


have to
Minimize r R1 R2
subject to the constraints

1 1

2 x1

2 x2 1
x1 x2

R1

R2

S1 2

1S1 1 x1 2 x2 0 All variables 0.


(We solve by " Modified Simplex " Algorithm)

Basic r

x1 x2

1 1 2

r
R1
R2
S1

1
0
0
0

2
0
2
0
1

2
0
0
2
1

2
0
1
1
0

-1
0
-1
0
0

r
R1
R2
x1

1
0
0
0

0
0
0
1

0
-2
2
1

2
1
1
0

1
0
0
0

0
0
0
1

4
-2
4
1

0
1
0
0

1
R2
x

R1

R2

S1

Sol

-1
0
0
-1
0

0
-1
1
0
0

0
-1
0
1
0

0
0
0
0
1

12
0
8
4
2

-1
-1
0
0

-1
0
-1
0

0
1
0
0

0
0
1
0

-2
-2
0
1

8
4
4
2

1
-1
1
0

-1
0
-1
0

-2
1
-1
0

0
0
1
0

2
-2
2
1

0
4
0
2

Thus we have got the feasible solution


x1 = 2, x2 = 0, 1 = 4, 1 = 0, 2 = 0
And the optimal value is: z = 12

x2

Level curves of z= f(x1, x2)


z=20
z=19

x1+x2=2

z=16
z=14
z=12
z=8
x1
(2,0)

Feasible region

Problem 1 Problem Set 21.2B


Pages 751-752
Maximize

z 6 x1 3x2 2 x 4 x1x2 3x
2
1

subject to

x1 x2 1
2 x1 3 x2 4
x1 , x2 0

2
2

Denoting the Lagrange multipliers by 1, 2,


1, and 2, the KKT conditions are:

1. 1 , 2 , 1 , 2 0
2. 6 4 x1 4 x2 1 22 1 0
3 4 x1 6 x2 1 32 2 0
i.e. 4 x1 4 x2 1 22 1 6
4 x1 6 x2 1 32 2 3
(Continued)

3. x1 x2 S1
2 x1 3 x2

1
S2 4

1S1 2 S 2 0
1 x1 2 x2 0
All variables 0.
Solving this by " Modified Simplex Algorithm ",
the optimal solution is:
x1 = 1, x2 = 0 and the optimal z = 4.

Basic r

x1 x2 1 2 1 2

r 1
R1 0
R2 0

8
0
4
4

S1 0 1

R1

R2 S1

S2 Sol

10
0
4
6

2
0
1
1

5 -1
0 0
2 -1
3 0

-1
0
0
-1

0
-1
1
0

0
-1
0
1

0
0
0
0

0
0
0
0

9
0
6
3

S2 0 2 3
r 1 4/3 0

0 0 0 0
1/3 0 -1 2/3

0
0

0
-5/3

0
0

1
0

4
4

R1 0 4/3 0
x2 0 2/3 1

1/3 0 -1 2/3
1/6 1/2 0 -1/6

1
0

-2/3
1/6

0
0

0
0

4
1/2

-1/6

1/2

-1/2

5/2

S1 0 1/3

0 -1/6 1/2 0

1/6

S2 0 0

0 -1/2 -3/2 0 1/2

Basic r

x1 x2 1 2 1 2

R1

R2 S1

S2 Sol

r 1

-2

0 -1 -1

-2

R1 0

3/2 1/4 3/4 0 -1/4

1/4

3/4

S1 0 0 -1/2 -1/43/4 0 1/4

0 -1/4

1/4

S2 0 0

0 -1/2 -3/2 0 1/2

-1/2

5/2

r 1 0

2 -1

-1

-4

R1 0 0

-1 0

-4

x1 0 1

2 0 0

-2
1

-1 3 0
0 0 0

1
0

0
0

-1
0

4
-2

0
1

1
2

x1 0 1

S2 0 0

2 -1

Basic r

x1 x2 1 2 1 2

R1

R2 S1

S2 Sol

r 1

-1

-1

1 0

2 -1

-4

x1 0

2 0 0

-2

0 1 -1

-1

S2 0 0

-2

Thus the optimum solution is:


x1 = 1, x2 = 0, 1 = 2, 2 = 0, 1 = 0, 2 = 3
And the optimal value is: z = 4

Problem 13.7-3 Hillier & Lieberman


Maximize

z 20 x1 50 x2 20 x 18 x1 x2 5 x
2
1

subject to

2
2

x1 x2 6
x1 4 x2 18
x1 , x2 0

Max z
= 224

Using Excel solver, the opt solution is: x1=2, x2=4

If the problem is a minimization problem,


say, Minimize z
we convert it into a maximization problem,
Maximize - z.

Problem 2 Problem Set 21.2B Page 752


Solve the following quadratic
programming problem
Minimize
subject to

z 2 x 2 x 3x
2
1

2
2

2
3

2 x1 x2 2 x2 x3 x1 3x2 5 x3

x1 x2 x3 1
3x1 2 x2 x3 6, x1 , x2 , x3 0

Problem (from Hillier & Lieberman)


Solve the following quadratic
programming problem
Maximize

z 20 x1 50 x2 20 x 18 x1 x2 5 x
2
1

subject to

x1 x2 6
x1 4 x2 18,
x1 , x2 0

2
2

Problem (from Hillier & Lieberman)


Solve the following quadratic
programming problem
Maximize
2

z 2 x1 3x2 x1 x

subject to

x1 x2 2
x1 , x2 0

2
2

You might also like