目标函数最优值与向量\(b\)的关系

在这一部分，我们分析目标函数最优值与向量\(b\)的关系。

首先，令

为一个可行的集合。令

并且观测

注意，\(S\)是一个凸集。对于任意\(b\in S\)，定义

它是关于\(b\)的最优值函数。

在这一部分，我们假设对偶可行域\(\{p\mid p^TA\leq c^T\}\)是非空的。那么，由对偶理论可知对所有\(b\in S\)，最优值\(F(b)\)是有限的。我们的目标是研究\(F(b)\)的结构。

首先固定\(b^*\in S\)。假设存在一个非退化的原始最优基本可行解，记\(B\)为相对应的最优基矩阵，那么基本变量\(x_B\)的值此时为\(x_B=B^{-1}b^*\)，并且由非退化知\(x_B > 0\)。另外，判断数向量也是非负的。如果此时改变\(b^*\)为\(b\)，并且假设\(b-b^*\)足够小，\(B^{-1}b\)维持为正值，那么原来的解对于新的问题仍然是一个基本可行解。而判断数由于并不受\(b\)影响，因此仍然保持非负。综上，\(B\)也是新问题的一个最优解，而新问题的最优值为

其中\(p^T=c^T_BB^{-1}\)是对偶问题的最优解。这说明\(F(b)\)是关于\(b\)的线性函数，并且梯度为\(p\)。下面叙述\(F(b)\)的一个全局性质。

定理： 最优值函数\(F(b)\)是关于\(b\in S\)的凸函数。

证：

令\(b^1\)和\(b^2\)为\(S\)中的两个元素。对于\(i=1,2\)，令\(x^i\)为问题

的最优解。因此，\(F(b^1)=c^Tx^1\), \(F(b^2)=c^Tx^2\)。对于\(\lambda \in [0,1]\)，向量

非负，且满足\(Ay=\lambda b^1+(1-\lambda )b^2\)。这说明当线性规划问题右侧的向量为\(\lambda b^1+(1-\lambda )b^2\)时，\(y\)是一个可行解。因此，

证毕。

下面我们从对偶的角度重新观测上面的定理。考虑对偶问题：

注意我们之前假设它是可行的。对于任意\(b\in S\)，\(F(b)\)是有限的，并且根据强对偶定理可知它的值等于对偶问题的最优目标函数值。令\(p^1,p^2,\cdots,p^N\)为对偶可行域的极点。（由于\(A\)是行线性无关的，因此\(A\)的列的扩张为\(\mathbb{R}^m\)，由线性规划中的几何（四 ）中的定理可知对偶问题至少存在一个极点）。由于对偶问题的最优解必然是落在一个极点上，因此

这说明，\(F\)等价于有限个线性函数的最大值。因此，它是一个分段线性凸函数。当\(F\)在线性部分时，存在唯一解，而当\(F\)在不可导的部分时（两个线性相接的部分），说明解不是唯一的，更进一步说明原始问题的解是退化的（这是因为当原问题非退化时，由前面叙述的局部性质可知，此时它是线性的）。

下面考虑一种特殊情形，将\(b\)变为\(b=b^*+\theta d\)，其中\(b^*\)和\(d\)固定。令\(f(\theta)=F(b^*+\theta d)\)为系数为\(\theta\)时的最优值。因此，

对偶最优解集

这一部分说明任意对偶最优解都可以看作是\(F\)的“广义梯度”。

定义： 令\(F\)为定义在凸集\(S\)上的凸函数，存在\(b^*\in S\)。我们称向量\(p\)是\(F\)在点\(b^*\)的次梯度 （subgradient） 是指满足

\[F(b^*)+p^T(b-b^*)\leq F(b),\quad \forall b\in S. \]

注意，如果\(b^*\)在交接点，那么将存在多个次梯度。下图分别给出两种不同情况的次梯度。

定理： 假设问题

\[\min_{x}\{c^Tx\mid Ax=b^*,\,x\geq 0\} \]

可行并且最优值有界。那么，向量\(p\)是对偶问题最优解当且仅当\(p\)是\(F\)在点\(b^*\)的次梯度。

证：

回忆定义在集合\(S\)上的函数\(F\)。假设\(p\)是对偶问题的最优解，那么由强对偶定理可知\(p^Tb^*=F(b^*)\)。考虑任意\(b\in S\)，对于任意可行解\(x\in P(b)\)，由弱对偶定理可得\(p^Tb\leq c^Tx\)。给这个不等式两边关于\(x\in P(b)\)取最小值，可得\(p^Tb\leq F(b)\)。因此

