对偶理论

http:\/\/xiaoyc.com\/duality-theory-for-optimization\/

1. 对偶函数

* 原问题

$\begin{align} &\operatorname{minimize}& & f_0(x) \\ &\operatorname{subject\;to}& &f_i(x) \leq 0, \quad i = 1,\dots,m \\ & & &h_i(x) = 0, \quad i = 1,\dots,p \end{align}$* 其最优解： $p^\ast$

• 最优解满足 $f_0(p^\ast) = \min \{f_0(x) \mid x \in \mathcal{D}\}$

其中：$\emptyset \neq \mathcal{D} \subset \mathbb{R}^n$ 是可行域

* 拉格朗日函数

• 定义上述问题的拉格朗日函数（Lagrangian）如下：

$L(x,\lambda,\nu) = f_0(x) + \sum\limits_{i=1}^m \lambda_i f_i(x) + \sum\limits_{i=1}^p \nu_i h_i(x)$

• 其中向量 $\lambda$ 和 $\nu$ 称为该问题的 对偶变量（dual variables） 或者 拉格朗日乘子（Lagrange multiplier vectors）。

2. 对偶函数

• 定义 拉格朗日对偶函数（Lagrange dual function） 如下：

$g(\lambda,\nu) = \inf\limits_{x\in\mathcal{D}} L(x,\lambda,\nu)$

$= \inf\limits_{x\in\mathcal{D}} \left ( f_0(x) + \sum\limits_{i=1}^m \lambda_i f_i(x) + \sum\limits_{i=1}^p \nu_i h_i(x) \right )$

2.1 对偶函数的凸性

• 无论原问题中的对偶函数是否是凸函数，其对偶函数总是凹的。这是因为可数个仿射函数的逐点最小值构成的函数是凹的

* 定理1

• 如果 $f$ 关于 $(x,y)$ 是凸函数，$\mathcal{C}$ 是非空凸集，则函数

  $g(x)=\inf\limits_{y\in\mathcal{C}} f(x,y)$

  关于 $x$ 是凹函数 。其中 $g$ 的定义域是 $f$ 的定义域到 $x$ 方向的投影，即：

  $\textbf{dom }g=\{x \mid (x,y)\in\textbf{dom }f \text{ for some } y \in \mathcal{C} \}$

• 而对偶函数 $g(\lambda,\nu)$ 恰好是一族关于 $(\lambda,\nu)$ 的仿射函数的逐点最小，因此它是凹的，这与 $f_i(x)$ 与 $h_i(x)$ 的凸性无关。

2.2 拉格朗日乘子法

• 关于求条件极值的方法，有如下定理，可用隐函数定理证明，过程从略

* 定理2 （Lagrange乘数法）

• 设 $f\in C^1\(U\)$，$x^0\in A$ 为 $f$ 的条件极值点。如果梯度 $\nabla \Phi\(x^0\)$ 的秩为 $m$，则存在 $\lambda \in \mathbb{R}^m$，使得

$\nabla f(x^0) - \lambda \cdot \nabla \Phi(x^0) = 0$

* 其中：

注：由定理可知，若 $x^0$ 为条件极值点，则 $(x^0,\lambda)$ 为辅助函数

$F(x,\lambda) = f(x) - \sum\limits_{i=1}^m \lambda_i \cdot \phi_i(x)$

的驻点。

3. 最优下界的估计

• 原问题中的最优解 $p^\ast$，引入对偶函数可以导出 $p^\ast$ 的下界。

* 性质1

对于任意的 $\lambda \succeq 0$ 和任意的 $\nu$，都有 $g(\lambda,\nu) \leq p^\ast$

* 证明

这个证明是很容易的，设 $\tilde{x}$ 是原问题的一个可行解，则有

$\sum\limits_{i=1}^m \lambda_i f_i(\tilde{x}) + \sum\limits_{i=1}^p \nu_i h_i(\tilde{x}) \leq 0$

从而，

$L(\tilde{x},\lambda,\nu) = f_0(\tilde{x}) + \sum\limits_{i=1}^m \lambda_i f_i(\tilde{x}) + \sum\limits_{i=1}^p \nu_i h_i(\tilde{x}) \leq f_0(\tilde{x})$

因此，

