Quadratic Programming
Quadratic Programming
Quadratic Programming
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
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
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
a
j 1
ij
x j bi
3. i S i 0,
i 1, 2, . . . , m
j x j 0 , j 1, 2, . . . , n
Referred to as " Restricted Basis " conditions.
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
*
1
*
1
x , x , . . ., x
*
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
Problem
Maximize
subject to
z 8 x1 x 2 x2 x3
2
1
x1 3 x2 2 x3 12
x1 , x2 , x3 0
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
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
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
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
Basic r
x1 x2 x3 1 1 2 3 R1 R2 R3 S1 Sol
r 1
0 0 0 0
x1 0
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
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
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
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.
1 1
2 x1
2 x2 1
x1 x2
R1
R2
S1 2
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
x2
x1+x2=2
z=16
z=14
z=12
z=8
x1
(2,0)
Feasible region
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
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
Basic r
x1 x2 1 2 1 2
R1
R2 S1
S2 Sol
r 1
-2
0 -1 -1
-2
R1 0
1/4
3/4
0 -1/4
1/4
S2 0 0
-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
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
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
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
z 2 x1 3x2 x1 x
subject to
x1 x2 2
x1 , x2 0
2
2