《线性空间的对偶空间和优化里的拉格朗日对偶有什么关系？》

2023-12-15 21:15:58

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

覃含章机器学习、数学话题的优秀回答者余昌黔、 Victory.Kong 、 rainoftime 等

这两个概念是非常有关系的。不过，要搞清楚这层关系，这个问题会变得非常深刻，对此很多著名的凸分析书都有很深入的阐述，比如R.T. Rockafellar的Convex Analysis 30章就写的非常清楚。

http://www.convexoptimization.com/TOOLS/ConvexAnalysis.pdf

下面我给一个更intuitive的阐释。

首先解释为什么在数学程度更轻的教材里我们一般看不到这两者的关系。因为在一般的application当中（比如 $\mathbb{R}^n$ 中的连续优化问题），我们考虑的problem domain（称作 $Y$ ）都是完备的内积空间（希尔伯特空间），所以这个时候考虑拉格朗日函数里面那个 $\lambda$ 应该属于 $Y$ 的对偶空间 $Y^*$ 没有什么意义，因为根据Riesz表示定理（Riesz representation theorem） $Y$ 和 $Y^*$ 是同构的。所以在这种情况下，“对偶空间”这个概念确实是多余的。

然而从纯粹数学的角度来说这种情况也只是所有情况中的一个特例。为此，不失一般性，我们考虑如下情况：让 $Y$ 是一个有限维的在 $\mathbb{R}$ 中的向量空间（不必是内积空间）。

顺便先指出，凸分析里对对偶问题的核心思路其实是把一个凸集（convex set）用它的支撑超平面（hyperplanes）来表示。注意，对闭凸集（closed convex sets）来说二者可以说是等价的，因为任何一个闭凸集 $C$ 都是包含它的所有半平面（halfspaces）的交集（Theorem 11.5 in R.T. Rocafellar）。实际上这便是对集合 $C$ 的“对偶表示”。

接下来我们考虑一个真正的优化问题，即在域 $Y$ 上我们希望最小化一个凸函数 $f$ （注意，凸函数的epigraph是一个凸集）。根据上一段的讨论，对偶问题的核心思路是考虑函数 $f$ 在 $Y$ 上的一个线性majorization $\langle \lambda,x \rangle - \alpha$ , $\lambda\in Y^*$ . 注意如果给定一个固定的 $\lambda$ ，我们可以选取一个“最好”的 $\alpha$ :
$f(x)\geq \langle \lambda, x \rangle-\alpha, \forall~x\in Y \Leftrightarrow \alpha\geq \sup\limits_{x\in Y} ( \langle \lambda, x \rangle-f(x))$
所以显然我们可以选择
$\alpha=f^*(\lambda)= \sup\limits_{x\in Y} ( \langle \lambda, x \rangle-f(x))$ .
注意对任意 $\lambda$ ， $\alpha$ 不一定是有限的（可能趋于无穷），这种情况下对偶问题会不well-defined，会需要一些专门的regularity条件和其它讨论，这里暂且不表。只是指出实际上 $f^*(\lambda)$ 实际上是 $f$ 的共轭函数（conjugate function），不了解这个定义intuition的同学可以看一下下图这张非常直观的解释（图来自Stephen Boyd的那本凸优化）。共轭函数有很多很有趣的性质，比如如果f是convex且closed的（closed表示它的epigraph是闭的）那么 $f^{**}=f$ (这个证明的实质和Theorem 11.5是一样的，你发现了么？)，而如果没有convex和closed这个条件一般来说 $f^{**} = cl (co(f) )$ .

