QUADRATIC PROGRAMMING

Example 1
A company can produce two different products, using
materials of two types.
The contracts have already been signed, meaning that the
company has a target to meet for each of the products.
What should be the level of production, assuming the
constraints on availability of the materials?

Notation:
xi – the number of products of i-th type
xi0 –target level for products of i-th type
aij – amount of i-th material needed for production of one
j-th product
bi – available amount of i-th material

1
 Example 1 - Mathematical problem statement


Min  f ( x1, x2 )  x1  x10 2  x2  x20 2
a11x1  a12 x2  b1 a11x1  a12 x2  x3  b1
a21x1  a22 x2  b2 a21x1  a22 x2  x4  b2

x1  0, x2  0 x3  0, x4  0

Remaining amounts
of material 1 and 2

Example 2
• The Markowitz Model for Portfolio Optimization
http://www.princeton.edu/rvdb

Rj(t) -
return on investment j
in time period t
(expected)

1990 Nobel prize in

economy

2
Example 2 - Mathematical problem statement
Profit from the j-th investment - estimated using historical
means:
1 T
p j   R j (t )
T t 1
Risk associated with the j-th investment - estimated using
historical variances:

 R j (t )  p j 2
1 T
rj 
T t 1

xj - fraction of portfolio to invest in j

Portfolio historical return: R( x)   x j R j (t )

j

Example 2 - Mathematical problem statement

Portfolio profit (expected):

1 T
p( x)   x j R j (t )
T t 1 j

Risk associated with the portfolio

2
 
      x j R j (t )  p j 
1 T 1 T
r ( x)    R( x)  p( x)  2
T t 1 T t 1  j 


max  J  p( x)  r ( x)
x

risk aversion factor

3
Example 2 - Mathematical problem statement
Linear w.r.t. x Quadratic w.r.t. x

max  J  p( x)  r ( x)
x

parameter

 xj 1
j

xj  0 for all investments j

Example 3 – Control systems

The Linear-Quadratic problem (the scalar case)

𝑁−1
1 1
min 𝐽 = 𝑞𝑥𝑖2 + 𝑟𝑢𝑖2 + 𝑓𝑥𝑁2
𝑢𝑖 2 2
𝑖=0
𝑞, 𝑓 ≥ 0; 𝑟 > 0
𝑥𝑖+1 = 𝑎𝑥𝑖 + 𝑏𝑢𝑖 𝑥0 - fixed

4
 Quadratic programming (QP)
1
min  J  x   xT Qx  cT x
2
Ax  b
x0

Q - semipositive definite, Q ≥ 0 → J – convex

Q - symmetric → Q = QT
Properties:
1. If solution exists then it is global.
2. Solution may be reached in many points but they
should constitute a convex set.
3. If Q > 0 (strictly positive definite) then J is strictly
convex and there exists one and only one solution.

Kuhn-Tucker conditions for QP

1
min  J  x   xT Qx  cT x Ax  b x0
2
1
𝑉 = 𝑥 𝑇 𝑄𝑥 + 𝑐 𝑇 𝑥 + 𝜆𝑇 𝐴𝑥 − 𝑏 + 𝜇 𝑇 (−𝑥)
2
𝜕𝑉
= 𝑥 𝑇 𝑄 + 𝑐 𝑇 + 𝜆𝑇 𝐴 − 𝜇 𝑇 = 0 or Qx  AT   c    0
𝜕𝑥
Ax  b
 0 linear equations and sign constraints only
x0
i xi  0
If Q nonsingular (Q > 0) then Problems:
• What if det(Q) is very small

x0  Q 1 AT   c    • We need  and 

5
 Algorithms for solving QP

Two groups of algorithms:

• based on linear form of K-T conditions and use of
simplex algorithm for linear programming (see later on)
– Wolfe algorithms
• based on a dual problem for QP (Hildebrand algorithm,
with inequality constraint Ax  b):

Wolfe algorithm (1)

Recall the K-T conditions:
Qx  AT   c    0
How to solve (efficiently) the
Ax  b
set of equations?
i xi  0
 0
x0

Let’s introduce new variables u, u* ≥ 0

Qx  AT   c    u  0
Ax  u*  b New task:
i xi  0 Min   u i   u*j
 0
x0

6
 Wolfe algorithm (2)
Qx  AT   c    u  0
Ax  u*  b
i xi  0
 0
x0
Min   u i   u*j

Almost LP, but:

There is no sign constraint on 

Additional, nonlinear constraint i xi  0

Wolfe algorithm (3)

There is no sign constraint on 

   ,  ,  0

Additional, nonlinear constraint i xi  0

It cannot be included in LP (due to its nonlinearity)

but we can take care of it later, modyfing simplex
algorithm in an appropriate way

7
 Wolfe algorithm (4)

Qx  AT   AT     u  c n equations
Ax  u*  b m equations
  0, x  0,   0, x, , u – n-dimensional
  0, u  0, u *  0 u*, ,  – m-dimensional

