Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Optimization I Notes

Page 1

OPTIMIZATION I
Introduction – Lots of Geometry


Some definitions
o

Definition (Convex set): The set  Í n if convex if for any x1, x 2 Î  and

l Î [0,1] , x(l) = lx1 + (1 - l)x 2 Î 
...

o

Definition (Convex function): A function f (x ) defined on a convex set
 Í n is convex if for any x1, x 2 Î  , the linear interpolation between those two

points lies above the curve:

f (lx1 + (1 - l)x 2 ) £ l f (x1 ) + (1 - l)f (x 2 )

x2

x1
o

l Î [0,1]



Definition (Cone): A set  Î n is a cone if for all x Î  and any l ³ 0 ,

lx Î  :

1

2

Daniel Guetta, 2010

Optimization I Notes

Page 2

{

The set x Î n : x = Aa, a ³ 0, A Î n´m , a Î m

}

is the cone generated by the

columns of A
...

Not an extreme point

Extreme point

Extreme point

o

Definition (Convex Combination): A convex combination of points x1, , xk
is a point x = å i =1 li xi , such that l ³ 0 and
k

å

k
i =1

li = 1
...

o

{

Definition (Hyperplane): The set  = x Î n : a ⋅ x = b, a Î n , b Î 

{

called a hyperplane with normal a
...

o

Definition (Afine set): A set a Î n is an affine set if for all x1, x 2 Î a and

l Î (-¥, ¥) , x(l) = lx1 + (1 - l)x 2 Î a
...
Roughly speaking, an affine set is a subspace that need not contain the
original
...
It is necessarily convex
...


o

Definition (Dimension): The dimension of an affine set a is the maximum
number of linearly independent vectors in a
...
The intersection  Ç  =  is a face of 
...
In
other words, we insist  Ç  = 
= x
...


Daniel Guetta, 2010

Optimization I Notes


Page 4

Polyhedra in standard form
o

The definition of a polyhedron above (in terms of the intersection of a number of

{

}

half-spaces) can be written as  = Ax £ b : A Î n´m , x Î n , b Î m , where
the rows of A contain the normals of the various hyperplanes defining the
polyhedron
...
This involves a number of steps:


Re-write each inequality constraint

Arow i ⋅ x £ bi

as the equality

Arow i ⋅ x + si = bi , where si > 0
...



Eliminate any linearly independent rows in A (this does not alter the
problem – see page 57 of B&T for proof)
...
)



Replace any unconstrained variables xi with two new variables x i+ and x i, both constrained to be positive, and add the constraint x i = x i+ - x i-
...




Algebraic Characterization of Vertices & Extreme Points
o

In the previous section, we provided definitions of vertices and extreme points
...
In this section, we see that these concepts are equivalent, and we develop
an algebraic characterization of such points
...


o

Theorem: Let  = {x : Ax ³ b, A¢x = b ¢} be a non-empty polyhedron, and let

x Î 
...
x is a vertex

Daniel Guetta, 2010

Optimization I Notes

Page 5

2
...
All equality constraints are active at x, some of the inequality constraints
are active, and out of all the constraints that are active at x, n of them
are linearly independent [Note: we say the vectors ai are linearly
independent if the system of equations ai ⋅ x = bi has a unique solution
(see p48 of B&T)]
...

o

{

Theorem: Let  = x Î n : Ax = b, x ³ 0

}

be a non-empty polyhedron in

standard form, and let x Î 
...
x is an extreme point of 
...
The columns of A corresponding to the strictly positive components of x
are linearly independent
...
x is a vertex of 
...
In fact, the two are equivalent; we discuss two ways of seeing
this; the first in terms of the rows of A, and the second in terms of the columns:


The fact that all variables Ï  are equal to 0 already creates n - 
linearly independent active constraints
...
Another way of saying this is that we need all the columns
of the matrix B (there are  of them) to be linearly independent
...

We have to combine the foods to get our requirements
...
In the diet problem,
water, sugar, lemon and lemonade might form such a group, because it is
possible, from 3 of these, to get all the nutrients available in the fourth
item
In that case, we must “standardize” the problem by having one of these
variables set to 0 – otherwise, our problem is indeterminate
...


Proof: We will prove 1  2  3  1
...
We
will be considering a point x in the polyhedron; we will define x to be the
strictly positive component of x, and x to be those components that are 0
...



1  2 Assume 2 is false, and let x be an extreme point
...
Thus, it
is true that A (x + ew ) = b , for all e
...


Daniel Guetta, 2010

Optimization I Notes

Page 7

Now, let w = (w  0)



and set x ¢ = x + e+w , and x ¢¢ = x - e-w
...
However, x = 12 x ¢ + 12 x ¢¢
...

Thus, by the contra-positive, 1  2
...
We would like to show

that there exists a supporting hyperplane  to the polygon  such that

Ç=x
...
We have
æ0ö÷ æy ÷ö
ç ç
c ⋅ x = çç ÷÷÷ ⋅ çç ÷÷÷ = e ⋅ y
çèe ÷ø çèy÷ø
But since y Î  , we must have y ³ 0
...




 Ç  = x Imagine y Î  Ç 
...


Furthermore, since y is in the polyhedron, Ay = b
...



3  1 Choose a point x Î  that satisfies (3), and assume that (1) is

not true; in other words, for some l Î [0,1] and x ¢, x ¢¢ Î  , we can write
x = lx ¢ + (1 - l)x ¢¢
...
Now:
c ⋅ x = c ⋅ éêëlx ¢ + (1 - l)x ¢¢ùúû
= lc ⋅ x ¢ + (1 - l)x ¢¢
> lc ⋅ x + (1 - l)c ⋅ x
> c ⋅x
This is a contradiction
...

o

Note that the theorem above says nothing of how many variables the set  must
contain
...




Choosing  < m would imply choosing more than n – m non-negativity
constraints, which, in total, would result in more than n constraints
...


We therefore define…
o

Definition

{A

col B1

(Basis):
col Bm

, , A

}

A

linearly

independent

set

of

m

columns

of A is a basis for the column space of A
...

col B
col B
B = éêA 1 , , A m ùú is called the basis matrix and the associated vector of
ë
û

variables x B that solves Bx B = b is called the vector of basic variables
...
There is no guarantee, however, that solving Bx B = b
will lead to x > 0
...

o

Definition (adjacent basis): Two distinct basic solutions are said to be
adjacent if we can find n – 1 linearly independent constraints that are active at
both of them
...
In terms of
polyhedra in standard form, two bases are said to be adjacent if they share all
but one basic columns
...


o

Definition (Degenerate basis): A basic feasible solution x is said to be
degenerate if some component of x B is 0
...

This is equivalent to the previous definition, because it implies that more than

n - m of the non-negativity constraints are tight at x
...
Clearly,
it only contains two vertices:

Daniel Guetta, 2010

Optimization I Notes

Page 10

The vertex x = (0, 23 , 23 ) is at the intersection of 3 planes; since there are three
variables, it is non-degenerate
...

The vertex x = (2, 0, 0) , however, is at the intersection of 4 planes
...


Representation & Optimality


In this section, we prove what might be called the “fundamental Theorem of Linear
Programming” – that the optimal solution of a linear program occurs at a vertex
...


o

Definition (recession direction): A recession direction of the polyhedron 
is

a

non-zero

vector

d Î n

such

that,

for

any

x Î,

{x : x = x + qd, q Î  } Î 
+



d
x

For a polyhedron in standard form, d is a recessive direction if and only if

Ad = 0 (so that we remain feasible as we move along that direction), d ³ 0 (so
that we never become negative as we move along that direction) and d ¹ 0
...

o

Proof: We prove this by induction, on the number of strictly positive
components in x
...
If x is a vertex, the theorem is
trivially true
...
This implies that there exists a w ¹ 0
such that wi = 0 if x i = 0 and Aw = 0
...
Clearly, Ax(q) = b for all q
...
We consider these two cases:


w has both +ve and - ve components

In that case, we’ll hit a non-

negativity constraint
...



q ¢¢ = largest negative q such that x (q ¢¢) has at most p – 1

strictly positive components
...
Thus, so can x
...
Assume
that w ³ 0 [the other case is similar]
...

Diagrammatically:


w
x
x (q ¢)
We can then write
x = x (q ¢) + qw

But w is a recession direction (because Aw = 0 and w ³ 0 ) and by the
inductive hypothesis, x(q ¢) can be written as required
...

The “starting point” for the induction is somewhat difficult to find
...
This must be a vertex,
because if it was not, we could carry out the steps outlined above and find a
point with fewer strictly positive components – this is a contradiction
...
However, the

non-negativity constrains of the standard-form polyhedron ensure there is at least
one
...


Proof: We consider two cases:


Case 1 –  has a recession direction d such that c ⋅ d < 0 : in
that case, the problem is unbounded, because for any

x Î,

c ⋅ x(q) = c ⋅ (x + qd ) = c ⋅ x + qc ⋅ d  -¥ as q  ¥
...
By our Representation Theorem, we can write
x =

ålv
i

i

+ ad , where l+ = 1, li ³ 0, a ³ 0
...


Simplex


We have thus far established that the optimum of a linear program occurs at one of the
vertices of the feasible region
...


Daniel Guetta, 2010

Optimization I Notes


Page 14

Representation in terms of emanating directions
o

Consider a polyhedron Ax = b , where A = éêëB, N ùúû Î m´n , and a non-degenerate
basic solution xˆ = (xˆB , xˆN ) , where xˆB = B -1b > 0 and xˆN = 0
...

Proof: Let h j be the jth column of M–1
...
This
point is still on the polyhedron, because

Ax B (q) = Bx B (q) + Nx N (q)

(

)

= B xˆ - qB -1Acol j + qAcol j
col j

= b - qA

col j

+ qA

=b

Thus, h j is indeed an edge of P, and it clearly results from increasing only one of
the xN
...
This means that our emanating edges
j

(columns of M–1) are perpendicular to every normal vector save one (along which
we’re trying to move):

Daniel Guetta, 2010

Optimization I Notes

Page 15
h1
a2

a1

s2 = 0

s1 = 0

For a final intuitive justification of this result, note that for a problem in
standard form, each emanating edge h j involves bringing one variable – say xj –
into the basis and consequently changing the value of the other variables in the
basis in order to keep Ax = b valid
...
Now, note that


If we increase xj by 1 unit, our “resultant vector” Ax increases by Acol j
...


Now, it makes sense that these two changes should “balance out” so as to keep
our “resultant vector” at b
...

o

Lemma: Given a BFS xˆ , every point y Î P can be expressed as

y = xˆ + å y j h j
j >m

Where h j is the jth column of M–1, and where yj > 0 for j > M
...


h j are the “extreme” recession directions of C
...


h j are the “edges” (1-dimensional faces) of C
...

3
...




Background to the Simplex Algorithm
o

Consider linear program is min z = c x
...
If it is greater than 0, the direction is
“uphill”, and vice-versa
...
Practically,
they can be calculated by


Solving p = cBB -1



Setting, for j > m, c j = c j - p ⋅ Acol j

Geometrically:


p is the particular linear combination of equality constraints that gives
cB
...




Thus, p ⋅ Acol j is the resulting change in the objective when we move one
unit along direction j
...


Theorem: If c j = c ⋅ h j ³ 0 for all j > m, then the current BFS is optimal
...

This theorem has an interesting geometrical explanation, which we discuss below,
when we motivate duality
...
Start with a BFS x
...
Compute the simplex multipliers p by solving B  p = cB , and compute the
reduced costs c j = c j - p ⋅ Acol j for all j Ï basis
...
Check for optimality: if c j ³ 0 "j Ï basis , then the current solution is optimal
...
Choose a nonbasic variable to enter the basis; ie: choose a “downhill edge” from
the set of downhill edges V along which to move (typically, the one with the
smallest reduced cost):

q Î V = { j Ï B : c j < 0}
5
...
Note that wq = -h j
...

6
...

7
...
Set:
xq ¬ q
x j ¬ x j - qwi
i



i

The Full Tableau Simplex
o

The simplex algorithm outlined above is relatively inefficient, because it involves
the inversion of the matrix B at each step
...

Typically, this information is stored in a tableau containing an extra row:

B -1A

B -1b

c  - cBB -1A

-cBB -1b

Or, in more detail:


-1


col 1

B A


c1

-1

col n

 B A




cn

Daniel Guetta, 2010

x B ,1

x B ,m

-cBxB

Optimization I Notes

Page 18

[Note that the columns of the tableau corresponding to basic variables will
contain the columns of the identity, because B–1B = I]
...
In that case, B = B -1 = I
(where some of the entries might be negative, depending on the type of
inequality), and the tableau can easily be filled in:
x1

x2



zm

a11

z1 basic

b
b1




zm basic

c1

c2



amn

bm

0

0

The last row contains the reduced costs; in this case, since the objective function
does not contain any slack variables, cB = 0, and so the reduced costs are simply
equal to the costs for the nonbasic variables
...
Simply multiply each rows by the
corresponding objective function coefficient (for example, multiply the
first row above by cz )…
1



…and add all the rows to get to get cBB -1A
...

In terms of our matrix:

c j = c j - å i aijci
 If c > 0 , then there is no improving direction; we’re done!

Daniel Guetta, 2010

Optimization I Notes

o

Page 19

Find pivot column: Choose the pivot column with the smallest reduced cost;
or, in the case of ties, the one with the smallest j
...

Very conveniently this is none other than the negative of the emanating direction
corresponding to j from our BFS, -h j
...
The problem is unbounded
...
See the discussion below for anti-cycling rules
...
Because of the structure of our tableau,
the only thing that needs to change is the vector cB and the matrix B, which
needs to change from B to B , where

B = éêAcol ?  Acol i  Acol ? ùú
ë
û
col ?
col j
col ? ù
é
B = êA
 A
 A ú
ë
û
To work out how to update the tableau, consider that

Daniel Guetta, 2010

Optimization I Notes

Page 20
B -1B = éêI col
ë

?

 B -1Acol j

 I col ? ùú
û

Now, imagine we found a matrix Q such that
QB -1B = Q éêI col
ë

?

 B -1Acol j

 I col ? ùú = I
û

Then we would have
QB -1 = B -1
So once we find the mysterious matrix Q, all we need to do is apply it to our
tableau to update it
...
These operations are:


Divide the pivot row by the pivot element, to get a 1 in there
...


In terms of our tableau

ìï a / a
aab = ïí ab ij
ïïa ab - aa jai b
î

for the pivot row (ie: a = i )
for every other row (ie: a ¹ i )

It turns out that the rule above also applies to the last row of the tableau
...




The last element of every other column that stays in the basis will also
contain a 0, because

Daniel Guetta, 2010

Optimization I Notes

Page 21


The original value there was 0, being the reduced cost of a basic
variable
...

This implies that once the row operations have been carried out

cB -TB = 0  T = cBB -1
And so we end up with a bottom row of

éc  | 0ù - c B -1 éA | b ù
úû
B
úû
ëê
ëê
As required
...
In this
section, we explore two different methods
...
If our original
problem is

min c ⋅ x s
...
Ax = b, x ³ 0 , we construct an auxiliary

program

min
s
...


y1 +  + ym
Ax + y = b
x ³0
y ³0

Initialization of this problem is easy; we simply let x = 0 and all the y be
basic
...
We conclude that the
original problem is feasible if and only if the auxiliary problem has 0
optimal cost; in which case x is a feasible solution of our original problem
...




It might be the case, however, that the problem ends with a zero-cost
solution (x *, 0 ) and basis B that has one or more of the yi in the basis (at
0 level)
...

It is also clear that once we have found this new basis matrix, the same
solution x * is valid for that basis
...




It remains to discuss how we can determine, from the final tableau of the
auxiliary problem, which variables to bring into the basis
...
This will be our leaving row
...
We
claim that Acol j is linearly independent of the other columns of A
in the basis
...
Thus, since our row corresponds to an
artificial variable, it is clear that every row corresponding to a
“real” variable that is in the basis will have a 0 in that row
...


Daniel Guetta, 2010

Optimization I Notes

Page 23


We now simply pivot, driving  out of the basis, and bringing jth
in
...




[Note that our assumption A is full rank precludes that possibility
that an entire row of B -1A is 0; thus, the method above always
works
...


o

The Big-M Method


An alternative method is to create a problem of the form above, but
minimize a function of the form c ⋅ x + M å i yi , where M is kept as a
large undetermined parameter
...




Anti-cyling Rules
o

If a vertex is degenerate, it is possible that q* = 0 at that vertex
...
Sometimes, this can happen many
times before we leave a vertex, and in some cases, the process returns us to the
basis we started with – in that case, the simplex algorithm cycles
...


o

Definition: u is lexicographically larger than v if the first nonzero component of
u – v is positive
...




For our entering variable, look at the rows which will need to be reduced
by the operation (ie: rows for which the pivot column is positive)
...


Daniel Guetta, 2010

Optimization I Notes


Page 24

It can be shown (p 110 of B&T) that under this pivoting rule, the simplex
algorithm will always terminate in a finite number of steps, provided that
every row is lexicographically positive at the start of the algorithm (if this
is not the base, we can simply re-arrange columns of B -1A to ensure that
the first columns of the tableau form the identity matrix)
...




It is also known to result in an algorithm in which cycling never occurs
...
t
...


Proof: First note that by the definition of a basic solution, the rows of M are
linearly independent, and so there is a vector that satisfies the equation above
...

Now:

Daniel Guetta, 2010

Optimization I Notes

Page 25

(y



,w



)=c



M

-1

æB -1 -B -1N ö÷
ç
= c , c çç
÷÷
I ÷÷ø
çè 0
= cBB -1 , cN - cBB -1N

(


B


N

)

(

= (p, c )

)

Since the reduced costs must be positive, this proves our theorem
...

The fact w > 0 has an interesting geometrical explanation
...
If this
were not the case, we would be able to move along that equality
constraint while decreasing the objective function
...
If this were not the case, it would be
possible to move away from the constraint while decreasing the objective
function
...
It should be clear that c needs to be contained in the cone defined by the two
directions; if it wasn’t the case, we’d be able to decrease the objective function by
moving in an opposite direction to c without violating the constraints
...
We saw above that c  h j ³ 0 for all
nonbasic j at an optimal solution
...


Daniel Guetta, 2010

Optimization I Notes

o

Page 26

Now, consider that the constraint in the previous theorem can be written as

æB N ö÷
ç
÷÷ = y A + w 
c  = y  , w çç
çè 0 I ÷÷ø

(

)

(

)

w = 0 , w ³ 0

Now, if we relax the requirement that the first m components of w be 0

Ay + w = c
This leads us to define the dual problem, with constraints Ay £ c , and y free:

max b ⋅ y s
...
Ay £ c
o

This already gives us some insight into complementary slackness; the dual is
basically equivalent to the primal, provided that w = 0 for the first m
components; ie: those components that are in the basis
...


o

The w (ie: the dual slacks) are none other than the reduced costs of the original
problem
...




We also have that Ay £ c  y A £ c  , and since x ³ 0 , y Ax £ c ⋅ x
...

o

Corollary: If x is primal feasible, and y is dual feasible, and b ⋅ y = c ⋅ x , then x
and y are optimal solutions to their respective linear programs
...
The answer is provided by…



…Strong duality
o

Theorem:


If either the primal problem or the dual problem has a finite optimal
solution, then so does the other, and min c ⋅ x = max b ⋅ y
...


(Note: the converse of the second statement is not true – it still leaves the
possibility that both problems are infeasible)
...
We then have
æc ö÷
ç
c - Ay = çç B ÷÷÷ - B 
çècN ÷ø

(

æ c -c
ö÷ æ 0 ö÷
ç
B
B
÷÷ = çç ÷÷ ³ 0
N  y = çç
 -
ç
çècN - N B cB ø÷÷ çècN ÷÷ø

)

And so the solution is dual feasible [this is a reformulation of the fact we
proved above; that we can write c = Ay + w, w ³ 0 ]
...



If c ⋅ x  -¥ , the dual cannot be feasible, because any feasible y would
result in a lower bound on c ⋅ x
...
At every iteration of the simplex
method, c ⋅ x = b ⋅ y still holds, but some of the reduced costs might be negative,
and so the problem is not dual feasible
...
An example is
Farkas’ Lemma
...
Ax = b, x ³ 0
2
...
The first statement implies that b is in the cone formed by the columns of
A
...
The second statement implies that y makes an obtuse angle will all the
columns of A, but an acute angle with b
...

Proof: Consider the primal-dual pair
(P)

min
s
...
t
...




If (D) is unbounded, (2) has a solution
...


Finally, we note that since the dual is feasible (y = 0 works), then by Strong
Duality, (P) is infeasible if and only if (D) is unbounded
...

In this case, it is easy to show that both (1) and (2) cannot have solutions:
y  (1)  y Ax = y ⋅ b

(2)x  y Ax £ 0 

This is clearly impossible if b ⋅ y > 0
...
To see why, consider the LP
min c ⋅ x s
...
Ax ³ b

And consider a basic feasible solution x * , and let Atight be the matrix of
constraints that happen to be satisfied there, so that Atightx * = b (the other
constraints, contained in Aslack

satisfy Aslackx * > b )
...

Thus, Farkas’ Lemma tells us that if there are no downhill feasible directions, c
must lie in the cone of the normals of the active inequality constraints
...
t
...
t
...
t
...
t
...
Now, consider that:


LHS of the above = 0



RHS of the above = 0



Optimality, by the corollary to weak duality

Daniel Guetta, 2010

Optimization I Notes


Page 30

RHS = 0

and the last statement implies the first
...

o

This makes intuitive sense in light of the above – it is only where the constraints
are tight that the Lagrange mutlipliers can be anything apart from 0, so as to
“penalize” departure from these constraints
...


Or, more general, x is a solution to the problem minx f (x ) s
...
g (x ) £ 0 , h(x ) = 0
if and only if



{

}



x f (x ) + mg (x ) + l h(x ) = 0 [Stationarity]



g (x ) £ 0 , h(x ) = 0 [Primal feasibility]



m ³ 0 [Dual feasibility]



mi gi (x ) = 0 for all i [complementary slackness]

Strict complimentary slackness
o

Consider a situation in which c is a linear combination of a single normal at x:

In this case, we have dual degeneracy – one of the reduced costs/optimal dual
variable slacks is equal to 0
...
This implies that primal non-uniqueness implies dual degeneracy
...

o

We say a solution satisfies strict complimentary slackness if the dual problem is
non-degenerate
...
Every linear program has at least one optimal solution which
satisfies strict complimentary slackness (in the case above, any solution along the
thick dotted line would do the trick)
...




Economic interpretation of duality
o

Consider a problem with optimal solution
æ * ö æ -1 ö
çx B ÷÷ ççB b ÷÷
ç
x = ç * ÷÷ = ç
÷
çèçx N ÷ø èç 0 ø÷÷
*

o

Consider what happens when b is changed to bˆ = b + dei
...


o

This also makes sense in terms of geometric interpretation above
...

Clearly, if constraint j changes by 1 unit, the amount we move along c is the
projection of that constraint onto c, which is none other than p j
...


Daniel Guetta, 2010

Optimization I Notes

o

Page 32

We can also ascribe an economic interpretation to the dual program itself
...
The constraint requires the total
cost of transportation of unit material from a given source to a given sink
be less than or equal to our cost for transportation along that path
...




The Dual Simplex Algorithm
o

The primal simplex algorithm effectively involved jumping from solution to
solution while maintaining primal feasibility and complementary slackness and
looking for dual feasibility
...


o

Consider a basis consisting of m linearly independent columns of A, with the
following tableau:

B -1A

B -1b

cT

-cTB B -1b

Or, in more detail:


-1


col 1

B A


c1

-1

col n

 B A




cn

x B ,1

x B ,m
-cTB x B

We consider a solution which might be primal infeasible (ie: some of the xB may
be negative) but primal optimal (ie: all the reduced costs are positive)
...
Once again, we describe the operations involved in terms of the array
a:

(aij )

xB

cT

-z

The steps involved are as follows:


Look at the components of xB
...

Else, pick a negative one; this is the row i, a row i on which we will pivot;
it will exit the basis
...




Otherwise, for each j such that a jrow i < 0 , compute c j / | a jrow i ; pick the
smallest ratio
...




Perform a pivot operation as for the standard simplex method
...
[Strictly
speaking, this is an ambiguous statement, because the dual is not in standard
form – more accurately, it is a version of simplex adapted to problems expressed
in terms of inequalities]
...
t
...
t
...
It
will be important, in doing this, to decide whether a change in a given parameter results
in a change in basis or not
...
This gives the new problem
min

c x

s
...


Ax + Acol n +1x n +1 = b
x ³ 0 , x n +1 ³ 0

o

We note that (x * , 0) is a basic feasible solution, with the same basic matrix B; so
we only need to check optimality
...


Daniel Guetta, 2010

Optimization I Notes

o

Page 35

Otherwise, it is a simple matter to add an extra column to the simplex tableau
and perform a few more iterations
...
If x *

satisfies this

constraint, then it is an optimal solution to the new problem
...
The matrix A is then replaced by

é A
0 ùú
A = êê row m +1
-1úú
êëa
û
We introduce a new basis that includes all the variables in B plus our new slack
variable
...

o

We want to figure out a way to add this new constraint to our tableau (which,
recall, contains B -1A )
...
We have that
é
B -1A
ê
B A = ê row m +1 -1
B A - a row m +1
êëa B
-1

0ùú
1 úú
û

And also that the reduced cost do not change, because the objective coefficient of
the new slack variable is 0:
éc 
ëê

o

0ùú - éêcB
û ë

0ùú B -1A = éêc  - c B -1A
û
ë

0ùú
û

The above is hardly useful in terms of practically writing the new tableau
...
In particular,
this involves:


Multiplying the row by –1, to obtain a 1 in the last column
...
But

remember that
o

The jth row will contain a 1 in the column corresponding to
the jth basic variable
...

Thus, these operations are equivalent to ensuring that every
component of the last row corresponding to basic variables is 0
...
This, however, is rather simple – the old basic variables remain
basic, and the slack variable picks up the slack from the inequality
...
If x *

satisfies this

constraint, then it is an optimal solution to the new problem
...
t
...




Changing the vector b
o

Imagine now that we change the vector b to bˆ = b + de j
...
As we
saw above, the change in the objective function will be dp j
...
In that case, we simply re-solve the problem using the dual simplex
...
Primal feasibility is clearly
not affected
...
Provided the vector c
remains within the cone of normals at the basic feasible solution, the solution
remains optimal
...




Parametric programming
o

Consider a linear program of the form
min
s
...


(c + qd ) ⋅ x
Ax = b
x ³0

Daniel Guetta, 2010

Optimization I Notes

Page 38

We denote the optimal value of this program by z(q)
...

o

Claim: The function z(q) is piecewise linear and concave
...

Proof: Two parts:


Proving linearity is simple; let q1 and q2 be two values of q for which the
same basis B is optimal
...



Proving concavity is slightly more involved
...
Consider any q1 and q2 , and define q3 = lq1 + (1 - l)q2 ,
where l Î [0,1]
...


Network flow problems


The network flow problem
o

I ( j ) = {(i, j ) : (i, j ) Î  }

Let

be the set of edges incoming into i, and

O(i ) = {(i, j ) : (i, j ) Î  } be the set of edges leaving node i
...
Then the network flow problem is

min å (i , j )Î cij fij s
...

o

å

f - å (i , j )ÎO (i ) fij = bj "j Î  , 0 £ fij £ uij

(i , j )ÎI ( j ) ij

The first constraint can concisely be expressed as Af = b where each row of A
represents a node and each column represents an arc
...


o

To deal with lower bound mij on flows, simply define fij = fij - mij , uij = uij - mij
and b = b - Am
...
t
...



Due to the structure of A, we in fact have pi - p j £ cij "(i, j ) Î 
...
As such,
we can assume pn = 0



Complementary slackness requires that pi - p j = c for all arcs on which
something flows (ie: on which fij ¹ 0 )
...






The pi represent shadow prices of increasing bi by a certain amount
...
The cost of such a circulation
is c ⋅ h , and “pushing” q units of the flow means setting f ¬ f + qh
...

Theorem: A vector is a spanning tree solution if and only if it is a basic solution
of the minimum-cost flow problem
...


o

Once we have such a solution, we can compute reduced costs for each arc not in
the spanning tree as cij = cij - (pi - p j )
...
Else,
choose a negative one
...


o

Note that since A only contains 0s or +1s, AB can be rearranged to contain only
+1 on its diagonal
...
Finally, f = AB-1b and l = cBAB-1 , and so
provided c and b are integer-valued, the primal and dual solutions also are
...
Finding a negative-cost cycle in the initial network is like finding one in
the residual network
...




The max-flow problem
o

Example: m identical machines
...
Create a node for
each job and a node for each time period (list the ri and di in order, and split
time at each point)
...
Arcs from time-periods with capacity

Daniel Guetta, 2010

Optimization I Notes

Page 41

m ´ length of time period indicate how much is done in that time period
...
Our scheduling problem is then a maximum-flow problem
...


o

To find an augmenting path, we use a labeling algorithm
...
Start with I = {s}
...
If so, add all the possible target nodes to I
...


o

A cut S is a subset of  such that s Î S and t Ï S
...
Clearly, the max flow is < the min
cut
...
Thus, max flow = min cut

---