Optimization - Linear Programming and Lagrangian Methods

Prévia do material em texto

Optimization
Linear Programming
P: maximize cTx s.t. Ax ≤ b, x ≥ 0
D: minimize λT b s.t. ATλ ≤ c, λ ≥ 0
The simplex algorithm. Slack variables. The two-phase algorithm — artificial variables.
Shadow prices.
Complementary slackness
P D
variables x constraints λ
xi basic (xi 6= 0) =⇒ constraint: tight (vi = 0)
xi non-basic (xi = 0) ⇐= constraint: slack (vi 6= 0)
constraints variables λ
constraint: tight (zi = 0) ⇐= λi basic (λi 6= 0)
constraint: slack (zi 6= 0) =⇒ λi non-basic (λi = 0)
Theorem
The feasible set of an LP problem is convex.
Proof
Write the problem as minimize cTx s.t. Ax = b, x ≥ 0, and let Xb be the feasible set. Suppose
x, y ∈ Xb, so x, y ≥ 0 and Ax = Ay = b. Consider z = λx + (1 − λ)y for 0 ≤ λ ≤ 1. Then
zi = λxi + (1− λ)yi ≥ 0 for each i. So z ≥ 0. Secondly,
Az = A(λx+ (1− λ)y) = λAx+ (1− λ)Ay = λb+ (1− λ)b = b.
So z ∈ Xb and hence Xb is convex.
Theorem
Basic feasible solutions ≡ extreme points of the feasible set.
Proof
Suppose x is a b.f.s. Then ∃ a basis B and non-basis N such that the non-basic components of
x satisfy xN = 0. Suppose x is not extreme. Then ∃y, z such that x lies on the line segment
between y and z and hence yN = zN = 0 (proof omitted). Furthermore, y and z are feasible, so
AByB = ABzB = b and this gives AB(yB − zB) = 0. But as AB is non-singular (by assumption)
we have yB = zB and hence y = z. This is a contradiction, and so x must be extreme.
Now suppose x is an extreme point of Xb. Since x ∈ Xb we know it is feasible — we just need
to show that it is basic.
1
Suppose it is not a b.f.s. Then the number of non-zero coordinates, p say, is greater than m. Let
P = {i : xi > 0} and Q = {i : xi = 0}. Since x is feasible, Ax = APxP+AQxQ = b⇒ APxP = b.
But this is m equations in p > m variables, so ∃ non-zero yP s.t. AP yP = 0. We put yQ = 0
and y =
( yP
yQ
)
.
Consider x+ y and x− y for small . For  > 0 small enough these two points are both feasible
since A(x± y) = Ax± Ay = b, and x± y ≥ 0 (for small  since yi > 0 implies xi > 0). Hence
x = 12(x+ y) +
1
2(x− y)
and so x is not extreme. This is a contradiction, and hence x must be a b.f.s.
Theorem
If an LP has a finite optimum then there is an optimal basic feasible solution.
Proof
See lecture notes.
Theorem (weak duality)
If x is feasible for P and λ is feasible for D then cTx ≤ bTλ. In particular, if one problem is
feasible then the other is bounded.
Proof
Let L(x, z, λ) = cTx − λT (Ax + z − b) where Ax + z = b. Now for x and λ satisfying the
conditions of the theorem,
cTx = L(x, z, λ) = (cT − λTA)x− λT z + λT b ≤ λT b.
Theorem (sufficient conditions for optimality)
If x∗, z∗ are feasible for P and λ∗ is feasible for D, and x∗, z∗, λ∗ satisfy complementary slackness,
then x∗ is optimal for P and λ∗ is optimal for D. Furthermore cTx∗ = λ∗T b.
Proof
Let L(x, z, λ) = cTx− λT (Ax+ z − b). Then
cTx∗ = L(x∗, z∗, λ∗)
= (cT − λ∗TA)x∗ − λ∗TAx∗ + λ∗T b
= λ∗T b
by complementary slackness. But for all x feasible for P we have cTx ≤ λ∗T b (by the weak
duality theorem) and this implies that for all feasible x, cTx ≤ cTx∗. So x∗ is optimal for P.
Similarly λ∗ is optimal for D, and the problems have the same solutions.
Theorem (strong duality: necessary conditions for optimality)
If both P and D are feasible then ∃ x, λ satisfying the conditions above.
2
Lagrangian Methods
The Lagrangian
For the general optimization problem
P: minimize f(x) s.t. g(x) = b, x ∈ X
the Lagrangian is
L(x, λ) = f(x)− λT (g(x)− b).
The Lagrangian sufficiency theorem
If x∗ and λ∗ exist such that x∗ is feasible for P and
L(x∗, λ∗) ≤ L(x, λ∗) ∀x ∈ X,
then X∗ is optimal for P.
Proof
Define
Xb = {x : x ∈ X and g(x) = b}.
Note that Xb ⊆ X and that for any x ∈ Xb
L(x, λ) = f(x)− λT (g(x)− b) = f(x).
Now
f(x∗) = L(x∗λ∗) ≤ L(x, λ∗) = f(x), ∀x ∈ Xb.
Thus x∗ is optimal for P.
Theorem (weak duality)
For λ ∈ Y , let
L(λ) = min
x∈X L(λ, x)
Then for any x ∈ Xb, λ ∈ Y ,
L(λ) ≤ f(x).
Proof
For x ∈ Xb, λ ∈ Y ,
f(x) = L(x, λ) ≥ min
x∈Xb
L(x, λ) ≥ min
x∈X L(λ, x) = L(λ).
Solution of general optimization problems
1. Find Y , the set of λ such that L(x, λ) has a finite minimum.
2. Find x(λ), the value of x at which this minimum is obtained, for all λ ∈ Y .
3. Find x∗ = x(λ∗), where x∗ is feasible for P.
4. Then x∗ is optimal for P.
3
Applications
Two person zero-sum games
Let A be the pay-off matrix for the game. A pair of strategies p and q with
∑
pi = qi = 1,
pi ≥ 0 and qi ≥ 0 are optimal if
pTA ≥ v, Aq ≤ v and pTAq = v
for some v ∈ R, where v is the value of the game.
The max flow/min cut theorem
The maximal flow value through a network is equal to the minimum cut capacity.
Proof
Define f(X,Y ) =
∑
i∈X,j∈Y xij , the flow from X to Y . Let the set of nodes of the network be
represented by N = {1, 2, . . . , n}. Let (S, S¯) be a cut and (xij) be a feasible flow with value v.
Note that f(X,N) = f(X,S) + f(X, S¯). Since (xij) is feasible, we have
∑
j
xij −
∑
j
xji =

