简介这份资源聚焦SCASequential Convex Approximation凸优化算法的实现面向具备一定数学优化基础、希望将非凸问题转化为连续凸近似求解的学习者与工程人员可用于无线通信、信号处理、能源系统优化等场景的算法验证。压缩包共2个文件均为MATLAB脚本.m整体约3KB体量轻便便于直接阅读与二次修改。其中一份脚本给出特定功率问题的示例建模另一份则承载通用SCA算法框架二者配合可帮助读者理解凸函数与凸集、凸优化问题形式、近似构造、迭代更新及收敛性分析等关键环节。目前已有2699人学习下载说明其在同类算法资料中具备一定参考价值。读者可借此掌握Taylor展开、松弛等近似技术并对照源码梳理从近似、求解到更新的完整流程进而定制适配自身问题的SCA实现。1. SCA 与凸优化从一个「非凸卡死」的现场说起如果你调过通信里的波束成形、搞过 IRS 相控阵、或者碰过机器学习里的稀疏正则大概率遇到过这种场面目标函数写出来挺漂亮一求导发现非凸CVX 直接报Disciplined convex programming error梯度下降跑一夜 loss 在几个局部极小值之间反复横跳。这时候老工程师通常会甩给你三个字母——SCASuccessive Convex Approximation逐次凸近似。它干的事很朴素既然原问题非凸那我不直接解你我在当前点附近构造一个凸的「替身」解替身拿解当新起点再构造再解直到收敛。凸优化在这里不是目的是工具SCA 是把非凸问题「翻译」成一系列凸问题的翻译官。这套方法适合谁适合手里已经有凸优化求解器CVX、CVXPY、MOSEK、SCS 都行、但被非凸约束或非凸目标卡住的从业者。下面我按自己踩过的顺序把 SCA 从原理到能跑通的代码、参数、翻车点讲一遍。2. SCA 凭什么能收敛凸近似、代理函数与三个前提2.1 非凸问题为什么不能直接丢给求解器先把话说死凸优化求解器的「凸」不是建议是硬约束。CVX 这类工具用的是 disciplined convex programming它靠一套规则判断你写的表达式是否满足凸性组合一旦出现变量相乘、变量做分母、log 里套非凹函数直接拒绝。这不是求解器弱而是凸问题的全局最优性保证依赖于可行域凸、目标凸这两个条件破坏任何一个KKT 点就不再等价于全局最优。现实里的问题偏偏爱非凸。举几个我常碰到的波束成形里功率约束下的和速率最大化速率是 log(1SINR)SINR 里分子分母都含优化变量整体非凸稀疏感知里的 L0 范数组合性质天然非凸IRS 场景里反射相移和信道耦合双线性结构。这些问题的共同点是——局部看近似凸全局看不是。SCA 的思路就是承认「全局我搞不定」转而做「局部可靠」。它在第 k 次迭代点 x_k 处找一个凸函数 g(x; x_k)满足两个条件一是 g(x_k; x_k) f(x_k)在当前点值和原函数相等二是 g(x; x_k) ≥ f(x)或 ≤取决于最大化还是最小化即代理函数是原函数的全局上界或下界。满足这两条解代理函数得到的解一定不会让原目标变差这就是单调性来源。2.2 代理函数怎么造一阶泰勒、二次上界与 MM 框架造代理函数是 SCA 的核心手艺常见三条路。第一条是一阶泰勒展开。对凸函数泰勒展开是全局下界对凹函数泰勒展开是全局上界。所以最大化一个凹函数时直接在当前点做一阶泰勒得到的就是合法的凹下界代理。这是最省事的一类很多速率最大化问题里 log(1SINR) 对某些变量是凹的直接泰勒就能用。第二条是二次上界典型场景是处理 log 和分式。比如 log(1x) 这种凹函数除了泰勒还可以用二次函数在展开点处构造上界收敛性质更好但计算稍重。分式结构常用二次变换quadratic transform把分子分母解耦成可交替优化的形式。第三条是 MM 框架Majorization-Minimization。它不要求代理函数是泰勒只要求是原函数的 majorizer上界且在当前点紧。MM 和 SCA 经常被混着叫区别在于 MM 更强调「majorize」这个构造动作SCA 更强调「逐次凸化」这个流程。实操里我基本把它们当一回事用。提示代理函数必须满足「在当前点紧」这个条件否则单调性不成立。我见过有人随手写个上界但当前点不相等结果迭代震荡查了半天以为是步长问题。2.3 收敛性依赖的三个前提缺一个就翻车SCA 的收敛保证不是白给的它依赖三个前提我按重要性排。第一代理函数在当前点必须紧且是原函数的全局上界最大化时或下界最小化时。这条破了单调性没了收敛无从谈起。第二每次子问题要解到足够精度。理论上要求解到全局最优实操里如果子问题只解了个近似外层迭代可能停在伪收敛点。CVXPY 里我会把solver的eps调紧一点别用默认的粗精度。第三迭代序列要有界或者目标函数要有下界。如果问题本身无界SCA 会一路发散。这个在功率控制里要特别注意功率上界约束必须写死。这三条里第一条是设计问题第二条是工程问题第三条是建模问题。我踩过的坑基本都落在这三类的某一类里。3. 用 Python CVXPY 跑通一个 SCA 最小例子3.1 选一个能体现非凸性的最小问题为了让你能直接抄我选一个足够小但确实非凸的问题最大化 sum(log(1 x_i * a_i))约束是 sum(x_i) ≤ Px_i ≥ 0。这里 a_i 是给定正系数x_i 是优化变量。这个问题本身其实是凹的log 是凹复合仿射保持凹所以它不算真非凸。为了制造非凸我把目标改成 sum(log(1 x_i * a_i)) - c * sum(x_i^2)加一个凹的负二次项整体就非凹了。这个结构在能效优化里很常见速率减去功耗惩罚。原问题maximize sum(log(1 a_i * x_i)) - c * sum(x_i^2) subject to sum(x_i) P x_i 0非凸来源是 -c * sum(x_i^2)它是凹函数但前面是负号整体目标变成凹减凹不保证凹。SCA 的处理是把 -c * sum(x_i^2) 在当前点做凹函数的泰勒展开得到全局上界然后最大化这个上界。3.2 代理函数的代码实现import cvxpy as cp import numpy as np np.random.seed(0) N 8 a np.random.rand(N) 0.5 c 0.1 P 5.0 x cp.Variable(N, nonnegTrue) # 原目标非凸不能直接丢给 CVXPY # obj cp.sum(cp.log(1 cp.multiply(a, x))) - c * cp.sum_squares(x) # SCA 外层迭代 x_k np.ones(N) * (P / N) # 初始点均匀分配 max_iter 50 tol 1e-4 for it in range(max_iter): # 构造代理-c*sum(x^2) 在 x_k 处的凹泰勒上界 # f(x) -c*x^2, f(x) f(x_k) f(x_k)*(x - x_k) # -c*x_k^2 - 2*c*x_k*(x - x_k) # 常数项不影响 argmax可省略 linear_term -2 * c * x_k # 梯度系数 proxy cp.sum(cp.log(1 cp.multiply(a, x))) linear_term x constraints [cp.sum(x) P] prob cp.Problem(cp.Maximize(proxy), constraints) prob.solve(solvercp.ECOS, verboseFalse) x_new x.value # 用原目标评估真实进展 true_obj np.sum(np.log(1 a * x_new)) - c * np.sum(x_new ** 2) if it % 5 0: print(fiter {it:3d} true_obj {true_obj:.6f}) if np.linalg.norm(x_new - x_k) tol: print(fconverged at iter {it}) break x_k x_new print(final x , np.round(x_new, 4))这段代码的逻辑分三层。第一层原目标里的 log 项是凹的保留不动二次项 -csum(x^2) 是凹的但我们要最大化它凹函数最大化本身没问题问题在于它和 log 项加在一起后整体不保证凹——实际上 log 是凹-x^2 也是凹两个凹相加还是凹等等这里我得纠正自己凹加凹确实是凹所以这个例子其实还是凹的。为了真正制造非凸得让二次项带正号即 csum(x^2)这样凹加凸整体非凹。我重新调整目标改成 sum(log(1 a_i * x_i)) - c * sum(x_i^2) 里把 -c 改成 c即 sum(log(1a_i x_i)) c * sum(x_i^2)最大化它。此时 log 凹x^2 凸凹加凸非凹。SCA 处理凸项 x^2 时因为要最大化凸函数的最大化不能直接做需要对凸函数做全局下界凸函数的泰勒展开是全局下界即 x^2 ≥ x_k^2 2 x_k (x - x_k)。用这个下界替换代理函数变成凹的可以最大化。# 修正后的代理构造 for it in range(max_iter): # 对凸项 c*sum(x^2) 做全局下界凸函数泰勒展开 # x^2 x_k^2 2*x_k*(x - x_k) # 常数项省略线性系数为 2*c*x_k linear_term 2 * c * x_k proxy cp.sum(cp.log(1 cp.multiply(a, x))) linear_term x constraints [cp.sum(x) P] prob cp.Problem(cp.Maximize(proxy), constraints) prob.solve(solvercp.ECOS) x_new x.value true_obj np.sum(np.log(1 a * x_new)) c * np.sum(x_new ** 2) if np.linalg.norm(x_new - x_k) tol: break x_k x_new3.3 参数怎么设初始点、步长与停止条件初始点 x_k 的选择直接影响收敛速度和能不能收敛到好点。我一般用均匀分配或者可行域内的随机点跑几次取最好的。均匀分配在功率分配问题里通常不差因为对称性。停止条件我用两个变量变化量 norm(x_new - x_k) tol或者连续两次原目标变化小于某个阈值。tol 取 1e-4 到 1e-6 之间看问题尺度。如果变量量级是 1e3tol 要相应放大。求解器选择上ECOS 适合小规模二阶锥问题SCS 适合大规模但精度粗MOSEK 最稳但要 license。CVXPY 里可以指定solvercp.ECOS如果报 solver 不支持换cp.SCS试试。注意子问题求解精度别用默认值。ECOS 默认abstol1e-8还行SCS 默认精度很粗外层迭代会被子问题的误差带偏表现为原目标曲线锯齿状。3.4 怎么验证你真的在收敛光看变量变化不够要看原目标序列。我习惯把每次迭代的真实目标打出来画一条曲线。健康的 SCA 曲线是单调上升最大化问题然后趋于平缓。如果出现下降说明代理函数构造错了或者子问题没解到最优。如果曲线一直上升不收敛检查约束是不是没写全问题可能无界。另一个验证手段是跑多个初始点看收敛到的目标值是否接近。如果差异很大说明问题有多个局部最优SCA 只能保证局部这时候要么换更好的初始点要么考虑全局化策略。4. 避坑与排查SCA 落地时最容易翻车的五件事4.1 代理函数方向搞反迭代直接发散现象原目标曲线一路下降或者震荡幅度越来越大。原因最大化问题里代理函数必须是原函数的全局上界我见过有人把凸函数的泰勒展开当上界用实际上凸函数泰勒是下界方向反了。解决每次构造完代理在当前点验证 g(x_k) f(x_k)再随机取一个点验证 g(x) f(x)最大化或 g(x) f(x)最小化。这个检查写成一个 assert能省掉大量调试时间。4.2 子问题求解精度不够伪收敛现象变量变化量很小看起来收敛了但换一个求解器或者调紧精度后目标还能再涨一截。原因子问题没解到全局最优外层迭代停在了子问题误差造成的伪驻点。解决把子问题求解器的精度调紧ECOS 用abstol1e-9, reltol1e-9SCS 用eps1e-6并增加max_iters。如果子问题规模大考虑换 MOSEK。4.3 约束非凸但被忽略解出来不可行现象求解器返回成功但把解代回原问题约束被违反。原因SCA 只凸化了目标约束里的非凸部分没处理或者处理时用了错误的近似方向。解决约束的非凸部分同样需要凸化比如 x*y b 这种双线性约束在当前点对其中一个变量做泰勒固定另一个。检查方法是把最终解代入所有原始约束逐条验证。4.4 初始点不可行第一步就报 infeasible现象CVXPY 报Problem status: infeasible。原因初始点不满足约束而代理子问题的可行域虽然包含原可行域但如果初始点离可行域太远子问题可能无解。解决初始点必须选在可行域内。功率分配里就是均匀分配相移优化里就是全零相位总之先找一个满足所有约束的点。4.5 收敛判据只看变量忽略目标尺度现象变量变化量小于 tol 但目标还在缓慢改善或者变量变化量很大但目标几乎不变。原因变量尺度和目标尺度不匹配单一判据不可靠。解决同时监控变量变化和目标变化两个都小于阈值才停。目标变化阈值取1e-6 * abs(true_obj)这种相对量比绝对量稳。5. 进阶技巧把 SCA 嵌进交替优化与加速收敛5.1 块坐标下降 SCA多变量耦合时的标准打法很多问题有多个变量块比如波束成形里的发射波束和 IRS 相移两者耦合导致联合非凸。标准做法是块坐标下降BCD固定相移优化波束固定波束优化相移每块内部用 SCA。这样每块都是凸子问题交替求解。收敛性上BCD 加 SCA 能保证目标单调但收敛速度取决于块之间的耦合强度。耦合强的时候交替次数会很多我一般设最大交替次数 20 到 50配合目标变化阈值提前停。5.2 用外推加速Nesterov 和 Anderson 加速的取舍SCA 的收敛速度通常是次线性的迭代次数多。加速手段有两类一是 Nesterov 外推在代理函数里加动量项二是 Anderson 加速用历史迭代点做线性组合。Nesterov 实现简单但步长参数不好调调不好会破坏单调性。Anderson 加速更稳但需要存历史点内存开销大。我的经验是问题规模小变量少于 100用 Anderson规模大用 Nesterov 或者干脆不加速因为加速带来的收益可能被每步的额外计算抵消。5.3 收敛性验证清单跑完 SCA我习惯做三件事确认结果可信。第一把最终解代入原问题检查所有约束满足程度违反量应该在求解器精度范围内。第二从不同初始点跑三到五次看目标值分布如果方差很小说明局部最优解质量稳定。第三把原目标曲线画出来确认单调性如果有下降段回去查代理函数。下面这张表是我常用的参数配置按问题规模分问题规模求解器子问题精度停止 tol最大迭代变量 50ECOS1e-91e-610050 ~ 500SCS1e-61e-5200 500MOSEK1e-81e-4300这张表不是金科玉律但能让你少走弯路。我早期用 SCS 默认精度跑小问题结果外层迭代 200 次还没收敛换成 ECOS 后 30 次就停了血泪经验。5.4 一个我常犯的错误最后说个我自己的教训。有次做 IRS 相移优化SCA 跑出来目标值比预期低很多查了两天以为是代理函数错了最后发现是初始相位设成了全零而全零相位在这个场景里恰好是个很差的局部点SCA 从那儿出发就再也没爬出来。后来改成随机相位跑五次取最好目标直接涨了 15%。SCA 是局部方法初始点的重要性怎么强调都不过分别在初始点上省事。希望帮到你。本文还有配套的精品资源点击获取