SCA逐次凸近似：非凸优化问题的工程实践与避坑指南

简介：这份资源聚焦SCA（Sequential Convex Approximation）凸优化算法的实现，面向具备一定数学优化基础、希望将非凸问题转化为连续凸近似求解的学习者与工程人员，可用于无线通信、信号处理、能源系统优化等场景的算法验证。压缩包共2个文件，均为MATLAB脚本（.m），整体约3KB，体量轻便，便于直接阅读与二次修改。其中一份脚本给出特定功率问题的示例建模，另一份则承载通用SCA算法框架，二者配合可帮助读者理解凸函数与凸集、凸优化问题形式、近似构造、迭代更新及收敛性分析等关键环节。目前已有2699人学习下载，说明其在同类算法资料中具备一定参考价值。读者可借此掌握Taylor展开、松弛等近似技术，并对照源码梳理从近似、求解到更新的完整流程，进而定制适配自身问题的SCA实现。

1. SCA 与凸优化：从一个「非凸卡死」的现场说起

如果你调过通信里的波束成形、搞过 IRS 相控阵、或者碰过机器学习里的稀疏正则，大概率遇到过这种场面：目标函数写出来挺漂亮，一求导发现非凸，CVX 直接报Disciplined convex programming error，梯度下降跑一夜 loss 在几个局部极小值之间反复横跳。这时候老工程师通常会甩给你三个字母——SCA，Successive Convex Approximation，逐次凸近似。它干的事很朴素：既然原问题非凸，那我不直接解你，我在当前点附近构造一个凸的「替身」，解替身，拿解当新起点，再构造再解，直到收敛。凸优化在这里不是目的，是工具；SCA 是把非凸问题「翻译」成一系列凸问题的翻译官。这套方法适合谁？适合手里已经有凸优化求解器（CVX、CVXPY、MOSEK、SCS 都行）、但被非凸约束或非凸目标卡住的从业者。下面我按自己踩过的顺序，把 SCA 从原理到能跑通的代码、参数、翻车点讲一遍。

2. SCA 凭什么能收敛：凸近似、代理函数与三个前提

2.1 非凸问题为什么不能直接丢给求解器

先把话说死：凸优化求解器的「凸」不是建议，是硬约束。CVX 这类工具用的是 disciplined convex programming，它靠一套规则判断你写的表达式是否满足凸性组合，一旦出现变量相乘、变量做分母、log 里套非凹函数，直接拒绝。这不是求解器弱，而是凸问题的全局最优性保证依赖于可行域凸、目标凸这两个条件，破坏任何一个，KKT 点就不再等价于全局最优。

现实里的问题偏偏爱非凸。举几个我常碰到的：波束成形里功率约束下的和速率最大化，速率是 log(1+SINR)，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(1+SINR) 对某些变量是凹的，直接泰勒就能用。

第二条是二次上界，典型场景是处理 log 和分式。比如 log(1+x) 这种凹函数，除了泰勒，还可以用二次函数在展开点处构造上界，收敛性质更好但计算稍重。分式结构常用二次变换（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) ≤ P，x_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, nonneg=True) # 原目标（非凸，不能直接丢给 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(solver=cp.ECOS, verbose=False) 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(f"iter {it:3d} true_obj = {true_obj:.6f}") if np.linalg.norm(x_new - x_k) < tol: print(f"converged 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(1+a_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(solver=cp.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_new

3.3 参数怎么设：初始点、步长与停止条件

初始点 x_k 的选择直接影响收敛速度和能不能收敛到好点。我一般用均匀分配或者可行域内的随机点跑几次取最好的。均匀分配在功率分配问题里通常不差，因为对称性。

停止条件我用两个：变量变化量 norm(x_new - x_k) < tol，或者连续两次原目标变化小于某个阈值。tol 取 1e-4 到 1e-6 之间，看问题尺度。如果变量量级是 1e3，tol 要相应放大。

求解器选择上，ECOS 适合小规模二阶锥问题，SCS 适合大规模但精度粗，MOSEK 最稳但要 license。CVXPY 里可以指定solver=cp.ECOS，如果报 solver 不支持，换cp.SCS试试。

注意：子问题求解精度别用默认值。ECOS 默认abstol=1e-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 用abstol=1e-9, reltol=1e-9，SCS 用eps=1e-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，我习惯做三件事确认结果可信。第一，把最终解代入原问题，检查所有约束满足程度，违反量应该在求解器精度范围内。第二，从不同初始点跑三到五次，看目标值分布，如果方差很小，说明局部最优解质量稳定。第三，把原目标曲线画出来，确认单调性，如果有下降段，回去查代理函数。

下面这张表是我常用的参数配置，按问题规模分：

这张表不是金科玉律，但能让你少走弯路。我早期用 SCS 默认精度跑小问题，结果外层迭代 200 次还没收敛，换成 ECOS 后 30 次就停了，血泪经验。

5.4 一个我常犯的错误

最后说个我自己的教训。有次做 IRS 相移优化，SCA 跑出来目标值比预期低很多，查了两天以为是代理函数错了，最后发现是初始相位设成了全零，而全零相位在这个场景里恰好是个很差的局部点，SCA 从那儿出发就再也没爬出来。后来改成随机相位跑五次取最好，目标直接涨了 15%。SCA 是局部方法，初始点的重要性怎么强调都不过分，别在初始点上省事。希望帮到你。

本文还有配套的精品资源，点击获取