优化理论之线性规划的对偶的互补松弛定理

Nov 3, 2019 · 优化理论  ·
分享到:

线性规划的对偶的互补松弛定理

前情提要

对称形式对偶问题定义

原问题 \[ \begin{aligned} \min\quad&\boldsymbol{c^Tx}\\ \mathop{s.t.}\quad&\boldsymbol{Ax≥b}（注意这里是≥）\\ &\boldsymbol{x≥0} \end{aligned}\tag{1.1} \] 对偶问题 \[ \begin{aligned} \max\quad&\boldsymbol{w^Tb}\\ \mathop{s.t.}\quad&\boldsymbol{w^TA≤c^T}（注意这里是≤）\\ &\boldsymbol{w^T≥0} \end{aligned}\tag{1.2} \] 其中，\(\boldsymbol{A=(p_1,p_2,\dotsb,p_n)}\)是\(m×n\)矩阵，\(\boldsymbol{b}=(b_1,b_2,\dotsb,b_m)^T\)是m维列向量，\(\boldsymbol{c^T}=(c_1,c_2,\dotsb,c_n)\)是n维行向量，\(\boldsymbol{x}=(x_1,x_2,\dotsb,x_n)^T\)是原问题的变量组成的n维列向量，\(\boldsymbol{w^T}=(w_1,w_2,\dotsb,w_m)\)是由对偶问题变量组成的m维行向量。

非对称形式对偶问题定义

原问题 \[ \begin{aligned} \min\quad&\boldsymbol{c^Tx}\\ \mathop{s.t.}\quad&\boldsymbol{Ax=b}\\ &\boldsymbol{x≥0} \end{aligned}\tag{1.3} \] 对偶问题 \[ \begin{aligned} \max\quad&\boldsymbol{w^Tb}\\ \mathop{s.t.}\quad&\boldsymbol{w^TA}≤\boldsymbol{c}\\ \end{aligned}\tag{1.5} \]

对偶定理

定理1.1 设\(\boldsymbol{x^{(0)}}\)和\(\boldsymbol{w^{(0)}}\)分别是\((1.1),(1.2)\)式的可行解,则\(\boldsymbol{c^Tx^{(0)}}≥\boldsymbol{w^{(0)T}b}\)

推论1： 若\(\boldsymbol{x^{(0)}}\)和\(\boldsymbol{w^{(0)}}\)分别是原问题\((1.1)\)和对偶问题\((1.2)\)的可行解，且\(\boldsymbol{c^Tx^{(0)}=w^{(0)T}b}\)，则\(\boldsymbol{x^{(0)}}\)和\(\boldsymbol{w^{(0)}}\)分别是原问题\((1.1)\)和对偶问题\((1.2)\)的最优解。(\(\boldsymbol{c^{(0)T}x≥w^{(0)T}b}\)恒成立因此相等的情况分别是二者的最优解)

定理1.2：设原问题\((1.1)\)和对偶问题\((1.2)\)中有一个问题存在最优解， 则另一个问题也存在最优解，且两个问题的目标函数的最优值相等。

互补松弛性质

利用对偶定理可以证明原问题和对偶问题的最优解满足重要的互补松弛关系。互补松弛定理可以了解到变量在限制条件中是否取等号或者是取上下限值。

对称形式

定理1.3：设\(\boldsymbol{x^{(0)}}\)和\(\boldsymbol{w^{(0)}}\)分别是原问题\((1.1)\)和对偶问题\((1.2)\)的可行解，那么\(\boldsymbol{x^{(0)}}\)和\(\boldsymbol{w^{(0)}}\)都是最优解的充要条件是，对所有\(i和j\)，下列关系成立：

  1. 如果\(x^{(0)}_j>0\)，就有\(\boldsymbol{w^{(0)T}p_j}=c_j\);
  2. 如果\(\boldsymbol{w^{(0)T}p_j}<c_j\)，就有\(x^{(0)}_j=0\);
  3. 如果\(w^{(0)}_i>0\)，就有\(\boldsymbol{A_i x^{(0)}}=b_i\);
  4. 如果\(\boldsymbol{A_i x^{(0)}}>b_i\)，就有\(w^{(0)}_i=0\);

其中\(\boldsymbol{p_j}\)是\(\boldsymbol{A}\)的第\(j\)列，\(\boldsymbol{A_i}\)是\(\boldsymbol{A}\)的第\(i\)行。

证明：先证必要性。最优解\(\Rightarrow\) (1,2,3,4)