$g(\lambda,\nu) = \inf\limits_{x\in\mathcal{D}} L(x,\lambda,\nu) \leq L(\tilde{x},\lambda,\nu) \leq f_0(\tilde{x})$

由于 $g(\lambda,\nu) \leq f_0(\tilde{x})$ 对任意 $\tilde{x}$ 皆成立，故 $g(\lambda,\nu) \leq p^\ast$。

* 对偶可行（dual feasible）的概念

当 $g(\lambda,\nu) = -\infty$ 时，上述不等式给出了一个平凡的结论。因此约定对偶可行域：

$\textbf{dom }{g} = \{(\lambda,\nu) \mid \lambda \succeq 0 \text{ and } g(\lambda,\nu) > -\infty \}$

注意到上式用了记号 $\lambda \succeq 0$，因为 $\lambda$ 是个向量，它等价于 $\lambda_i \geq 0,\quad i = 1,\dots,m$。

* 弱对偶性

由于 $g(\lambda,\nu) \leq p^\ast$ 对任意的 $\lambda \succeq 0$ 和 $\nu$ 都成立，故

$\max\limits_{\lambda \succeq 0, \nu} g(\lambda,\nu) \leq p^\ast$ 亦成立，这也是下面要提到的弱对偶性的概念。

4. 对偶问题

• 原问题最优值的下界估计，其中重要的一个不等式是 $g(\lambda,\nu) \leq p^\ast$，其中 $g(\lambda,\nu)$是原问题的（拉格朗日）对偶函数。

• 对偶函数是 $p^\ast$ 的下界估计，那么可以取到的最优下界是什么？

* 另一个优化问题：(对偶问题)

$\begin{align} &\operatorname{maximize}& & g(\lambda,\nu) \\ & \operatorname{subject\;to}& &\lambda \succeq 0 \end{align}$

* 拉格朗日对偶问题是非线性对偶问题和线性对偶问题不一样，拉格朗日对偶问题是通过拉格朗日对偶函数构建的

• 对偶可行（dual feasible）的概念也好理解了，即 $(\lambda,\nu)$ 对该对偶问题是可行的。同时，把该问题的最优解 $(\lambda^\ast,\nu^\ast)$ 称为对偶最优解（dual optimal）或最优拉格朗日乘子（optimal Lagrange multipliers）。

• 原问题的对偶问题总是凸优化问题，与原问题是否是凸优化问题无关。

4.1 弱对偶性

• 偶问题的最优解为 $d^\ast$，由性质1，便很容易推出,若对偶性：

  $d^\ast \leq p^\ast$

• 弱对偶性（weak duality），即对偶问题的最优解不超过原问题的最优解。

• 在任何情况下，弱对偶性总是成立的。

4.2 强对偶性

如果原问题与对偶问题的最优解相等，即等式 $d^\ast = p^\ast$ 成立，则称它满足强对偶性。

• 强对偶性一般而言是不成立的。但若原问题是凸优化问题，即在形式

$\begin{align} &\operatorname{minimize}& & f_0(x) \\ &\operatorname{subject\;to}& &f_i(x) \leq 0, \quad i = 1,\dots,m \\ & & &Ax=b \end{align}$

中 $f_0, \dots, f_m$ 都是凸函数。则强对偶性 通常 是成立的。

* slater条件

• 之所以说通常，是因为可能存在两个问题都无可行解的状况，这时强对偶性不成立。所以有必要建立“使其有解”的约束条件，其中之一便是 Slater's condition：

Slater's condition 存在一点 $x \in \textbf{relint } \mathcal{D}$ （$\mathcal{D}$的相对内点集）满足 $f_i(x) \lt 0, \quad i=1,\dots,m,\quad Ax=b$ 这样的点也可称之为 严格可行 的。

• Slater's Theorem则给出了强对偶性成立的一个充分条件：

* 定理3

Slater's Theorem 若 Slater's condition 成立且原问题是凸优化问题，则强对偶性成立。

• 当有部分约束条件是仿射函数时，Slater's condition 可以被弱化。假定前 $k$ 个约束条件是仿射函数，那么可以弱化为：

Refined Slater's condition 若 $f_1,\dots,f_k$ 是仿射函数，则存在一点 $x \in \textbf{relint } \mathcal{D}$ （$\mathcal{D}$的相对内点集）满足

$f_i(x) \leq 0, \quad i=1,\dots,k,\quad$