这说明\(p\)是\(F\)在\(b^*\)的次梯度。

下面证另一面，记\(p\)为\(F\)在\(b^*\)的次梯度，那么

选择使得\(Ax=b\)及\(x\geq 0\)成立的\(x\in P(b)\)。已知\(F(b)\leq c^Tx\)，因此

由于上式对任意的\(x\geq 0\)都成立，因此必然有\(p^TA\leq c^T\)（因为如果不满足的话，我们总可以通过扩大x的值使得上述不等式不成立），这说明\(p\)是对偶问题的一个可行解。另外，令\(x=0\)，可得\(F(b^*)\leq p^Tb^*\)。由弱对偶可知，对于任意可行解\(q\)都有\(q^Tb^*\leq F(b^*)\leq p^Tb^*\)，这说明\(p\)是对偶问题最优解。证毕。

目标函数最优值与向量\(c\)的关系

假设原问题的可行域非空。定义对偶可行域

并且令

若\(c^1\in T\)并且\(c^2\in T\)，那么存在\(p^1\)和\(p^2\)使得\((p^1)^TA\leq (c^1)^T\)及\((p^2)^TA\leq (c^2)^T\)。对于\(\lambda \in [0,1]\)，我们有

这说明\(\lambda (c^1)^T+(1-\lambda) (c^2)^T\in T\)，与此同时也说明\(T\)是一个凸集。

若\(c\notin T\)，对偶问题可行域为空说明原问题的最优值为\(-\infty\)（因为我们假设原问题可行域非空）。若\(c\in T\)，那么最优值一定有界。因此，原问题的最优解\(G(c)\)有界当且仅当\(c\in T\)。

记\(x^1,x^2,\cdots,x^N\)是原问题可行域的基本可行解，显然它与\(c\)无关。由于标准型问题的最优解总是出现在极点，因此

这说明\(G(c)\)是有限个线性方程的最小值，因此它是一个分段线性凹函数。如果对于\(c^*\in T\)，原问题有唯一的最优解\(x^i\)，那么\((c^*)^Tx^i < (c^*)^Tx^j\)对任意\(j\not= i\)都成立。假设\(c\)非常接近\(c^*\)， 不等式\(c^Tx^i < c^Tx^j\)对于\(j\not= i\)仍然成立。这说明\(x^i\)仍然是原问题的唯一最优解且最优值为\(c^Tx^i\)。因此，局部的有\(G(c)=c^Tx^i\)。另外，\(G\)在交叉点时对应多个原问题。

下面的定理总结上面提到的结论。

定理： 考虑可行域非空的标准型的线性规划问题。

1. 集合\(T\)是凸集，且\(T\)中\(c\)对应的最优值有界。
2. 最优值函数\(G(c)\)是关于\(c\in T\)的凹函数。
3. 如果与\(c\)有关的原问题存在唯一最优解\(x^*\)，那么\(G\)在\(c\)的邻域内是线性的且梯度等于\(x^*\)。

参数规划

固定\(A,B,C\)以及一个与\(c\)维度相同的向量\(d\)。对于任意实数\(\theta\)，考虑问题

记\(g(\theta)\)为这个问题的最优值，并且假设可行域非空。对于最优值有界的\(\theta\)，有

其中\(x^1,\cdots,x^N\)是可行域的极点，如下图所示，\(g(\theta)\)是关于\(\theta\)的一个分段线性凹函数。为了更进一步观察\(g(\theta)\),我们先观察一个例子。

例： 考虑问题

然后引入松弛变量，是的上述问题转化为标准型问题，接着令松弛变量为基本变量。这样的方式确定了一个基本可行解，然后有如下的单纯形表

若\(-3+2\theta\geq 0\)且\(2-\theta\geq 0\)，那么所有的判断数都非负，说明此时得到了最优基本可行解。也即，

若\(\theta\)增加到高于3，那么\(x_2\)的判断数此时为负值。此时令\(x_2\)进入基矩阵，\(x_4\)出基矩阵，得到如下的单纯形表

如果\(3\leq \theta\leq 5.5/1.5\)，那么表中的判断数都是非负，此时有

