不同目标与约束下拉格朗日对偶函数求解方法问询

作为刚啃完Boyd这本经典教材对偶性章节不久的过来人，太能共情你现在的感受了！从原问题推导拉格朗日对偶函数（也就是定义里的 $g(\lambda,v)=\inf_x L(x,\lambda,v)$）这一步，确实是新手入门时最容易卡壳的环节。我当时也整理了不同场景下的求解思路，分享给你参考：

• 线性/二次规划场景：这应该是最“常规”的情况了，直接对拉格朗日函数 $L(x,\lambda,v)$ 关于 $x$ 求梯度，令梯度 $\nabla_x L = 0$，解出对应的 $x^*$ 后代回 $L$，就能得到对偶函数 $g(\lambda,v)$。这里要注意，因为原问题是凸的，梯度为零的点就是全局极小点，所以直接用这个方法没问题。

• 涉及范数的场景：这种情况就不能直接求导了（毕竟很多范数在原点不可导），得用上凸函数的共轭或者极小化的性质来处理。比如如果原问题里有 $|x|$ 这类项，拉格朗日函数里会包含线性项和范数项的组合，这时候可以利用范数的对偶范数性质来求下确界。举个简单例子，当 $L(x,\lambda) = \lambda^T x + |x|$ 时，它关于 $x$ 的下确界就是：当 $|\lambda|* \leq 1$ 时为0，否则为 $-\infty$（这里 $|\cdot|*$ 是原范数的对偶范数）。本质上就是利用了凸函数的Fenchel共轭来快速求解下确界。

• 含指示函数/约束集的场景：如果原问题的约束是 $x \in C$（$C$ 是凸集），拉格朗日函数里会包含指示函数 $I_C(x)$，这时候求 $\inf_x L(x,\lambda,v)$ 就等价于在凸集 $C$ 上极小化 $L$ 里的其他项。这时候可以用凸集上的极小化技巧，比如投影定理（如果是欧几里得空间的凸集），或者利用凸集的支撑函数来求解。

另外给你提个小提醒：对偶函数的核心是对所有可行的 $x$ 取下确界，所以不管用哪种方法，最终都要验证得到的结果是不是对所有 $x$ 都满足 $L(x,\lambda,v) \geq g(\lambda,v)$，并且存在某个 $x$ 使得等号成立（也就是达到下确界）。

内容的提问来源于stack exchange，提问作者lehung