$f_i(x) \lt 0, \quad i=k+1,\dots,m,\quad$

$Ax=b$

• 满足 Slater's condition（或 Refined Slater's condition） 不仅意味着（凸优化问题）强对偶性的成立，而且也表示当 $d^\ast \gt -\infty$ 时，存在一组对偶变量 $(\lambda^\ast, \nu^\ast)$满足 $g(\lambda^\ast, \nu^\ast)=d^\ast=p^\ast$，即此时对偶最优值是可取到的。

* slater条件的再解释

http:\/\/blog.csdn.net\/kaka20080622\/article\/details\/49201063

5. 最优条件

* 互不松弛条件

* KKT条件

* KKT条件的意义

6 对偶问题的求解方法

6.1 由定义求驻点

这一种方法比较直接，其思路是由 $g(\lambda,\nu) = \inf\limits_{x\in\mathcal{D}} L(x,\lambda,\nu)$ 的定义，直接求最值。这种方法可用于 $L(x,\lambda,\nu)$ 的表达式比较简单的情形。举例如下：

* 问题

$\begin{align} &\operatorname{minimize}& & x^{T} x \\ &\operatorname{subject\;to}& &Ax=b \end{align}$

• 则该问题的拉格朗日量是 $L(x,\nu) = x^T x + \nu^T (Ax-b)$，对偶函数是 $g(\lambda,\nu) = \inf_{x\in\mathcal{D}} L(x,\lambda,\nu)$。因为 $L(x,\nu)$ 是关于 $x$ 的二次凸函数，对 $x$ 求导：

$\nabla_{\boldsymbol{x}} L(x,\nu) = 2x + A^T \nu = 0$

因此推出 $x=-(1/2)A^T \nu$，代入对偶函数表达式，即得：

$g(\nu) = L(-(1/2)A^T \nu, \nu) = -(1/4)\nu^T A A^T \nu - b^T \nu$

6.2 隐式求解约束条件

这种方法的思路是先求出拉格朗日量 $L(x,\lambda,\nu)$，然后求出对偶可行域：即要使 $g(\lambda,\nu) = \inf\limits_{x\in\mathcal{D}} L(x,\lambda,\nu) \gt -\infty$ 成立，$(\lambda,\nu)$ 所需满足约束条件。这些约束条件加上 $\lambda \succeq 0$ 便构成了对偶问题约束条件。

考虑标准形式的线性规划（Linear Programming）问题：

$\begin{align} &\operatorname{minimize}& & c^T x \\ &\operatorname{subject\;to}& &Ax=b \\ & & &x \succeq 0 \end{align}$

这时拉格朗日量是：

$L(x,\nu) = c^T x - \sum_{i=1}^m \lambda_i x_i + \nu^T (Ax-b) = -b^T \nu + (A^T\nu + c - \lambda)^T x$

注意到当 $A^T\nu + c - \lambda \neq 0$ 时，$g(\lambda,\nu) = -\infty$，因此：

$g(\lambda,\nu) =\begin{cases} -b^T \nu & A^T\nu + c - \lambda = 0 \\ -\infty & \text{otherwise.} \end{cases}$

于是，该问题的对偶问题可表示成如下形式：

$\begin{align} &\operatorname{maximize}& & -b^T \nu \\ &\operatorname{subject\;to}& &A^T\nu + c - \lambda = 0 \\ & & &\lambda \succeq 0 \end{align}$

6.3 共轭函数法

共轭函数法给出了从（线性约束条件下的）原问题到对偶问题的一般化形式，同时也揭示了对偶函数与共轭函数间的关系。

先给出共轭函数的定义：

• 一个函数 $f: R^n \to R$ 的共轭函数 $f^\ast$ 定义如下： $f^\ast(y) = \sup\limits_{x \in \textbf{dom } f } (y^T x - f(x))$

接着考虑如下有线性等式和线性不等式约束的优化问题：

$\begin{align} &\operatorname{minimize}& & f_0(x) \\ &\operatorname{subject\;to}& &Ax \preceq b \\ & & &Cx = d \end{align}$

于是，由对偶函数及共轭函数的定义可得：

