biscuitの博客

核心出装：共轭函数（Fenchel Conjugate）#

给定一个函数 $f: \mathbb{R}^n \to \mathbb{R}$，其共轭函数 $f^*$ 定义为：

• $y^T x$ ：向量 $y$ 和 $x$ 的内积,线性函数

• $f(x)$ ：原函数的值

• sup ：取上确界（supremum），即在 $x$ 的定义域内找到使 $y^T x - f(x)$ 最大的值

ps:对于二维情况，x,y 都是实数。y就是斜率。

Fenchel对偶#

Fenchel对偶是一个更一般的框架，可以处理更广泛的优化问题，包括非凸问题。拉格朗日对偶可以看作是Fenchel对偶在特定约束条件下的一个特例。

原问题形式一般长这样：

Fenchel对偶问题的形式是：

这里 $f^*$ 是 $f$ 的共轭函数，$f^*(-A^T y)=\sup_{x} (-y^T A x - f(x))$；$g^*$ 是 $g$ 的共轭函数，$g^*(y)=\sup_{z} (y^T z - g(z))$。

$g(Ax)$ 是什么？代表了约束条件，是约束条件的指示函数（indicator function），当 $Ax$ 满足约束条件时 $g(Ax)=0$，否则 $g(Ax)=+\infty$。因此，原问题中的约束条件被隐含在 $g(Ax)$ 中。

例如线性规划标准形式中的约束条件 $Ax = b$ 可以通过定义 $g(z) = 0$ if $z = b$ else $+\infty$ 来表示。