The Mathematics of Financial Modelingand Investment Management

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

Optimization 207

fx( 1 , ...,xn )= c T x , c = (c 1 , ..., cn), x = (x 1 ,...,xn)

subject to the constraints





≤

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

 ≥

or, in matrix notation



Axb

≤

 =

 ≥

with additional sign restrictions such as xi ≤0, xi ≥0, or xi unrestricted

in sign.

The largest or smallest value of the objective function is called the

optimal value, and a vector [x 1 ... xn] that gives the optimal value con-

stitutes an optimal solution. The variables x 1 ,...,xn are called the deci-

sion variables. The feasible region determined by a collection of linear

inequalities is the collection of points that satisfy all of the inequalities.

The optimal solution belongs to the feasible region.

The above formulation has the general structure of a mathematical

programming problem as outlined in the introduction to the chapter,

but is characterized, in addition, by the fact that the objective function

and the constraints are linear.

LP problems can be transformed into standard form. An LP is said

to be in standard form if (1) all constraints are equality constraints and

(2) all the variables have a nonnegativity sign restriction. An LP prob-

lem in standard form can therefore be written as follows

min cTx

subject to constraints

Ax = b 

x ≥ 0 



where A is an m ×n matrix and b is an m-vector.

Every LP can be brought into standard form through the following

transformations: