The Mathematics of Financial Modelingand Investment Management

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

208 The Mathematics of Financial Modeling and Investment Management

1. An inequality constraint





≤

ai, 1 x 1 + ...+ ain, xn=bi

 ≥

can be converted into an equality constraint through the introduction

of a slack variable, denoted by S, or an excess variable, denoted by E,

such that

ai, 1 x 1 + ...+ ain, xn + S = bi

or

ai, 1 x 1 + ...+ ain, xn – E = bi

2. A variable with negative sign restriction xi ≤0 can be substituted by
   xi = –xi ′, xi ′ ≥0 while an unrestricted variable can be substituted by
   xi = xi ′– xi ′′, xi ′,xi ′′ ≥0.

There are two major techniques for solving an LP problem: the sim-

plex method and the interior-point method. The simplex method was

discovered by Dantzig in the 1940s. Although the number of iterations

may be exponential in the number of unknowns, the simplex method

proved very useful and was unrivaled until the late 1980s. The exponen-

tial computational complexity of the simplex method led to a search for

algorithms with better computational complexity features, in particular

polynomial complexity. Khachiyan’s ellipsoid method—the first polyno-

mial-time algorithm—appeared in the 1970s. Most interior-point meth-

ods also have polynomial complexity. We will briefly describe both the

simplex and the interior-point methods.

The Simplex Algorithm

Linear constraints identify a region called a simplex. The simplex

method searches for optima on the vertices of the simplex. Recall from

Chapter 5 on matrix algebra that the system Ax = b admits solutions if

and only if rank [Ab] = rank A. We can assume without loss of general-

ity that rank A = m, otherwise we drop redundant equations. The feasi-

ble set is the set B of points that satisfy the constraints

B = {x: Ax = b, x ≥0}