最优化——对偶问题的性质(弱对偶性,强对偶性),对偶问题形式的书写(对偶规则)
对偶性质
弱对偶性
原对偶问题任何可行解的目标值都是另一问题最优目标值的界。(推论:原对
偶问题目标值相等的一对可行解是各自的最优解)
强对偶性
原对偶问题只要有一个有最优解,另一个就有最优解,并且最优目标值相等。
对偶问题解之间的关系
线性规划与其对偶规则的关系
互补松弛定理
原问题
max
C
T
X
\max C^{T} X
maxCTX 对偶问题
min
b
⃗
T
Y
\min \vec{b}^{T} Y
minbTY
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. AX≤bX≥0 s.t. ATY≥CY≥0
设
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