当前位置:网站首页>【学习笔记】线性规划对偶定理
【学习笔记】线性规划对偶定理
2022-08-11 10:38:00 【OneInDark】
注:向量并不一定用粗体标明,尤其是 x , y x,y x,y,因为它们的粗体太丑。
Definition. 向量比较 x < y x<y x<y 等价于 ∀ i , x i < y i \forall i,\;x_i<y_i ∀i,xi<yi,即在每个分量上做数值比较。
半空间( affine halfspaces \text{affine halfspaces} affine halfspaces):形如 { x : a T x ⩽ b } \{x:\mathbf a^{\sf T}x\leqslant b\} { x:aTx⩽b},其中 x ∈ R dim a x\in\Reals^{\dim\bf a} x∈Rdima 。
多面形( polyhedra/polyhedron \text{polyhedra/polyhedron} polyhedra/polyhedron):有限个半空间的交。它等价于 P = { x : A x ⩽ b } P=\{x:\mathscr Ax\leqslant\bf b\} P={ x:Ax⩽b},其中 A \mathscr A A 是 m × n m\times n m×n 矩阵, b ∈ R m \mathbf b\in\Reals^m b∈Rm 而 x ∈ R n x\in\Reals^n x∈Rn 。
多胞体( polytope \text{polytope} polytope):有限个向量生成的凸包。等价于有限大小的 p o l y h e d r o n \rm polyhedron polyhedron 。
Comment. 我并不确定上面这些东西的中文译名应为什么。
Proposition. 若 x ∉ P x\notin P x∈/P 其中 P P P 是 p o l y h e d r a \rm polyhedra polyhedra,则存在半空间 C C C 使得 P ⊆ C P\subseteq C P⊆C 且 x ∉ C x\notin C x∈/C 。
该定理的证明很难脱离几何学的支持:需要找到 y ∈ P y\in P y∈P 使得 ∥ x − y ∥ \Vert x-y\Vert ∥x−y∥ 最小,而 y y y 的存在性由其几何直观性质保证。但倘若承认几何在其中的运用,那么该定理是显然的。故此处不给出证明。
Lemma.( Farkas’ lemma \text{Farkas' lemma} Farkas’ lemma) A x = b \mathscr Ax=\mathbf b Ax=b 有 x ⩾ 0 x\geqslant\mathbf 0 x⩾0 的解,当且仅当 A T y ⩾ 0 ∧ b T y < 0 \mathscr A^{\sf T}y\geqslant\mathbf 0\land \mathbf b^{\sf T}y<0 ATy⩾0∧bTy<0 无 y ∈ R n y\in\R^n y∈Rn 的解。
Proof. 当 A x = b \mathscr Ax=\mathbf b Ax=b 有解时,反证法设 y y y 有解,则
0 > b T y = ( A x ) T ⋅ y = x T ( A T y ) ⩾ 0 0>\mathbf b^{\sf T}y=(\mathscr Ax)^{\sf T}\cdot y=x^{\sf T}(\mathscr A^{\sf T}y)\geqslant 0 0>bTy=(Ax)T⋅y=xT(ATy)⩾0
当 A x = b \mathscr Ax=\mathbf b Ax=b 无解时,设 a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a1,a2,…,an 为 A \mathscr A A 的列向量,令 C C C 为它们张成的凸包,则 x x x 无解等价于 b ∉ C \mathbf b\notin C b∈/C,故存在半平面分割 b \mathbf b b 和 C C C,即存在向量 y y y 使得 b T y < 0 \mathbf b^{\sf T}y<0 bTy<0 且 x T y ⩾ 0 ( x ∈ C ) x^{\sf T}y\geqslant 0\;(x\in C) xTy⩾0(x∈C),后者蕴含 A T y ⩾ 0 \mathscr A^{\sf T}y\geqslant 0 ATy⩾0 。 ■ \blacksquare ■
Corollary. 设 P = { x : A x ⩽ b } ≠ ∅ P=\{x:\mathscr Ax\leqslant\mathbf b\}\ne\varnothing P={ x:Ax⩽b}=∅,则 ∀ x ∈ P , c T x ⩽ δ \forall x\in P,\;\mathbf c^{\sf T}x\leqslant\delta ∀x∈P,cTx⩽δ 等价于 ∃ y ⩾ 0 , A T y = c ∧ b T y ⩽ δ \exists y\geqslant 0,\;\mathscr A^{\sf T}y=c\land\mathbf b^{\sf T}y\leqslant\delta ∃y⩾0,ATy=c∧bTy⩽δ 。
Proof. 充分性:若 y y y 存在,则立刻有
A x ⩽ b * y T A x ⩽ y T b * c T x ⩽ y T b * c T x ⩽ δ \mathscr Ax\leqslant\mathbf b \implies y^{\sf T}\mathscr Ax\leqslant y^{\sf T}\mathbf b \implies\mathbf c^{\sf T}x\leqslant y^{\sf T}\mathbf b \implies\mathbf c^{\sf T}x\leqslant\delta Ax⩽b*yTAx⩽yTb*cTx⩽yTb*cTx⩽δ
必要性:它本质上是解方程
( y T λ ) ( A b 0 1 ) = ( c T δ ) \begin{pmatrix}y^{\sf T} & \lambda\end{pmatrix} \begin{pmatrix} A & b\\ 0 & 1\end{pmatrix} =\begin{pmatrix}\mathbf c^{\sf T} & \delta\end{pmatrix} (yTλ)(A0b1)=(cTδ)
的 y T , λ ⩾ 0 y^{\sf T},\lambda\geqslant 0 yT,λ⩾0 的解。由 Farkas’ lemma \text{Farkas' lemma} Farkas’ lemma 可知存在 z , μ ∈ R z,\mu\in\Reals z,μ∈R 使得
( A b 0 1 ) ( z μ ) ⩾ 0 and ( c T δ ) ( z μ ) < 0 \begin{pmatrix} A & b\\ 0 & 1\end{pmatrix} \begin{pmatrix}z \\ \mu\end{pmatrix}\geqslant 0 \quad\text{and}\quad \begin{pmatrix}\mathbf c^{\sf T}&\delta\end{pmatrix} \begin{pmatrix}z \\ \mu\end{pmatrix}<0 (A0b1)(zμ)⩾0and(cTδ)(zμ)<0
由前者知 μ ⩾ 0 \mu\geqslant 0 μ⩾0 。讨论 μ = 0 \mu=0 μ=0 和 μ > 0 \mu>0 μ>0 的情况,分别取 x = x 0 − γ z ( γ → + ∞ ) x=x_0-\gamma z\;(\gamma\rightarrow+\infty) x=x0−γz(γ→+∞) 和 x = − μ − 1 z x=-\mu^{-1}z x=−μ−1z 即可推出矛盾,完成证明。留作习题。 ■ \blacksquare ■
Theorem.( Duality theorem of linear programming \text{Duality theorem of linear programming} Duality theorem of linear programming) 令 A \mathscr A A 为 m × n m\times n m×n 矩阵, b ∈ R m , c ∈ R n \mathbf b\in\Reals^m,\;\mathbf c\in\Reals^n b∈Rm,c∈Rn,则
max { c T x : A x ⩽ b } = min { y T b : y ⩾ 0 ∧ A T y = c } \max\{\mathbf c^{\sf T}x:\mathscr Ax\leqslant\mathbf b\}=\min\{y^{\sf T}\mathbf b:y\geqslant\mathbf 0\land \mathscr A^{\sf T}y=\mathbf c\} max{ cTx:Ax⩽b}=min{ yTb:y⩾0∧ATy=c}
Proof. 设左式为 δ \delta δ,根据 Corollary \text{Corollary} Corollary 立刻有 ∃ y ⩾ 0 \exists y\geqslant 0 ∃y⩾0 使得 A T y = c ∧ b T y ⩽ δ \mathscr A^{\sf T}y=\mathbf c\land\mathbf b^{\sf T}y\leqslant\delta ATy=c∧bTy⩽δ 。这说明右式至多为 δ \delta δ 。
而左式不超过右式,因为 c T x = ( y T A ) ⩽ y T b \mathbf c^{\sf T}x=(y^{\sf T}\mathscr A)\leqslant y^{\sf T}\mathbf b cTx=(yTA)⩽yTb 。 ■ \blacksquare ■
平时常用的线性规划对偶中 x ⩾ 0 x\geqslant\mathbf 0 x⩾0,若将其统一至 A x ⩽ b \mathscr Ax\leqslant\mathbf b Ax⩽b 中,不难发现有
max { c T x : x ⩾ 0 ∧ A x ⩽ b } = min { b T y : y ⩾ 0 ∧ A T y ⩾ c } \max\{\mathbf c^{\sf T}x:x\geqslant\mathbf 0\land\mathscr Ax\leqslant\mathbf b\}=\min\{\mathbf b^{\sf T}y:y\geqslant\mathbf 0\land\mathscr A^{\sf T}y\geqslant\mathbf c\} max{ cTx:x⩾0∧Ax⩽b}=min{ bTy:y⩾0∧ATy⩾c}
这是对偶定理的特殊形式,也是平时惯用的对偶。 crashed \textsf{crashed} crashed 指出:互松弛定理是显然的。因此略去。
边栏推荐
猜你喜欢
HDRP shader to get shadows (Custom Pass)
How to determine the neural network parameters, the number of neural network parameters calculation
Qihua stores the future and interprets the origin of distributed
使用树莓派和OAK相机部署机器人视觉模型
Ali Ermian: Do you know how to tune the JVM?
Simple interaction between server and client
How to explain to my girlfriend what is cache penetration, cache breakdown, cache avalanche?
Deploying Robot Vision Models Using Raspberry Pi and OAK Camera
Use Function Compute to package and download OSS files [Encounter Pit Collection]
TIOBE - 2022年8月编程语言排行
随机推荐
SDUT数据库 SQL语句练习(MySQL)
Neuropathic pain classification picture Daquan, neuropathic pain classification
B端产品需求分析与优先级判断
Typora and basic Markdown syntax
【综合练习12】实现静态网页的相关功能
【luogu CF1286E】Fedya the Potter Strikes Back(字符串)(KMP)(势能分析)(线段树)
Gold Transfer(树上倍增)
What is the difference between the qspi interface and the ordinary four-wire SPI interface?
卷积神经网络梯度消失,神经网络中梯度的概念
【翻译】Drafting and Revision: Laplacian Pyramid Network for Fast High-Quality Artistic Style Transfer
安装nodejs
Primavera P6 Professional 21.12 Login exception case sharing
【UOJ 454】打雪仗(通信题)(分块)
AcWing 273. 分级(线性DP+结论)
Jetpack Compose学习(9)——Compose中的列表控件(LazyRow和LazyColumn)
HDRP shader to get shadows (Custom Pass)
数据库 SQL 优化大总结之:百万级数据库优化方案
Calculate the sum of an element of an array
当科学家决定搞点“花里胡哨”的东西
MySQL表sql语句增删查改_查询