$\begin{align} g(\lambda,\nu) = & \inf_{x\in\mathcal{D}} \left ( f_0(x) + \lambda^T (Ax-b) + \nu^T (Cx-d) \right ) \\ = & -b^T \lambda - d^T \nu + \inf\limits_{x\in\mathcal{D}} \left ( f_0(x) + (A^T\lambda + C^T\nu)^T \right ) \\ = & -b^T \lambda - d^T \nu - f_0^\ast(-A^T\lambda - C^T\nu) \end{align}$

且对偶函数 $g$ 的定义域由共轭函数 $f^\ast$ 的定义域所确定，即：

$\textbf{dom }g = \left\{ (\lambda,\nu) \mid -A^T\lambda - C^T\nu \in \textbf{dom }f_0^\ast \right\}$

于是，求对偶函数的问题便转换成了求共轭函数的问题。

下面列举一些常用目标函数的共轭函数：

• 线性函数 $f(x)=ax+b$ 的共轭函数是 $f^\ast(a)=-b$，且 $f^\ast$ 的定义域是单点 $\{a\}$。
• 负对数 $f(x)=-\log{x}$ 的共轭函数是 $f^\ast(y)=-\log{(-y)}-1$，定义在 $y \lt 0$。
• 指数函数 $f(x)=\mathrm{e}^x$ 的共轭函数是 $f^\ast(y)=y\log{y}-y$，定义在 $y\geq 0$。
• 负熵函数 $f(x)=x\log{x}$ 的共轭函数是 $f^\ast(y)=\mathrm{e}^{y-1}$，定义域为 $R$。
• Hinge Loss $f(x)=\max\{0, 1-x\}$ 的共轭函数是 $f^\ast(y)=y$，定义域是 $-1 \leq y \leq 0$。
• 任意范数 $f(x)=\Vert x \Vert$ 的共轭函数是 $f^\ast(y)=\begin{cases} 0 & \Vert y \Vert_\ast \leq 1 \\ \infty & \text{otherwise} \end{cases}$ 其中 $\Vert y \Vert_\ast$ 是原范数 $\Vert x \Vert$ 的对偶范数。

• 范数平方 $f(x)=(1/2)\Vert x \Vert^2$ 的共轭函数是 $f^\ast(y)=(1/2)\Vert y \Vert_\ast^2$，
  其中 $\Vert y \Vert_\ast$ 是原范数 $\Vert x \Vert$ 的对偶范数。
  用这种方法可以很快捷地推出上面两种方法中提到的例子，可自行检验之。

• 二次型 $f(x)=(1/2)x^T Q x$ 的共轭函数是 $f^\ast(y)=(1/2)y^T Q^{-1} y$。

TODO：需要推导 $\Vert Ax-b \Vert$ 的共轭函数。

--

7. 最优条件求解对偶问题

7.1 互不松弛

假设强对偶性成立，则原问题与对偶问题的解相等。记 $x^\ast$ 和 $(\lambda^\ast,\nu^\ast)$ 分别表示原问题与对偶问题的最优解，那么，

$\begin{align} f_0(x^\ast) = & g(\lambda^\ast,\nu^\ast) \\ = & \inf_{x} \left( f_0(x) + \sum_{i=1}^m \lambda_i^\ast f_i(x) + \sum_{i=1}^p \nu_i^\ast h_i(x) \right) \\ \leq & f_0(x^\ast) + \sum_{i=1}^m \lambda_i^\ast f_i(x^\ast) + \sum_{i=1}^p \nu_i^\ast h_i(x^\ast) \\ \leq & f_0(x^\ast) \end{align}$

故上述不等号皆可取等，这其中蕴含着两个重要的结论，

• 一是“ $x^\ast$ 最小化了 $L(x,\lambda^\ast,\nu^\ast)$ 的值”，这个结论会在下一小节中用到，

• 另一个重要结论是：

$\sum_{i=1}^m \lambda_i^\ast f_i(x^\ast) = 0$

• 又因为 $\lambda\_i^\ast \geq 0$，$f_i(x^\ast) \leq 0$，所以，

$\lambda_i^\ast f_i(x^\ast) = 0, \quad i=1,\dots,m$

这个条件被称为互补松弛条件（Complementary slackness）。它对原问题的 任意 的最优解 $x^\ast$ 和对偶问题最优解 $d^\ast$ 皆成立。

这个条件实际上描述的是：

