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

randolf2022年8月9日

library
math
优化

convex-optimization
dual
lagrange

大约 8 分钟

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

本文由 v2-8d60cb90a307d11d3daeaaff0dd051fa_xs 覃含章

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

http://www.convexoptimization.com/TOOLS/ConvexAnalysis.pdfopen in new window

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

首先解释为什么在数学程度更轻的教材里我们一般看不到这两者的关系。因为在一般的 application 当中（比如 $\mathbb{R}^n$ 中的连续优化问题），我们考虑的 problem domain（称作 $Y$ ）都是完备的内积空间（希尔伯特空间），所以这个时候考虑拉格朗日函数里面那个 $\lambda$ 应该属于 $Y$ 的对偶空间 $Y^*$ 没有什么意义，因为根据 Riesz 表示定理（Riesz representation theoremopen in new window） $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) )$ .

06fbef91668b24b638fc065f7989b51f_r

**注意 $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) .$

这便是拉格朗日对偶的标准形式。最后申明：我的回答非常受 StackExchange 上这段讨论的影响：Please explain the intuition behind the dual problem in optimization.open in new window

首先你要明白对偶问题的实质是什么，

一个简单而深刻的原理：闭凸集外一点到这个凸集的距离，恰好等与这个点到所有分离这个点与凸集的超平面的距离的上确界。

求一点到凸集的距离，这是一个最小化的问题；求一点到若干超平面的距离最大值，这是一个最大化问题。

事实上，在泛函分析中，每个超平面都能与一个线性泛函联系起来，最后的对偶问题，其实是想找一个线性泛函！

dual space 是所有 linear functionals(linear map from Vector space to Field) 组成的 vector space.

lagrange duality 是将原来的问题转换成一个对偶问题即 primal problem 和 dual problem, 其中通过解决 dual problem 可以给 primal 提供解集的一定范围。

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

# 线性空间的对偶空间和优化里的拉格朗日对偶的关系

# 线性空间的对偶空间和优化里的拉格朗日对偶的关系

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

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