凸化松弛

1. SQP（序列二次规划）

1.1 它是什么

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

它的基本思想是：

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

原问题：

$$\underset{x}{\min }f(x)\text{s.t. }{c}_i(x)=0,h_j(x)\le 0$$

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

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

得到一个 QP 子问题。

1.2 数学形式

Lagrangian 为

$$\mathcal{L}(x,\lambda ,\mu )=f(x)+{\lambda }^{\top }c(x)+{\mu }^{\top }h(x)$$

SQP 取步长方向 $d$，解

$$\underset{d}{\min }\nabla f(x^k{)}^{\top }d+\frac{1}{2}{d}^{\top }{B}_{k}d$$

约束近似为

$$c(x^k)+\nabla c(x^k{)}^{\top }d=0$$ $$h(x^k)+\nabla h(x^k{)}^{\top }d\le 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 它是什么

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

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

2.2 什么叫凸松弛

原问题非凸，例如有：

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

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

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

这样原问题变成凸问题。

2.3 什么是内点法

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

例如不等式约束

$$g_i(x)\le 0$$

可转成 barrier 形式：

$$\underset{x}{\min }f(x)-\mu \sum _i\log (-g_i(x))$$

然后逐步让 $\mu \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：维护当前最好可行解，上界
• 若某节点下界 $\ge$ 当前最好上界，则剪枝

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

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：

$$\underset{x}{\min }{x}^{\top }{Q}_{0}x+c_0^{\top }x\text{s.t.}{x}^{\top }{Q}_{i}x+c_i^{\top }x+d_i\le 0$$

引入

$$X=x{x}^{\top }$$

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

$$x^{\top }Qx=\mathrm{Tr}(QX)$$

但原本要求

$$X=x{x}^{\top }⟺X⪰0,\mathrm{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^{\star }$ 恰好 rank 1，那就完美恢复原解。
若不是，常用：

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

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

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

所以：

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