Min   u i   u*j We can use Simplex algorithm

3n+3m variables!!! – need to find a way to reduce this number

The best way to show

how to do that is to solve
an example

Example 1


Max  2 x1  x2  x12 
2 x1  3 x2  6 2 x1  3x2  x3  6
2 x1  x2  4 2 x1  x2  x4  4
x1  0, x2  0 x1, x2 , x3 , x4  0

We already have 2 base variables for

the simplex algorithm (x3 and x4), so we
don’t have to introduce u*

Conclusion:
First 2 base variables can be found by
appropriately transforming the equality constraint
Ax = b

8
 Example 1
Now we determine Q, c, A and b


Max  2 x1  x2  x12  2 0 0 0
 2 3 1 0
0 0 A  
2 x1  3x2  x3  6 Q
0 0
 
2 1 0 1
0 0 0 0
2 x1  x2  x4  4 0
 0 0 0
x1, x2 , x3 , x4  0
  2
1 6 
c  b 
0  4
0
 x  6   
xB   3    
 x4   4 

Example 1
Ax  b

Qx  AT   AT     u  c
To start with an initial feasible solution we need positive uB.
Therefore we should modify it a bit:

Qx  AT   AT       u  c
QB xB  QN x N  AT   AT     u  c
where
1 0 0 0 
0   1 if  ci  QBi xB  0
0 0 i  
  2 
      1 if  ci  QBi xB  0
0 0 0  n 


9
 Example 1
QB – matrix created from those columns of Q that correspond
to base variables xB

2 0 0 0
0 0 0 0  x  6 
Q  xB   3    
0 0 0 0  x4   4 
0 0
 0 0

0 0
0 0
QB    QBi − i-th row of QB
0 0
0 0


Example 1 0 0
0 0
6
𝑐 𝑇 = −2 1 0 0 𝑥𝐵 = QB   
4 0 0
0 0

6
−𝑐1 − 𝑄𝐵1 𝑥𝑏 = 2 − 0 0 = 2 > 0 → ∆1 = 1
4
6
−𝑐2 − 𝑄𝐵2 𝑥𝑏 = −1 − 0 0 = −1 < 0 → ∆2 = −1
4
6
−𝑐3 − 𝑄𝐵3 𝑥𝑏 = 0 − 0 0 = 0 ≥ 0 → ∆3 = 1
4
6
−𝑐4 − 𝑄𝐵4 𝑥𝑏 = 0 − 0 0 = 0 ≥ 0 → ∆4 = 1
4
1 0 0 0
0  1 0 0
 
0 0 1 0
0 0 1
 0

10
 Example 1
Finally:
Min   u i
Ax  b

Qx  AT   AT     u  c
First simplex table
(without the last row)

x
 
A 0 0 0 0    b 
Q A T   
  AT  1 Δ    c 
 

 u 

𝑥1 𝑥2 𝑥3 𝑥4 𝜁1 𝜁2 𝜉1 𝜉2 𝜇1 𝜇2 𝜇3 𝜇4 𝑢1 𝑢2 𝑢3 𝑢4

2 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 6
2 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 4
2 0 0 0 2 2 -2 -2 -1 0 0 0 1 0 0 0 2
0 0 0 0 3 1 -3 -1 0 -1 0 0 0 -1 0 0 -1
0 0 0 0 1 0 -1 0 0 0 -1 0 0 0 1 0 0
0 0 0 0 0 1 0 -1 0 0 0 -1 0 0 0 1 0

𝑥
𝜁
𝑨 𝟎 𝟎 𝟎 𝟎
𝜉 = 𝒃
𝑸 𝑨𝑻 −𝑨𝑻 −𝟏 𝜟 𝜇 −𝒄
𝑢

11
𝑥1 𝑥2 𝑥3 𝑥4 𝜁1 𝜁2 𝜉1 𝜉2 𝜇1 𝜇2 𝜇3 𝜇4 𝑢1 𝑢2 𝑢3 𝑢4

2 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 6
2 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 4
2 0 0 0 2 2 -2 -2 -1 0 0 0 1 0 0 0 2
0 0 0 0 3 1 -3 -1 0 -1 0 0 0 -1 0 0 -1
0 0 0 0 1 0 -1 0 0 0 -1 0 0 0 1 0 0
0 0 0 0 0 1 0 -1 0 0 0 -1 0 0 0 1 0

2𝑥1 + 2𝜁1 + 2𝜁2 − 2𝜉1 − 2𝜉2 − 𝜇1 + 𝑢1 = 2

3𝜁1 + 𝜁2 − 3𝜉1 − 𝜉2 − 𝜇2 − 𝑢2 = −1
𝜁1 − 𝜉1 − 𝜇3 + 𝑢3 = 0

