如何通俗地讲解对偶问题?尤其是拉格朗日对偶lagrangian duality?

能不能给我讲讲对偶问题,kkt条件?为什么存在duality gap?满足kkt条件又能说明什么? 我们能不能在知乎上开个optimization workshop,这样应该比live要强。 我先邀请了几位专业人士,希望你们能不吝赐教。先谢谢了。也请大家帮忙多邀请人来回答。 我的提问也都是抛砖引玉,任何关于优化的理解,都可以写下来,我不胜感激了。我相信很多知乎上的朋友,都会从你们的答案中得到帮助,谢谢了。
关注者
749
被浏览
32868

16 个回答

谢谢题主 @孤云独去闲 邀请。前段时间就看到这个问题了,现在看到很多答主都答得不错,那我给一个基于column geometry(翻译成列几何?)的解释吧。拉格朗日对偶有很多种理解和推导的方式,这一种是我比较喜欢的,几何和代数的方法结合,也比较有intuition。关于KKT条件的几何解释很多答主都提了,那个也是比较经典的,我这个回答就先不涉及了。


我们考虑优化问题如下,记作问题(P)。(知乎编辑器似乎出了点问题,函数括号圆括号显示不了,我就用方括号了)

z^* = \min_x f[x]\text{s.t. } g_i[x]\leq 0 ,~\forall~ i=1,\ldots,m,x\in X

大家都知道(P)的拉格朗日对偶问题(D)写作

v^* = \max_{u\geq 0} \min_{x\in X} \underbrace{f[x]+u^T g[x]}_{L[x,u]}

其中的函数L[x,u]就是我们熟知的拉格朗日函数。


这边先给一个小note,实际上原问题和拉格朗日对偶的代数形式就是一组max-min关系式(只有max和min的顺序换一下)。具体说明如下。

引理:(P)也可以写成 z^* = \min_{x\in X}\max_{u\geq 0}L[x,u] .

证明是很容易的,留作练习。那么这里其实我们看到所谓的拉格朗日对偶从代数上看很简单,就是研究这一对max-min优化问题之间的关系。


好了,之前都是预热。接下来我们来看如何通过column geometry来理解这对关系式。这一段首先介绍一些符号和定义。首先注意到给定一个 x\in X ,实际上(P)可以用一个在 \mathbb{R}^{m+1} 里的向量来描述:

\left[s,z\right]=[s_1,s_2,\ldots,s_m,z]=[g_1[x],g_2[x],\ldots,g_m[x],f[x]]=[g[x],f[x]] .

这样我们把问题转换到 [s,z] 定义的空间上,定义集合

I:=\{ [s,z]\in \mathbb{R}^{m+1}: \exists x\in X \text{ s.t. } s\geq g[x], z\geq f[x] \} .

然后我们引入“支撑”(support)的概念,我们称一个超平面 H_{u,\alpha}:= \{ [s,z]\in \mathbb{R}^{m+1}:u^Ts+z=\alpha \}I 的下支撑(lower support)仅当

u^Ts+z\geq \alpha, \forall~ [s,z]\in I.

直观的意思就是指 H_{u,\alpha} I的下方。下面给一张图片加以解释(黄色部分就是 I ,那条线就代表超平面 H_{u,\alpha})。


注意到这里我们图上看到 I 画的是一个凸集(convex set),我们指出在凸优化的一般情况下这是一个必然的事实。

引理:如果 X 是凸集, f,g_1,\ldots,g_m 都是 X 上定义的凸函数,那么 I 是一个凸集。

证明也很容易,利用凸函数epigraph的性质就能立即得出,这里从略。


好了,准备工作到这里,我们给出对偶问题(D)的column geometry解释:拉格朗日对偶问题(D),在空间 [s,z] 中的几何含义是:找到 I 的下支撑超平面 H_{u,\alpha} 中与z轴交点最 “高”(即 \alpha 最大)的那个超平面。注意到在 m=1 的情况下( [s,z] 是二维的)我们可以知道 -u 是直线 H_{u,\alpha} 的斜率, \alpha 则是截距。这个intuition到高维情况也是成立的。


把上面提到的几何含义用代数表示出来则是:

\max_{u,\alpha} ~ \alpha\text{s.t. } ~ u^Ts+z\geq \alpha, ~ \forall~ [s,z]\in I

注意到我们其实只需要考虑 u\geq 0 的情况,因为如果 u 存在一个coordinate是负的,那么我们总可以找到一个无限大的 s (注意 I 的定义,这样的 s 永远是存在的)使得 u^Ts+z<\alpha ,所以以上问题也等于

\max_{u\geq 0,\alpha}~\alpha\text{s.t.} u^Ts+z\geq \alpha,~ \forall~ [s,z]\in I

= \max_{u\geq 0,\alpha}~\alpha

\text{s.t. } \underbrace{u^Tg[x]+f[x]}_{L[x,u]}\geq \alpha,~\forall~x\in X

= \max_{u\geq 0,\alpha } \alpha

\text{s.t. } \min_{x\in X} L[x,u]\geq \alpha

= \max_{u\geq 0}\min_{x\in X}L[x,u]

我们于是发现这就是问题(D)。


这就是拉格朗日对偶基于column geometry的几何解释。 顺便说一下,如果我们考虑一个更特殊的情况, f,g 都是线性函数,即线性规划问题,column geometry会给出更多很有意思的几何解释,这边就留给感兴趣的同学自己去琢磨了。


版权声明:这里的内容(包括那张图)基本都来自于Robert M. Freund和Jorge R. Vera合写的Fundamentals of Nonlinear Optimization: a Constructive Approach的草稿(这书应该还没出版)。


--------------------------------------------------------------------------------------------------------------------------

我的另一个相关回答:(讨论更抽象的对偶优化问题,不过核心思路都是一致的,对偶的核心思想就是要找原问题的线性majorization)

线性空间的对偶空间和优化里的拉格朗日对偶有什么关系? - 知乎

抛砖引玉, 说一下(Lagrangian) duality是怎么来的。先考虑下面的nonlinear programming:

\min \{f(\mathbf{x}): g_i(\mathbf{x})\leq 0,\; i=1,2,...,m\} (1)

现在的问题是如何找到问题(1) 的最优值的一个最好的下界? 首先我们知道若方程组

\begin{align}&f(\mathbf{x})<v\\&g_i(\mathbf{x})\leq 0, i=1,2,...,m\end{align} (2)

无解,则v是问题(1)的一个下界。注意到方程组(2)有解可以推出对于任意的\bm{\lambda}\geq \mathbf{0}, 以下方程

f(\mathbf{x})+\sum_{i=1}^{m}\lambda_ig_i(\mathbf{x})<v (3)

有解。因此根据逆否命题,方程组(2)无解的充分条件是存在\bm{\lambda}\geq \mathbf{0},让方程(3)无解。方程(3)无解的充要条件是

\min_{\mathbf{x}} f(\mathbf{x})+\sum_{i=1}^m \lambda_ig_i(\mathbf{x})\geq v (4)

因为我们要找最好的下界,所以这个时候的v\bm{\lambda} 应该取

v=\max_{\bm{\lambda}\geq \mathbf{0}}\min_{\mathbf{x}} f(\mathbf{x})+\sum_{i=1}^{m}\lambda_ig_i(\mathbf{x}) (5)

由此引入了dual problem. 证明逻辑是根据式(5)取v\bm{\lambda}, 则(4)成立,从而导出(3)无解,然后可以知道(2)无解,因此v是问题(1)的下界