线性优化之对偶理论

---

前言—为什么需要对偶

(参见知乎书树小数)

一. 如何转化为对偶

二. 强弱对偶

1. 弱对偶

2. 弱对偶推论

3. 强对偶

c^TX = b^Ty 可转化为松弛互补条件 解释：原问题和对偶问题有一个处于“active mode”就行。

4. 原问题和对偶问题的关系

存在与有界的关系

解得大小关系

Primal: X_B = A_B^-1 * bDual: y = C_B^T * A_B^-1

解的数量关系 无确定关系，依情况而定。

三. 举例应用

Production Planning

Game Theory 原问题为Player I 赢得最多钱 对偶问题则为Player 2 输得最多钱

Max Flow & Min Cut

四. 敏感度分析

Let Optimal Value be V Let Optimal Solution of P and D be x* y*

1. 改变b (Δb)

If (Δb)is small enough:

V(b) = b^T y*∇ V(b) = y*ΔV = Δb^T * ∇ V(b) = Δb^T * y*

因为b与解x有关，所以若b太大，x^*就可能小于0了，于是就换了个basis，结论就不成立了 Thus How samll is small? 新的x_B~为 Assume ∆b = λe i (e i is a vector with 1 at position i) 怎么确保新的x_B~ 仍然feasible呢？ 如此可知满足 λ 的步长都可。

2. 改变c (Δc)

If (Δc)is small enough:

V( c ) = c^T x*∇ V( c ) = x*ΔV = Δc^T * ∇ V( c ) = Δc^T * x*

因为c与reduced cost有关，所以若c太大，reduced cost 可能不全大于等于0，就不optimal了 Thus How samll is small? 1） j 属于 basic 2） j 属于 non-basic

如此可知满足 λ 的步长都可。