如果对偶变量的某个分量非零 $\lambda_i^\ast \gt 0$，那该分量对应的约束条件严格取等号，即 $f_i(x^\ast) = 0$。
如果某约束条件不严格取等号，即 $f_i(x^\ast) \lt 0$，则对应的对偶变量分量一定为零，即 $\lambda_i^\ast = 0$。

7.2 KKT条件

在继续之前，需要假定函数 $f_0,\dots,f_m,h_1,\dots,h_p$ 是一阶可微的，因此定义域是开集。并且对问题的凸性仍无任何假定。

* 必要性（对任意问题）

还是记 $x^\ast$ 和 $(\lambda^\ast,\nu^\ast)$ 分别表示原问题与对偶问题的最优解。则 $x^\ast$ 最小化了 $L(x,\lambda^\ast,\nu^\ast)$（这是上一小节的一个结论），从而梯度为 $0$，即有：

$\nabla f_0(x^\ast)+\sum_{i=1}^m \lambda_i^\ast\nabla f_i(x^\ast)+\sum_{i=1}^p \nu_i^\ast\nabla h_i(x^\ast)=0$

因此，我们有，

* KKT条件

$\begin{align} f_i(x^\ast) \leq & 0, \quad i=1,\dots,m \\ h_i(x^\ast) = & 0, \quad i=1,\dots,p \\ \lambda_i^\ast \succeq & 0, \quad i=1,\dots,m \\ \lambda_i^\ast f_i(x^\ast) = & 0, \quad i=1,\dots,m \\ \nabla f_0(x^\ast)+\sum_{i=1}^m \lambda_i^\ast\nabla f_i(x^\ast)+\sum_{i=1}^p \nu_i^\ast\nabla h_i(x^\ast) = & 0 \end{align}$

这便是KKT条件（Karush-Kuhn-Tucker condition）。对任何优化问题而言，最优解一定满足KKT条件。

* KKT条件必要性

对于任何优化问题，只要 $x^\ast$ 和 $(\lambda^\ast,\nu^\ast)$ 分别是原问题与对偶问题的最优解，则 $(x^\ast,\lambda^\ast,\nu^\ast)$ 一定满足KKT条件。即KKT条件是使一组解成为最优解的必要条件。

7.3 充分性（对凸优化问题）

既然任意的最优解都满足KKT条件，那么自然要问，满足KKT条件的解是否就是问题的最优解呢？

实际上，当问题是凸优化问题时，KKT条件便是充分的了。简单证明如下：

设 $(\tilde{x},\tilde{\lambda},\tilde{\nu})$ 满足KKT条件。因为 $\lambda_i \geq 0$，所以 $L(x,\tilde{\lambda},\tilde{\nu})$ 是关于 $x$ 的凸函数。由KKT最后一个条件知，$\tilde{x}$最小化了 $L(x,\tilde{\lambda},\tilde{\nu})$ 的值。因此，

$\begin{align} g(\tilde{\lambda},\tilde{\nu}) = & L(\tilde{x},\tilde{\lambda},\tilde{\nu}) \\ = & f_0(\tilde{x})+\sum_{i=1}^m \tilde{\lambda_i} f_i(\tilde{x}) + \sum_{i=1}^p \tilde{\nu_i} h_i(\tilde{x}) \\ = & f_0(\tilde{x}) \end{align}$

因此对偶差（duality gap）为$0$，解分别是原问题最优和对偶最优的。
小结一下，这就是说，对于任何目标函数和约束函数都一阶可微的凸优化问题，任何满足KKT条件的 $x^\ast$ 和 $(\lambda^\ast,\nu^\ast)$，其对偶差为 $0$。此时若 Slater's condition 满足，则说明这个对偶最优值可以被取到，因而它就是问题的最优解了。

* KKT条件充分性

对于任何目标函数和约束函数都一阶可微的凸优化问题，且满足 Slater's condition，则 $x$ 和 $(\lambda,\nu)$ 分别是原问题与对偶问题的最优解，当且仅当 $(x,\lambda,\nu)$ 满足KKT条件。即KKT条件是使一组解成为这类问题最优解的充分（也是必要）条件。
KKT条件的作用在于，某一类问题的KKT条件可以直接被（分析地）解出。而对大多数其他凸优化问题，便把任务由解优化问题转移到解KKT条件上，因为两者是等价的。

8. 例子：注水算法

* P237-boyed