原问题：\(min \ c^Tx\)
- 约束条件：\(Ax \leq b\)
- \(x \in R^d, A^{m \times d}, b \in R^m\)
- 目标函数、约束条件都是线性表达式，故称线性规划
构造拉格朗日函数
- 定义拉格朗日参数 \(\lambda \geq 0\)
- 拉格朗日函数 \(L(x, \lambda)=c^Tx + \lambda^T(Ax-b)\)
- 注意：约束条件标准格式的符号是 \(\leq\) ，构造 \(L(x, \lambda)\) 时一定是“\(+\)”惩罚项 \(\lambda^T(Ax-b)\)
- 从而保证了当 \(\lambda \geq 0\) 时，惩罚项 \(\lambda^T(Ax-b)\) 与原约束项是同向的
- 从而保证 \(min_x \ L(x, \lambda)\) 求解出的最小值下界 \(D(\lambda)\) 不会跑到 \(-\infty\)
对偶问题：\(max \ D(\lambda)\)
- 改写 \(L(x, \lambda)\) 的表达式
- \(L(x, \lambda)=(c+A^T\lambda)x-\lambda^Tb\)
- 极值点一阶导为0： \(c+A^T\lambda=0\)
- \(D(\lambda)=-\lambda^Tb \ \ \ \ \leftarrow\) 对偶函数
找到\(D(\lambda)\)的最大值，就找到了\(L(x, \lambda)\)的最小值，也就找到了\(c^Tx\)的最小值
惩罚项原理
- 对于 \(λ_i≥0, \ g_i(x)≤0\)
- 会使惩罚项 \(λ_i g_i(x)≤0\)，这一项在可行域内是“非正”的惩罚
- 如果 \(x\) 违反约束使 \(g_i(x)>0\)，则 \(λ_i g_i(x)\) 立即变成正数，把\(L(x, \lambda)\)抬高，从而 \(min_x L\) 时会被排斥，这就是“惩罚”机制。
原问题、对偶问题
- 原问题 \(x \in R^d\)
- 对偶问题 \(\lambda \in R^m\)
- 将 \(d\) 维的问题转化成了 \(m\) 维的问题
- 选择求解哪一个问题，取决于 \(d\) 和 \(m\) 谁大，源自矩阵 \(A \in R^{m \times d}\)，低维更利于求解