v i = 1
0 i 6= 1, n
−v i = n
Summing this equality over i ∈ S we obtain
v =
∑
i∈S
∑
j
(xij − xji)
=
∑
i∈S
∑
j
xij −
∑
i∈S
∑
j
xji
= f(S,N)− f(N,S)
= f(S, S) + f(S, S¯)− f(S¯, S)− f(S, S)
= f(S, S¯)− f(S¯, S)
≤ f(S, S¯)
≤ C(S, S¯)
where C(S, S¯) is the capacity of the cut (S, S¯). So any flow is ≤ any cut capacity, and in
particular the maximal flow is ≤ the minimal cut capacity.
Now let f be a maximal flow, and define S ⊆ N recursively by:
1. 1 ∈ S
2. i ∈ S and xij < cij =⇒ j ∈ S
3. i ∈ S and xji > 0 =⇒ j ∈ S
So S is the set of nodes to which we can increase the flow. Now if n ∈ S then we can increase
the flow along some path to n and so the flow is not maximal. Hence n ∈ S¯ = N \ S and so
4
(S, S¯) is a cut. From the definition of S we know that for i ∈ S and j ∈ S¯ we have xij = cij and
xji = 0, so in the formula above we get
v = f(S, S¯)− f(S¯, S) = f(S, S¯) = C(S, S¯).
Therefore the maximal flow is equal to the minimal cut capacity.
Sufficient conditions for a minimum cost circulation
If (xij) is a feasible circulation and there exists λ such that
xij =
{
c−ij if dij − λi + λj > 0
c+ij if dij − λi + λj < 0
c−ij ≤ xij ≤ c+ij if dij − λi + λj = 0
then (xij) is a minimal cost circulation. The λi are known as node numbers or potentials. In
particular, if c−ij = 0 and c+ij =∞ then the conditions are
dij − λi + λj ≥ 0
(dij − λi + λj)xij = 0.
Proof
Apply the Lagrangian sufficiency theorem.
The transportation algorithm
1. Pick an initial feasible solution with m+ n− 1 non-zero flows (NW corner rule).
2. Set λ1 = 0 and compute λi, µi using dij − λi + µj = 0 on arcs with non-zero flows.
3. If dij − λi + µj ≥ 0 for all (i, j) then the flow is optimal.
4. If not, pick (i, j) for which dij − λi + µj < 0.
5. Increase flow in arc (i, j) by as much as possible without making the flow in any arc
negative. Return to 2.
5