局部近似求解

1. SCA / SCP

1.1 它是什么

SCA = Successive Convex Approximation，逐次凸近似。
SCP = Sequential Convex Programming，序列凸规划。

这两个名字非常接近，很多文献里几乎混用。核心思想都是：

原问题非凸，但我在当前点附近，把它近似成一个凸子问题；
解出这个凸子问题后得到新点；
再在新点附近重新凸化；
不断迭代。

所以它本质上是：

• 用一串凸问题逼近一个非凸问题
• 每一步都尽量调用成熟的凸优化工具

1.2 它怎么做

设原问题是

$$\underset{x}{\min }f(x)\text{s.t. }{g}_i(x)\le 0$$

其中目标或约束有非凸项。
SCA / SCP 在第 $k$ 步常做的是：

• 对非凸部分在当前点 $x^k$ 附近做一阶或二阶近似
• 构造一个凸上界 / 局部近似模型
• 解

$$x^{k+1}=\arg \underset{x}{\min }\tilde{f}(x;x^k)\text{s.t. }{\tilde{g}}_i(x;x^k)\le 0$$

其中 $\tilde{f},{\tilde{g}}_i$ 是当前的凸近似。

常见技术：

• 一阶泰勒展开
• trust region
• 罚函数
• DC 分解后局部线性化

1.3 适合什么问题

非常适合：

• 工程优化
• 通信资源分配
• 控制
• 轨迹规划
• 稀疏优化
• 带非凸约束但“局部凸化”容易的问题

尤其当原问题的非凸性来自：

• 差分凸结构
• 某些可微非线性项
• 乘积项、分式项、对数项等可局部线性化的结构

1.4 优点

• 每一步只解凸问题，数值稳定
• 能直接利用 CVX、MOSEK、ECOS、OSQP 等工具
• 对中大规模问题很实用
• 工程上很常见

1.5 缺点

• 一般只保证收敛到驻点 / 局部最优 / KKT 点
• 不保证全局最优
• 近似模型设计不好时可能不收敛或收敛慢
• 初值依赖很强

1.6 和其他方法的关系

• 和 MM 很接近，很多 SCA 可以写成 MM
• 和 SQP 也近：SQP 是“二次近似 + 线性化约束”的特殊强力版本
• 可作为 Branch-and-Bound 每个节点的局部求解器

2. MM 算法（Majorization-Minimization）

2.1 它是什么

MM 的思想比 SCA 更抽象一些。
它不是简单说“凸化”，而是说：

在当前点构造一个容易优化的代理函数 $Q(x\mid x^k)$，
这个代理函数在当前点与原函数接触，并且对原函数有某种上界或下界关系；
然后优化这个代理函数。

对于最小化问题，典型要求是：

$$f(x)\le Q(x\mid x^k),Q(x^k\mid x^k)=f(x^k)$$

然后令

$$x^{k+1}=\arg \underset{x}{\min }Q(x\mid x^k)$$

这叫 majorization-minimization：
先 majorize（构造上界），再 minimization（最小化这个上界）。

2.2 它的本质

MM 的关键不是“凸”，而是“代理函数好解且保证下降”。

因为如果 $Q$ 满足上面条件，那么：

$$f(x^{k+1})\le Q(x^{k+1}\mid x^k)\le Q(x^k\mid x^k)=f(x^k)$$

所以目标值单调下降。

这很重要。
MM 最大的特点就是：很强调单调改进。

2.3 常见来源

MM 代理函数常来自：

• Jensen 不等式
• 一阶上界
• Lipschitz 梯度上界
• 二次上界
• 凹函数线性上界
• EM 算法（EM 可以视为 MM 的特例）

2.4 适合什么问题

适合：

• 目标函数结构复杂，但容易构造“好优化的代理函数”
• 统计学习
• 稀疏正则化
• 矩阵分解
• 鲁棒估计
• 最大似然 / 后验估计

2.5 优点

• 经常能保证目标单调下降
• 代理函数设计灵活
• 很适合推导新算法
• 对复杂目标很有表达力

2.6 缺点

• 代理函数设计靠经验和结构洞察
• 仍然通常只有局部收敛保证
• 代理函数过松时收敛慢