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.

7

Quadratic Programming

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,

the quadratic programming problem is

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

is a quadratic program where

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

Quadratic Programming 251

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.

Get Mark Richards’s *Software Architecture Patterns* ebook to better understand how to design components—and how they should interact.

Dive in for free with a 10-day trial of the O’Reilly learning platform—then explore all the other resources our members count on to build skills and solve problems every day.

Start your free trial Become a member now