Algorithmic Game Theory and Applications
Lecture 7:
The LP Duality Theorem
Kousha Etessami AGTA: Lecture 7
Copyright By PowCoder代写 加微信 powcoder
recall LP’s in “Primal Form”
Maximize c1 x1 +c2 x2 +…+cn xn
Subject to:
a1,1 x1 +a1,2 x2 +…+a1,n xn ≤ b1 a2,1 x1 +a2,2 x2 +…+a2,n xn ≤ b2 … … am,1 x1 +ai,2 x2 +…+am,n xn ≤ bm
x1,…,xn ≥0
An LP can concisely be represented in
matrix notation:
Define the (m × n)-matrix A by: (A)i,j = ai,j. Define (column) vectors x = [x1, . . . , xn]T ,
b = [b1,…,bm]T & c = [c1,…,cn]T.
The LP is:
Maximize cT x Subject to: Ax ≤ b x1,…,xn ≥0
AGTA: Lecture 7
Solving LPs against an Adversary
Suppose you want to optimize this Primal LP:
Maximize cT x Subject to: Ax ≤ b x1,…,xn ≥0
Suppose an “Adversary” comes along with a m-vector y ∈ Rm, y ≥ 0, such that:
For any solution, x, you may have for the Primal:
cTx ≤ (yTA)x (becausex≥0&cT ≤yTA) = yT (Ax)
≤ yTb (becauseyT ≥0&Ax≤b) So, the adversary’s goal is to minimize yT b, subject
tocT ≤yTA,i.e.,tooptimizethefollowingDualLP:
Minimize bT y Subject to: AT y ≥ c y1,…,ym ≥0
AGTA: Lecture 7
The LP Duality Theorem
As we saw, a feasible value of the primal LP is at most the optimal value of the dual, i.e.:
Proposition (“Weak Duality”) If x∗ ∈ Rn and y∗ ∈ Rm are optimal feasible solutions to the primal and dual LPs, then:
cTx∗ ≤bTy∗ Amazingly, equality holds!
Theorem(“Strong Duality”, von Neumann’47) One of the following four situations holds:
1. Both the primal and dual LPs are feasible, and for any optimal solutions x∗ of the primal and y∗ of the dual:
cTx∗ =bTy∗
2. The primal is infeasible and the dual is unbounded.
3. The primal is unbounded and the dual is infeasible.
4. Both LPs are infeasible.
AGTA: Lecture 7
Simplex and the Duality Theorem
• It turns out, LP Duality follows from the “proof of correctness” of the Simplex algorithm (which we didn’t provide).
• In fact, suppose Simplex on the Primal LP halts and produces an optimal solution vector x∗.
Let y∗ = −cˆ , where cˆ is the coefficient
of the “slack variable” xn+j in the last objective
function f(x) associated with the final dictionary for the primal LP. This defines y∗ ∈ Rm, and it turns out the following holds:
Facty∗ ≥0,ATy∗ ≥c,andcTx∗ =bTy∗.
• So, using Simplex, we can actually compute an optimal solution for the dual while we compute an optimal solution for the primal (or find out neither exists).
AGTA: Lecture 7
Complementary Slackness
Useful Corollary of LP Duality: solutions x∗ and y∗ to the primal and dual LPs, respectively, are both optimal if and only if both of the following hold:
• For each primal constraint, (Ax)i ≤ bi, i = 1,…,m, either
(Ax∗)i = bi or yi∗ = 0 (or both).
• For each dual constraint, (AT y)j ≥ cj , j = 1,…,n, either
(ATy∗)j = cj or x∗j = 0 (or both). Proof By weak duality
cT x∗ ≤ ((y∗)T A)x∗ = (y∗)T (Ax∗) ≤ (y∗)T b
By strong duality each inequality holds with equality
precisely when x∗ and y∗ are optimal.
So, when optimal, (((y∗)T A) − cT )x∗ = 0. Sinceboth((y∗)TA)−cT)≥0andx∗ ≥0,itmust be that for each j = 1,…,n,
( A T y ∗ ) j = c j o r x ∗j = 0
Likewise, when optimal, (y∗)T (b − Ax∗) = 0, and thus, for each i = 1,…,m, (Ax∗)i = bi or yi∗ = 0.
AGTA: Lecture 7
general recipe for LP duals
If the “primal” is:
Maximize cT x
Subject to:
(Ax)i ≤ bi , i = 1,…,d, (Ax)i = bi , i = d + 1, . . . , m, x1,…,xr ≥0
Then the “dual” is:
Minimize bT y
Subject to:
(ATy)j ≥cj,j=1,…,r, (ATy)j =cj,j=r+1,…,n, y1,…,yd ≥0
Strong Duality holds also in this more general setting. Fact: The “dual” of the “dual” is the primal.
AGTA: Lecture 7
Duality and the Minimax Theorem
Recall the LP for solving Minimax for Player 1 in a zero-sum game given by matrix A:
Maximize v
Subject to:
v−(xTA)j ≤0forj=1,…,m2, x1+…+xm1 =1,
xi ≥ 0 for j = 1, . . . , m1.
What is the Dual to this LP? It can be shown to be:
Minimize u
Subject to constraints: u−(Ay)i ≥0fori=1,…,m1, y1+…+ym2 =1
yj ≥0forj=1,…,m2.
This is exactly the LP for Player 2’s optimal strategy!
Thus, the minimax theorem follows from Duality: the optimal value for the two LPs is the same.
AGTA: Lecture 7
In fact, LP Duality can also be “derived” from the Minimax Theorem. Consider (A a (m × n)-matrix):
Maximize cT x Subject to: Ax ≤ b x1,…,xn ≥0
Proof (sketch) that Minimax ⇒ LP-duality: Consider the zero-sum payoff matrix:
0 A −b B=−AT 0 c
This is a symmetric zero-sum game: B = −BT. By a simple exercise, such a game must have minimax value 0, and every minmaximizer for player 1 is also a maxminimizer for player 2. Consider a symmetric minimax profile:
((Y∗,X∗,z),(Y∗,X∗,z))
for this game. Here Y ∗ is a (row) vector of length
m,andX∗ isa(row)vectoroflengthn,andz∈R. AGTA: Lecture 7
From Minimax to LP Duality
more in Minimax ⇒ LP-duality Suppose z > 0, in the minimax strategy (Y ∗, X∗, z).
Note that, by the Minimax Theorem, we have AX∗−bz≤0 and cz−ATY∗≤0
Letting y∗ = (1/z)Y ∗, and x∗ = (1/z)X∗, we would have Ax∗ ≤ b and AT y∗ ≥ c, i.e., feasible solutions for the LP and its Dual.
Moreover, by Useful Corollary to Minimax, player 1 can switch to ANY pure strategy j in its “support” (i.e., where x1(j) > 0) and not change its profit. Let it switch to the last row (i.e., letting z = 1). Then we also have: bY∗ −cX∗ = 0, and hence by∗ − cx∗ = 0. Thus,
by∗ = cx∗ The only thing left to prove is:
Claim If both the LP and its Dual are feasible, the game B has some minimax profile where z > 0.
AGTA: Lecture 7
• The claim can be proved (see [Dantzig’51], [Raghavan,HGT,Ch.20]) using facts related to the “geometry” of LP and Minimax: specifically the “Farkas lemmas”.
• Such “ ” can actually be proved very nicely using Fourier-Motzkin elimination. Here is a Farkas lemma:
Ax ≤ b has no solutions if and only if there exists y ≥ 0 such that yT A = 0 and yT b < 0.
(HW1 asks you to prove this.)
• This proof is somewhat unsatisfactory because the Farkas lemmas are essentially “equivalent” to LP- duality. (A recent modification of this proof, by [Adler 2013], avoids the use of Farkas lemmas.)
AGTA: Lecture 7
Significance of LP Duality
• The Duality Theorem is an extremely important fact in subjects like mathematical economics and combinatorial optimization.
So much so that we can not possibly do it justice.
• Often, you can “learn something” about an LP by looking at its dual.
• In Economics, one often sets up an LP to optimize some economic goal. Often, the dual LP can be meaningfully interpreted as a problem of optimizing some real economic “counter” goal.
The fact that the optimal solutions of the two goals are the same is very powerful.
• Duality has many consequences in algorithms.
For example, duality implies that LPs can be solved in “NP ∩ co-NP”.
(Of course, we know from [Khachian’79] that the LP problem is in “P”.)
AGTA: Lecture 7
more on algorithmic significance
• approximation algorithms: hard combinatorial optimization problems can often be formulated as “Integer Linear Progams” (ILPs). One can often use the “LP-relaxation” of the ILP together with its Dual to find approximate solutions and to bound the proximity of the approximate solution to the optimal. (See, e.g., [Vazirani’2001].)
• Many important results in combinatorics can be viewed as particular manifestations of LP Duality.
– Max-Flow Min-Cut Theorem; Hall’s Theorem;
Dilworth’s Theorem; Konig-Egervary Theorem......
Each result says “the maximum value of one useful quantity associated with a combinatorial object is the same as the minimum value of another useful quantity associated with it.”
These follow from LP-Duality: dual LPs for these “complementary” quantities can be set up (with solutions that consist necessarily of integers, due to the LPs’ structure).
AGTA: Lecture 7
food for thought
(in this case “thought for food”)
• Recall the “Diet Problem”. It has the form:
Minimize cT x Subject to: Ax ≥ b x1,...,xn ≥0
• Construct the dual to this LP.
• What do the dual variables “mean” in the context
of the diet problem?
Try to come up with an interpretation.
(Hint: try to assign consistent “units of measure” to the primal variables, constants, and coefficients. These will determine the “units of measure” of the dual variables, and will guide you toward an interpretation.)
• What is the dual LP trying to optimize? AGTA: Lecture 7
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com