凸优化入门：从凸函数到全局最优的建模与求解

1. 凸优化到底在做什么凭什么它是数值分析的硬骨头打开任何一本数值分析教材翻到优化那一章多半会先碰到“凸优化”三个字。很多初学者会问我们不是已经学了牛顿法、共轭梯度法、最小二乘吗为什么还要单独花力气研究凸性我的回答很简单因为凸性是“能保证找到全局最优解”的金字招牌。非凸问题你算半天可能只是掉进了一个局部坑里而凸问题的局部最优解就是全局最优解这一点直接决定了算法的可靠性和收敛行为的可预测性。这一篇笔记聚焦两个核心概念凸函数和凸优化问题。我会从定义出发讲到判别方法、典型例子、一阶和二阶条件的几何含义再落到实际求解时怎么把一个具体问题包装成凸优化标准形。整个过程不需要太高深的数学底子但需要你对手上的问题保持足够诚实——很多工程问题其实不是天然的凸问题而是我们通过变量替换、松弛、近似等手段“改造”出来的凸问题。这篇文章就是帮你建立这双改造问题的手。适合谁来读正在学数值分析、优化理论、机器学习基础的同学或者做工程仿真、信号处理、控制系统设计时被局部最优困扰的开发者。读完你至少能回答三件事什么是凸集、什么是凸函数、怎么判断一个优化问题是不是凸的以及不是凸的时候有哪些相对可行的处理思路。2. 凸集凸函数的地基先把这个概念吃透2.1 凸集的几何直觉与严格定义凸函数定义在凸集上所以先聊凸集。几何直觉特别简单一个集合是凸的当且仅当集合内任意两点的连线仍然完全落在集合内部。闭着眼睛想圆盘是凸的正方形是凸的任何实心多边形都是凸的但“月牙形”不是凸的空心圆环更不是因为你随便选两点连线线段会跑到集合外面。严格写成数学语言设集合 C 是某个向量空间通常是 R^n的子集若对任意 x, y ∈ C 以及任意 θ ∈ [0, 1]都有θx (1 - θ)y ∈ C则称 C 为凸集conv_set。注意这里 θ 的取值范围是闭区间 [0, 1]它的几何含义就是“插值比例”当 θ 1 时取 x当 θ 0 时取 yθ 在中间就对应线段上的某个点。这个看似不起眼的参数其实是整个凸分析的杠杆——所有关于凸性的命题最后几乎都落在“加权平均是否还留在集合里”这句话上。2.2 常见的凸集合从超平面到多面体给你几个高频出现的凸集例子数值分析里天天见超平面{x | a^T x b}。这是个平坦的仿射集合显然任何两点连线都在上面。半空间{x | a^T x ≤ b}。注意不等号方向这是一个“切蛋糕”式的区域也是凸的。多面体{x | Ax ≤ b}即若干半空间的交集。线性规划里说的可行域就是它凸性保证了单纯形法或内点法在理论上能走得很漂亮。范数球{x | ‖x‖ ≤ r}。任意范数定义的球都是凸集这个性质在正则化、稀疏优化里非常有用。比如 L2 球是圆球L1 球是菱形两者都凸但几何形态完全不同这直接影响了优化解的稀疏性。半正定锥S^n_ {X ∈ S^n | X ⪰ 0}对称半正定矩阵组成的集合。这个在矩阵优化、协方差估计、控制系统里属于“主场主力”。2.3 凸集的运算性质为什么交集不出问题凸集的运算有个特别让人省心的性质任意多个凸集的交集仍然是凸集。这句话太重要了因为它意味着你可以放心地把多个约束条件叠加在一起只要每个约束各自的集合是凸的整体可行域就还是凸的。比如说约束 x ≥ 0、y ≥ 0、x y ≤ 1 各自对应一个半空间取交集后得到的三角形区域依然凸。这在建模时是个强心针你可以把不同来源的约束拼装起来而不用担心拼出一个破碎的非凸区域。不过要小心一点两个凸集的并集不一定凸。两个不相交的圆盘并起来像个哑铃中间连线悬空当然不是凸的。所以建模时如果用了“或”逻辑x 属于 A 或 x 属于 B这通常就是非凸的警报信号。实操提示建模时看到“或”“不等于”“整数约束”“至少有一个成立”这类字眼第一反应就该是“这里可能破坏了凸性”需要额外处理。3. 凸函数定义、几何含义和一阶二阶条件3.1 凸函数的定义与直观看图有了凸集再定义凸函数就顺理成章。设 f 的定义域 dom f 是凸集且对任意 x, y ∈ dom f、任意 θ ∈ [0, 1]满足f(θx (1 - θ)y) ≤ θ f(x) (1 - θ) f(y)则 f 是凸函数。如果你把图画出来这个不等式说的就是函数图像上任意两点连成的弦永远位于函数图像的上方。反过来说如果弦跑到图像下方去了那就不是凸函数而是凹函数或者干脆不凸不凹。理解这个几何画面远比死记不等式重要——做题时你可以靠“画个草图、看弦的位置”快速判断一个函数是否凸。补充一个容易混淆的点凸函数和凸集的关系其实可以互相转化最著名的转化是下水平集。对任意实数 t凸函数 f 的下水平集 {x | f(x) ≤ t} 一定是凸集。这个性质的反方向不成立下水平集是凸的不代表函数是凸的。但这个单向性质已经很有用了比如在故障诊断、鲁棒优化里你要判断某个故障域是否“良性”先看它是不是某个凸函数的下水平集通常是一招好棋。3.2 一阶条件切平面永远在函数图像下方假设 f 可微那么凸函数有一个等价刻画对定义域内任意 x, y都有f(y) ≥ f(x) ∇f(x)^T (y - x)这个式子的几何意思是函数在任意一点的切线或切平面永远位于函数图像的下方。你想象一个碗形的抛物线从最低点引一条切线整条抛物线都在切线上面这就是一阶条件。这个条件在算法设计中是命根子。很多迭代算法梯度下降、牛顿法的变形其实都在做一件事利用当前点的梯度信息构造一个“切平面下的支撑”然后沿着让支撑面下降最快的方向试探。既然切线永远不高于函数值你沿着负梯度方向走一小步函数值理论上应该下降——这就是梯度下降法收敛性证明的核心依赖。如果你非要用生活类比把 f 想象成一个滑雪场的山丘凸函数的意思是整个山丘是一个光滑的凹形碗你在任何一点站的切线方向都能告诉你一条不让你“意外爬高”的路线。3.3 二阶条件Hessian 矩阵的半正定性如果 f 二阶可微凸性还有更代数化的等价条件对定义域内任意 xHessian 矩阵 ∇²f(x) 必须半正定即∇²f(x) ⪰ 0也就是对任意方向向量 d都有 d^T ∇²f(x) d ≥ 0。这个条件的直观理解是函数沿任意方向的二阶导数非负意味着函数在任何方向上都呈现“局部碗形”没有向下凹的方向。数值上怎么判断一个小矩阵可以算特征值看特征值是否全部非负大矩阵则常用 Cholesky 分解来判断半正定性或者在迭代过程中观察 Hessian 的最小特征值是否出现负值。单变量函数时这个条件就退化为熟悉的 f(x) ≥ 0。比如 f(x) x² 二阶导是 2恒正凸f(x) -x² 二阶导是 -2恒负凹f(x) x³ 在 x 0 区域二阶导为正在 x 0 区域为负所以整个 R 上非凸但在正半轴上是凸的。3.4 凸函数的运算规则怎么从已知构造未知实操中我们判断一个复杂函数是否凸很少直接拿定义去验证而是靠几条“组合规则”。这些规则自己动手一推就能记住非负加权和若 f, g 都是凸函数α, β ≥ 0则 αf βg 是凸函数。仿射复合若 f 是凸函数g(x) f(Ax b) 也是凸函数。这个规则特别常用比如把矩阵变换“嵌套”进凸函数里。最大值若 f_i 都是凸函数则 max_i f_i(x) 是凸函数。这是支撑函数、最大范数损失函数的凸性来源。最小值最小值运算一般保不住凸性除非对其中某一组变量做部分最小化且有额外条件。这一点经常被误用需要特别注意。透视函数g(x, t) t f(x/t)t 0保持凸性。这个在几何规划、熵类问题的建模中相当有用但理解门槛稍高本期先记结论。这些规则组合起来能让你像拼乐高一样判断复杂表达式的凸性。看到 L1 正则化的目标函数 ‖Ax - b‖² λ‖x‖₁第一项是范数的平方凸第二项是范数凸加法和非负系数还是凸。整个过程不需要手算二阶导。实操心得我判断一个函数凸不凸先画图一维或二维切片再用组合规则快速推理最后才用二阶条件做验证。三种手段互相交叉印证基本不会走眼。4. 凸优化问题标准形的写法与范式的力量4.1 凸优化问题的标准形一个优化问题写成标准形通常长这样minimize f₀(x) subject to f_i(x) ≤ 0, i 1, ..., m h_j(x) 0, j 1, ..., p如果 f₀ 和所有 f_i 都是凸函数所有 h_j 都是仿射函数即线性函数加常数这个问题就是凸优化问题。注意三个词目标函数凸、不等式约束函数凸、等式约束必须仿射。为什么等式约束不能是一般的非线性函数因为等式 h(x) 0 等价于 h(x) ≤ 0 且 -h(x) ≤ 0如果 h 是凸函数那么 -h 通常不是凸函数除非 h 正好是仿射的这样就会破坏可行域的凸性。所以等式约束的“仿射限制”不是建模者的偏好而是凸性理论上的一种必然。4.2 常见的凸优化问题家族很多教材喜欢把凸优化按类型分成几个家族实际工程中你遇到的八成问题都能归入其中问题类型目标函数约束典型场景线性规划LP线性线性不等式 线性等式生产调度、运输问题、资源分配二次规划QP二次凸函数线性最小二乘、模型预测控制、投资组合二次约束二次规划QCQP二次凸函数二次凸约束信号检测、鲁棒波束形成半定规划SDP线性线性矩阵不等式控制系统综合、传感器网络定位锥规划SOCP线性二阶锥约束机器人运动规划、鲁棒优化需要说明的是LP 和 QP 在数值代数里最常出现因为它们的求解算法非常成熟一些教科书会直接教用迭代法甚至直接法。而 SDP 和 SOCP 更接近“现代凸优化”的范畴工程价值极大但入门门槛稍高。4.3 为什么说“局部最优就是全局最优”这么值钱凸优化最迷人的性质就是任何局部最优解都是全局最优解。这个结论从凸性和可行域凸性直接推出。假设 x* 是局部最优那么存在一个小邻域内没有更优点。如果存在某个全局更好的点 y那么 x* 和 y 连线上的点都在可行域内可行域凸而函数在连线上的值被弦的位置限制住函数凸沿着连线靠近 y 的方向走就能找到比 x* 更优的可行点跟局部最优矛盾。这个性质的工程意义怎么强调都不过分非凸问题的迭代算法能不能收敛到全局最优通常取决于初值猜得好不好你需要跑几十次多起点随机初始化还得祈祷运气凸优化问题则完全不需要这种赌博无论从哪个初始点出发任何收敛的迭代序列最终都指向同一个最优值。这个“可复现性”在工程汇报、做对比实验、写论文时太重要了。5. 怎么判断“手上这个问题”是不是凸的5.1 一个函数一个约束地排查纸上谈兵结束来点实用的。一位朋友拿来一个优化问题我通常会按下面这个清单过一遍整个过程大概几分钟明确变量、目标函数、约束。先把问题写清楚含糊的条件往往会掩盖非凸性。逐项检查目标函数的凸性。用组合规则先推必要时用二阶条件验证。逐项检查不等式约束函数的凸性。如果某个约束是“函数 g(x) ≥ 0”先改写成 -g(x) ≤ 0再看 -g 是否凸。检查等式约束是否全部仿射。只要出现 x₁x₂ c 这种乘积项基本宣告非凸。看可行域是否凸。可行域是所有约束下水平集的交集如果里面有离散点集、非凸集合或等式非线性就不是凸优化。5.2 三个让我印象深刻的真实例子第一个例子来自某图像去噪模拟项目。原始模型是带总变分TV正则化的最小二乘看起来目标函数是凸的但有个学生想当然加了“像素值要么是 0 要么是 255 的整数”约束这一下子就把问题变成了非凸的离散优化。后来我们把整数约束松弛为区间约束 [0, 255]问题重新变凸求解过程立刻稳定下来结果虽然不完全满足“要么 0 要么 255”但用阈值量化后视觉效果几乎无损。第二个例子发生在一次教学答疑中。某同学处理一个投资组合问题写了目标函数 w^T Σ w - λ w^T μ这里是协方差矩阵按定义是半正定的第一项应该是凸的但他为了追求某种“平衡”加了一个约束“持仓中最多 5 只股票非零”这又是组合约束瞬间非凸。这是典型的“结构化的稀疏约束”问题严格凸优化框架下没法直接表达后来改用 L1 正则化近似才把问题拉回凸世界。第三个例子来自一个最小二乘几何定位的项目。目标是距离残差平方和最小这本来很凸但有人把未知点坐标写成了“单位四元数”来表达旋转单位四元数约束是 Q^T Q 1这是一个二次等式约束不是仿射等式于是问题变成了非凸 QCQP。这类问题在导航、姿态估计里太常见了现实中处理办法通常是半定松弛SDR把问题放宽成 SDP再对松弛解做投影或随机化恢复。这三个例子说明一个规律很多人遇到“问题不是凸的”第一反应是放弃但工程上的正确反应是问三个问题——这个约束能不能松弛掉这个目标函数能不能用更简单的凸函数近似这个变量能不能换个参数化方式让约束变仿射5.3 有时候不凸也不是世界末日说了这么多凸优化的好处也得说句公道话现实世界很多问题确实是非凸的而且非凸并不代表没法算。深度神经网络的损失函数就是典型的深度非凸问题但实践中动量、自适应学习率、归一化、残差连接这些设计让梯度下降在绝大多数情况下都能训出可用的模型。所以正确的心态是遇到非凸问题不必慌但要知道自己在赌什么——赌初值、赌优化景观的局部结构、赌统计上的“充分好在大多数情况下够用”。学凸优化的意义之一就是给你一双“识别何时不靠运气”的眼睛当问题可以被证明是凸的你可以骄傲地说“这个局部解就是全局解”当问题不是凸的你至少能清醒地知道当前算法的收敛证书并不成立需要额外手段支撑。6. 把一个具体问题包装成凸优化标准形的实操示例6.1 问题描述与原始建模假设我们从某传感器网络定位问题中提取出一个简化版有若干基站坐标 a₁, ..., a_n 已知未知点 x ∈ R²每个基站对未知点有一个带噪声的距离测量值 r_k。目标是从这些测量中估计 x。最自然的思路是求解最小二乘minimize Σ (‖x - a_k‖ - r_k)²表面看这个目标很温和但麻烦在于 ‖x - a_k‖ 这个范数的存在。范数是凸函数没错但目标里是范数与常数 r_k 的差再平方这个复合形式不一定凸实际数值实验中也常常看到多峰现象。这类问题在定位领域被称为“非凸最小二乘定位问题”直接梯度法容易陷入局部解。6.2 松弛变量法把一个不凸问题变成凸问题聪明一点的做法是引入松弛变量 d_k 表示“估计的距离”把问题改写成受限优化minimize Σ (d_k - r_k)² subject to d_k ‖x - a_k‖, k 1, ..., n这样一来目标函数变成关于 d 的二次凸函数但约束 d_k ‖x - a_k‖ 依然是非凸等式的没有解决问题。真正实用的一招是“二阶锥松弛”。把等式约束改成不等式minimize Σ (d_k - r_k)² subject to ‖x - a_k‖ ≤ d_k, k 1, ..., n这个放缩有没有道理注意到 d_k 是目标函数里的惩罚项让 d_k 尽量接近 r_k。如果最优解处 ‖x - a_k‖ d_k那么把 d_k 减小到 ‖x - a_k‖目标函数还会下降所以最优解必然满足 d_k ‖x - a_k‖。这个逻辑加上约束的凸性二阶锥约束是凸集就把原问题成功转化成了一个凸优化问题通常称为二阶锥规划SOCP。如果你设想一下实际效果SOCP 问题的求解从任何初始点出发都能稳定收敛到同一个全局最优解对应的定位精度和传统非凸最小二乘几乎一样还省掉了多起点试探的焦虑。6.3 代码骨架如何在数值库中直接求解上面的 SOCP 问题用什么工具解不少建模库都支持二阶锥约束。以常见建模语法为例骨架如下import numpy as np from scipy.optimize import minimize # 也可以使用支持SOCP的专用建模接口这里只展示目标与约束的数值核心 def build_problem(A, r): n A.shape[0] def objective(vars): x vars[:2] d vars[2:] return np.sum((d - r) ** 2) def constraints(vars): x vars[:2] d vars[2:] return [np.linalg.norm(x - A[k]) - d[k] for k in range(n)] x0 np.mean(A, axis0) d0 np.linalg.norm(x0 - A, axis1) init np.concatenate([x0, d0]) cons [{type: ineq, fun: lambda v, kk: -constraints(v)[k] 1e-8} for k in range(n)] return minimize(objective, init, constraintscons, methodSLSQP)上面的代码只是为了演示数值核心实际性能更好的方案是用专门的锥优化建模语言或求解器声明“二阶锥约束”后交给内点法处理。不过骨架思路是通用的把非凸等式“‖x - a‖ d”替换为凸不等式“‖x - a‖ ≤ d”并让目标函数在最优处自动“拉紧”这个不等式。注意事项松弛法的本质是放宽了约束空间求解出来的解如果某个 d_k 和 ‖x - a_k‖ 相差大于设定阈值说明你的目标函数没有“把约束拉紧”这时候要检查惩罚系数是否合理或者需要加一个小的正则项帮助收紧。6.4 求解凸问题时的算法选择心得把问题变成凸的只是成功了三分之一剩下三分之二是选对算法。根据不同情况我的经验建议是变量规模小几百以内、精度要求高用内点法类求解器收敛快精度通常能达到机器精度级别适合离线计算。变量规模大、精度要求适当放宽用一阶方法比如加速梯度法FISTA 类每次迭代只涉及矩阵乘法和软阈值操作内存友好适合大规模稀疏问题。矩阵结构里有明显的稀疏性或低秩性优先考虑 ADMM 等分解算法可以把原问题拆成几个子问题每个子问题都有闭式解工程实现非常干净。选算法不是越高级越好关键是看问题结构和计算资源。我见过一个场景某同学拿着几十万个变量的凸问题去跑内点法内存直接爆掉换成一阶法之后虽然迭代次数多了一个数量级但每次迭代开销极低实际墙钟时间反而快得多。这种经验不值钱但踩过一次就忘不掉。7. 常见坑与排查速查表这一节把我个人踩过的、以及在答疑中反复见到的坑整理成一张表一行行过也许能帮你省下几个小时症状可能原因排查思路梯度下降不收敛目标值反复震荡问题可能非凸或学习率过大画目标曲线减小步长检查是否掉入局部解多起点测试内点法报警“可行域为空”约束过于严格或松弛不恰当检查每个约束的可满足性暂时去掉部分约束找原因松弛后解不满足原始等式目标函数没有足够“拉紧”松弛变量增加拉紧项检查惩罚权重改用精确罚函数Hessian 出现负特征值目标函数实际上并非凸函数用组合规则重新判断凸性检查变量定义域可行域明明看着像凸的算法却乱跑数值问题约束没归一化、量纲差异过大对变量和约束做归一化或缩放条件数改善后再跑优化结果依赖初值这是一个强信号问题不是凸的不要盲目全局搜索考虑松弛、凸近似或更换参数化方式这表里的每一条我都在真实场景里碰到过尤其是“优化结果依赖初值”这一条。按我的经验只要出现这个信号第一件事不是调参而是回去检查问题的凸性——这才是治本思路。另外一个非常容易被忽略的坑是“凸函数定义域”的细节。有些函数在某个集合上是凸的但定义域外可能是凹的。典型如 f(x) 1/x在 x 0 区间是凸函数但在整个 R{0} 上既不是凸也不是凹。所以判断凸性一定要说明定义域不然结论是错的。这跟做实验先写清楚实验条件一个道理。8. 从凸函数到凸优化还需要哪些“周边知识”托底8.1 对偶理论凸优化的另一半风景学会了判断凸性、写出标准形、求解这只是凸优化的前半程。后半程是对偶理论。对每个凸优化问题你可以构造一个拉格朗日函数并定义对偶函数g(λ, ν) inf_x [ f₀(x) Σ λᵢ fᵢ(x) Σ νⱼ hⱼ(x) ]其中 λᵢ ≥ 0。对偶函数有一个迷人的性质无论原问题是不是凸的对偶函数永远是凹函数对 λ、ν 而言且对偶函数的最大值不会超过原问题的最小值——这就是弱对偶。当原问题满足某些约束规范条件比如 Slater 条件时强对偶成立即对偶最优值等于原问题最优值。强对偶的价值在于很多工程问题中对偶问题比原问题更容易求解或者能提供原问题最优值的下界用来判断当前解离最优有多远。这在分布式优化、资源分配、经济学里的拍卖机制中都是核心工具。8.2 无约束凸优化的经典算法快览凸优化问题的求解算法主线大概四条梯度下降实现最简单依赖 Lipschitz 常数的步长选择收敛速度对条件数敏感。牛顿法利用二阶信息收敛速度极快二次收敛但每次迭代需要解线性方程组适合中小规模问题。拟牛顿法BFGS 等用梯度差构造 Hessian 近似在无约束光滑凸问题上表现很好工程库中常见。加速梯度法Nesterov 加速在梯度下降基础上加“动量”项理论收敛速度从 O(1/k) 提升到 O(1/k²)是大规模问题的默认选择之一。这些算法在凸问题上都有扎实的收敛性保证核心原因是凸性保证了目标函数在迭代过程中不会出现“假下降点”。选哪个看问题规模、可微性、精度要求和 Hessian 是否容易求。8.3 约束优化中的转机KKT 条件与内点法对有约束的凸优化问题KKT 条件是最优性的充要条件在约束规范成立时。库恩-塔克条件的核心是一条“互补松弛”关系λᵢ fᵢ(x*) 0意思是某约束在最优解处要么是松的fᵢ(x*) 0此时乘子 λᵢ 0要么是紧的fᵢ(x*) 0乘子可以为正。这个条件不仅是理论判据也是很多算法的终止判据。内点法就是巧妙结合了 KKT 条件、障碍函数和牛顿法的范例它把不等式约束近似成对数障碍项沿着“中心路径”迭代最终逼近 KKT 点。理论复杂度是多项式级的实践上对于几千到几万变量的中等规模凸优化问题非常可靠。这也是为什么“只要你能把问题变成凸的剩下的就交给求解器”这句话有底气的原因。9. 说点实操里的体感几个值得长期留意的习惯写到这里这篇笔记的核心内容已经全部铺开。最后想分享几个我在实操中慢慢养成的习惯都是踩过坑之后才明白的第一个习惯是“建模前先画图”。哪怕问题有一百个变量我先挑两个关键方向做切片可视化看看目标函数长什么样、可行域是什么形状。这一步经常能发现肉眼可见的非凸区域省去后面一大堆白算功夫。第二个习惯是“随时检查约束规范”。有时候问题确实是凸的但约束规范不满足导致强对偶不成立KKT 条件也未必是充要条件。像“可行域内部为空”这种极端情况就属于约束规范被破坏求解器给出的结果会让人摸不着头脑。多问一句“可行域有没有内点”是成本极低但收益很高的检查。第三个习惯是“把复杂的非凸问题分解成多个凸子问题”。全局非凸不代表处处非凸。交替方向法坐标下降、ADMM 的思想在不少场景下能把一个非凸大问题切成几个凸子问题每个子问题都有可靠求解器。这样做即便没有全局收敛保证工程上通常也能得到一个不错的解而且比盲目跑一个非凸优化器稳定得多。第四个习惯是“永远记录初值和解的稳定性”。我每跑一个优化问题都会故意用几个差异很大的初值试一遍观察最优解是否一致。如果结果一致心里就有底如果不一致立刻标记为“疑似非凸”然后回头分析。这个习惯帮我拦下了无数次“假报告”级别的错误结论。凸函数和凸优化问题的内容本身就像一座桥——桥的一端连着数学分析里的光滑函数性质另一端连着数值计算里的算法实现。这篇笔记帮你把桥面铺到“能判断、能建模、能求解”的程度再往深处走就是对偶、内点法、大规模分布式优化这些更专门的课题了。后面有机会再一篇一篇展开。