Lecture 13 · Duality Uses and Correspondents

References

• Lecture: https://www.stat.cmu.edu/~ryantibs/convexopt-F18/
• Reading:
  1. 最优化: 建模、算法与理论, 刘浩洋等, 2.6 小节 (Conjugate Functions)
  2. 一文读懂凸优化中的「对偶」概念（二）：可以用一个观点解释所有对偶吗？ - 江南FLY的文章 - 知乎
  3. 一文读懂凸优化中的「对偶」概念（三）：Fenchel 共轭是什么东西？它有什么用？ - 江南FLY的文章 - 知乎

本章将希望通过讨论对偶这一概念在数学中的各种应用, 来串联深化对对偶概念的理解.

1. Dual Norm

Definition (Norm and Semi-Norm). 对于向量空间 $V$, 其上的范数 (Norm) 是一个从 $V$ 到实数域 $\mathbb{R}$ 的函数, 记为 $\Vert \cdot \Vert :V\to \mathbb{R}$. 满足以下性质:

1. 绝对齐次性: 对于任意 $x\in V$ 和任意实数 $t$, 有 $\Vert tx\Vert =|t|\Vert x\Vert$.
2. 三角不等式: 对于任意 $x,y\in V$, 有 $\Vert x+y\Vert \le \Vert x\Vert +\Vert y\Vert$.
3. 非负性: 对于任意 $x\in V$, 有 $\Vert x\Vert \ge 0$. 并且当且仅当 $x=0$ (零向量) 时, 有 $\Vert x\Vert =0$.
   • 若对于某范数只满足绝对齐次性和三角不等式, 但允许在某些 $x\ne 0$ 时 $\Vert x\Vert =0$, 则称为半范数 (Semi-Norm).

范数有如下性质:

• 对于任意范数 $f(x)=\Vert x\Vert$, 其都是凸函数.

  Proof of norm convexity

  立即由三角不等式和齐次性推出。对于任意 $x,y\in V$ 和 $t\in [0,1]$, 有:

  $$\Vert tx+(1-t)y\Vert \le t\Vert x\Vert +(1-t)\Vert y\Vert$$

  因此, $f(x)$ 是凸函数.

  $\square$

Definition (Dual Norm). 对于任意范数 $f(x)=\Vert x\Vert$, 其对偶范数 $f_{\ast }$ 定义为:

$$f_{\ast }(x):=\Vert x{\Vert }_{\ast }=\underset{\Vert z\Vert \le 1}{\max }{z}^{\top }x$$

对于范数和其对偶范数, 由定义立刻可以推得如下不等关系:

$$|z^{\top }x|\le \Vert x\Vert \cdot \Vert z{\Vert }_{\ast }$$

Proof of the dual norm inequality

• 对任意 $x\ne 0$, 都有:

  $$z^{\top }x=\Vert x\Vert z^{\top }\frac{x}{\Vert x\Vert }$$

• 而 $x/\Vert x\Vert$ 是单位向量, 因此有:

  $$z^{\top }x=\Vert x\Vert z^{\top }\frac{x}{\Vert x\Vert }\le \Vert x\Vert \cdot \underset{\Vert v\Vert \le 1}{\max }{z}^{\top }v=\Vert x\Vert \cdot \Vert z{\Vert }_{\ast }$$

$\square$

给定任意一个具体范数, 其对偶范数总是存在的, 例如:

• 对于 ${\ell }_p$ 范数, 其对偶范数为 ${\ell }_q$ 范数, 其中 $1/p+1/q=1$.

  • ${\ell }_1$ 范数的对偶范数为 ${\ell }_{\infty }$ 范数; ${\ell }_2$ 范数的对偶范数为 ${\ell }_2$ 范数

  Proof of the ${\ell }_p/{\ell }_q$ dual norm claim

  • 由 Holder’s Inequality 可得:

    $$|z^{\top }x|\le \Vert z{\Vert }_q\cdot \Vert x{\Vert }_p$$

  • 若 $\Vert x\Vert \le 1$, 则有:

    $$|z^{\top }x|\le \Vert z{\Vert }_q\cdot \Vert x{\Vert }_p\le \Vert z{\Vert }_q\cdot 1=\Vert z{\Vert }_q$$

  • 因此:

    $$\underset{\Vert x{\Vert }_p\le 1}{\max }|z^{\top }x|\le \underset{\Vert x\Vert \le 1}{\max }\Vert z{\Vert }_q\cdot \Vert x{\Vert }_p=\Vert z{\Vert }_q$$

  • 并且确能找到一个 $x$ 使得上式等号成立.

  $\square$

