简介这份资源聚焦SCASequential Convex Approximation凸优化算法的实现面向无线通信、信号处理、能源系统优化等方向的研究生与工程人员帮助解决非凸问题难以直接求解的痛点。压缩包共2个文件均为MATLAB脚本.m整体约3KB其中一份为通用SCA算法框架另一份为特定功率增强问题的示例实现便于对照理解近似、求解与迭代更新的完整流程。资源涉及凸函数与凸集、凸优化问题形式、Taylor展开等近似技术以及收敛性分析等关键知识点读者可据此掌握将非凸目标逐次凸化并调用梯度下降、牛顿法或内点法求解的思路。已有2699人学习下载适合作为入门SCA与定制算法以适配具体场景的参考代码。1. SCA 与凸优化从“非凸卡死”到“逐步逼近”的那条路做通信资源分配、阵列信号处理或者机器学习超参搜索的人大概率都遇到过同一个场景目标函数写出来挺漂亮一求导发现是非凸的梯度下降要么原地打转要么直接发散。这时候老工程师嘴里会蹦出一个词——SCASuccessive Convex Approximation逐次凸逼近。它干的事情说白了就一句话把一个难啃的非凸问题在每一步用一个凸的“替身”去近似解完替身再更新替身反复迭代直到收敛。凸优化在这里扮演的是“替身工厂”的角色因为凸问题有全局最优、有成熟求解器、有收敛保证拿它当每一步的子问题最稳。这套方法适合谁适合手里已经有优化模型、但被非凸约束卡住的算法工程师和研究生不适合连目标函数都没写清楚的人。下面我按自己踩过的路把 SCA 从建模到落地讲透。2. SCA 的数学骨架为什么凸替身能收敛到原问题的解2.1 非凸问题到底难在哪凸优化又为什么是“安全区”先把问题摆出来。一个典型的非凸优化长这样minimize f(x) subject to g_i(x) 0, i 1,...,m h_j(x) 0, j 1,...,p其中 f 或某个 g_i 是非凸的。非凸的麻烦在于可行域可能是多个不相连的“坑”梯度类方法只能保证找到局部最优而且对初值极其敏感。凸优化之所以是安全区是因为凸问题的可行域是凸集、目标函数是凸函数任何局部最优就是全局最优KKT 条件充要内点法、ADMM 这些求解器都能稳定给出解。SCA 的核心思路不是去直接征服非凸而是“化整为零”在第 k 次迭代围绕当前点 x^k 构造一个凸的代理函数 f̃(x; x^k)满足两个关键性质——一致性f̃(x^k; x^k) f(x^k)以及上界性f̃(x; x^k) f(x)对最小化问题。满足这两条解子问题得到的点就不会让原目标变差形成单调下降序列。提示上界性是最容易被忽略的一条。很多人只保证了一致性就上手结果迭代震荡不收敛回头查半天以为是步长问题其实是代理函数没控住上界。2.2 三种主流代理构造一阶泰勒、二次上界、MM 框架代理函数怎么造决定了 SCA 的收敛速度和实现难度。我常用的有三种第一种一阶泰勒展开。对可微的 f直接在当前点做线性近似f(x) ≈ f(x^k) ∇f(x^k)^T (x - x^k)简单但线性代理没有上界性保证凸函数才有所以只适用于 f 本身凸、非凸性来自约束的情况。如果 f 非凸线性近似可能低于真实值单调性就丢了。第二种二次上界。对梯度 Lipschitz 连续的非凸 f可以构造f(x) f(x^k) ∇f(x^k)^T (x - x^k) (L/2) ||x - x^k||^2右边这个二次函数是凸的L 0而且天然满足上界性和一致性。L 是 Lipschitz 常数取大了收敛慢取小了上界不成立这是实操中最需要调的参数。第三种MM 框架Majorization-Minimization。这是更一般化的说法找一个 majorizer 函数只要它满足上界和一致就能用。很多论文里的 SCA 其实就是 MM 的特例。MM 的好处是代理函数可以针对具体问题“定制”比如利用 Jensen 不等式、一阶条件等构造出比二次上界更紧的代理收敛更快。选哪种我的经验是目标函数可微且 L 好估计用二次上界最省事问题结构特殊比如有对数、有分式用 MM 定制代理往往能快好几倍如果非凸性只在约束里一阶泰勒配合约束的凸化就够了。2.3 收敛性判据与停止条件怎么设SCA 的收敛性理论保证是在代理函数满足上界、一致、梯度一致等条件下迭代序列的聚点是原问题的稳定点KKT 点。注意是稳定点不是全局最优——非凸问题本来就没法保证全局最优谁跟你说能保证那是忽悠。实操中停止条件我一般设三个满足其一就停判据表达式典型阈值适用场景目标函数相对变化|f(x^{k1}) - f(x^k)| / max(1, |f(x^k)|)1e-4 ~ 1e-6通用最常用迭代点变化||x^{k1} - x^k|| / max(1, ||x^k||)1e-4变量尺度差异大时最大迭代次数k K_max100 ~ 500兜底防止死循环注意只设目标函数变化是不够的。我遇到过一次目标函数几乎不变但变量还在缓慢漂移的情况最后发现是代理函数在某个区域太平梯度接近零。加上变量变化判据就能抓住这种“假收敛”。3. 用 Python 把 SCA 跑起来一个功率分配的最小可复现例子3.1 问题建模非凸和速率最大化拿通信里最经典的和速率最大化举例。两个用户功率分配变量 p [p1, p2]总功率约束 p1 p2 P_max信道增益 h [h1, h2]噪声方差 σ²。目标maximize log2(1 h1*p1/σ²) log2(1 h2*p2/σ²) subject to p1 p2 P_max p1, p2 0这个目标函数其实是凸的log 是凹函数但如果我们加上用户间干扰变成maximize log2(1 h1*p1/(σ² h2*p2)) log2(1 h2*p2/(σ² h1*p1))这就非凸了因为分母里有另一个变量。这就是 SCA 的用武之地。3.2 构造代理函数并写迭代循环对 log2(1 h1p1/(σ² h2p2)) 这一项用 MM 框架里的一个常用技巧利用 log(1 x/y) 在 y 固定时的凹下界或者直接对干扰项做线性上界。我这里用更直接的方式——对第二项中的干扰 h1*p1 在 p1^k 处做一阶泰勒把分母线性化然后整体用二次上界保证凸性。import numpy as np def rate(p, h, sigma2): 计算和速率p 是功率向量h 是信道增益 sinr1 h[0] * p[0] / (sigma2 h[1] * p[1]) sinr2 h[1] * p[1] / (sigma2 h[0] * p[0]) return np.log2(1 sinr1) np.log2(1 sinr2) def sca_power_allocation(h, sigma2, P_max, max_iter200, tol1e-6): SCA 求解两用户功率分配 h: 信道增益 [h1, h2] sigma2: 噪声方差 P_max: 总功率上限 p np.array([P_max / 2, P_max / 2]) # 初值均分 L 10.0 # 二次上界的 Lipschitz 常数需要根据问题尺度调 obj_history [] for k in range(max_iter): # 当前点的干扰项 I1 sigma2 h[1] * p[1] I2 sigma2 h[0] * p[0] # 构造代理对 log2(1 h_i*p_i/I_i) 在 I_i 固定时是凹的 # 用一阶泰勒展开干扰项加上二次正则保证凸性 # 代理目标最小化负速率 def surrogate(p_new): # 线性化干扰后的近似速率 r1 np.log2(1 h[0] * p_new[0] / I1) r2 np.log2(1 h[1] * p_new[1] / I2) # 二次惩罚项保证代理是凸的且是原问题的上界 reg (L / 2) * np.sum((p_new - p) ** 2) return -(r1 r2) reg # 用简单的投影梯度解子问题实际可用 cvxpy p_new p.copy() step 0.01 for _ in range(50): grad np.zeros(2) # 数值梯度 eps 1e-6 for i in range(2): e np.zeros(2); e[i] eps grad[i] (surrogate(p_new e) - surrogate(p_new - e)) / (2 * eps) p_new p_new - step * grad # 投影到可行域 p_new np.maximum(p_new, 0) if np.sum(p_new) P_max: p_new p_new * P_max / np.sum(p_new) obj_new rate(p_new, h, sigma2) obj_old rate(p, h, sigma2) obj_history.append(obj_new) # 停止条件 if abs(obj_new - obj_old) / max(1, abs(obj_old)) tol: print(f收敛于第 {k} 次迭代) break p p_new return p, obj_history # 跑一下 h np.array([1.0, 0.8]) sigma2 0.1 P_max 2.0 p_opt, history sca_power_allocation(h, sigma2, P_max) print(f最优功率分配: p1{p_opt[0]:.4f}, p2{p_opt[1]:.4f}) print(f和速率: {rate(p_opt, h, sigma2):.4f} bps/Hz)这段代码的逻辑链条每次迭代先用当前功率算出干扰项 I1、I2把干扰当常数这样 log 项就变成凹函数再加上二次正则项 (L/2)||p_new - p||² 保证代理函数是凸的且是原目标的上界。子问题用投影梯度解投影保证功率非负且总和不超过 P_max。收敛判据用目标函数相对变化。参数说明L 是关键取 10 是经验值实际应该根据目标函数的二阶导数上界估计。L 太大收敛慢但稳太小可能破坏上界性导致震荡。step 是子问题的梯度步长0.01 偏保守可以用线搜索加速。max_iter 设 200 是兜底通常几十次就收敛了。3.3 用 cvxpy 替换手写子问题求解器上面的投影梯度是手写的实际项目里我强烈建议用 cvxpy子问题求解更稳、代码更短import cvxpy as cp def sca_with_cvxpy(h, sigma2, P_max, max_iter100, tol1e-6): p np.array([P_max / 2, P_max / 2]) L 10.0 for k in range(max_iter): I1 sigma2 h[1] * p[1] I2 sigma2 h[0] * p[0] p_var cp.Variable(2, nonnegTrue) # 代理目标凹的 log 项 凸的二次正则 r1 cp.log(1 h[0] * p_var[0] / I1) / np.log(2) r2 cp.log(1 h[1] * p_var[1] / I2) / np.log(2) reg (L / 2) * cp.sum_squares(p_var - p) obj cp.Maximize(r1 r2 - reg) constraints [cp.sum(p_var) P_max] prob cp.Problem(obj, constraints) prob.solve(solvercp.ECOS, verboseFalse) p_new p_var.value if abs(rate(p_new, h, sigma2) - rate(p, h, sigma2)) tol: break p p_new return pcvxpy 版本的好处是子问题求解有内点法保证不用手调步长。ECOS 适合小规模二阶锥问题大规模可以用 SCS 或 MOSEK。注意 cp.log 里如果 I1 是变量就会破坏凸性所以必须把 I1 当常数——这正是 SCA 的精髓每步固定一部分让剩下的变凸。4. SCA 落地避坑五个让我熬夜排查的真实问题4.1 代理函数不满足上界迭代震荡不收敛现象目标函数值上下跳动迭代 100 次还在震荡没有下降趋势。原因代理函数只满足了一致性没有满足上界性。常见于用一阶泰勒近似非凸函数时线性近似可能低于真实值导致子问题的最优解反而让原目标变差。解决检查代理构造。对非凸项要么加二次正则 (L/2)||x - x^k||²要么用 MM 框架找严格 majorizer。验证方法在代码里加一行断言检查 f̃(x; x^k) f(x) 在当前点附近是否成立。4.2 Lipschitz 常数 L 取太小上界失效现象前几次迭代目标下降突然某次跳到一个更差的点然后卡住。原因二次上界里的 L 估计偏小导致代理函数在某些区域低于真实目标上界性被破坏。解决L 的估计可以用回溯法——先取一个较小的 L如果解出的点让原目标变差就增大 L 重解直到原目标不差为止。这叫自适应 SCA多花一点计算但稳得多。4.3 初值选得离谱收敛到差的稳定点现象算法收敛了但解明显不是想要的和速率比预期低很多。原因非凸问题有多个稳定点SCA 只能保证收敛到其中一个初值决定了去哪个。解决多初值重启。跑 10 个随机初值取目标最好的解。或者用启发式比如均分、注水法的解做初值。别指望一个初值打天下。4.4 子问题求解精度不够外层迭代被拖死现象外层迭代次数暴增每次子问题求解时间不长但总时间很长。原因子问题用迭代求解器时精度设太低解出来的点不够准导致外层需要更多次迭代来补偿。解决子问题求解精度要随外层迭代动态调整。早期可以松一点1e-4后期收紧1e-8。cvxpy 里可以用prob.solve(solver..., abstol..., reltol...)控制。4.5 变量尺度差异大停止条件误判现象目标函数变化很小但变量还在大幅移动或者反过来。原因变量之间量级差几个数量级比如功率是 1e-3 量级带宽是 1e6 量级用绝对变化做判据会误判。解决停止条件用相对变化并且对变量做归一化。或者分别监控每个变量的变化只要有一个还在动就不停。5. 让 SCA 更快更稳自适应 L 与热启动的两个技巧5.1 自适应 Lipschitz 常数不用再猜 L固定 L 是我早期最头疼的事。后来改成回溯线搜索代码大概长这样def adaptive_sca_step(p, h, sigma2, P_max, L_init1.0, eta1.5, max_backtrack20): 自适应 L 的 SCA 单步 L_init: 初始 L eta: 每次增大倍数 L L_init f_old rate(p, h, sigma2) for _ in range(max_backtrack): # 用当前 L 解子问题这里简化为投影梯度实际用 cvxpy p_new solve_subproblem(p, h, sigma2, P_max, L) f_new rate(p_new, h, sigma2) if f_new f_old - 1e-8: # 原目标没有变差 return p_new, L L * eta # 增大 L 重试 return p, L # 回溯失败保持原点逻辑是先用小 L 试如果解出的点让原目标变差说明上界不成立增大 L 重解。这样 L 会自动适应问题的局部曲率不用手工调。代价是可能多解几次子问题但比震荡不收敛强太多。5.2 热启动把上一次的解当这一次的初值在滚动优化场景比如实时资源分配每个时隙都要解一次相邻时隙的最优解通常很接近。把上一个时隙的解作为当前时隙 SCA 的初值迭代次数能从几十次降到几次。这个技巧在论文里叫 warm-start实操中效果立竿见影。具体做法维护一个p_last变量每次 SCA 开始前用p_last初始化收敛后更新p_last。注意如果问题参数突变比如信道突然深衰落热启动可能反而拖慢收敛这时候可以加一个检测如果前 3 次迭代目标没有改善就换成均分初值重启。5.3 验证 SCA 解的质量上界与下界的夹逼怎么知道 SCA 解靠不靠谱我的习惯是同时算一个上界。对最大化问题可以放松约束或忽略干扰得到一个上界对最小化问题可以固定部分变量得到一个下界。如果 SCA 解和上界差距在 5% 以内基本可以接受差距太大要么是初值不好要么是代理太松。另一个验证手段是蒙特卡洛随机跑 100 个初值看解的分布。如果大部分初值都收敛到同一个解说明这个稳定点吸引域大可信度高如果解散得到处都是说明问题非凸性太强需要换方法或者接受次优。我自己的习惯是每次写完 SCA 代码先跑三个初值——均分、注水解、随机——对比结果。如果三个解一致收工不一致加多初值重启。这个习惯帮我省了无数次回头查 bug 的时间。希望帮到你。本文还有配套的精品资源点击获取