非凸优化

非凸优化

非凸优化（Non-convex Optimization）是指目标函数或可行域不满足凸性条件的最优化问题。与凸优化不同，非凸问题中可能存在多个局部极小值、鞍点和平坦区域，使得寻找全局最优解在计算上通常为 NP-hard。非凸优化广泛存在于深度学习、信号处理、组合优化和经济学中的规模报酬递增等领域，是当代优化理论与算法研究的核心前沿。

非凸性的来源

非凸性主要源于以下三种情形：

• 目标函数非凸：即使约束为凸集，目标函数 $f(\mathbf{x})$ 可能具有多个局部极小点。经典的例子包括Rastrigin 函数、Ackley 函数等测试函数，以及深度神经网络中高度非凸的损失景观（loss landscape）。
• 可行域非凸：约束集合可能由非凸约束定义。例如 $g(\mathbf{x}) = 0$ 形式的等式约束在 $g$ 非线性时通常产生非凸可行集；整数约束（如 $\mathbf{x} \in \mathbb{Z}^n$）也使可行域变为离散非凸集合。
• 混合情形：目标函数与约束同时非凸，典型如双线性优化、带有秩约束的矩阵优化问题，以及经济学中非凸生产集下的一般均衡问题。

核心困难

非凸优化的根本困难在于：局部信息（如梯度、Hessian）无法区分局部极小值与全局极小值。具体而言：

1. 局部极小值的泛滥：在高维非凸问题中，局部极小值的数量可能随维度指数增长，且它们的目标函数值可能远离全局最优值。
2. 鞍点的困扰：在高维空间中，鞍点（梯度为零但 Hessian 同时具有正负特征值）远比局部极小值更常见。经典的一阶方法可能在鞍点附近停滞，因为梯度近乎消失。
3. 全局最优性认证：与凸优化不同，满足KKT 条件仅保证驻点性，无法保证全局最优性。认证全局最优通常需要分支定界等组合方法，计算代价极高。
4. NP-hardness：大量非凸优化问题（如带有非凸约束的二次规划、稀疏优化中的 $\ell_0$ 最小化）被证明是 NP-hard，最坏情况下不存在多项式时间算法（除非 P = NP）。

主要方法

针对不同类型的非凸问题，研究者发展出多种求解策略：

凸松弛方法

将非凸问题松弛为凸问题进行求解，再通过松弛解恢复原问题的可行解。代表性方法包括：

• 半定规划松弛 (SDP Relaxation)：将非凸二次约束松弛为线性矩阵不等式，广泛用于组合优化（如 MAX-CUT）和传感器网络定位。
• 压缩感知中的 $\ell_1$ 松弛：将 NP-hard 的 $\ell_0$ 问题松弛为凸的 $\ell_1$ 问题，在一定条件下（如受限等距性质）二者等价。
• 拉格朗日松弛：通过松弛难约束获得可解的下界问题，常用于整数规划。

全局优化方法

当凸松弛不够紧时，需要严格的全局优化技术：

• 分支定界：系统地分割可行域，利用凸松弛提供下界、局部搜索提供上界，逐步剪枝收敛到全局最优。
• Lipschitz 优化：利用目标函数的 Lipschitz 常数构造确定性全局搜索算法，如 Piyavskii-Shubert 算法和 DIRECT 算法。
• 单调优化与DC 规划：将目标分解为两个凸函数之差（Difference of Convex functions），利用凸分析的结论设计全局算法。

局部优化与逃逸机制

在深度学习等大规模非凸问题中，全局最优往往不可企及，但高质量的局部极小值或甚至鞍点附近的解已足够实用：

• 随机梯度下降 (SGD) 及其变体（Adam、RMSprop）：随机噪声使迭代能够逃离严格的鞍点，实证表明在高维深度网络中大部分局部极小值与全局最优值非常接近。
• 扰动梯度下降 (Perturbed GD)：Jin 等（2017）证明，在梯度下降中加入各向同性小扰动，可在多项式时间内逃逸所有严格鞍点，收敛到二阶驻点。
• 模拟退火与遗传算法：通过随机搜索跳出局部陷阱，适用于低维、黑箱或高度不光滑的问题。

景观分析与"良性非凸"

近年来，一个重要研究方向是证明某些看似非凸的问题实为"隐蔽凸"（hidden convex）或具有良性非凸景观（benign non-convex landscape）：其所有局部极小值均为全局极小值，且鞍点为严格的（Hessian 有负特征值，可通过二阶信息逃逸）。典型例子包括：

• 矩阵补全与矩阵感知：在满足非相干性条件时，低秩矩阵分解的 Burer-Monteiro 分解形式虽非凸，但所有局部极小值都是全局极小值。
• 相位恢复（Phase Retrieval）：Wirtinger Flow 算法在充足测量下，损失景观具有良性结构。
• 字典学习与盲反卷积：在一定条件下具有类似的景观性质。

经济学中的应用

经济学中非凸优化出现于以下关键场景：

1. 规模报酬递增：生产集非凸时，利润最大化问题成为非凸优化，传统边际分析方法失效，需借助整数规划或全局搜索。
2. 机制设计：在非线性定价、最优拍卖设计中，激励相容约束可能导致非凸可行集。
3. 网络经济学：具有外部性的均衡选择问题常表现为非凸势函数（potential function）的全局优化。
4. 计量经济学：有限混合模型（finite mixture models）和结构估计中，似然函数常为非凸，需谨慎处理多峰性。

非凸优化已从"无法解决的禁区"逐步转变为"可结构化攻克的领域"。凸松弛、全局方法、随机逃逸策略与景观分析各自从不同角度为非凸问题提供了可计算性与理论保证，这一领域的持续突破正在深刻重塑优化理论、机器学习和经济分析的面貌。