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

搞机器学习、做运筹调度、写信号处理算法，绕来绕去都会撞上同一个词：凸优化。如果你正在啃凸函数定义和判定条件，或者刚翻开那本经典的《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 = -1，y = 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*) ≤ 0，hⱼ(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 Optimization（Boyd & 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||₁，用近端梯度法手写一遍，感受不可导凸函数怎么处理。

当年我学凸优化时，就是靠这一连串的小例子把概念串起来的。每跑通一个例子，就用手推一遍理论，再改改参数看看结果如何变化。现在看来，这种“理论-代码-应用”交替推进的方式，是学习凸优化性价比最高的路径。