min 𝑢𝑖 𝜁2 − 𝜉2 − 𝜇4 + 𝑢4 = 0

min 𝑢𝑖 = min(𝟑 − 𝟐𝒙𝟏 − 𝟐𝜻𝟐 + 𝟐𝝃𝟐 + 𝝁𝟏 − 𝝁𝟐 + 𝝁𝟑 + 𝝁𝟒 )

𝑥1 𝑥2 𝑥3 𝑥4 𝜁1 𝜁2 𝜉1 𝜉2 𝜇1 𝜇2 𝜇3 𝜇4 𝑢1 𝑢2 𝑢3 𝑢4

2 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 6
2 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 4
2 0 0 0 2 2 -2 -2 -1 0 0 0 1 0 0 0 2
0 0 0 0 -3 -1 3 1 0 1 0 0 0 1 0 0 1
0 0 0 0 1 0 -1 0 0 0 -1 0 0 0 1 0 0
0 0 0 0 0 1 0 -1 0 0 0 -1 0 0 0 1 0
2 0 0 0 0 2 0 -2 -1 1 -1 -1 0 0 0 0 3

The initial simplex table

(with the first feasible basic solution)

12
 Example 2

Min  x12  2 x1  x22 
2 x1  3 x2  12
2 x1  x2  4
x2  0

No constraints on the 𝑥1 sign, so:

𝑥1 = 𝑥0∗ − 𝑥1∗
𝑥0∗ ≥ 0, 𝑥1∗ ≥ 0
min 𝑥0∗ − 𝑥1∗ 2
+ 2 𝑥0∗ − 𝑥1∗ + 𝑥22 =

= min 𝑥0∗2 + 𝑥1∗2 + 𝑥22 − 2𝑥0∗ 𝑥1∗ + 2𝑥0∗ − 2𝑥1∗

2𝑥0∗ − 2𝑥1∗ + 3𝑥2 + 𝑥3 = 12

2𝑥0∗ − 2𝑥1∗ + 𝑥2 = −4

Example 2
min 𝑥0∗2 + 𝑥1∗2 + 𝑥22 − 2𝑥0∗ 𝑥1∗ + 2𝑥0∗ − 2𝑥1∗

2𝑥0∗ − 2𝑥1∗ + 3𝑥2 + 𝑥3 = 12

2𝑥0∗ − 2𝑥1∗ + 𝑥2 = −4 No first basic
feasible solution
After transformation (or the first simplex stage)

2𝑥2 + 𝑥3 = 16
𝑥3 16
1 𝒙𝑩 = 𝑥 ∗ =
−𝑥0∗ + 𝑥1∗ − 𝑥2 = 2 1 2
2 𝑥0∗ 𝑥1∗ 𝑥2 𝑥3
0 0 2 1 16 2 −2 0 0
𝑨= 𝒃=
−1 1 2
−0.5 0 𝑸 = −2 2 0 0
0 0 2 0
𝑐𝑇 = 2 −2 0 0 0 0 0 0

13
 −2 0
𝑥3 16
𝑸𝑩 = 2 0 𝑐𝑇 = 2 −2 0 0 𝒙𝑩 = 𝑥 ∗ =
0 0 1 2
0 0

 1 if  ci  QBi xB  0
i  
 1 if  ci  QBi xB  0

16
−𝑐1 − 𝑄𝐵1 𝑥𝑏 = −2 − −2 0 = 30 > 0 → ∆1 = 1
2
16
−𝑐2 − 𝑄𝐵2 𝑥𝑏 = 2 − 2 0 = −30 < 0 → ∆2 = −1
2
16
−𝑐3 − 𝑄𝐵3 𝑥𝑏 = 0 − 0 = 0 ≥ 0 → ∆3 = 1
2
16
−𝑐4 − 𝑄𝐵4 𝑥𝑏 = 0 − 0 = 0 ≥ 0 → ∆4 = 1
2

Modification of Simplex algorithm

OK., but what about the condition 𝜇𝑖 𝑥𝑖 = 0 ?

• The initial feasible base solution satisfies it: the variables 

do not belong to the base, so they are equal to 0.

• Then, it is enough to generate the next node (choose the

pivot element) in subsequent iterations in such way that
this condition is satisfied.

• Note that the variables xi and i cannot be zero

simultaneously.

• Since in LP problem a variable can become non-zero only

if it becomes a base variable, the only condition to be
modified in the simplex algorithm is the following

14
 Modification of Simplex algorithm

• If the variable chosen for entering the base is one of i, i

or ui, then we can proceed with this change
• If the variable chosen for entering the base is xi, then
before pivoting we must check, if respective i is a base
variable. If so, xi can enter the base only if the base i = 0.
Otherwise other variable must be chosen.
• If the variable chosen for entering the base is i, then
before pivoting we must check, if respective xi is a base
variable. If so, i can enter the base only if the base xi = 0.
Otherwise other variable must be chosen.

15