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.