注意 $f^*(\lambda)$ 是定义在 $Y^*$ 上的，所以我们已经看到了对偶空间在优化理论中描述“对偶”的作用。接下来我们说明如何进一步推导出其和拉格朗日对偶的关系（我们先推导一个一般情况的）。注意在优化理论中，对偶问题是通过对原问题进行扰动（perturb）才得到的（对于这一点，不仅R.T. Rockafellar凸分析的30章写的很好，A. Shapiro有本Perturbation Analysis of Optimization Problems整本书都在阐述这一核心思想），而不同的扰动方式会得到不同形式的对偶问题，这也是我们常看到等价的原问题会有不同的对偶形式的原因。为了说明这一点，我们考虑如下优化问题(记作原问题 $\textbf{P}$ ): $\min_{x\in C} \phi(x,0)$ ，其中 $\phi:C\times D\rightarrow \mathbb{R}$ 是凸的。

对任意 $y\in D$ ，原问题 $\textbf{P}$ 的扰动问题定义为 $\min_{x\in C} \phi(x,y)$ 。接着定义函数 $h(y)=\inf_{x\in C}\phi(x,y)$ ，则显然原问题 $\textbf{P}$ 等价于估计 $h(0)$ 的值。注意根据共轭函数的定义我们有 $h(0)\geq h^{**}(0)$ 而且满足一些特定的regularity条件我们就有等号成立（比如 $h$ 在0点处有次梯度，这对凸函数来说是trivial的）。

由此，我们定义对偶问题 $\textbf{D}$ 为估计 $h^{**}(0)$ 的值。或者利用 $h^{**}(0)$ 是 $h^*$ 在0点的共轭得到 $\textbf{D}$ 的等价定义： $\max_{y^*\in D^*}-h^*(y^*)=\max_{y^*\in D^*}-\phi^*(0,y^*)$ .

对比 $\textbf{P}$ 关于 $\phi$ 的定义，我们得到了一组min-max的对偶形式，在原问题中出现的是 $x,\phi$ 和定义域 $C$ ，在对偶问题中出现的是变量 $y$ ， $\phi$ 的共轭和 $D$ 的对偶空间，在数学上十分优美。

在这个数学形式下，各种优化理论的经典命题可以很容易讨论。比如强对偶定理即意味着 $\phi^{**}=\phi$ （对偶问题perturb之后和原问题等价），而这个定理的成立要求 $Y$ 和 $Y^{**}$ 同构，这便是我们通常看不到此类讨论的深层原因。

最后我们给出拉格朗日对偶是这个框架的特例。此时， $\textbf{P}$ 定义为
$\begin{align}\min_{x\in \mathbb{R}}~ & f(x)\\\text{s.t. } & g(x)\leq 0.\end{align}$
可以被扰动成（对任意 $y \in \mathbb{R}$ ）
$\begin{align}\min_{x\in \mathbb{R}}~ & f(x)\\ \text{s.t. } & g(x)+y\leq 0.\end{align}$
沿用之前的定义，我们知道 $\phi(x,y)=f(x) \cdot 1(g(x)+y\leq 0 ) + \infty \cdot 1(g(x)+y>0 )$ 那么 $\textbf{P}$ 仍然可以看做在估计 $h(0)$ 的值。为了求 $\textbf{D}$ ，我们知道我们需要求出 $-\phi^*(0,y^*)$ 的显式形式，即
$\begin{align}-\phi^*(0,y^*)= & -\sup\limits_{g(x)+y\leq 0 } (\langle y^*,y\rangle -f(x))\\ = & -\sup\limits_{x\in \mathbb{R}, q\geq 0} \langle y^*,-g(x)-q \rangle - f(x)\\ = & \inf_{x\in \mathbb{R},q\geq 0} f(x)+\langle y^*,g(x)\rangle +\langle y^*,q\rangle.\end{align}$

注意到 $\mathbb{R}$ 的对偶空间和 $\mathbb{R}$ 同构，我们用 $\lambda$ 代替 $y^*$ ，那么显然 $-\phi^*(0,\lambda)= \inf_{x\in \mathbb{R}} (f(x)+\langle \lambda,g(x)\rangle)\cdot 1(\lambda\geq 0)-\infty \cdot 1 (\lambda<0) .$