设\(\boldsymbol{x^{(0)}}\)和\(\boldsymbol{w^{(0)}}\)分别是原问题\((1.1)\)和对偶问题\((1.2)\)的最优解。由于\(\boldsymbol{c^T≥w^{(0)T}A}\)以及\(\boldsymbol{x^{(0)}≥0}\)，则有 \[ \boldsymbol{c^T x^{(0)}}≥\boldsymbol{w^{(0)T}A x^{(0)}}\tag{1.16} \] 由于\(\boldsymbol{Ax^{(0)}≥b}\)和\(\boldsymbol{w^{(0)T}≥0}\)，则 \[ \boldsymbol{w^{(0)T}A x^{(0)}}≥\boldsymbol{w^{(0)T}b}\tag{1.17} \] 由于\(\boldsymbol{x^{(0)}}\)和\(\boldsymbol{w^{(0)}}\)分别是原问题\((1.1)\)和对偶问题\((1.2)\)的最优解，根据定理1.2必有： \[ \boldsymbol{c^T x^{(0)}}=\boldsymbol{w^{(0)T}b}\tag{1.18} \] 用\((1.18)\)夹逼\((1.16),(1.17)\)可得 \[ \boldsymbol{c^T x^{(0)}}=\boldsymbol{w^{(0)T}A x^{(0)}}=\boldsymbol{w^{(0)T}b} \tag{1.19}\\ \] \[ \boldsymbol{(c^T-w^{(0)T}A) x^{(0)}}=0 \tag{1.20}\\ \] \[ \boldsymbol{w^{(0)T}(A x^{(0)}-b)}=0\tag{1.21}\\ \] 由于\(\boldsymbol{c^T-w^{(0)T}A≥0}，\boldsymbol{x^{(0)}≥0}\)，因此对于两项分量非0时都为正，因此对于每一个分量都有 \[ (c_j-\boldsymbol{w^{0T}p_j})x_j^{(0)}=0,\quad j=1,2,\dotsb,n \] 故定理1.3中关系（1）（2）成立。

由于\(\boldsymbol{Ax^{(0)}-b≥0}，\boldsymbol{w^{(0)}≥0}\)，因此对于两项分量非0时都为正，因此对于每一个分量都有 \[ w_i^{(0)}(\boldsymbol{A_ix^{(0)}}-b_i)=0,\quad i=1,2,\dotsb,m \] 故定理1.3中关系（3）（4）成立。必要性得证。

再证充分性。最优解\(\Leftarrow\) (1,2,3,4)

设\(\boldsymbol{x^{(0)}}\)和\(\boldsymbol{w^{(0)}}\)分别是原问题\((1.1)\)和对偶问题\((1.2)\)的可行解，且关系（1）（2）（3）（4）成立。

由于关系（1）和（2）成立，则对每一个\(j\)，有 \[ (c_j-\boldsymbol{w^{0T}p_j})x_j^{(0)}=0,\quad j=1,2,\dotsb,n\tag{1.22} \] 由此可推出\(\boldsymbol{(w^{(0)T}A-c^T)x^{(0)}=0}\)，即 \[ \boldsymbol{c^T x^{(0)}}=\boldsymbol{w^{(0)T}A x^{(0)}}\tag{1.23} \] 由于关系（3）（4）成立，则对于每一个\(i\)，有 \[ w_i^{(0)}(\boldsymbol{A_ix^{(0)}}-b_i)=0,\quad i=1,2,\dotsb,m\tag{1.24} \] 由此可以看出\(\boldsymbol{w^{(0)T}(A x^{(0)}-b)}=0\)，即 \[ \boldsymbol{w^{(0)T}A x^{(0)}}=\boldsymbol{w^{(0)T}b} \tag{1.25} \] 由\((1.23)\)和\((1.25)\)可以得到 \[ \boldsymbol{c^T x^{(0)}}=\boldsymbol{w^{(0)T}b} \] 由定理1.1的推论1可知，\(\boldsymbol{x^{(0)}}\)和\(\boldsymbol{w^{(0)}}\)分别是原问题\((1.1)\)和对偶问题\((1.2)\)的最优解。

非对称形式

对于非对称形式的对偶规划，由于在原问题中约束条件是\(\boldsymbol{Ax=b}\)，而对偶变量无正负 限制。因此互补松弛性质叙述如下

定理1.4：设\(\boldsymbol{x^{(0)}}\)和\(\boldsymbol{w^{(0)}}\)分别是原问题\((1.3)\)和对偶问题\((1.5)\)的可行解，那么\(\boldsymbol{x^{(0)}}\)和\(\boldsymbol{w^{(0)}}\)都是最优解的充要条件是，对于所有\(j\)，下列关系成立：

  1. 如果\(x^{(0)}_j>0\)，就有\(\boldsymbol{w^{(0)T}p_j}=c_j\);
  2. 如果\(\boldsymbol{w^{(0)T}p_j}<c_j\)，就有\(x^{(0)}_j=0\);

强互补松弛定理

暂时略