The Mathematics of Financial Modelingand Investment Management

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

210 The Mathematics of Financial Modeling and Investment Management

ate extreme points visited improve the objective function. Many standard

optimization software packages contain the simplex algorithm. However,

the simplex method exhibits exponential complexity. This means that the

number of steps required for finding a solution grows exponentially with

the number of unknowns.

Interior-Point Methods

The exponential complexity of the simplex method was behind the search

for more computationally efficient methods. The 1980s saw the introduc-

tion of the first fast algorithms that generate iterates lying in the interior

of the feasible set rather than on the boundary, as simplex methods do.

The primal-dual class of interior-points algorithms is today considered

the state-of-the-art technique for the practical solution of LP problems.

Furthermore, this class of methods are also very amenable to theoretical

analysis, and has opened up a new area of research within optimization.

We will limit our brief discussion to this class of interior-point algorithms.

Let’s begin by formulating the concept of duality. Every problem of

the type

maximize c 1 x 1 + ... + cnxn

subject to

ai,1x 1 + ... + ai,nxn ≥ bi, i = 1,2,...,m

xj ≥ 0, j = 1,2,...,n

has a dual problem

minimize b 1 y 1 + ... + bmym

subject to

y 1 a1,i + ... + ymam,i ≤ ci, i = 1,2,...,n

yj ≥ 0, j = 1,2,...,m

The original problem is called the primal problem. The primal-dual gap

is the difference, if it exists, between the largest primal value and the small-

est dual value. The Strong Duality Theorem states that, if the primal prob-

lem has an optimal solution x* = (x 1 ,...,xn), the dual also has an optimal

solution y* = (y 1 ,...,ym) and there is no primal-dual gap in the sense that