The Mathematics of Financial Modelingand Investment Management

7-Optimization Page 211 Wednesday, February 4, 2004 12:50 PM

Optimization 211

∑cixi = ∑bjyj

i j

Interior-point algorithms generate iterates such that the duality gap is

driven to zero, yielding a limiting point that solves the primal and dual

linear programs. Commercial software packages that contain primal-

dual interior-point solvers are available.

Quadratic Programming

The general quadratic programming (QP) problem is a mathematical

programming problem where the objective function is quadratic and

constraints are linear as follows:

minimize fx( 1 , ..., xn ) = c T x +^1 ---x TDx

2

where c = (c 1 ,...,cn), x = (x 1 ,...,xn) are n-vectors and D is a n×n matrix,

subject to

aix ≤ bi, i ∈ I

aix = bi, i ∈ E

x ≥ 0

where b is an m-vector b = (b 1 ,...,bm), A = [ai] is an m×n matrix, and I

and E specify the nonequality and equality constraints respectively.

The major classification criteria for these problems come from the

characteristics of the matrix D as follow:

■ If the matrix D is positive semidefinite or positive definite, then the QP

problem is a convex quadratic problem. For convex quadratic prob-

lems, every local maximum is a global maximum. Algorithms exist for

solving this problem in polynomial time.^5 The Markowitz mean-vari-

ance optimization problem is of this type.

■ If the matrix D is negative semidefinite, that is, its eigenvalues are all

nonpositive, then the QP problem is a concave quadratic problem. All

solutions lie at some vertex of the feasible regions. There are efficient

algorithms for solving this problem.

(^5) A problem is said to be solvable in polynomial time if the time needed to solve the
problem scales with the number of variables as a polynomial.