凸优化入门：凸函数定义、判定条件与主流求解方法

搞机器学习、做运筹调度、写信号处理算法绕来绕去都会撞上同一个词凸优化。如果你正在啃凸函数定义和判定条件或者刚翻开那本经典的《Convex Optimization》那么这篇东西就是给你准备的。我当年第一次看到“凸函数”四个字的时候也觉得不就是个碗状曲线吗有什么好讲的。后来真到建模和调算法时才发现凸性不是一个“性质”而是一张安全网它保证了局部最优就是全局最优保证了一堆数值方法不会乱跑也让“为什么梯度下降能收敛”这种事有了理论底气。这篇博文打算把凸函数的定义、判定条件、凸优化问题的标准形式以及主流求解方法串成一条线中间穿插我实际建模和写代码时踩过的坑。适合正在学优化理论的研究生、做算法工程的开发者以及任何想搞清楚“为什么凸优化这么有用”的读者。我不堆公式但该严格的地方也会给出严格的数学形式保证你看完既能理解原理也能直接上手用。1. 凸优化为什么值得单独拿出来说1.1 现实问题里到处都是“找最优”先聊点实际的。工程里所谓优化本质就是在一堆可行选择里挑一个最好的。物流公司要设计配送路线让总里程最短广告系统要在预算约束下让点击量最大机器学习要在参数空间里找一组权重让损失函数最小这些都叫优化问题。可现实中的优化问题大多数是“野路子”目标函数坑坑洼洼有无数个局部最低点。你从一个点出发往下走走到一个谷底就停住了但你没法保证这是不是整个山脉的最低点。神经网络训练就是这样损失函数高度非凸我们实际上连“全局最优”的边都摸不到只能靠各种启发式技巧去找一个“足够好”的解。凸优化之所以被单独拎出来是因为它恰好避开了这个麻烦。凸优化问题的目标函数和可行域都有非常好的几何性质在这种结构下任何一个局部最优解都天然是全局最优解。这意味着你不需要碰运气不需要试几百个随机起点算法稳稳当当往下走就行。1.2 凸优化是“可验证的少数派”你可能想问现实中真的有多少问题是凸的我的经验是比你想象的多但需要你会“变着法子看”。很多经典模型比如线性回归、岭回归、Lasso、支持向量机、线性规划、二次规划、最大熵模型本质上都是凸优化问题。有些问题本身不是凸的但经过变量替换、松弛、对偶变换之后能转成一个凸问题来近似求解。这几年大火的压缩感知、低秩矩阵恢复核心思想就是把非凸的难题“松弛”成凸问题再解。所以凸优化不是一门“象牙塔学问”它几乎是所有定量学科的公共基础设施。理解了凸函数定义和判定条件你才谈得上真正理解这些算法为什么有效什么时候会失效以及怎么把一个新问题转化成能用现成工具求解的形式。2. 凸函数定义从直观到严谨2.1 先用橡皮筋和碗建立直觉凸函数最直观的理解就是“碗状函数”。画一条曲线如果在曲线上任意取两个点把这两个点用线段连起来线段上的每一个点都在曲线的上方那这个函数就是凸函数。你可以想象在曲线下方拉一根橡皮筋如果橡皮筋和曲线完全贴合、中间没有缝隙那这就是凸的反过来如果曲线像个波浪橡皮筋会被“架空”在某段上方那它就不是凸函数。一维情况很好理解但工程里我们遇到的函数绝大多数是多元的曲面在三维空间里就像一个碗但更高维就想象不出来了。没关系数学定义可以帮我们严格地判定。2.2 严格的数学定义和那个常被忽略的前提凸函数的严格定义长这样一个函数 f: R^n → R如果它的定义域 dom f 是凸集并且对任意 x, y ∈ dom f任意 θ ∈ [0, 1]都有f(θx (1-θ)y) ≤ θf(x) (1-θ)f(y)那么 f 是凸函数。这个式子第一眼看可能有点抽象拆开来看其实就是刚才橡皮筋那句话的数学版θ 相当于在线段上“走”的比例θ 0 时在 y 端θ 1 时在 x 端中间值就是线段上的点。左边是函数在线段中点的实际值右边是两端函数值的加权平均。要求左边 ≤ 右边就是说函数图像永远不高于割线也就是“碗口朝上”。这里有个细节我当年学的时候完全没注意定义域必须是凸集。很多教材讲判定条件时默认定义域是 R^n 或者一个区间一带而过。但一旦定义域本身凹凹凸凸、不满足凸集条件哪怕函数表达式再漂亮它也不是凸函数。举个例子f(x) 1/x 在正半轴上是凸的在整个实数域上并不是因为定义域在 0 处断开了而且 (-∞, 0) ∪ (0, ∞) 这个集合不是凸集——取 x -1y 1线段中点 0 根本不在定义域里。这种小坑在建模时特别容易踩尤其是用变量代换之后定义域悄悄变了而你还在用原来的结论。2.3 严格凸和强凸别混为一谈凸函数的基础上还有两个加强版本实际分析算法收敛性时经常用到。严格凸函数要求不等号在 x ≠ y、θ ∈ (0, 1) 时严格成立即函数图像和割线之间永远有缝隙不允许存在平直的“躺在割线上”的部分。比如 f(x) x² 是严格凸的而 f(x) x 既是凸的也是凹的但不严格凸。强凸函数则更强它要求函数在“碗状”的基础上还有一定的曲率下限。用式子表达就是存在一个常数 m 0使得 f(x) - (m/2)||x||² 仍然是凸函数。直观理解就是这个碗至少和某个二次函数一样“翘”。强凸性是很多算法收敛速度分析的关键比如梯度下降在强凸函数上能线性收敛而在一般凸函数上只有 O(1/k) 的次线性速度。三者的关系我用一个简单的对照表整理一下类型核心要求几何直觉对算法的意义凸割线在函数图像上方碗状局部最优 全局最优严格凸割线严格在图像上方没有平直段最优解唯一若存在强凸曲率有正下界碗够“翘”梯度类方法可线性收敛注意严格凸不一定强凸比如 f(x) x⁴ 是严格凸的但在 x 0 附近曲率趋于 0不是强凸。这一点在分析算法时经常被拿出来考值得记牢。3. 凸函数判定条件怎么快速判断一个函数是不是凸的3.1 一阶条件切平面永远在函数下方如果函数 f 可微那么判凸有一个非常漂亮的一阶条件对定义域内任意 x, y都有f(y) ≥ f(x) ∇f(x)^T (y - x)这个式子的意思是函数在任意一点做一阶泰勒展开得到的切平面或切线永远位于函数图像的下方。你可以想象一个碗随便在哪一点放一个平板切平面碗的其余部分一定在这个平板上面绝不会穿透到下面去。这个条件的实际价值在算法设计里体现得最明显。很多迭代算法比如梯度下降、近端梯度法本质上是反复利用这个切平面构造一个“目标函数的下界”然后去最小化这个下界来逼近最优解。如果你确认目标函数是凸的那么用一阶条件构造的下界就是可靠的迭代不会出现“越走越离谱”的情况。我建议你自己动手画一个非凸函数的图像试试比如 f(x) x³在 x 0 附近的切线已经和函数相交了函数会穿到切线的下方。这种“切线穿帮”的情况就是非凸函数的典型特征。3.2 二阶条件海森矩阵半正定如果函数二阶可微判定更省事f 是凸函数当且仅当它的海森矩阵Hessian matrix也就是二阶偏导数组成的矩阵在整个定义域上都是半正定的记作 ∇²f(x) ⪰ 0。一维情况下这个条件等价于 f(x) ≥ 0也就是二阶导数非负、曲线一直“凹向上”。多维情况下海森矩阵的半正定意味着它所有的特征值都 ≥ 0也就是函数沿任何方向的二阶方向导数都非负。换句话说不管从哪个方向切一刀截面曲线都是碗状。实际判断时多元函数的半正定性检查通常靠特征值分解或者用西尔维斯特准则检查各阶顺序主子式。但手算二维、三维还行高维就麻烦了。工程上更常用的做法是“看结构”如果一个函数能表示成若干个已知凸函数的保凸运算组合那它大概率是凸函数。这就引出了下一小节。3.3 保凸运算你不需要每次都从头判定研究判定的最终目的是为了建模型。真正干活的时候没人会对一个十几维的海森矩阵挨个做特征值分解。我们更常用的是一套“保凸运算规则”像搭积木一样从已知凸函数构造新凸函数。最常用的保凸运算有这几类非负加权和如果 f₁, f₂ 是凸函数且 w₁, w₂ ≥ 0那么 w₁f₁ w₂f₂ 也是凸函数。与仿射函数复合如果 f 是凸函数那么 f(Ax b) 也是凸函数。这个性质非常重要因为它允许你做变量替换不破坏凸性。逐点最大值如果 f₁, f₂ 是凸函数那么 max(f₁, f₂) 也是凸函数。比如多个线性函数取最大得到的正是常见的分段线性凸函数。逐点上确界无穷多个凸函数的逐点上确界仍然是凸函数。这个性质是很多对偶方法成立的基石。透视函数如果 f 是凸函数那么 g(x, t) t·f(x/t)t 0也是凸函数。这个运算看起来冷门但它能把很多看似不凸的问题“看”成凸的信息论里的相对熵、量子力学里的某些熵函数都和透视运算有关。我自己的实操经验是拿到一个新函数先别急着手算二阶条件先看它是不是由已知凸函数通过上述运算组合出来的。如果答案是肯定的那凸性基本就保住了省去大量验证时间。4. 凸优化问题的标准形式与核心性质4.1 标准形式目标函数 不等式约束 等式约束光有凸函数还不够优化问题还要把可行域约束进来。凸优化问题的标准形式长这样minimize f₀(x) subject to fᵢ(x) ≤ 0, i 1, ..., m hⱼ(x) 0, j 1, ..., p其中 f₀, f₁, ..., fₘ 都是凸函数而 hⱼ 必须是仿射函数也就是线性函数加常数形如 a^T x - b 0。这里有个容易让人困惑的点为什么不等式约束要求凸函数 ≤ 0等式约束却必须是仿射原因在于我们要求可行域是凸集。不等式约束 fᵢ(x) ≤ 0 中fᵢ 是凸函数它的下水平集 {x | fᵢ(x) ≤ 0} 是凸集多个凸集的交集还是凸集。但如果等式约束里 hⱼ 是随便一个非线性函数hⱼ(x) 0 的集合一般不是凸集比如 h(x) x² - 1 0 的解集是 {1, -1}根本不连通更谈不上凸。所以标准形式把等式约束限制成仿射本质是为了保护可行域的凸性。4.2 局部最优就是全局最优凸优化最核心的定理凸优化问题最迷人的一条性质就是任意局部最优解同时也是全局最优解。证明并不复杂假设 x* 是局部最优解如果存在某个可行点 y 使得 f₀(y) f₀(x*)那么考虑连接 x* 和 y 的线段上的点 z θy (1-θ)x*。由于可行域凸、目标函数凸f₀(z) ≤ θf₀(y) (1-θ)f₀(x*) f₀(x*)。当 θ 趋向 0 时z 无限靠近 x*这就和 x* 是局部最优解矛盾了。这条性质的实际意义怎么强调都不为过。在非凸问题里算法跑完你根本不知道结果到底好不好可能只是一个局部陷阱但在凸问题里只要能找到局部最优解就一定是全局最优解。所以工程上一旦把问题建模成凸优化就等于给结果上了“全球保底”。4.3 对偶理论和 KKT 条件约束优化的钥匙实际约束优化问题不能光靠梯度等于零来解因为最优解很可能落在约束边界上。这时候就要引入拉格朗日对偶。对原始问题构造拉格朗日函数 L(x, λ, ν) f₀(x) Σλᵢfᵢ(x) Σνⱼhⱼ(x)其中 λ ≥ 0 是 Lagrange 乘子。然后定义对偶函数 g(λ, ν) infₓ L(x, λ, ν)。对偶函数一定是凹函数即使原始问题非凸且在任何可行点上对偶函数值都不超过原始目标值。如果原始问题是凸的并且满足某些约束规范条件比如 Slater 条件存在严格可行的内点那么强对偶成立——原始问题的最优值和对偶问题的最优值相等。这时最优解 x* 与最优对偶变量 (λ*, ν*) 满足 KKT 条件原始可行性fᵢ(x*) ≤ 0hⱼ(x*) 0对偶可行性λᵢ* ≥ 0互补松弛λᵢ* fᵢ(x*) 0稳定性∇f₀(x*) Σλᵢ* ∇fᵢ(x*) Σνⱼ* ∇hⱼ(x*) 0我对 KKT 条件最直观的理解是它在告诉你“约束边界上哪块起作用、哪块可以忽略”。互补松弛条件说明如果某个不等式约束在最优点处没有绷紧fᵢ(x*) 0那对应的乘子必然是 0反过来只有真正挡路的约束fᵢ(x*) 0才会有非零乘子。这个视角在建模型时极有用——你可以一眼看出哪些约束是“虚的”哪些是真正限制系统性能的瓶颈。5. 凸优化方法总论从识别到求解的完整路径5.1 拿到问题先做三件事识别、变换、验证很多初学者拿到一个实际问题第一反应是直接调库求解结果要么求解器报错要么解出来结果完全不合理。我自己的经验是建模阶段应该先做三件事。第一件事是识别凸性。把目标函数和约束逐项列出来再用第 3 节那套保凸运算去验证确认它确实是凸优化问题。如果发现某个约束是非凸的先别放弃看看能不能通过变量代换、松弛、或者把约束改写到目标函数里来把它变成凸的。比如经典的 Lasso 问题带 L1 范数惩罚的目标本身是凸的但如果有人把约束写成 ||x||₁ ≥ t 这种“大于等于”的形式那就变成非凸了因为 L1 范数的上水平集不是凸集。这种错误我在帮同事 review 代码时见过不止一次。第二件事是变换形式。同一个问题可以用多种等价形式表达但不同形式对数值算法的友好程度差别巨大。比如把绝对值约束展开成两个线性不等式把二次约束用 Schur 补引理改写成线性矩阵不等式这些变换都能让标准求解器更快、更稳地处理。第三件事是验证最优性。解完之后用 KKT 条件或者对偶间隙检查结果。这一步很多人在科研和工程里都会跳过但其实非常关键。有一次我调一个资源分配问题求解器返回了一个看起来合理的解结果一对 KKT 条件发现互补松弛严重不满足——原因是建模时把某个约束方向写反了。没有验证步骤这种错误会一直潜伏到上线才暴露。5.2 主流求解算法梯度法、牛顿法、内点法凸优化问题的算法工具箱相当丰富按适用场景大致分几类。梯度下降类方法是最基础的。因为一阶条件保证切平面在函数下方所以沿着负梯度方向走一定能下降。普通梯度下降适合大规模问题、精度要求不高的场景如果函数强凸加个合适步长就能获得线性收敛。近端梯度法Proximal Gradient是梯度法的进阶版适合目标函数里含有不可导项比如 L1 范数的情况它把可导部分做梯度步、不可导部分做近端算子投影。我处理稀疏优化问题时最喜欢用它每步计算都很轻量。牛顿类方法利用二阶信息迭代次数远少于梯度法但每步要算海森矩阵的逆适合中小规模、精度要求高的场景。拟牛顿法比如 L-BFGS则平衡了两者不用显式构造海森矩阵只需要利用梯度差来近似二阶信息是很多机器学习库的默认选项。内点法Interior Point Method是求解中小规模凸优化问题最经典的通用方法。它的核心思路是把不等式约束通过障碍函数“塞进”目标函数里然后沿着中心路径迭代逼近边界。Boyd 教材里大量例题用的就是内点法思路。实际软件里像 CVX、CVXPY 背后的求解器如 ECOS、SCS都实现了内点法或一阶方法用户不需要关心细节但理解原理能帮你选择合适的求解器如果问题规模不大、精度要求高选内点法如果数据量巨大选一阶方法更划算。5.3 工程求解工具随手记我自己常用的工具链是这么搭配的CVXPY / CVX建模层用 Python 或 MATLAB 描述目标函数和约束自动检测凸性底层调用求解器。适合快速原型验证。ECOS / SCS / OSQP底层求解器。ECOS 适合中小规模锥规划SCS 适合大规模问题OSQP 专门解二次规划速度很快。Gurobi / MOSEK商业求解器处理大规模线性规划、二次规划、锥规划非常强悍许可证对学生免费工业界也广泛使用。自己写梯度下降当问题规模极大、标准求解器内存撑不住时手写分布式梯度下降往往是最终方案。选工具的经验法则先试 CVXPY 加默认求解器Thomas 问题解不动再换 SCS再不行换 Gurobi。实测下来大部分规模在几千变量以内的凸优化问题CVXPY 一行代码就能搞定根本不用手写算法。6. 学习路上的常见坑与实用经验6.1 初学凸函数时容易踩的五个坑第一个坑是不检查定义域。前面提到的 f(x) 1/x 就是典型例子。很多教材习题会故意用这类函数钓鱼考试时也喜欢出一定记住凸函数要求定义域本身是凸集。第二个坑是把“凸函数”和“凸集”搞混。函数凸不凸看的是函数图像和割线的关系集合凸不凸看的是集合内任意两点连线是否还在集合内。凸函数的下水平集一定是凸集但凸集对应的指示函数才是凸函数两者不能画等号。第三个坑是一维结论直接搬到多维。一维情况下凸函数要求 f(x) ≥ 0高维要求海森矩阵半正定。问题在于半正定不是“每个对角元素大于等于 0”就行的还要检查交叉项和非对角项。初学者最常犯的错误就是只检查了对角线忽略了海森矩阵的耦合特征值。第四个坑是忽视非光滑凸函数。凸函数不一定可微比如 f(x) |x| 在原点不可导但它确实是凸函数。很多初学者一开始学的判定条件都要求可微遇到不可导的凸函数就懵了。实际工程里 L1 范数、 hinge loss 都是不可导凸函数需要用次梯度或近端算子来处理。第五个坑是以为“凸问题一定有解析解”。凸优化保证的是全局最优和算法收敛不保证你能写出解的闭式表达式。绝大多数现实建模问题最终都得靠数值算法跑不要总想着推公式。6.2 Boyd 那本书怎么读一个参考路线因为标题里提到了那本经典的 Convex OptimizationBoyd Vandenberghe王书宁等译网上常见的电子版也基本是这个很多人买了或下载之后发现书太厚啃不下去就放弃了。我的建议是分三条线来读。第一条线第 2 章和第 3 章是关于凸集和凸函数的所有基础概念配合每章末尾的习题做一遍尤其是那些“判断下面函数是不是凸函数”的题这些训练会大幅提高你对凸性的敏感度。这一阶段大概需要两到三周每天一到两小时。第二条线第 4 章和第 5 章讲凸优化问题形式和对偶理论这是理解整个领域的枢纽。第 5 章的 KKT 条件如果第一遍看不懂可以先跳过证明只记住结论和几何含义。我建议用一个小规模二次规划亲手验证 KKT 条件比读书更有效。第三条线第 9 章到第 11 章讲数值算法包括梯度法、牛顿法、内点法。这一部分如果觉得数学推导繁琐可以直接用代码实现一遍单纯形法之外的简单梯度算法观察收敛曲线再回头看书。Boyd 这本教材的课后配套课程视频斯坦福公开课也值得跟刷笔记网上到处都有配合食用效果拔群。还有一个实用技巧做例题时不要只看不画图。把所有例题里的凸函数、水平集、最优解位置在二维平面上画出来理解速度会快非常多。凸优化的可视化直觉一旦建立起来后面学对偶、学分解算法都会轻松不少。6.3 理论、代码与应用三条腿走路最后说点我做这类项目总结出来的体会。凸优化理论本身很优美但如果只学理论不碰代码容易变成“纸上谈兵”——你会在真正建模时发现自己连 CVXPY 怎么定义变量都要查半天。反过来如果只调库不学理论遇到求解器报错、收敛慢、结果解释不了的情况你完全没有排查方向。我个人的工作流程是先用纸笔把问题写成标准形式标出目标函数、不等式约束、等式约束验证凸性再用 CVXPY 快速搭一个原型跑通小规模数据最后如果规模大了、速度不够再考虑针对性手写算法。这套流程我推荐给所有刚入门凸优化的朋友它能把理论和工程串起来让你每一步都有据可依。7. 一个可以立刻上手的例子最小二乘加线性约束讲了这么多抽象的东西最后我分享一个可以直接跑的小例子帮你把上面的概念串起来。假设我们要解一个带线性等式约束的最小二乘问题minimize (1/2)||Ax - b||² subject to Cx d这个问题的目标是凸函数二次函数海森矩阵 A^T A 半正定等式约束是仿射的所以整体是凸优化问题。用 CVXPY 求解只需要几行代码import cvxpy as cp import numpy as np # 构造数据 m, n 100, 20 A np.random.randn(m, n) b np.random.randn(m) C np.random.randn(5, n) d np.random.randn(5) # 定义变量与目标 x cp.Variable(n) objective cp.Minimize(0.5 * cp.sum_squares(A x - b)) # 定义约束并求解 constraints [C x d] problem cp.Problem(objective, constraints) problem.solve() # 输出结果 print(最优值:, problem.value) print(最优解:, x.value)跑完这个例子你可以做几件加深理解的事第一用拉格朗日乘子手推这个问题的闭式解再和 CVXPY 的结果对比验证 KKT 条件第二把等式约束改成不等式约束 Cx ≤ d观察行为变化第三在目标函数里加一个 L1 正则项 λ||x||₁用近端梯度法手写一遍感受不可导凸函数怎么处理。当年我学凸优化时就是靠这一连串的小例子把概念串起来的。每跑通一个例子就用手推一遍理论再改改参数看看结果如何变化。现在看来这种“理论-代码-应用”交替推进的方式是学习凸优化性价比最高的路径。