• 对于 Trace Norm, 其对偶范数为 Nuclear Norm.

  • Trace Norm 类比 ${\ell }_1$ 范数, 定义为 $\Vert X{\Vert }_{\ast }={\sum }_{i=1}^n{\sigma }_i(X)$, 其中 ${\sigma }_i(X)$ 是 $X$ 的奇异值.
  • Nuclear Norm 类比 ${\ell }_{\infty }$ 范数, 定义为 $\Vert X{\Vert }_{op}={\sigma }_{\max }(X)$, 其中 ${\sigma }_{\max }(X)$ 是 $X$ 的最大奇异值.

Note: Young's Inequality and Holder's Inequality

Holder’s Inequality 是一个常见的代数不等式, 其证明由 Young’s Inequality 推出. 而对偶相当于是给出了该不等式的几何解释.

Lemma (Young’s Inequality). 设 $p>1$, 且 $q$ 满足 $1/p+1/q=1$, 则对于任意 $a,b\ge 0$, 有:

$$ab\le \frac{a^p}{p}+\frac{b^q}{q}$$

Theorem (Holder’s Inequality). 设 $1\le p\le \infty$, 且 $q$ 满足 $1/p+1/q=1$, 则对任意 $x,z\in {\mathbb{R}}^n$, 有:

$$|x^{\top }z|\le \Vert x{\Vert }_p\cdot \Vert z{\Vert }_q$$

对偶范数还有一个重要性质:

$$(\Vert x{\Vert }_{\ast }{)}_{\ast }=\Vert x\Vert$$

Proof of the double dual norm identity

• 考虑如下优化问题:

  $$\underset{y}{\min }\Vert y\Vert ,\text{s.t.}y=x$$
  • 显然, 唯一可行解为 $y=x$, 故最优解也是 $p^{\ast }=\min y=\Vert x\Vert$.

• 其 Lagrangian 为:

  $$L(y,\lambda )=\Vert y\Vert +{\lambda }^{\top }(x-y)=\Vert y\Vert +{\lambda }^{\top }x-{\lambda }^{\top }y$$

