1. SQP（序列二次规划）

1.1 它是什么

SQP = Sequential Quadratic Programming。
这是求解光滑非线性约束优化最经典的一类方法之一。

它的基本思想是：

在当前点，把目标函数用二次模型近似，把约束函数线性化，
得到一个二次规划（QP）子问题；
解这个 QP，得到搜索方向，再更新。

原问题：

x min f (x) s.t. c_{i} (x) = 0, h_{j} (x) \leq 0

SQP 在当前点 $x^{k}$ 上构造：

目标：Lagrangian 的二次近似
约束：一阶线性化

得到一个 QP 子问题。

1.2 数学形式

Lagrangian 为

L (x, λ, μ) = f (x) + λ^{⊤} c (x) + μ^{⊤} h (x)

SQP 取步长方向 $d$ ，解

d min \nabla f (x^{k})^{⊤} d + \frac{1}{2} d^{⊤} B_{k} d

约束近似为

c (x^{k}) + \nabla c (x^{k})^{⊤} d = 0

h (x^{k}) + \nabla h (x^{k})^{⊤} d \leq 0

其中 $B_{k}$ 常取为 Lagrangian Hessian 或其拟牛顿近似。

1.3 它为什么强

因为它直接在逼近 KKT 条件。
如果问题光滑且正则性好，SQP 常常有非常强的局部收敛性质：

线性收敛
超线性收敛
甚至二次收敛（理想情形）

1.4 适合什么问题

适合：

光滑非线性规划
中等规模高精度连续优化
工程设计
参数辨识
约束优化

1.5 优点

局部收敛性能强
对高精度解很有效
理论成熟
是非线性规划里的主力方法之一

1.6 缺点

对初值较敏感
主要是局部方法
需要梯度甚至 Hessian 信息
对不可微问题不合适
大规模问题时每步 QP 可能较重

1.7 和 SCA 的关系

SQP 可以看成一种结构化的局部近似法。
但它比一般 SCA 更“硬核”：

SCA：近似模型可以很自由
SQP：固定成“二次目标 + 线性约束”的 QP 形式

所以：

SQP 是 SCA 家族中非常经典、理论最成熟的一支。

2. 内点法配合凸松弛

2.1 它是什么

这不是一个单独算法，而是一种组合套路：

先把原问题做凸松弛
得到 LP / QP / SOCP / SDP 等凸优化问题
再用内点法高效求解

2.2 什么叫凸松弛

原问题非凸，例如有：

秩约束
0-1 约束
双线性项
分式非凸项
整数约束

把它们替换成更大的凸可行域，比如：

去掉 rank = 1 约束
用 $[0, 1]$ 代替 ${0, 1}$
用 McCormick 包络包住双线性项
把 QCQP 放松成 SDP / SOCP

这样原问题变成凸问题。

2.3 什么是内点法

内点法是解凸优化问题的核心数值方法。
它不是在边界上走，而是在可行域内部通过 barrier function 逼近边界最优解。

例如不等式约束

g_{i} (x) \leq 0

可转成 barrier 形式：

x min f (x) - μ i \sum lo g (- g_{i} (x))

然后逐步让 $μ \to 0$ 。

2.4 为什么这套组合重要

因为很多非凸问题虽然难，但松弛后是标准凸问题，而标准凸问题最成熟的求解器往往就是内点法。

典型流程：

非凸 QCQP
做 SDR 变成 SDP
用内点法求 SDP
得到下界或近似解

2.5 优点

能利用凸优化强大的理论和数值工具
常能给出下界、可行性证书、近似保证
在中小规模上很稳

2.6 缺点

松弛可能很松，解不接近原问题
内点法对大规模稀疏超大问题可能代价高
得到的解可能需要“舍入 / 恢复”才能回到原问题

2.7 适用场景

QCQP
组合优化的连续松弛
鲁棒优化
控制
通信波束赋形
电力系统

3. Branch-and-Bound

3.1 它是什么

Branch-and-Bound（分支定界）是全局优化 / 整数优化的核心框架。

思想非常朴素：

把大问题拆成很多子问题；
对每个子问题算一个下界或上界；
如果某个子问题不可能优于当前最好解，就直接剪掉；
只对有希望的子问题继续分裂。

3.2 基本机制

对于最小化问题：

Branch：把可行域切分成若干子区域
Bound：对每个子区域算一个下界
Incumbent：维护当前最好可行解，上界
若某节点下界 $\geq$ 当前最好上界，则剪枝

直到所有节点都被剪掉或证完最优。

3.3 它的关键

关键不在“分支”，而在“定界”。

如果下界很强，就能大量剪枝。
如果下界很弱，树会爆炸。

所以 B&B 实际效果高度依赖：

松弛质量
分支策略
节点选择策略
可行解启发式

3.4 适合什么问题

MILP / MIQP / MINLP
全局优化
非凸整数规划
空间分支定界（spatial branch-and-bound）

3.5 优点

理论上可以求全局最优
是整数优化的标准方法
可以和各种松弛、割平面、启发式结合

3.6 缺点

最坏情况指数复杂度
对大规模非凸问题可能极慢
强依赖好的下界和剪枝

3.7 和前面方法的关系

B&B 是一个总框架，里面常嵌入：

LP / QP / SOCP / SDP 松弛
McCormick 包络
RLT
局部 NLP 求解器
启发式找可行解

所以：

Branch-and-Bound 不是“一个孤立算法”，而是全局优化的大骨架。

4. 半定松弛（SDR）

4.1 它是什么

SDR = Semidefinite Relaxation。
这是把某类非凸问题提升到矩阵空间，再丢掉秩约束，变成半定规划（SDP）。

最典型的是 QCQP：

x min x^{⊤} Q_{0} x + c_{0}^{⊤} x s.t. x^{⊤} Q_{i} x + c_{i}^{⊤} x + d_{i} \leq 0

引入

X = x x^{⊤}

则二次项可写成线性形式：

x^{⊤} Q x = Tr (QX)

但原本要求

X = x x^{⊤} ⟺ X ⪰ 0, rank (X) = 1

难点就在 rank = 1。
SDR 做的就是：

保留 $X ⪰ 0$ ，丢掉 rank = 1

于是得到 SDP。

4.2 本质

它是一种lift-and-relax：

升维到矩阵变量
把原来非凸的二次结构线性化
用 PSD 锥约束代替原来的非凸秩结构

4.3 适合什么问题

QCQP
波束赋形
最大割
传感器定位
相位恢复
控制与鲁棒优化

4.4 优点

常给出很强的下界
某些问题中松弛很紧
理论深厚
可直接用 SDP 求解器

4.5 缺点

变量维度会显著膨胀
SDP 求解成本高
松弛后得到的矩阵不一定 rank 1，需要恢复
大规模时很吃资源

4.6 解恢复

如果 SDR 解出来的 $X^{⋆}$ 恰好 rank 1，那就完美恢复原解。
若不是，常用：

随机化 rounding
特征分解后取主方向
局部优化再修正

4.7 和“内点法配合凸松弛”的关系

SDR 就是“凸松弛”的一种典型实例。
而 SDP 往往用内点法求。

所以：

SDR = 松弛建模层面；内点法 = 数值求解层面。

杂谈目录

凸化松弛