如果\(\theta\)增加的超过\(5.5/1.5\)，那么\(x_3\)的判断数变为负值。如果我们想要\(x_3\)进基，但是不存在正的pivot元素，因此此时原问题无界且\(g(\theta)=-\infty\)。

现在我们回到第一个表再考虑另一面，如果\(\theta\)增加的小于\(3/2\)，那么\(x_1\)的判断数就变为负值，此时使得\(x_1\)进基，\(x_5\)出基，得到

如果\(5/4\leq \theta\leq 3/2\)，那么得到最优解，且

而对于\(\theta < 5/4\)，\(x_3\)的判断数变为负值，但是所对应的列不存在正的pivot元素，因此这时的最优值为\(-\infty\)。

我们将上述的结果汇总绘制得到如下的图：

接下来，我们总结上面例子的一般步骤。假设现在我们有一个基本可行解以及它所对应的基矩阵\(B\)，并且假设这个基矩阵对于满足\(\theta_1\leq \theta\leq\theta_2\)的\(\theta\)是最优的。令\(x_j\)为当\(\theta >\theta_2\)时，它的判断数为负值。又因为当\(\theta_1\leq \theta\leq\theta_2\)时，\(x_j\)的判断数为正值，因此当\(\theta =\theta_2\)时，\(x_j\)的判断数为0。然后此时考虑令\(x_j\)进基。

若列\(B^{-1}A_j\)不存在正的pivot元素，那么对于\(\theta > \theta_2\)，\(x_j\)的判断数为负值，因此此时的最优值为\(-\infty\)。

若列\(B^{-1}A_j\)至少存在一个正元素，那么我们可以进行基变换得到新的基矩阵\(\overline B\)。当\(\theta = \theta_2\)时，进基变量的判断数为0，则新的基矩阵对应的目标函数值不变。并且，对于旧基矩阵，目标函数值是最优值，那么对于新的基矩阵，这个值仍然为最优值。对于\(\theta < \theta_2\)，由于进基变量的判断数为正值，因此新的基矩阵对应的目标函数值不会小于原基矩阵对应的最优值（注：判断数为负值时是使得目标函数值下降的方向）。这说明新的基矩阵在\(\theta < \theta_2\)时不可能是最优基矩阵。那么，上述的叙述表明新的基矩阵为最优基矩阵是在\(\theta\)满足\(\theta_2 \leq \theta \leq \theta_3\)时成立的。重复上述的操作，我们可以得到一组基矩阵以及相对应的满足最优性的\(\theta\)的范围。

注意，当一个基矩阵在满足\(\theta \in [\theta_i,\theta_{i+1}]\)时是最优的，那么对于\(\theta \geq \theta_{i+1}\)，这个基矩阵将不可能是最优的（存在判断数为负值，说明存在了下降方向）。因此，若\(\theta_{i+1} > \theta_{i}\)对于所有\(i\)都成立，那么同一个基矩阵不会出现两次，并且\(\theta\)的所有范围也将会在有限次迭代后得到。注意，每一次迭代都会得到一个新的交界点。

如果存在\(\theta_i = \theta_{i+1}\)，说明上面提到的操作可能会出现循环（注：这种情形仅会在原问题退化时出现），但是可以使用一些反循环的技巧避免循环的出现。

敏感性分析总结

1. 若加入新变量，检查判断数是否为负值，若是，原单纯形表中加入新的列继续使用单纯形法。
2. 若加入新约束，检查约束是否还满足，若不满足，构造辅助问题继续求解。
3. 若\(b\)或\(c\)改变了\(\delta\)，得到原基矩阵维持最优性的\(\delta\)的范围。
4. 若\(A\)中元素变化\(\delta\)，分析与上述类似。不过，如果变化的是基本列中的元素，分析过程稍有复杂。
5. 假设对偶问题可行域非空，最优值是关于\(b\)的分段线性凸函数（前提\(b\)使得原问题存在可行解）。另外，最优值的次梯度与对偶问题的最优解有关。
6. 假设原问题可行域非空，最优值是关于向量\(c\)的分段线性凹函数（前提\(c\)使得原问题有界）。
7. 如果目标函数中系数是参数\(\theta\)的仿射函数，那么可通过一系列操作得到所有\(\theta\)的最优值。

参考文献: Introduction to Linear Optimization by Dimitris Bertsimas & John N. Tsitsiklis.

21. 敏感性分析（二）全局敏感性分析及总结

原文：https://www.cnblogs.com/yhxm/p/13127303.html