★ FEATURED ARTICLE 简介这份资源是凸优化理论学习的心得配套代码包面向正在入门或希望系统梳理凸优化知识体系的机器学习、数据分析方向学习者。内容围绕学习路径展开涵盖入门书籍选择、Boyd《凸优化》结构解读、线性代数与微积分基础铺垫以及多所高校公开教程与资源的整理帮助读者建立从数学基础到凸优化核心概念的完整认知框架。压缩包共3个文件包含1个inscode工程配置、1个html页面和1个gitignore文件整体约5KB体量轻巧便于快速查看与本地运行。目前已有71人学习下载。读者可借助其中的页面结构与工程配置对照心得内容梳理学习脉络理解凸优化在机器学习、信号处理等领域的应用价值并参考作者推荐的课程与书籍安排自学节奏适合作为凸优化入门阶段的辅助参考材料。1. 凸优化学习心得从「看得懂公式」到「跑得动代码」的那道坎很多人学凸优化卡住的地方不是数学而是从公式到代码的那一步。你能看懂拉格朗日对偶、能背出 KKT 条件但真让你用代码把一个 LASSO 问题解出来或者自己写一个投影梯度法去跑图像去噪手就僵住了。这个标题下的「项目代码」本质上就是解决这道坎的把凸优化的标准问题形式、经典算法和可运行实现串成一条线让你不只是「知道」而是能跑、能改、能验证。它适合两类人一类是刚学完凸优化理论、想找一套能动手的代码把概念落地的新手另一类是做机器学习、信号处理、控制方向需要自己写求解器或调参的从业者。我自己的体会是凸优化真正的门槛不在推导而在「选哪个算法、参数怎么设、收敛判据怎么写」这些工程细节上而这些恰恰是大多数教材不讲、项目代码里才有的东西。2. 凸优化问题的标准形式与代码映射先搞清楚你在解什么2.1 从数学形式到数据结构目标函数、约束、变量怎么落到代码里凸优化的标准形式通常写成最小化 $f_0(x)$满足 $f_i(x) \leq 0$ 和 $Ax b$。落到代码里第一件事不是写算法而是决定「怎么表示这个问题」。常见做法是定义一个 Problem 类把目标函数、不等式约束、等式约束、变量维度都封装进去。我一般会用一个字典或数据类来存这些字段而不是散落在各个函数里。原因很简单后面换算法时你只需要换 solver问题定义不用动。import numpy as np class ConvexProblem: def __init__(self, f0, ineq_constraintsNone, eq_constraintsNone, x0None): f0: 目标函数输入 x返回 (值, 梯度) ineq_constraints: 不等式约束列表每个元素返回 (值, 梯度) eq_constraints: 等式约束列表每个元素返回 (值, 梯度) x0: 初始点 self.f0 f0 self.ineq ineq_constraints or [] self.eq eq_constraints or [] self.x0 x0 def objective(self, x): return self.f0(x) def is_feasible(self, x, tol1e-6): for g in self.ineq: if g(x)[0] tol: return False for h in self.eq: if abs(h(x)[0]) tol: return False return True这段代码的关键在于每个函数都返回「值 梯度」而不是只返回值。为什么因为凸优化算法几乎都要用梯度信息如果你只返回值后面要么用数值差分慢且不准要么回头重写。参数tol是可行性判断的容差一般设 1e-6 到 1e-8取决于你的问题尺度。初始点x0不是随便给的后面会讲它对收敛的影响。2.2 目标函数和约束的梯度怎么写数值差分 vs 解析梯度新手最容易翻车的地方是梯度。很多人图省事用数值差分结果算法收敛慢、精度差还以为是算法不行。我的血泪经验是只要目标函数不是特别复杂一定写解析梯度。比如 LASSO 的目标 $f(x) \frac{1}{2}|Ax-b|_2^2 \lambda |x|_1$它的次梯度是 $A^T(Ax-b) \lambda \cdot \text{sign}(x)$。注意这里用的是次梯度因为 L1 范数在 0 点不可导。def lasso_objective(A, b, lam): def f(x): r A x - b val 0.5 * np.dot(r, r) lam * np.sum(np.abs(x)) grad A.T r lam * np.sign(x) return val, grad return f逻辑说明r是残差val是目标值grad是次梯度。参数lam控制稀疏性越大越稀疏。注意np.sign(0)返回 0这在次梯度里是合法的但如果你用梯度下降0 点会停住所以 LASSO 一般不用普通梯度下降而用近端梯度法ISTA/FISTA。这就是「选算法」和「写梯度」之间的耦合关系很多人一开始没意识到。2.3 收敛判据怎么设别只看迭代次数收敛判据是另一个容易被忽略的点。我见过不少代码只设最大迭代次数跑完就完事结果要么没收敛要么早停。常见做法是同时看三个量目标函数变化量、梯度范数、可行性违反量。对于无约束问题梯度范数小于1e-6通常够了对于有约束问题还要看约束违反量。def check_convergence(prob, x, x_prev, tol1e-6): f_val, grad prob.objective(x) f_prev, _ prob.objective(x_prev) grad_norm np.linalg.norm(grad) f_diff abs(f_val - f_prev) feasible prob.is_feasible(x, tol1e-4) return grad_norm tol and f_diff tol and feasible参数tol设 1e-6 是通用起点但如果你的变量尺度很大比如 1e4这个值可能太严导致迭代次数爆炸。这时候可以改成相对判据比如f_diff / max(1, abs(f_prev)) tol。可行性容差一般比梯度容差松一点1e-4 是常见选择。3. 三类经典算法的代码实现梯度下降、近端梯度、内点法3.1 投影梯度法处理简单约束的首选投影梯度法Projected Gradient Descent适合约束集合简单、投影容易算的问题比如箱约束、球约束。它的迭代格式是 $x_{k1} \Pi_C(x_k - \alpha \nabla f(x_k))$其中 $\Pi_C$ 是投影算子。def projected_gradient(prob, proj, alpha0.01, max_iter1000, tol1e-6): x prob.x0.copy() for k in range(max_iter): f_val, grad prob.objective(x) x_new proj(x - alpha * grad) if np.linalg.norm(x_new - x) tol: break x x_new return x, k逻辑说明proj是投影函数比如箱约束的投影就是np.clip(x, lower, upper)。参数alpha是步长固定步长下要求alpha 2/L其中 L 是梯度 Lipschitz 常数。如果你不知道 L可以用线搜索但线搜索会增加每次迭代的计算量。我一般先估计 L然后设alpha 1/L这样最稳。3.2 近端梯度法ISTA/FISTALASSO 和稀疏问题的标配近端梯度法解决的是 $f(x) g(x) h(x)$ 形式的问题其中 g 可导h 不可导但近端算子好算。LASSO 就是典型g 是最小二乘h 是 L1 范数。ISTA 的迭代是 $x_{k1} \text{prox}_{\alpha h}(x_k - \alpha \nabla g(x_k))$FISTA 加了动量项收敛速度从 O(1/k) 提升到 O(1/k^2)。def soft_threshold(x, thresh): return np.sign(x) * np.maximum(np.abs(x) - thresh, 0) def fista(A, b, lam, alphaNone, max_iter1000, tol1e-6): n A.shape[1] x np.zeros(n) y x.copy() t 1.0 if alpha is None: L np.linalg.norm(A, 2) ** 2 alpha 1.0 / L for k in range(max_iter): grad A.T (A y - b) x_new soft_threshold(y - alpha * grad, lam * alpha) t_new (1 np.sqrt(1 4 * t * t)) / 2 y x_new ((t - 1) / t_new) * (x_new - x) if np.linalg.norm(x_new - x) tol: break x x_new t t_new return x, k逻辑说明soft_threshold是 L1 的近端算子也叫软阈值。alpha默认用1/LL 是A^T A的最大特征值用np.linalg.norm(A, 2)**2估计。动量项(t-1)/t_new是 FISTA 的核心少了它退化成 ISTA收敛慢很多。参数lam控制稀疏度实际调参时一般从0.01 * max(abs(A.T b))开始试。3.3 内点法小规模高精度问题的兜底方案内点法适合变量维度不高几百以内、但要求高精度解的问题。它的核心是把不等式约束通过障碍函数变成无约束问题然后用牛顿法解一系列子问题。自己写完整内点法比较复杂常见做法是用现成的求解器比如 CVXPY 或 scipy.optimize.minimize 的 SLSQP。但如果你想理解原理可以写一个简化的对数障碍法。def barrier_method(prob, t01.0, mu10, tol1e-6): x prob.x0.copy() t t0 while True: def barrier_obj(x): val, grad prob.objective(x) for g in prob.ineq: gv, gg g(x) val - np.log(-gv) / t grad - gg / (t * gv) return val, grad # 用牛顿法解子问题这里简化为梯度下降 for _ in range(100): _, grad barrier_obj(x) x - 0.01 * grad if len(prob.ineq) / t tol: break t * mu return x逻辑说明t是障碍参数mu是递增因子一般取 10 到 20。barrier_obj里减去了对数障碍项梯度也相应调整。注意-gv必须为正否则对数无定义所以初始点必须在可行域内部。这个方法收敛慢但胜在逻辑清晰适合理解内点法的思想。4. 避坑与排查凸优化代码里最容易翻车的 5 个地方4.1 现象算法不收敛目标函数震荡原因步长太大超过了 2/L 的稳定边界。解决先估计 L设alpha 1/L或者用回溯线搜索。如果还震荡检查梯度是不是写错了尤其是矩阵转置和符号。4.2 现象解出来全是 0 或者全是 NaN原因正则化系数lam太大或者初始点不可行导致对数障碍爆炸。解决把lam调小一个数量级再试对于内点法确保x0严格可行可以用x0 x0 0.01 * np.random.randn(n)扰动一下。4.3 现象收敛很慢迭代几千次还在动原因用了 ISTA 但没加动量或者梯度用了数值差分。解决换成 FISTA或者把数值差分改成解析梯度。如果问题有约束检查投影是不是写对了投影后的点必须满足约束。4.4 现象结果和 CVXPY 对不上原因收敛判据太松或者问题定义不一致比如约束方向写反了。解决把tol调到 1e-8对比目标函数值和约束违反量。如果还不对逐项检查约束的符号和在代码里很容易搞混。4.5 现象内存爆了原因把A存成稠密矩阵而A其实是稀疏的。解决用scipy.sparse存A矩阵乘法用A x而不是np.dot(A, x)。对于大规模问题这一步能省几十倍内存。5. 进阶技巧用对偶间隙做验证用 warm start 加速5.1 对偶间隙判断解是否最优的硬指标对偶间隙是原问题最优值和偶问题最优值的差理论上等于 0。实际计算中如果对偶间隙小于 1e-6基本可以认为解是最优的。对于 LASSO对偶问题有解析形式可以快速算出来。def dual_gap_lasso(A, b, lam, x): r A x - b primal 0.5 * np.dot(r, r) lam * np.sum(np.abs(x)) dual -0.5 * np.dot(r, r) - np.dot(b, r) # 简化形式具体推导略 return primal - dual参数说明primal是原问题值dual是对偶问题值。如果间隙大于 1e-4说明还没收敛继续迭代或者调小tol。5.2 Warm start把上一次的解当初始点如果你要解一系列相似的问题比如调lam的路径warm start 能省一半以上的迭代次数。做法很简单把上一个lam的解作为下一个lam的初始点。def lasso_path(A, b, lam_list): x np.zeros(A.shape[1]) solutions [] for lam in sorted(lam_list, reverseTrue): x, _ fista(A, b, lam, x0x) # 传入 x0 solutions.append(x.copy()) return solutions逻辑说明lam从大到小排先解大lam解稀疏容易收敛再逐步减小。x0x就是 warm start。这个技巧在 scikit-learn 的Lasso里是默认开启的自己写代码时别忘了。5.3 验证方法用 KKT 条件做最终检查KKT 条件是凸优化最优解的充要条件。对于 LASSOKKT 条件可以写成$A^T(Ax-b) \lambda s$其中 $s$ 是次梯度满足 $s_i \text{sign}(x_i)$ 当 $x_i \neq 0$$|s_i| \leq 1$ 当 $x_i 0$。你可以写一个检查函数看残差是否满足这个条件。def check_kkt_lasso(A, b, lam, x, tol1e-4): grad A.T (A x - b) for i in range(len(x)): if abs(x[i]) tol: if abs(grad[i] - lam * np.sign(x[i])) tol: return False else: if abs(grad[i]) lam tol: return False return True这个检查比看目标函数变化量更可靠因为它直接验证了最优性条件。我一般会在算法跑完后跑一遍这个函数如果返回 False说明要么没收敛要么梯度写错了。5.4 一个具体技巧用 Nesterov 加速时注意重启FISTA 的动量项在目标函数非强凸时可能震荡这时候可以用自适应重启如果 $f(x_{k1}) f(x_k)$就把动量项清零重新开始。这个技巧在实践里很管用能避免很多玄学震荡。def fista_with_restart(A, b, lam, alphaNone, max_iter1000, tol1e-6): n A.shape[1] x np.zeros(n) y x.copy() t 1.0 if alpha is None: L np.linalg.norm(A, 2) ** 2 alpha 1.0 / L f_prev np.inf for k in range(max_iter): grad A.T (A y - b) x_new soft_threshold(y - alpha * grad, lam * alpha) f_val 0.5 * np.linalg.norm(A x_new - b) ** 2 lam * np.sum(np.abs(x_new)) if f_val f_prev: t 1.0 y x_new.copy() else: t_new (1 np.sqrt(1 4 * t * t)) / 2 y x_new ((t - 1) / t_new) * (x_new - x) t t_new if np.linalg.norm(x_new - x) tol: break x x_new f_prev f_val return x, k逻辑说明f_val f_prev时重置动量t1.0yx_new。这个改动很小但在很多问题上能显著减少迭代次数。我自己的习惯是只要用 FISTA就默认加上重启除非问题强凸且条件数很好。最后说一个我踩过的坑不要迷信「算法越复杂越好」。很多实际问题用投影梯度法加 warm start 就能解决上内点法反而因为每次迭代太慢而总时间更长。选算法的标准是「问题结构 精度要求 时间预算」不是「哪个听起来高级」。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
