凸优化核心：共轭函数定义、性质与对偶推导全解析

老实说第一次在凸优化教材里撞见共轭函数Fenchel conjugate时我是非常抗拒的。一个如此抽象的定义f*(y) sup_x { yᵀx − f(x) }既不知道它想描述什么也不知道它能用来干什么只能机械地背性质应付考试。直到后来自己在推导对偶问题、折腾近端算法、分析各种正则化项的时候才意识到这个看似绕圈子的概念本质上是把函数从“点坐标”换到“斜率坐标”的一种视角转换。这篇内容我就想把这个理解过程完整拆开讲清楚。从几何直观、手算流程、核心性质到对偶推导里的实际应用都会尽量用大白话讲明白全程还会穿插一些我踩过的坑和总结出来的验证方法。适合正在学凸优化、最优化理论或者搞机器学习但一直没弄懂对偶那块来龙去脉的读者。读完你至少能做到两件事见到一个常见函数能独立求出它的共轭以及看懂拉格朗日对偶问题是怎么一步步被“翻”出来的。1. 先从几何直观下手共轭函数是“斜率坐标”下的函数1.1 忘掉公式一条下界直线背后的最大截距先别看那个 sup 公式我们从几何出发。一个函数 f(x)画在坐标系里是一条曲线或者高维的曲面。对于任意给定的斜率 y我可以考虑一族直线L(x) yᵀx − b这里的 b 是截距。如果某个 b 让整条直线都在函数 f 的下方也就是对所有 x 都满足 yᵀx − b ≤ f(x)那这条直线就是 f 的一个全局下界。问题是给定斜率 y我最多能把这条直线抬多高也就是所有可行 b 里面最大值是多少把不等式重新整理一下b ≥ yᵀx − f(x)要对所有 x 成立。所以 b 的最大值就是 sup_x { yᵀx − f(x) }。这个值就是 f*(y)。而 f(x) 的最小值不是f*(y) 是“给定斜率下的最大允许截距”。所以共轭函数的几何含义其实特别朴素它记录的是原函数在所有不同斜率下能被多高的下界直线贴住。y 是斜率f*(y) 本质上是这个斜率对应截距的相反数信息。每一个 y 对应一个“斜率通道”f* 表示的是原函数在这个通道里呈现出来的样子。1.2 为什么逐点上确界能带来“凸性白嫖”共轭函数还有一条很妙的性质不管原函数 f 是不是凸函数f* 一定是凸函数。这几乎是白来的原因就藏在定义的形式里。你看 f*(y) sup_x { yᵀx − f(x) }。这里 x 只是参数真正自变量是 y而 yᵀx 对固定 x 来说就是关于 y 的仿射函数。一族仿射函数的逐点上确界不管这族函数本身长什么样结果一定是凸函数。这个结论在凸分析里非常重要它意味着我们总能从任意一个“糟糕”的函数出发通过共轭变换得到一个“品性端正”的凸函数。这个性质让我想到一个类比一堆方向各异的射灯同时打向一面墙墙上的光斑轮廓一定是中间凸出来的那种形状不可能凹下去。仿射函数就是射灯墙上包络就是共轭函数。理解这一点之后再看各种证明里动不动就“因为 f* 是凸的所以……”这一步你就不会再发懵了。2. 共轭函数的计算流程三步走 一张常用表2.1 标准计算三步写目标式、找极值点、代回去很多教材不讲计算的通用流程我一律建议自己推一遍。求共轭函数不需要什么高深技巧本质就是一个带参数的优化问题第一步把 f*(y) sup_x { yᵀx − f(x) } 写出来明确目标函数 g(x) yᵀx − f(x)同时注意 f 的定义域。第二步对 x 求梯度或者一阶条件令梯度为零解出最优 x*(y) 的表达式。第三步把 x*(y) 代回 g(x)整理得到关于 y 的表达式就是 f*(y)。最后再检查一下定义域哪些 y 会让 sup 变成无穷大那些点也要写清楚。这套流程看着简单但第二步有个坑很多函数的极值点不在定义域内部或者一阶条件解不出来。这时候要回头重新考虑 sup而不是硬套求导。后面第 6 节我会专门说这个坑。2.2 四组必须手推的典型例子我建议大家至少亲手推一遍下面这几个例子它们几乎覆盖了 90% 的实际应用场景。第一个是二次函数。设 f(x) (1/2)xᵀQx其中 Q 是对称正定矩阵。计算过程很顺f*(y) sup_x { yᵀx − (1/2)xᵀQx }对 x 求导得到 y − Qx 0所以 x* Q⁻¹y代回去f*(y) yᵀQ⁻¹y − (1/2)(Q⁻¹y)ᵀQ(Q⁻¹y) (1/2)yᵀQ⁻¹y也就是说正定二次函数的共轭还是正定二次函数只是矩阵变成了逆矩阵。这个结论在实际里太常用了比如高斯分布的负对数似然、岭回归的目标函数都能直接套。第二个是负熵函数。设 f(x) x log x定义域 x ≥ 0并且补充定义 f(0) 0。计算f*(y) sup_{x ≥ 0} { yx − x log x }一阶条件y − (log x 1) 0得到 x* e^{y−1}代回去f*(y) y e^{y−1} − e^{y−1}(y−1) e^{y−1}这个结果在信息论、最大熵模型里会反复出现值得记牢。第三个是范数。设 f(x) ‖x‖其对偶范数记为 ‖y‖_* sup_{‖x‖≤1} yᵀx。这里要分两种情况讨论如果 ‖y‖_* ≤ 1那么对任意 x 都有 yᵀx ≤ ‖y‖_*‖x‖ ≤ ‖x‖所以 yᵀx − ‖x‖ ≤ 0而且 x 0 时取到 0因此 f*(y) 0。如果 ‖y‖_* 1那么存在一个单位向量 z 使得 yᵀz c 1取 x tz令 t → ∞yᵀx − ‖x‖ t(c − 1) → ∞所以 f*(y) ∞。合并起来就是 f*(y) I_{‖y‖_* ≤ 1}(y)也就是对偶范数单位球这个集合的示性函数。这个例子经常让人惊讶一个处处有限的范数它的共轭居然是一个只取 0 和 ∞ 的函数。第四个是示性函数。设 C 是一个集合f(x) I_C(x)x 在 C 内取 0否则取 ∞。直接套定义f*(y) sup_{x∈C} yᵀx这个 sup 就是集合 C 的支撑函数记作 σ_C(y)。示性函数和支撑函数是一对“完美对偶”在凸几何里地位很高。因为这四个例子太重要我建议把它们整理成一张对照表放在手边原函数 f(x)共轭函数 f*(y)备注(1/2)xᵀQx(1/2)yᵀQ⁻¹yQ 正定对称x log xe^{y−1}定义域 x≥0信息论常用‖x‖I_{‖y‖_*≤1}(y)对偶范数的单位球示性函数I_C(x)σ_C(y)示性函数与支撑函数对偶|x|₁I_{‖y‖_∞≤1}(y)L1 范数对偶是 L∞(1/2)|x|²(1/2)|y|²平方 L2 范数自共轭2.3 Fenchel 不等式定义带来的免费午餐从定义出发直接就能得到一个非常漂亮的不等式对任意 x ∈ dom f、y ∈ dom f*有f*(y) sup_z { yᵀz − f(z) } ≥ yᵀx − f(x)整理一下f(x) f*(y) ≥ yᵀx这个式子叫 Fenchel 不等式也常被称为 Young 不等式的一般形式。它的几何含义就是前面说的所有在 f 下方的直线满足的截距约束。别看它简单后面推导对偶问题时几乎处处要用到它而且它是判断次梯度关系的关键桥梁第 4 节会展开讲。3. 核心性质解析从 Fenchel 不等式到双共轭恢复3.1 Fenchel 不等式到底说了什么Fenchel 不等式看起来平淡其实它给出了原函数和共轭函数之间的一种“互制”关系。你如果知道 f(x) 的下界f*(y) 就会被压住反过来也一样。这种对称性正是对偶理论能工作的前提。有一个等价形式非常有用Fenchel 不等式取等号即f(x) f*(y) yᵀx这个等式并不总成立但一旦成立就说明 x 和 y 之间存在很强的对应关系。这个关系就是次梯度条件。在优化问题里它通常对应着原变量和对偶变量之间的最优性条件。这点留到第 4 节详细展开因为我觉得它是理解共轭函数价值的钥匙。3.2 共轭一定是凸函数哪怕原函数并不凸前面已经说过f* 是一族仿射函数的逐点上确界因此一定是凸函数。这个性质的意义再强调一遍就算 f 完全不凸、处处不连续只要它的共轭存在在其定义域内f* 一定是凸的。这在某些非凸优化场景里会派上大用场。比如一些非凸正则化问题虽然原问题难解但通过对偶变换可以在共轭那一侧得到一个凸问题。当然代价通常是原变量和对偶变量之间的映射关系不再是一一对应的所以实际使用时还得结合具体问题分析。3.3 双共轭定理与闭凸函数把共轭再共轭一次会怎样定义f**(x) sup_y { xᵀy − f*(y) }这个表达式可以理解为先转成“斜率坐标”再转回“点坐标”。问题是一次往返之后函数会被还原吗答案是不一定。这里必须引入一个概念闭凸函数。直观来说闭函数就是满足下半连续特性的函数它的上镜图epigraph是一个闭集。对于闭的真凸函数我们才有一个经典结论f** f如果 f 是闭真凸函数双共轭就精确还原 f。如果不是闭的比如定义在开区间上的凸函数双共轭通常会把定义域“补”成闭包。换句话说双共轭算子 f ↦ f** 实际上自动给原函数做了一个凸闭包运算。我一开始学到这里总是犯迷糊后来给自己找了个记忆方法共轭变换类似给函数做了一次“拉链”操作如果函数本身是闭凸的拉开再拉上就完全还原如果不是拉上后会被“物理定型”成它的闭凸包。这个偏差在实际问题里不能忽略很多理论证明都要求函数是闭的真凸函数原因就在这。3.4 一个打开定义域的反例为了说明“闭”这个条件不是摆设看一个简单的例子。设 f(x) I_{x ∈ (0,1)}(x)也就是开区间 (0,1) 的示性函数。它的共轭是f*(y) sup_{x ∈ (0,1)} yx如果 y 0sup 在 x → 1⁻ 时趋近 y但取不到所以 f*(y) y如果 y 0sup 在 x → 0⁺ 时趋近 0取不到所以 f*(y) 0如果 y 0sup 0。综合起来是 f*(y) max(y, 0)也就是 ReLU 函数。再共轭一次f**(x) I_{x ∈ [0,1]}(x)定义域被闭包成了 [0,1]。这个细微差别就体现了“开区间”问题。这个例子也提醒我遇到示性函数和支撑函数时边界上的开闭要特别小心。很多初学者算完就丢结果在对偶问题推导到最后一步才发现差了一个闭包debug 半天。4. 共轭与次梯度两者之间的“充要条件桥”4.1 关键等价关系与证明如果说共轭函数是几何上的“斜率坐标”那么次梯度就是分析上的“局部斜率信息”。两者之间有一个非常漂亮的完全等价关系y ∈ ∂f(x) ⟺ f(x) f*(y) yᵀx ⟺ x ∈ ∂f*(y)第一个等价其实从次梯度的定义就能直接推。y ∈ ∂f(x) 的定义是对所有 z 都有 f(z) ≥ f(x) yᵀ(z − x)。移项得到yᵀz − f(z) ≤ yᵀx − f(x) 对所有 z 成立左边对 z 取 sup正好就是 f*(y)所以得到 f*(y) ≤ yᵀx − f(x)。而 Fenchel 不等式又保证反向不等号恒成立所以只能取等号f*(y) f(x) yᵀx。反过来如果等号成立把上面的推导倒过来就能得到 y ∈ ∂f(x)。至于第二个等价因为 f*(y) 是闭凸函数共轭函数一定是闭凸的对它应用同一个结论就有 x ∈ ∂f*(y) 等价于 f*(y) f**(x) xᵀy。在 f 是闭真凸函数时 f** f就自然得到 x ∈ ∂f*(y)。这条链式等价关系像一座桥把“原函数的次梯度”和“共轭函数的次梯度”联系起来。对偶问题里的最优性条件、灵敏度分析、KKT 条件的解读很多都根植于这座桥。4.2 绝对值函数例子光说理论太干用绝对值函数 f(x) |x| 来走一遍。它的共轭函数是 f*(y) I_{|y| ≤ 1}(y)。现在检查几个点。当 x 0 时∂f(x) {1}对应的 y 只能是 1并且等号 f(x) f*(1) x 0 x yᵀx 成立。同时看共轭那侧∂f*(1) [0, ∞)确实包含 x 0。当 x 0 时∂f(x) {−1}对应 y −1∂f*(−1) (−∞, 0]确实包含 x 0。当 x 0 时情况最有意思。∂f(0) [−1, 1]也就是任何一个 y ∈ [−1, 1] 都满足 y ∈ ∂f(0)。再看共轭侧当 |y| 1 时∂f*(y) {0}包含 0当 y 1 时∂f*(1) [0, ∞)也包含 0当 y −1 时∂f*(−1) (−∞, 0]同样包含 0。完美对上。这个例子让我第一次真切感受到共轭函数“坐标变换”的威力绝对值函数在 x 0 有一个“角”这个角在斜率坐标下对应一整段区间 [−1, 1]而共轭函数在那个区间内是常数 0其在端点的次微分又能精确还原出所有 x。凸分析里“不可微点”的很多微妙之处用共轭视角一看就特别清楚。5. 现实应用对偶问题是怎么用共轭“翻”出来的5.1 从拉格朗日函数到对偶问题的一般套路学共轭函数最大的回报就是能很优雅地推导对偶问题。很多教材里对偶问题像是“变魔术”一样突然冒出来其实背后就是共轭函数在统一驱动。考虑一类非常常见的问题min_x f(x) g(Ax)这里 A 是线性映射。引入辅助变量 z Ax把问题改写为min_{x,z} f(x) g(z) s.t. z Ax写出拉格朗日函数L(x, z, y) f(x) g(z) yᵀ(z − Ax)对偶函数是 inf_{x,z} L(x, z, y)。关键在于这个 inf 可以拆成两个独立的 infinf_x { f(x) − (Aᵀy)ᵀx } −f*(Aᵀy)inf_z { g(z) yᵀz } −g*(−y)所以对偶函数就是d(y) −f*(Aᵀy) − g*(−y)看到没有f 和 g 的共轭函数直接跑到了对偶问题里。这一步推导为什么重要因为它把“写对偶问题”从玄学变成了机械运算原问题拆成 f g∘A对偶问题就是一组共轭函数的组合外加一个线性映射的转置。5.2 实操Lasso 回归的对偶推导拿 Lasso 练个手。问题min_β (1/2)‖y − Xβ‖₂² λ‖β‖₁引入 z Xβ拉格朗日写出来L(β, z, u) (1/2)‖y − z‖² λ‖β‖₁ uᵀ(z − Xβ)对 z 求 inf配方一下min_z { (1/2)‖z − y‖² uᵀz }令 w z − y则原式 min_w { (1/2)‖w‖² uᵀ(w y) } min_w { (1/2)‖w‖² uᵀw } uᵀy。在 w −u 处取得最小值 −(1/2)‖u‖² uᵀy。对 β 求 infinf_β { λ‖β‖₁ − (Xᵀu)ᵀβ } −sup_β { (Xᵀu)ᵀβ − λ‖β‖₁ }这里括号里正是 λ‖β‖₁ 的共轭在 y Xᵀu 处的取值。根据 L1 范数的共轭结论当 ‖Xᵀu‖∞ ≤ λ 时这个值是 0否则 −∞。所以对偶问题可以写成max_u { yᵀu − (1/2)‖u‖² } s.t. ‖Xᵀu‖∞ ≤ λ这个约束条件干净利落整个过程几乎没有手算负担。如果不借助共轭函数直接求对偶会绕很多弯。当你自己动手走完一遍这个推导再看网上各种对偶形式的推导基本都是一眼看穿。5.3 邻近算子与 Moreau 分解共轭函数在近端算法里还有一个非常漂亮的结论Moreau 分解。对任意闭真凸函数 f有prox_f(x) prox_{f*}(x) x这个恒等式意味着原函数的近端算子和对偶函数的近端算子之间存在一个互补关系。实际应用中很多算法需要交替计算原问题和对偶问题的近端算子Moreau 分解可以省一半计算量。举个例子如果 f(x) λ‖x‖₁prox_f 是软阈值算子那么 f* 是 ‖·‖∞ 约束的示性函数prox_{f*} 就是向 L∞ 球做投影。这两者确实互补。我在实现一些对偶近端算法时靠这个恒等式快速验证过不少实现是否正确非常实用。6. 常见问题与学习建议这些坑我基本都踩过6.1 常见的理解误区第一个误区是混淆 sup 和 max。很多教材里写 sup但初学者经常默认能取到最大值。实际上很多情况下 sup 是趋近但取不到的比如开区间上的支撑函数。我在第 3.4 节给的那个例子就属于这种。这个细节重要吗重要因为一旦写成 max后续推导中对“可达性”的判断就会出问题。第二个误区是忽略定义域外的函数值。凸分析约定函数在定义域外取 ∞这不是为了赶时髦而是让示性函数、支撑函数、共轭函数这些概念能统一处理。你写代码时可以不管 ∞但理论推导时一定要带着定义域走否则很多结论会出错。第三个误区是滥用双共轭还原。f** f 需要闭真凸函数作为前提。很多人在非凸问题里也直接写 f** f这显然是错的。非凸函数经过双共轭实际上会变成它的凸包这在某些松弛算法里是有意为之但在精确建模时不能想当然。第四个误区是把 Fenchel 共轭和复数的共轭弄混。虽然是同一个词但完全是两个概念。这个说法虽然有点好笑但我在实际指导学生时真的见过这种混淆。6.2 一条验证计算结果的操作路径共轭函数手算容易出错我自己的经验是算完之后一定要用数值方法交叉验证。对某个固定的小维度问题比如 n 3随机生成一组 x 和 y用解析表达式算 f*(y)再用数值方法求解 sup_x { yᵀx − f(x) }对比两者差值。比如用 Python 的 scipy.optimize.minimize 或者简单的网格搜索都能做。要注意的是数值求解时可能要处理定义域边界但作为一个 sanity check 已经足够了。这个习惯帮我抓出过不少符号运算里的正负号错误。另一个验证手段是用次梯度关系。随便取一个 x计算 ∂f(x) 里的一个 y然后验证 f(x) f*(y) 是否等于 yᵀx。如果不等说明某个环节算错了。这个检查完全不需要额外写优化代码非常便宜我强烈建议养成这个习惯。6.3 我的个人学习顺序建议如果你是刚开始学这块我不建议按照教材的顺序硬啃。我自己的体会是先花一小时理解几何直观也就是“斜率坐标”这个说法然后动手手推第 2.2 节那四组例子推完基本就有手感了之后再学 Fenchel 不等式和双共轭定理这时候定义和性质就不再是空中楼阁最后再去做 Lasso 或者 SVM 的对偶推导你会发现很多推导根本不需要死记硬背现推都来得及。反过来一上来就啃性质证明很容易陷入“每个字都认识但不知道在干嘛”的状态。我自己当年就是从性质开始学结果事倍功半后来换成“几何 → 手算 → 性质 → 应用”的顺序整个人通透了很多。最后再分享一个个人习惯遇到一个新的优化问题我第一件事就是尝试把目标函数拆成 f(x) g(Ax) 这种形式然后在心里过一遍两个函数的共轭长什么样。如果某个部分的共轭能算出来且形式简单那这个问题大概率有比较漂亮的对偶结构。如果你也能熟练做到这一点那说明共轭函数这个工具你已经真正拿捏住了。