• 其对偶函数为:

  $$d(\lambda )=\underset{y}{\inf }L(y,\lambda )=\underset{y}{\inf }(\Vert y\Vert +{\lambda }^{\top }x-{\lambda }^{\top }y)=\underset{y}{\inf }(\Vert y\Vert -{\lambda }^{\top }y)+{\lambda }^{\top }x$$

  • 若 $\Vert \lambda {\Vert }_{\ast }\le 1$

    • 根据广义 Holder’s Inequality 可得:

      $${\lambda }^{\top }y\le \Vert \lambda {\Vert }_{\ast }\cdot \Vert y\Vert \le \Vert y\Vert$$

    • 故 $\Vert y\Vert -{\lambda }^{\top }y\ge \Vert y\Vert -\Vert y\Vert =0$.

    • 此时 $d(\lambda )={\lambda }^{\top }x$.

  • 若 $\Vert \lambda {\Vert }_{\ast }>1$

    • 根据 Dual Norm 的定义, 有:

      $$\Vert \lambda {\Vert }_{\ast }=\underset{\Vert y\Vert \le 1}{\max }{y}^{\top }\lambda \ge 1$$

    • 这说明在单位球内, 至少存在一个 $y$ 使得 $y^{\top }\lambda \ge 1$. 故有关系:

      $$y^{\top }\lambda \ge 1\ge \Vert y\Vert$$

    • 此时 $d(\lambda )={\inf }_y(\Vert y\Vert -{\lambda }^{\top }y)=-\infty$.

  • 综上所述, Lagrangian 的对偶函数为:

    $$d(\lambda )=\{\begin{array}{ll}{\lambda }^{\top }x,& \text{if }\Vert \lambda {\Vert }_{\ast }\le 1\\ -\infty ,& \text{if }\Vert \lambda {\Vert }_{\ast }>1\end{array}$$

• 而 Lagrange 对偶问题本身即为对偶函数的最优值:

  $$\underset{\Vert \lambda {\Vert }_{\ast }\le 1}{\max }d(\lambda )=\underset{\Vert \lambda {\Vert }_{\ast }\le 1}{\max }{\lambda }^{\top }x=(\Vert x{\Vert }_{\ast }{)}_{\ast }$$

• 最后可以验证, 最开始构造的 ${\min }_y\Vert y\Vert ,\text{s.t.}y=x$ 是一个满足 Slater 条件的凸优化问题, 满足强对偶性, 故原问题和对偶问题的最优值相等, 即:

  $$\Vert x\Vert =(\Vert x{\Vert }_{\ast }{)}_{\ast }$$

$\square$

2. Conjugate Functions

Definition (Fenchel Conjugate). 对于函数 $f:{\mathbb{R}}^n\to \mathbb{R}$, 其 Fenchel 共轭 (Fenchel Conjugate) $f^{\ast }:{\mathbb{R}}^n\to \mathbb{R}$ 定义为:

$$f^{\ast }(\mathbf{t})=\underset{\mathbf{x}\in {\mathbb{R}}^n}{\sup }({\mathbf{t}}^{\top }\mathbf{x}-f(\mathbf{x}))$$

Fenchel 共轭在几何上可以直观理解如下 (此处考虑一元情况).

• 共轭函数将遍历每一个可能的 $t$ 的取值. 对于当前的 $t$ 值:

  • 考虑一个以 $t$ 为斜率的直线, 记作 $l_t=tx+c$.

  • 保证 $l_t$ 恒在 $f$ 的下方, 即 $l_t\le f(x)$ 恒成立.

  • 在此前提下, 通过移动 $c$ 使得 $l_t$ 与 $f$ 相切, 则此时的截距 $c$ 即为 $-f^{\ast }(t)$, 即在该 $t$ 值下, 共轭函数 $f^{\ast }(t)$ 的值为 $-c$.

    Proof of the geometric conjugate interpretation

    • 对于直线 $l_t=tx+c$, 由于其恒在 $f$ 的下方, 故有:

      $$tx+c\le f(x)$$

    • 因此:

      $$c\le f(x)-tx$$

    • 在相切的极端情况下, 表示 $c$ 已取最大值, 此时有 ${\inf }_{x}f(x)-tx=c_{\max }$. 故取相反数, 有 ${\sup }_x(f(x)-tx)=-c_{\max }$. 即 $f^{\ast }(t)=-c_{\max }$.

    $\square$

Fenchel 共轭有如下性质:

1. 不论 $f$ 是否为凸函数, $f^{\ast }$ 都是凸函数.
2. 若 $f$ 为凸函数, 则 $f^{\ast \ast }=f$. 这意味着, 对于凸函数, 共轭函数和凸函数是一一对应的. 给定一个凸函数的共轭函数, 可以唯一确定一个凸函数: $$f(x)=\underset{\mathbf{t}\in {\mathbb{R}}^n}{\sup }({\mathbf{t}}^{\top }\mathbf{x}-f^{\ast }(\mathbf{t}))$$
3. 即使对于非凸函数, 也有 $f^{\ast \ast }$ 也能正常定义, 且有 $f^{\ast \ast }\le f$ 恒成立. 此时, $f^{\ast \ast }$ 可以看作是 $f$ 的一种凸化(convexification)近似.
4. Fenchel-Young Inequality: $\forall \mathbf{t}\in {\mathbb{R}}^n,\mathbf{x}\in {\mathbb{R}}^n$, 有: $$f(\mathbf{x})+f^{\ast }(\mathbf{t})\ge {\mathbf{t}}^{\top }\mathbf{x}$$
5. 若 $f(\mathbf{u},\mathbf{v})=f_1(\mathbf{u})+f_2(\mathbf{v})$, 则有 $f^{\ast }(\mathbf{u},\mathbf{v})=f_1^{\ast }(\mathbf{u})+f_2^{\ast }(\mathbf{v})$.
6. 如果函数 $f$ 是 $\beta$-strongly convex 的, 则有 $f^{\ast }$ 是 ${\beta }^{-1}$-smooth 的.
7. 对于闭凸函数 $f$ 及任意 $\mathbf{x},\mathbf{y}\in {\mathbb{R}}^n$, 有: $$\mathbf{x}\in \partial f(\mathbf{y})⟺\mathbf{y}\in \partial f^{\ast }(\mathbf{x})⟺{\mathbf{x}}^{\top }\mathbf{y}=f(\mathbf{x})+f^{\ast }(\mathbf{y})$$

Note: Geometric Interpretation and Convexity Revisit

首先补充一些解析几何的基础知识.

• 给定一个方向向量 $\mathbf{u}\in {\mathbb{R}}^n$ 以及截距 $b\in \mathbb{R}$, 则可以由此定义一个超平面: ${\mathbf{u}}^{\top }\mathbf{x}=b$.

  
  • 其含义为, 所有在 $\mathbf{u}$ 方向上投影长度为 $b$ 的点的集合, 即为一个超平面.
  • 其中, $\mathbf{u}$ 为超平面的法向量; $b$ 为超平面距离原点的距离, 并且其正负代表了超平面是沿着法向量的正方向还是负方向.

• 给定超平面 ${\mathbf{u}}^{\top }\mathbf{x}=b$, 其将空间分为两个半空间, 分别记作 ${\mathbf{u}}^{\top }\mathbf{x}\le b$ 和 ${\mathbf{u}}^{\top }\mathbf{x}\ge b$. 此处符号本身就代表了是沿着 $\mathbf{u}$ 的箭头方向同侧或异侧.

• 给定凸集 $C\subseteq {\mathbb{R}}^n$, 固定方向 $\mathbf{u}$, 则定存在一个超平面, 使得 $C$ 中的所有点都在该超平面的同侧, 即支撑超平面 (Supporting Hyperplane) 定理.

  • 若记这个 $\mathbf{u}$ 方向上的关于 $C$ 的支撑超平面为 ${\mathbf{u}}^{\top }\mathbf{x}=h_C(\mathbf{u})$, ($h$ 称为支撑函数 (Support Function)), 则有: $$h_C(\mathbf{u})=\underset{\mathbf{x}\in C}{\sup }{\mathbf{u}}^{\top }\mathbf{x}$$
    • 此处可以理解为: $h_C(\mathbf{u})$ 即为超平面的截距项, 相当于是在给定平面的方向角度后, 不断沿着 $\mathbf{u}$ 指向方向移动, 直到恰好和 $C$ 中的点”相切”, 此时得到的最大距离即为 $h_C(\mathbf{u})$.
    • 支持函数本身还具有如下性质:
      • 支持函数本身是凸函数, 且具有齐次性: $h_C(\alpha \mathbf{u})=\alpha h_C(\mathbf{u})$.
      • 两个凸集的 Minkowski Sum 的支撑函数等于两个凸集的支撑函数之和: $h_{C_1+C_2}(\mathbf{u})=h_{C_1}(\mathbf{u})+h_{C_2}(\mathbf{u})$. 其中 $C_1+C_2=\{\mathbf{x}+\mathbf{y}\mid \mathbf{x}\in C_1,\mathbf{y}\in C_2\}$.
      • 若集合在 $\mathbf{u}$ 方向上的支撑超平面与集合的交点唯一, 则其在该点可微.

• 任意凸集也可以表示为其所有的支撑超平面的交集.

Note: Conjugate Functions and Duality

我们可以从 epigraph 的角度来理解 Fenchel 共轭 (参见 Reading References 3).

• 回忆, 对于凸函数 $f$, 其 epigraph 为这个函数图象及其上方所有点构成的集合, 即:

  $$\text{epi}(f)=\{(\mathbf{x},t{)}^{\top }\in {\mathbb{R}}^{n+1}:t\ge f(\mathbf{x})\}$$

  并且对于凸函数, 其 epigraph 是凸集.

• 根据支撑超平面的性质, 可以得到, 对于凸集 $\text{epi}(f)$, 其在 $\mathbf{u}\in {\mathbb{R}}^{n+1}$ 方向上的支撑超平面为 ${\mathbf{u}}^{\top }\mathbf{x}=h_f(\mathbf{u})$, 其中:

  $$h_f(\mathbf{u})=\underset{(\mathbf{x},t{)}^{\top }\in \text{epi}(f)}{\sup }⟨\left(\begin{array}{c}\mathbf{x}\\ t\end{array}\right),\mathbf{u}⟩$$
  • 进一步, 将方向 $\mathbf{u}$ 分解为 $\mathbf{u}=(\mathbf{v},\nu {)}^{\top }$, 其中 $\mathbf{v}\in {\mathbb{R}}^n$ 和 $\nu \in \mathbb{R}$, 则有: $$h_f(\mathbf{v},\nu )=\underset{(\mathbf{x},t{)}^{\top }\in \text{epi}(f)}{\sup }(\nu t+{\mathbf{v}}^{\top }\mathbf{x})$$
  • 注意到, 在最后一个维度 (即 $t$ 所在维度) 上, 恒有 $t\ge f(\mathbf{x})$, 即 $t$ 是有下界而无上界的. 因此, 为保证上式有解 (确定一个有穷的超平面), 必须有 $\nu <0$ (这里为了和后文记号一致, 取 $\nu =-\lambda <0$, 则此刻有: $$\begin{array}{rl}{h}_f(\mathbf{v},\nu )& =\underset{(\mathbf{x},t{)}^{\top }\in \text{epi}(f)}{\sup }({\mathbf{v}}^{\top }\mathbf{x}-\lambda t)\\ & \le \underset{\mathbf{x}\in {\mathbb{R}}^n}{\sup }\left({\mathbf{v}}^{\top }\mathbf{x}-\lambda f(\mathbf{x})\right),\text{since }t\ge f(\mathbf{x})\\ & =\lambda \left(\underset{\mathbf{x}\in {\mathbb{R}}^n}{\sup }⟨\frac{\mathbf{v}}{\lambda },\mathbf{x}⟩-f(\mathbf{x})\right)\\ & =\lambda f^{\ast }\left(\frac{\mathbf{v}}{\lambda }\right)\end{array}$$

• 惊! 这里发现, 对于凸函数的 epigraph, 其支撑超平面的截距项 (即支持函数) 竟然就是其 Fenchel 共轭函数! 即:

  $$h_f(\mathbf{v},\nu )=\lambda f^{\ast }\left(\frac{\mathbf{v}}{\lambda }\right)$$

反过头来, 我们再从代数角度说明共轭函数和支撑函数的关系.

• 考虑一个关于凸集的指示函数, 即:

  $$f(\mathbf{x})=I_C(\mathbf{x})=\{\begin{array}{ll}0,& \mathbf{x}\in C\\ +\infty ,& \mathbf{x}\notin C\end{array}$$

  其中 $C$ 是凸集.

• 易知, 对于该函数, 当 $\mathbf{x}\in C$ 时, $f(\mathbf{x})=0$; 当 $\mathbf{x}\notin C$ 时, $f(\mathbf{x})=+\infty$. 因此为取 $\sup$ 时, 只有当 $\mathbf{x}\in C$ 时, 函数有界, 即:

  $$f^{\ast }(\mathbf{y})=\underset{\mathbf{x}\in C}{\sup }({\mathbf{y}}^{\top }\mathbf{x})$$

• 该共轭函数恰恰就是刚刚介绍的支撑函数! 这也再次从数学上印证了支撑函数和共轭函数是等价的.

因此, 支撑函数和共轭函数, 其本质相当于都在描述对于凸集的支持平面的超参数化.

2.1 Conjugate of Simple Quadratic Function

• 考虑 $f(x)=\frac{1}{2}{\mathbf{x}}^{\top }Q\mathbf{x}$，其中 $Q\in {\mathbb{S}}_{++}^n$（即 $Q$ 是 $n$ 阶实对称正定矩阵）。
• 根据共轭函数的定义，有： $$f^{\ast }(\mathbf{y})=\underset{\mathbf{x}\in {\mathbb{R}}^n}{\sup }({\mathbf{y}}^{\top }\mathbf{x}-\frac{1}{2}{\mathbf{x}}^{\top }Q\mathbf{x})$$
• 易知，对于该函数，这个表达式是关于 $\mathbf{x}$ 的严格 concave 函数，在 $\mathbf{x}=Q^{-1}\mathbf{y}$ 处取得极值。因此，共轭函数为： $$f^{\ast }(\mathbf{y})=\frac{1}{2}{\mathbf{y}}^{\top }{Q}^{-1}\mathbf{y}$$

2.2 Conjugate of Norm

任何范数的共轭是其对偶范数单位球的 indicator, 即:

$${\left(\Vert x{\Vert }_p\right)}_{\text{conjugate}}⟷I_{\{\Vert x{\Vert }_q\le 1\}},\frac{1}{p}+\frac{1}{q}=1$$

Warning: 注意区分 Dual Norm 和 Conjugate Norm.

2.3 Lasso Dual

我们下面尝试用这个例子将上述的几个理论和性质串联起来.

给定 $\mathbf{y}\in {\mathbb{R}}^n,X\in {\mathbb{R}}^{n\times p}$, 考虑如下 Lasso 问题:

$$\underset{\mathbf{\beta }\in {\mathbb{R}}^p}{\min }\frac{1}{2}\Vert \mathbf{y}-X\mathbf{\beta }{\Vert }_2^2+\lambda \Vert \mathbf{\beta }{\Vert }_1$$

• 首先, 根据 Lagrange Duality 的思路, 我们需要将该问题转为一个含约束问题. 引入辅助变量 $\mathbf{z}=X\mathbf{\beta }$, 则有:

  $$\underset{\mathbf{\beta }\in {\mathbb{R}}^p,\mathbf{z}\in {\mathbb{R}}^n}{\min }\frac{1}{2}\Vert \mathbf{y}-\mathbf{z}{\Vert }_2^2+\lambda \Vert \mathbf{\beta }{\Vert }_1,\text{s.t.}\mathbf{z}=X\mathbf{\beta }$$
  • 则对应的 Lagrangian 为: $$L(\mathbf{\beta },\mathbf{z},\mathbf{\lambda })=\frac{1}{2}\Vert \mathbf{y}-\mathbf{z}{\Vert }_2^2+\lambda \Vert \mathbf{\beta }{\Vert }_1+{\mathbf{\mu }}^{\top }(\mathbf{z}-X\mathbf{\beta })$$
  • 则对应的 Lagrange Dual Function 为: $$\begin{array}{rl}d(\mathbf{\mu })& =\underset{\mathbf{\beta }\in {\mathbb{R}}^p,\mathbf{z}\in {\mathbb{R}}^n}{\inf }L(\mathbf{\beta },\mathbf{z},\mathbf{\mu })=\underset{\mathbf{\beta }\in {\mathbb{R}}^p,\mathbf{z}\in {\mathbb{R}}^n}{\inf }\left(\frac{1}{2}\Vert \mathbf{y}-\mathbf{z}{\Vert }_2^2+\lambda \Vert \mathbf{\beta }{\Vert }_1+{\mathbf{\mu }}^{\top }(\mathbf{z}-X\mathbf{\beta })\right)\\ & =\underset{\mathbf{z}}{\inf }\left(\frac{1}{2}\Vert \mathbf{y}-\mathbf{z}{\Vert }_2^2+{\mathbf{\mu }}^{\top }\mathbf{z}\right)+\underset{\mathbf{\beta }}{\inf }\left(\lambda \Vert \mathbf{\beta }{\Vert }_1-{\mathbf{\mu }}^{\top }(X\mathbf{\beta })\right)\\ & =\frac{1}{2}\Vert \mathbf{y}{\Vert }_2^2-\frac{1}{2}\Vert \mathbf{y}-\mathbf{\mu }{\Vert }_2^2-\lambda \cdot \underset{\text{Fenchel Conjugate of }\Vert \mathbf{\beta }{\Vert }_1}{\underbrace{\underset{\mathbf{\beta }}{\sup }\left(-\Vert \mathbf{\beta }{\Vert }_1+⟨\mathbf{\beta },\frac{X^{\top }\mathbf{\mu }}{\lambda }⟩\right)}}\\ & =\frac{1}{2}\Vert \mathbf{y}{\Vert }_2^2-\frac{1}{2}\Vert \mathbf{y}-\mathbf{\mu }{\Vert }_2^2-\lambda \cdot I\{\Vert X^{\top }\mathbf{\mu }/\lambda {\Vert }_{\infty }\le 1\}\end{array}$$
  • 则对应的对偶问题为: $$\begin{gathered} \underset{\mathbf{\mu }}{\sup }d(\mathbf{\mu })=\frac{1}{2}\Vert \mathbf{y}{\Vert }_2^2-\frac{1}{2}\Vert \mathbf{y}-\mathbf{\mu }{\Vert }_2^2,\text{s.t.}\Vert X^{\top }\mathbf{\mu }{\Vert }_{\infty }\le \lambda \\ ⟺\underset{\mathbf{\mu }}{\inf }\Vert \mathbf{y}-\mathbf{\mu }{\Vert }_2^2\text{subject to}\Vert X^{\top }\mathbf{\mu }{\Vert }_{\infty }\le \lambda \end{gathered}$$
    • 其相当于一个投影问题, 将 $\mathbf{y}$ 投影到一个凸多面体上: $C:=\{\mathbf{u}\in {\mathbb{R}}^n:\Vert X^{\top }\mathbf{u}{\Vert }_{\infty }\le \lambda \}$.
  • 此外, 可以验证 Slater 条件成立, 故强对偶性成立, 最优解必满足 KKT 条件.
    • 其中, 关于 $\mathbf{z}$ 的 Stationary 条件为: $${\nabla }_{\mathbf{z}}L(\mathbf{\beta },\mathbf{z},\mathbf{\mu })=\mathbf{z}-\mathbf{y}+\mathbf{\mu }=0⟹\mathbf{\mu }=\mathbf{z}-\mathbf{y}=X\mathbf{\beta }-\mathbf{y}$$
    • 这说明对偶变量 $\mathbf{\mu }$ 事实上即为 Lasso 问题的残差, 对偶问题即为在一个 ${\ell }_{\infty }$ 的约束下, 最小化残差.
    • 反过来, $X\mathbf{\beta }=\mathbf{y}-\mathbf{\mu }$, 因此原问题的解同时也相当于对偶问题的残差.

• 上述的 Lasso Dual 问题事实上是 Fenchel Duality 的特例. 因此若在不引入辅助变量 $\mathbf{z}$ 的情况下, 也可以直接使用 Fenchel Duality 来求解. 其一般形式为:

  $$\underset{\mathbf{\beta }}{\inf }f(X\mathbf{\beta })+g(\mathbf{\beta })$$

  给出结论, 其对偶问题为:

  $$\underset{\mathbf{\mu }}{\sup }-f^{\ast }(\mathbf{\mu })-g^{\ast }(-X^{\top }\mathbf{\mu })$$

  • 首先利用该结论求解 Lasso 问题. 将 Lasso 的表达式与 Fenchel Duality 这里的记号对齐, 则有原始形式 ${\inf }_{\mathbf{\beta }}\frac{1}{2}\Vert \mathbf{y}-X\mathbf{\beta }{\Vert }_2^2+\lambda \Vert \mathbf{\beta }{\Vert }_1$, 其中 $f(X\mathbf{\beta })=\frac{1}{2}\Vert \mathbf{y}-X\mathbf{\beta }{\Vert }_2^2$ 和 $g(\mathbf{\beta })=\lambda \Vert \mathbf{\beta }{\Vert }_1$.

  • 分别计算 $f^{\ast }$ 和 $g^{\ast }$ 的值.

    • $f(\mathbf{z})=\frac{1}{2}\Vert \mathbf{y}-\mathbf{z}{\Vert }_2^2=\frac{1}{2}\Vert \mathbf{y}{\Vert }_2^2-{\mathbf{y}}^{\top }\mathbf{z}+\frac{1}{2}\Vert \mathbf{z}{\Vert }_2^2$, 因此根据 Fenchel 共轭的定义, 有: $$\begin{array}{rl}{f}^{\ast }(\mathbf{\mu })& =\underset{\mathbf{z}}{\sup }({\mathbf{\mu }}^{\top }\mathbf{z}-f(\mathbf{z}))\\ & =\underset{\mathbf{z}}{\sup }({\mathbf{\mu }}^{\top }\mathbf{z}-\frac{1}{2}\Vert \mathbf{y}{\Vert }_2^2+{\mathbf{y}}^{\top }\mathbf{z}-\frac{1}{2}\Vert \mathbf{z}{\Vert }_2^2)\\ & ={\mathbf{y}}^{\top }\mathbf{\mu }+\frac{1}{2}\Vert \mathbf{\mu }{\Vert }_2^2-\frac{1}{2}\Vert \mathbf{y}{\Vert }_2^2\end{array}$$
    • $g(\mathbf{\beta })=\lambda \Vert \mathbf{\beta }{\Vert }_1$, 因此根据 Fenchel 共轭的定义, 有: $$g^{\ast }(\mathbf{\mu })=I\{\Vert \mathbf{\mu }{\Vert }_{\infty }\le \lambda \}$$

  • 因此, 其对偶问题为:

    $$\underset{\mathbf{\mu }}{\sup }\left[-f^{\ast }(\mathbf{\mu })-g^{\ast }(-X^{\top }\mathbf{\mu })\right]=\underset{\mathbf{\mu }}{\sup }\left[-{\mathbf{y}}^{\top }\mathbf{\mu }-\frac{1}{2}\Vert \mathbf{\mu }{\Vert }_2^2-\frac{1}{2}\Vert \mathbf{y}{\Vert }_2^2-I\{\Vert X^{\top }\mathbf{\mu }{\Vert }_{\infty }\le \lambda \}\right]$$

    其等价于:

    $$\begin{array}{rl}\underset{\Vert X^{\top }\mathbf{\mu }{\Vert }_{\infty }\le \lambda }{\inf }\left[{\mathbf{y}}^{\top }\mathbf{\mu }+\frac{1}{2}\Vert \mathbf{\mu }{\Vert }_2^2+\frac{1}{2}\Vert \mathbf{y}{\Vert }_2^2\right]& =\underset{\Vert X^{\top }\mathbf{\mu }{\Vert }_{\infty }\le \lambda }{\inf }\left[\frac{1}{2}\Vert \mathbf{y}+\mathbf{\mu }{\Vert }_2^2-\frac{1}{2}\Vert \mathbf{y}{\Vert }_2^2+\frac{1}{2}\Vert \mathbf{y}{\Vert }_2^2\right]\\ & =\frac{1}{2}\underset{\Vert X^{\top }\mathbf{\mu }{\Vert }_{\infty }\le \lambda }{\inf }\left[\Vert \mathbf{y}+\mathbf{\mu }{\Vert }_2^2\right]\end{array}$$

  • 若进行变量等价代换, 令 $\mathbf{u}=\mu +\mathbf{y}$, 则有:

    $$\underset{\Vert X^{\top }\mathbf{u}{\Vert }_{\infty }\le \lambda }{\inf }\left[\Vert \mathbf{y}-\mathbf{u}{\Vert }_2^2\right]$$

    此处和 Lasso 问题的对偶问题形式一致.

2.4 Duality and Conjugate

最终再强调一下 Duality 和 Conjugate 的关系作为上述的总结.

当我们考虑一个一般的无约束优化问题:

$$\min f(x)+g(x)$$

我们可以引入辅助变量 $z=x$, 则有:

$$\min f(x)+g(z),\text{s.t.}z=x$$

因此其 Lagrange 函数为:

$$L(x,\mu ,z)=f(x)+g(z)+\mu (z-x)$$

因此其 Lagrange Dual Function 为:

$$\begin{array}{rl}d(\mu )& =\underset{x,z}{\inf }L(x,\mu ,z)\\ & =\underset{x}{\inf }\left[f(x)+g(z)+\mu (z-x)\right]\\ & =-\underset{x}{\sup }\left[-f(x)+\mu x\right]-\underset{z}{\sup }\left[g(z)-\mu z\right]\\ & =-f^{\ast }(\mu )-g^{\ast }(-\mu )\end{array}$$

故: 对于 ${\inf }_{x}f(x)+g(x)$ 问题, 其对偶问题为 ${\sup }_{\mu }-f^{\ast }(\mu )-g^{\ast }(-\mu )$. 对偶和共轭总是这样成对出现的.

3. Dual Cones

Definition (Dual Cone). 对于一个 Cone $K\subseteq {\mathbb{R}}^n$ ($K$ 是锥, 即满足 $\forall x\in K,\alpha \ge 0,\alpha x\in K$), 其对偶锥 (Dual Cone) 定义为:

$$K^{\ast }=\{\mathbf{y}\in {\mathbb{R}}^n\mid {\mathbf{y}}^{\top }\mathbf{x}\ge 0\text{ for all }\mathbf{x}\in K\}$$

Figure: Illustration of a dual cone.

对于 Dual Cone, 有如下性质:

• $K^{\ast }$ 永远是凸锥, 即使 $K$ 不是凸的.
• $y\in K^{\ast }$ 当且仅当 $\{y^{\top }x\ge 0\}$ 的半空间包含 $K$.
• 对于凸且闭的 $K$, 有 $K^{\ast \ast }=K$.

我们同样可以用支撑超平面的方法来理解 Dual Cones 的定义. (参见 Reading Reference 2)

• 首选原始的 $K$, 其作为锥, 天然的就必须以原点为顶点. 而对应的支撑超平面也就必然经过原点

• 而考虑其支撑函数, 有

  $$h_K(\mathbf{u})=\underset{\mathbf{x}\in K}{\sup }{\mathbf{u}}^{\top }\mathbf{x}=\{\begin{array}{ll}\infty & \text{if }\mathbf{u}\notin K^{\ast }\\ 0& \text{if }\mathbf{u}\in K^{\ast }\end{array}$$

• 因此, 如果我们从支撑超平面的视角去看，对偶锥是非常平凡的记号, 其表示的就是该凸锥的支撑超平面的所有法向量.

3.1 Dual Cones and Dual Problems

考虑如下一般形式的优化问题:

$$\underset{x}{\min }f(x),\text{s.t.}x\in K$$

其中 $f$ 是凸函数, $K$ 是凸锥.

其对偶问题为:

$$\underset{\mu }{\max }-f^{\ast }(A^{\top }\mu )-I_K^{\ast }(-\mu )$$

其中 $I_K^{\ast }(y)={\sup }_{z\in K}{y}^{\top }z$, 是 $K$ 的 support function. 因此其等价于

$$\underset{\mu }{\max }-f^{\ast }(A^{\top }\mu ),\text{s.t.}\mu \in K^{\ast }$$

其中 $K^{\ast }$ 是 $K$ 的对偶锥.

Related Notes

• Duality
• Optimality Conditions for Constrained Optimization
• Canonical Problem Forms