7
7.1 Introduction
In this chapter, we consider a generalization of linear programming that in-
volves linear constraints, but the objective function is a quadratic function and
so will contain terms that involve the products of pairs of variables. Such an
optimization problem is called a quadratic programming (QP) problem and is
a very important class of problems as many applications can be modeled in this
framework. We illustrate the importance of quadratic programming through
ﬁnancial portfolio applications. A characterization of optimality of quadratic
programs is given that will serve as the basis for algorithmic development.
7.2 QP Model Structure
The quadratic programming (QP) problem can be stated as
minimize c
T
x +
1
2
x
T
Qx
subject to Ax b
Ex = d
x 0
where c, x R
n
, Q is a n ×n symmetric matrix, A is an m
1
×n matrix, and E
is an m
2
× n matrix. Constraints are partitioned into linear inequality con-
straints and linear equality constraints. Note that if Q = 0, then the problem
becomes a linear program.
In addition, when there are no constraints and variables are unrestricted,
minimize c
T
x +
1
2
x
T
Qx
subject to x R
n
.
This problem will be referred to as the unconstrained quadratic program-
ming problem (UQP).
Example 7.1
249
© 2014 by Taylor & Francis Group, LLC
250 Introduction to Linear Optimization and Extensions with MATLAB
R
The following problem
minimize 4x
2
1
+ x
1
x
2
+ 2x
1
x
3
+ 3.5x
2
2
+ x
2
x
3
+ 3x
2
3
+ 2x
1
x
2
+ x
3
subject to x
1
+ 2x
3
5
3x
2
+ x
3
2
x
1
+ x
3
= 2
x
1
0, x
2
0, x
3
0
Q =
8 1 2
1 7 1
2 1 6
, c =
2
1
1
, x =
x
1
x
2
x
3
,
A =
1 0 2
0 3 1
, b =
5
2
, E =
1 0 1
, d = [2].
Example 7.2 (Least Squares Fit)
Quadratic problems arise naturally in statistics. Suppose that you have
observed values (t
1
, u
1
), (t
2
, u
2
), ..., (t
n
, u
n
) where t
i
is the unemployment rate
in year i and u
i
is the rate of inﬂation for year i. Based on these observations,
you believe that the unemployment rate and inﬂation rate in a year are related.
In particular, you believe that t
i
and u
i
are related by a polynomial function
p(t) = x
0
+ x
1
t + x
2
t
2
··· + x
k
t
k
where the degree of the polynomial k is determined in advance. However, the
coeﬃcients x
0
, x
1
, ..., x
k
are not known. The goal is to choose the values for
these coeﬃcients so that the absolute diﬀerence between the observed values
u
i
and p(t
i
), i.e.,
|u
i
p(t
i
)|
are as small as possible. Let x = (x
0
, x
1
, ..., x
n
), then one strategy is to mini-
mize the function
ϕ(x) =
n
P
i=1
(u
i
p(t
i
))
2
=
n
P
i=1
(u
i
k
P
j=1
x
j
t
j
i
)
2
.
We can express ϕ(x) in terms of norms on vector quantities. Let
A =
1 t
1
t
2
1
··· t
k
1
1 t
2
t
2
2
t
k
2
.
.
.
.
.
.
1 t
n
t
2
n
··· t
k
n
and b =
u
1
u
2
.
.
.
u
n
© 2014 by Taylor & Francis Group, LLC
then,
ϕ(x) = kb Axk
2
= (b Ax) · (b Ax)
= b · b 2b · Ax + Ax · Ax
= b · b 2A
T
b · x + xA
T
Ax.
(Note: · indicates the dot product of two vectors.) Now if we let Q =
A
T
A and c = A
T
b, then it is clear that minimizing ϕ(x) subject to x
R
k+1
is equivalent to minimizing
1
2
x
T
Qx + cx subject to x R
k+1
, which
is an unconstrained quadratic program. The optimal solution provides the
coeﬃcients for p(t) that represent a least squares ﬁt of the observed data.
Note: It is generally the case that the number of observations n is greater
than k + 1, so that the system Ax = b will have more rows than columns, i.e.,
it is an over-determined system of linear equations and so an exact solution
will not exist, which makes the search for a best approximating solution
meaningful.
7.3 QP Application: Financial Optimization
We consider a ﬁnancial portfolio problem of Markowitz (1952) that was brieﬂy
introduced in Chapter 1. This model is perhaps the most well-known instance
of a quadratic program and served as the basis of the research in portfolio
selection by Markowitz that was awarded the 1992 Nobel Prize in Economic
Sciences. We start the development from ﬁrst principles.
Consider an investor that wishes to allocate funds into n ﬁnancial securities
now (t = 0), and will hold the investment until time t = T in the future. Let
w
i
= the dollar amount invested in security i and w =
n
P
i=1
w
i
, then x
i
=
w
i
w
is
the proportion of total funds invested in security i. The vector
x =
x
1
x
2
.
.
.
x
n
represents the portfolio of investments.
Portfolio Returns
If the current (t = 0) price of security i is p
0
i
and the price of security i
at time T is p
T
i
, then the rate of return of security i, denoted by r
i
, over the
time period [0, T ] is deﬁned as
© 2014 by Taylor & Francis Group, LLC

Get Introduction to Linear Optimization and Extensions with MATLAB® now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.