<aside> 🧸 线形规划的对偶； 对偶单纯性法
</aside>
$$ \min c^T x\\s.t.\ Ax=b,x\ge 0 $$
拉格朗日函数 鞍点
$$ l(x,\mu,\lambda)=c^T x\pm \lambda^T(Ax-b)-\mu^Tx,\bm \mu \ge \bm 0 $$
对偶问题 需要先求解这个无约束优化问题
$$ q(\lambda,\mu)=\min_{\bm x} f (x,\lambda,\mu)=\min_{\bm x} \left\{(c-A^T\lambda-\mu)^T\bm x+\bm \lambda^T\bm b\right\} $$
梯度为零$c-A^T\lambda -\mu =0$时取极小值
$$ q(\lambda,\mu)=\left\{\begin{matrix}\lambda^Tb&c-A^T\lambda-\mu=0\\-\infty& otherwise\end{matrix}\right. $$
对偶duality 问题 写成$q$有限时的极值问题
$$ \max_{\bm x}\lambda^Tb\\ s.t. \ c=A^T\lambda +\mu ,\bm \mu\ge\bm 0 $$
进一步，$\bm \mu$就是（化成标准型）辅助变量
$$ \max \bm \lambda ^T\bm b\\s.t.\ A^T\lambda\le \bm c $$
线形规划问题的对偶还是线性规划问题。
【弱对偶问题】原始问题的最小值$\omega^$大于对偶问题的最大值$q^$(弱对偶问题) 故 任取可行解$x,\lambda$
$$ \bm c^T\bm x\ge \bm \lambda^T\bm b $$
【强对偶 strong duality】
<aside> 📢
线形规划问题的原始问题和对偶问题有更强的定理。 大部分问题只满足弱对偶问题，拉格朗日函数存在鞍点，则存在强对偶命题
</aside>
可行解满足
$$ \bm c^T\bm x_0=\bm \lambda_0^T\bm b $$
则他们分别是问题的最优解。
$$ \begin{pmatrix}A&b\\c^T&0\end{pmatrix}\overset{分块}\to \begin{pmatrix}B&D_{对应非基变量所在列}&b\\c_B^T&c_D^T&0\end{pmatrix}\overset{\begin{pmatrix}I_B&0\\-c_B^T&1\end{pmatrix}\begin{pmatrix}B^{-1}&0\\0&1\end{pmatrix}}\to \begin{pmatrix}I&B^{-1}D_{获得非基变量所在列}&B^{-1}b_{最优点}\\0&\underline{c_D^T-c_B^TB^{-1}D}{r_D^T{判别数}}&-\underline{c_B^TB^{-1}b}{最优值}\end{pmatrix} $$
单纯形法中最终单纯形表中判别数非负
$$ r_D^T=c_D^T-c_B^TB^{-1}D\ge0 $$
$$ \lambda^T=c_B^TB^{-1} $$
代入得到
$$ \lambda^T\begin{pmatrix}B&D\end{pmatrix}\le \begin{pmatrix}c^T_B&c^T_D\end{pmatrix} $$
正是对偶问题$\lambda^TA\le c^T$的一个可行解 $\lambda$ . 这个可行解可以证明是最优解,最优解通过求解线形方程组得到
$D$行满秩 $rank \ D=m$
$$ \lambda^TD=c^T_D-r_D^T $$
$rank \ D<m$
$$ \left\{\begin{aligned}&\lambda^TD=c^T_D-r_D^T\\ &\lambda^TB=c_B^T\end{aligned}\right. $$
$$ A^T\lambda=c-\begin{pmatrix}0\\r_D\end{pmatrix} $$
【互补松弛条件】
最优解↔$(c^T-\lambda^TA)x=0 \& \lambda^T(Ax-b)=0$
互补:通过一方可以得到另一方.
【对偶单纯形法】
动机：初始单纯形表要求苛刻$\bm b\ge 0,\exist I$，
判别数已经非负$\sigma_l\ge 0$，存在$b_k<0$，只需要选择一个$a_{kl}<0$做转轴元素，满足与单纯形法相反的条件$\frac{\sigma_l}{a_{kl}}=\max j\{\frac{\sigma_j}{a{kj}}\mid a_{kj}<0\}$,依此迭代调整至最终单纯形表
$$ b_k^\prime =\frac{b_k}{a_{kl}},\sigma_j^\prime=\sigma_j-\frac{a_{kj}}{a_{kl}}\sigma_l,j=m+1,\cdots,n $$