欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

最优化——对偶问题的性质(弱对偶性,强对偶性),对偶问题形式的书写(对偶规则)

程序员文章站 2022-06-23 11:26:50
对偶性质弱对偶性原对偶问题任何可行解的目标值都是另一问题最优目标值的界。(推论:原对偶问题目标值相等的一对可行解是各自的最优解)强对偶性原对偶问题只要有一个有最优解,另一个就有最优解,并且最优目标值相等。对偶问题解之间的关系线性规划与其对偶规则的关系互补松弛定理​原问题 max⁡CTX\max C^{T} XmaxCTX对偶问题 min⁡b⃗TY\min \vec{b}^{T} YminbTYs.t.AX≤b⃗s...

对偶性质

弱对偶性

原对偶问题任何可行解的目标值都是另一问题最优目标值的界。(推论:原对
偶问题目标值相等的一对可行解是各自的最优解)

强对偶性

原对偶问题只要有一个有最优解,另一个就有最优解,并且最优目标值相等。

对偶问题解之间的关系

最优化——对偶问题的性质(弱对偶性,强对偶性),对偶问题形式的书写(对偶规则)

线性规划与其对偶规则的关系

最优化——对偶问题的性质(弱对偶性,强对偶性),对偶问题形式的书写(对偶规则)

互补松弛定理

​ 原问题 max ⁡ C T X \max C^{T} X maxCTX 对偶问题 min ⁡ b ⃗ T Y \min \vec{b}^{T} Y minb TY
 s.t.  A X ≤ b ⃗  s.t.  A T Y ≥ C X ≥ 0 Y ≥ 0 \begin{array}{lll} \text { s.t. } A X \leq \vec{b} & \text { s.t. } A^{T} Y \geq C \\ X \geq 0 & \quad\quad Y \geq 0 \end{array}  s.t. AXb X0 s.t. ATYCY0
X ^ \hat{X} X^ Y ^ \hat{Y} Y^ 分别是原问题和对偶问题的可行解,则它 们分别是各自问题最优解的充要条件是满足互补松弛定理等式
Y ^ T ( b ⃗ − A X ^ ) = 0 , X ^ T ( A T Y ^ − C ) = 0 \hat{Y}^{T}(\vec{b}-A \hat{X})=0, \hat{X}^{T}\left(A^{T} \hat{Y}-C\right)=0 Y^T(b AX^)=0,X^T(ATY^C)=0
含义:如果原问题某个不等式是松的(不等于0), 则其相应的对偶变量必须是紧的(等于0), 反之亦然。

本文地址:https://blog.csdn.net/qq_38800089/article/details/110955526