凸优化深度指南

文档概述

凸优化是现代机器学习与统计推断的理论支柱。本指南系统介绍凸集与凸函数的基本理论、典型优化问题（LP、QP、SOCP、SDP）、对偶理论与KKT条件、梯度下降法及其收敛性分析、投影方法与约束处理、以及各类一阶二阶优化方法的深入讨论。附录包含变分不等式、分散式优化、凸优化的计算复杂性等高级专题。

关键词

序号	关键词	英文	核心概念
1	凸集	Convex Set	$\forall x, y \in C, θ \in [0, 1] : θ x + (1 - θ) y \in C$
2	凸函数	Convex Function	$f (θ x + (1 - θ) y) \leq θ f (x) + (1 - θ) f (y)$
3	线性规划	Linear Programming	$min c^{T} x s.t. A x \leq b$
4	二次规划	Quadratic Programming	$min \frac{1}{2} x^{T} Q x + c^{T} x s.t. A x \leq b$
5	KKT条件	Karush-Kuhn-Tucker	最优性的必要条件
6	对偶问题	Dual Problem	原问题的下界优化
7	梯度下降	Gradient Descent	$x_{k + 1} = x_{k} - η \nabla f (x_{k})$
8	收敛率	Convergence Rate	$O (1/ k), O (1/ k^{2}), exp (- k)$
9	Lipschitz连续	Lipschitz Continuity	$∥ f (x) - f (y) ∥ \leq L ∥ x - y ∥$
10	强凸	Strong Convexity	$f (x) - \frac{μ}{2} ∥ x ∥^{2}$ 凸
11	Frank-Wolfe	Frank-Wolfe Algorithm	线性约束优化的投影自由方法
12	拉格朗日	Lagrangian	$L (x, λ, ν) = f_{0} (x) + \sum λ_{i} f_{i} (x) + \sum ν_{j} h_{j} (x)$
13	半定规划	SDP	$min C ∙ X s.t. A_{i} ∙ X = b_{i}, X ⪰ 0$
14	二阶锥规划	SOCP	$∥ A_{i} x + b_{i} ∥_{2} \leq c_{i}^{T} x + d_{i}$
15	原对偶方法	Primal-Dual	同时追踪原变量和对偶变量的算法
16	近端方法	Proximal Methods	$prox_{τ h} (x) = ar g min_{y} {h (y) + \frac{1}{2 τ} ∥ y - x ∥^{2}}$
17	交替方向乘子法	ADMM	分布式凸优化的经典框架
18	镜像下降	Mirror Descent	通过Bregman散度定义的梯度类方法
19	Nesterov加速	Nesterov Acceleration	达到 $O (1/ k^{2})$ 收敛率
20	坐标下降	Coordinate Descent	沿坐标轴方向依次优化

一、凸集与凸函数

1.1 凸集的定义与性质

凸集：集合 $C \subseteq R^{n}$ 是凸的，当且仅当对任意 $x, y \in C$ 和 $θ \in [0, 1]$ ，有：

$θ x + (1 - θ) y \in C$

几何直观：凸集内任意两点的线段完全包含在集合内。换言之，用直尺连接凸集内任意两点，整条线段都不会”跑出去”。

凸集的代数理解：从仿射几何的角度，凸集可以视为所有仿射包的子集。对于任意有限点集 ${x_{1}, \dots, x_{k}}$ ，其凸包（convex hull）定义为：

$conv {x_{1}, \dots, x_{k}} = {\sum_{i = 1}^{k} θ_{i} x_{i} : θ_{i} \geq 0, \sum_{i = 1}^{k} θ_{i} = 1}$

凸包是包含给定点的最小凸集。

常见的凸集：

超平面： ${x : a^{T} x = b}$ ，维数为 $n - 1$
半空间： ${x : a^{T} x \leq b}$ （闭半空间）或 ${x : a^{T} x < b}$ （开半空间）
多面体：有限个半空间和超平手的交集，记作 $P = {x : A x ⪯ b, C x = d}$
范数球： ${x : ∥ x ∥ \leq 1}$ （任意范数 $∥ \cdot ∥$ ）
范数锥： ${(x, t) : ∥ x ∥ \leq t} \subseteq R^{n + 1}$
仿射集： ${x : A x = b}$ ，仿射集既是凸集也是凸锥的平移
正象限： $R_{+}^{n} = {x \in R^{n} : x_{i} \geq 0, \forall i}$
概率单纯形： $Δ_{n} = {x \in R_{+}^{n} : \sum_{i} x_{i} = 1}$
半正定锥： $S_{+}^{n} = {X \in R^{n \times n} : X = X^{T}, X ⪰ 0}$ ，这是一个自对偶锥

仿射变换保凸：若 $C$ 是凸集，则其仿射像 $f (C) = {f (x) : x \in C}$ 和仿射逆像 $f^{- 1} (C) = {x : f (x) \in C}$ 都是凸集，其中 $f (x) = A x + b$ 。

透视变换：透视函数 $P : R^{n + 1} \to R^{n}$ 定义为 $P ((x, t)) = x / t$ ，定义域要求 $t > 0$ 。透视变换将凸锥映射为凸集（反之，将凸集提升为凸锥）。

凸集的运算保凸性：

交集：凸集的交集仍是凸集。这是最重要的保凸运算之一。例如，多面体是多半空间的交集。
和：如果 $C_{1}, C_{2}$ 凸，则 $C_{1} + C_{2} = {x + y : x \in C_{1}, y \in C_{2}}$ 凸（ Minkowski 和）。
直积： $C_{1} \times C_{2} = {(x, y) : x \in C_{1}, y \in C_{2}}$ 凸。
仿射变换： $f (C) = {f (x) : x \in C}$ 保持凸性。
透视变换：保持凸性。
线性分式变换： $f (x) = \frac{A x + b}{c ^{T} x + d}$ ，定义域为 ${x : c^{T} x + d > 0}$ ，保持凸性。

凸集示例

单位球 $B = {x : ∥ x ∥_{2} \leq 1}$ 是凸的。证明：任取 $x, y \in B$ ，则 $∥ θ x + (1 - θ) y ∥_{2} \leq θ ∥ x ∥_{2} + (1 - θ) ∥ y ∥_{2} \leq θ \cdot 1 + (1 - θ) \cdot 1 = 1$ 。

三角形的内部及边界是凸的。

圆盘（平面内）是凸的。

环形区域 ${x : 1 \leq ∥ x ∥ \leq 2}$ 不是凸的（因为不包含原点到边界点的线段）。

任意椭球 ${x : (x - x_{c})^{T} P^{- 1} (x - x_{c}) \leq 1}$ 是凸的，其中 $P ≻ 0$ 。

凸集的分离定理：分离定理是凸分析中最深刻的结果之一，也是对偶理论的基石。

超平面分离定理：若 $C$ 和 $D$ 是不相交的凸集（即 $C \cap D = \emptyset$ ），则存在超平面将它们分离： $\exists a \neq = 0, b$ 使得 $a^{T} x \leq b$ 对所有 $x \in C$ 成立， $a^{T} y \geq b$ 对所有 $y \in D$ 成立。
严格分离定理：若 $C$ 和 $D$ 是闭凸集且 $C \cap D = \emptyset$ ，则在适当条件下可严格分离。
支撑超平面定理：每个凸集的边界点都有支撑超平面。

这些定理的几何直觉是：两个互不相交的凸集之间可以”塞”进一张无限薄的纸把它们隔开。

1.2 凸函数的定义

凸函数：函数 $f : R^{n} \to R \cup {+ \infty}$ 是凸的，当且仅当 $dom (f)$ 是凸集，且对任意 $x, y \in dom (f)$ 和 $θ \in [0, 1]$ ：

$f (θ x + (1 - θ) y) \leq θ f (x) + (1 - θ) f (y)$

几何意义：函数图像上任意弦线位于函数图像上方。换言之，函数的 epigraph（上境图） $epi (f) = {(x, t) : f (x) \leq t}$ 是 $R^{n + 1}$ 中的凸集——这是凸函数的一个等价定义。

严格凸：若上述不等式在 $x \neq = y$ 和 $θ \in (0, 1)$ 时严格成立，即 $f (θ x + (1 - θ) y) < θ f (x) + (1 - θ) f (y)$ 。

凹函数： $- f$ 是凸的。

拟凸函数：函数 $f$ 是拟凸的，若其所有下水平集 ${x : f (x) \leq α}$ 是凸集。拟凸不蕴含凸，反之亦然。例如， $f (x) = e^{x}$ 既是凸的也是拟凸的，但 $f (x) = - x^{2}$ 在 $x \neq = 0$ 时是拟凸的（非严格凸）但不是凸的。

对数凸函数：函数 $f$ 是对数凸的，若 $f (x) > 0$ 且 $lo g f (x)$ 是凸的。对数凸函数一定是凸的，但凸函数不一定是严格凸的。典型例子：Gamma 函数在正实轴上是对数凸的（由 Bohr-Mollerup 定理可证）。

Jensen不等式：凸函数的期望形式。设 $X$ 是随机变量， $ϕ$ 是凸函数，则 $ϕ (E [X]) \leq E [ϕ (X)]$ 。离散形式：对任意 $x_{1}, \dots, x_{k}$ 和 $θ_{i} \geq 0$ ， $\sum θ_{i} = 1$ ：

$f (\sum_{i} θ_{i} x_{i}) \leq \sum_{i} θ_{i} f (x_{i})$

Jensen 不等式是概率论、信息论和统计学中许多重要不等式的源头。例如，利用 Jensen 不等式可立即推导出 AM-GM 不等式（令 $f (x) = - lo g x$ ）。

1.3 凸函数的判别与性质

一阶条件：若 $f$ 可微，则 $f$ 凸当且仅当

$f (y) \geq f (x) + \nabla f (x)^{T} (y - x), \forall x, y \in dom (f)$

即函数位于任一点切平面的上方（支持超平面性质）。这个不等式称为梯度不等式，是凸函数的核心特征。

二阶条件：若 $f$ 二阶可微，则 $f$ 凸当且仅当其Hessian矩阵半正定：

$\nabla^{2} f (x) ⪰ 0, \forall x \in dom (f)$

几何直觉：Hessian 半正定意味着函数的曲率处处非负，即函数图形处处向上弯曲。

注意可微性假设

对于不可微的凸函数，一阶和二阶条件不适用，但可以用次梯度（subgradient）来描述。凸函数在每一点都存在次梯度。次梯度集为 $\partial f (x) = {g : f (y) \geq f (x) + g^{T} (y - x), \forall y}$ 。

常见的凸函数：

指数函数 $e^{a x}$
负对数 $- lo g x$ （在 $x > 0$ ），是严格凸的
范数 $∥ x ∥_{p}$ （任意 $p \geq 1$ ），是凸的但非严格凸
二次函数 $\frac{1}{2} x^{T} Q x + b^{T} x + c$ （ $Q ⪰ 0$ ）
最大函数 $max (x_{1}, \dots, x_{n})$
幂函数 $x^{a}$ 在 $x > 0$ 区间： $a \geq 1$ 时凸， $0 \leq a \leq 1$ 时凹
指数和函数 $lo g \sum_{i} e^{x_{i}}$ （log-sum-exp），是 $R^{n}$ 上可微凸函数的典型例子
几何平均 $(\prod_{i} x_{i})^{1/ n}$ ，在正象限上是对数凹的
行列式 $det (X)^{1/ n}$ 在正定矩阵锥上是凹函数

凸函数的运算：

非负加权和：若 $f_{i}$ 凸， $w_{i} \geq 0$ ，则 $\sum w_{i} f_{i}$ 凸。
仿射复合：若 $f$ 凸，则 $g (x) = f (A x + b)$ 凸。
逐点上确界：凸函数族的逐点上确界是凸的： $g (x) = sup_{i \in I} f_{i} (x)$ 。
最小化：凸函数在凸集上的最小化可能失去凸性（但仍是拟凸的）。
透视变换：若 $f$ 凸，则 $g (x, t) = t f (x / t)$ （定义域 $t > 0$ ）凸。

凸函数的重要性

凸优化问题的局部最优解即全局最优解。这一性质使得凸问题在理论上”容易”求解——只需找到局部最优即可。这是凸优化区别于一般非凸优化的根本特征。

1.4 函数的共轭与Fenchel对偶

共轭函数（Conjugate Function）：给定函数 $f : R^{n} \to R \cup {+ \infty}$ ，其 Fenchel 共轭定义为：

$f^{*} (y) = sup_{x \in dom (f)} {y^{T} x - f (x)}$

几何直觉： $f^{*} (y)$ 是超平面 $z = y^{T} x - f (x)$ 在 $x$ 上取上确界时，超平面在 $z$ 轴方向的截距。

共轭的性质：

$f^{*}$ 恒为凸函数（作为逐点上确界）。
Fenchel-Moreau 定理：若 $f$ 是闭凸函数，则 $f^{**} = f$ 。
Legendre 变换关系：若 $f$ 可微且严格凸，则 $y = \nabla f (x) ⟺ x = \nabla f^{*} (y)$ 。

Fenchel 不等式：对任意 $x, y$ ，有：

$f (x) + f^{*} (y) \geq x^{T} y$

等号成立当且仅当 $y \in \partial f (x)$ （或 $x \in \partial f^{*} (y)$ ）。

共轭函数示例

二次函数： $f (x) = \frac{1}{2} x^{T} Q x$ （ $Q ≻ 0$ ），则 $f^{*} (y) = \frac{1}{2} y^{T} Q^{- 1} y$ 。

范数： $f (x) = ∥ x ∥$ ，则 $f^{*} (y) = δ_{B^{*}} (y)$ ，即单位范数对偶球的指示函数。

负对数： $f (x) = - lo g x$ （ $x > 0$ ），则 $f^{*} (y) = - 1 - lo g (- y)$ （ $y < 0$ ）。

二、典型优化问题

2.1 线性规划（LP）

线性规划的标准形式：

$min_{x} c^{T} x$ $s.t. A x = b$ $x \geq 0$

或不等式形式：

$min_{x} c^{T} x$ $s.t. A x \leq b$

线性规划的几何：目标函数定义一族平行超平面 ${x : c^{T} x = α}$ 。约束定义一个多面体（凸集）。最优解出现在多面体的顶点（extreme point）。若最优解存在，则至少有一个顶点是最优的。

单纯形法（Dantzig, 1947）：通过在顶点间移动来寻找最优解。基本思想：从一个顶点出发，若存在相邻顶点的目标函数值更优，则沿边移动到该顶点；重复直到不存在改进方向。最坏情况时间复杂度为指数级（ $O (2^{n})$ ），但在实践中通常很快，因为”平均”迭代次数与约束数和变量数呈线性关系。

椭球法（Khachiyan, 1979）：首个多项式时间算法，时间复杂度 $O (n^{6} L)$ ，其中 $L$ 是输入编码长度。虽然理论上有突破，但实际效率不如单纯形法。

内点法：通过障碍函数在多面体内部移动，多项式时间复杂度 $O (n^{3.5} L)$ 。现代LP求解器（如CPLEX、Gurobi）主要基于内点法和单纯形法的结合。

对偶理论：LP 的对偶问题为：

$max_{y} b^{T} y$ $s.t. A^{T} y \leq c$

弱对偶性： $b^{T} y \leq c^{T} x$ 对所有原-对偶可行解对 $(x, y)$ 成立。若存在可行解使得等号成立（强对偶），则两者均达到最优。

diet problem（饮食问题）

最小化成本选择食物满足营养需求： $min \sum_{j} c_{j} x_{j} s.t. \sum_{j} a_{ij} x_{j} \geq b_{i}, x_{j} \geq 0$ 其中 $x_{j}$ 是食物 $j$ 的量， $c_{j}$ 是单价， $a_{ij}$ 是营养 $i$ 的含量， $b_{i}$ 是每日需求。

运输问题是 LP 的另一个经典例子：在多个供应点和多个需求点之间安排运输，使得总运输成本最小，同时满足供需约束。

2.2 二次规划（QP）

二次规划：

$min_{x} \frac{1}{2} x^{T} Q x + c^{T} x$ $s.t. A x \leq b$

当 $Q ⪰ 0$ （半正定）时，问题为凸二次规划，全局最优可达。

当 $Q$ 不定或负定时，问题是非凸的，可能存在多个局部最优。

等效于：最小二乘的正则化形式

$min_{x} ∥ A x - b ∥^{2} + λ ∥ x ∥^{2}$

展开后得到 $Q = 2 (A^{T} A + λ I) ⪰ 0$ ，故是凸 QP。

KKT条件简化（无不等式约束时）：

$\nabla f (x) = Q x + c = 0 \Rightarrow x^{*} = - Q^{- 1} c$

这是闭式解。但当 $Q$ 很大时，直接求逆 $O (n^{3})$ 代价过高，需要迭代方法。

活跃约束集法（Active Set Method）：QP 的经典求解方法。假设某些不等式约束在最优解处是紧的（活跃的），将它们转化为等式约束，然后求解。迭代地在活跃集上切换，直到找到最优解。

序列最小化规划（SMO）：SVM 训练中使用的特殊 QP 分解算法。将大的 QP 问题分解为一系列小的二变量 QP 子问题。

2.3 二阶锥规划（SOCP）

二阶锥规划（Second-Order Cone Programming）是 LP 和 QP 的推广：

$min_{x} f^{T} x$ $s.t. ∥ A_{i} x + b_{i} ∥_{2} \leq c_{i}^{T} x + d_{i}, i = 1, \dots, m$

二阶锥约束 $∥ A_{i} x + b_{i} ∥_{2} \leq c_{i}^{T} x + d_{i}$ 可以理解为在 $n + 1$ 维空间中的旋转二阶锥约束。

SOCP 包含的问题类型：

LP：令 $A_{i} = 0$ ， $c_{i}^{T} x + d_{i} \geq 0$ 退化为线性约束
QP：设 $A_{i} x + b_{i} = [Q^{1/2} x; 0]$ ， $c_{i}^{T} x + d_{i} = 0$ ，可转化
鲁棒 LP：不确定约束 $∥ \overset{ˉ}{A}_{i} x + \overset{ˉ}{b}_{i} ∥_{2} \leq \overset{c}{ˉ}_{i}^{T} x + \overset{ˉ}{d}_{i}$ 可以建模为 SOCP

应用场景：

金融中的均值-方差投资组合优化（最小化方差，受线性预算约束）
滤波器设计
天线阵列波束成形
鲁棒优化

2.4 半定规划（SDP）

半定规划（Semidefinite Programming）是向量空间到矩阵空间的推广：

$min_{X ⪰ 0} C ∙ X$ $s.t. A_{i} ∙ X = b_{i}, i = 1, \dots, m$

其中 $X ∙ Y = tr (X^{T} Y) = \sum_{ij} X_{ij} Y_{ij}$ 是 Frobenius 内积， $X ⪰ 0$ 表示 $X$ 是半正定矩阵。

SDP 与 SOCP 的关系：SOCP 是 SDP 的特例。实际上，二阶锥可以嵌入到半正定锥中： $∥ (u, v) ∥_{2} \leq t ⟺ (t u u^{T} t I) ⪰ 0$ 。

SDP 的应用：

组合优化松弛：MAX-CUT、图着色等问题可通过 SDP 松弛获得近似比保证（Goemans-Williamson 算法）。
控制理论：线性矩阵不等式（LMI）可转化为 SDP。
欧氏距离几何：传感器网络定位、蛋白质结构预测。
多项式优化：通过 Sum-of-Squares (SOS) 方法转化为 SDP。

Goemans-Williamson MAX-CUT 松弛

MAX-CUT 问题：将图的顶点划分为两部分，最大化cut边的数量。SDP 松弛为： $max \frac{1}{4} \sum_{ij} w_{ij} (1 - X_{ij})$ $s.t. X ⪰ 0, X_{ii} = 1$ Goemans 和 Williamson 证明：SDP 解的随机舍入给出 $0.878...$ 倍近似比（在某些条件下）。这是一个里程碑式的理论结果。

SDP 的求解：内点法可达 $O (n^{3.5})$ 复杂度，但直接内点法无法处理大规模问题。大规模 SDP 需要：

一阶方法：交替方向法（ADM）、增广拉格朗日法
图结构利用：稀疏 SDP、 Chordal 扩展
低秩结构：利用解的低秩表示

2.5 锥规划统一框架

LP、SOCP、SDP 都可以统一在锥规划的框架下：

$min_{x} c^{T} x$ $s.t. A x = b, x \in K$

其中 $K$ 是闭凸锥。取不同的锥得到不同的特例：

$K = R_{+}^{n}$ ：LP
$K = SOC^{n_{1} + 1} \times \dots \times SOC^{n_{m} + 1}$ ：SOCP
$K = S_{+}^{n}$ ：SDP

自对偶性：许多锥规划问题具有自对偶结构，这为设计算法提供了方便。

三、对偶理论与KKT条件

3.1 拉格朗日函数

考虑标准优化问题（原问题）：

$min_{x} f_{0} (x)$ $s.t. f_{i} (x) \leq 0, i = 1, \dots, m$ $h_{j} (x) = 0, j = 1, \dots, p$

其中 $f_{0} : R^{n} \to R$ 是目标函数， $f_{i}$ 是不等式约束， $h_{j}$ 是等式约束（通常约定 $h_{j}$ 为仿射函数）。

拉格朗日函数：

$L (x, λ, ν) = f_{0} (x) + \sum_{i = 1}^{m} λ_{i} f_{i} (x) + \sum_{j = 1}^{p} ν_{j} h_{j} (x)$

其中 $λ_{i} \geq 0$ （不等式约束的乘子）， $ν_{j}$ （等式约束的乘子，可以取任意符号）。

3.2 拉格朗日对偶函数

对偶函数定义为拉格朗日函数关于 $x$ 的下确界：

$g (λ, ν) = in f_{x \in D} L (x, λ, ν)$

其中 $D = ⋂_{i} dom (f_{i}) \cap ⋂_{j} dom (h_{j})$ 。

若 $L$ 关于 $x$ 无下界，则 $g (λ, ν) = - \infty$ 。

对偶函数的性质（弱对偶性）：

$g (λ, ν) \leq p^{*}, \forall λ \geq 0, \forall ν$

即对偶函数给出原问题最优值 $p^{*}$ 的下界。这个不等式的证明非常直接：对于任意原始可行解 $x$ ，由于 $λ_{i} \geq 0$ 和 $f_{i} (x) \leq 0$ ，有 $L (x, λ, ν) \leq f_{0} (x)$ ，取下确界即得 $g (λ, ν) \leq p^{*}$ 。

对偶函数的几何解释：对偶函数可以理解为一族参数化的线性下界函数的逐点上确界。拉格朗日乘子 $λ, ν$ 参数化了这些线性下界。

线性规划的对偶函数

原问题： $min c^{T} x s.t. A x = b, x \geq 0$ 对偶函数： $g (ν) = in f_{x \geq 0} {c^{T} x + ν^{T} (A x - b)} = in f_{x \geq 0} {(c + A^{T} ν)^{T} x} - b^{T} ν = {- b^{T} ν - \infty 若 c + A^{T} ν \geq 0 否则$ 因此对偶问题是 $max - b^{T} ν s.t. A^{T} ν \leq c$ ，与之前的标准形式一致。

3.3 对偶问题

对偶问题（拉格朗日对偶）：

$max_{λ, ν} g (λ, ν)$ $s.t. λ \geq 0$

对偶问题的最优值记为 $d^{*}$ ，恒有 $d^{*} \leq p^{*}$ （弱对偶性）。差值 $p^{*} - d^{*} \geq 0$ 称为对偶间隙（duality gap）。

强对偶性：在某些条件下， $d^{*} = p^{*}$ ，即对偶间隙为零。强对偶成立的充分条件包括：

Slater 条件（约束品性）：存在严格可行的 $x$ ，即对于凸问题（ $f_{i}$ 凸， $h_{j}$ 仿射）， $\exists x$ 使得 $f_{i} (x) < 0$ （而非 $\leq 0$ ）且 $A x = b$ 。对于非凸问题，Slater 条件也是充分条件（但那时我们称其为”广义 Slater 条件”）。
线性约束独立（LCQ）：等式约束 $h_{j}$ 线性且梯度线性无关。
Mangasarian-Fromovitz 约束规范（MFCQ）：比 Slater 条件更弱一些。

对偶定理：对于凸规划，当 Slater 条件满足时，强对偶性成立。这是凸优化的核心结果之一。

3.4 KKT条件

对于最优解 $x^{*}$ 和对偶变量 $λ^{*}, ν^{*}$ ，KKT条件为：

原始可行性： $f_{i} (x^{*}) \leq 0$ ， $h_{j} (x^{*}) = 0$
对偶可行性： $λ_{i}^{*} \geq 0$
互补松弛： $λ_{i}^{*} f_{i} (x^{*}) = 0$ （即每个乘子与其对应约束的乘积为零）
拉格朗日平稳性： $\nabla f_{0} (x^{*}) + \sum_{i} λ_{i}^{*} \nabla f_{i} (x^{*}) + \sum_{j} ν_{j}^{*} \nabla h_{j} (x^{*}) = 0$

KKT的意义

在强对偶性成立的条件下，KKT条件是 $x^{*}$ 为原问题最优解的充要条件。这使得我们可以将约束优化问题转化为解方程组。对于凸问题（且满足约束品性），KKT条件是最优性的充要条件；对于一般非凸问题，KKT条件是最优性的必要条件。

互补松弛的深入理解：对于每个不等式约束 $f_{i} (x) \leq 0$ ，有两种情况：

若 $f_{i} (x^{*}) < 0$ （约束未活跃），则 $λ_{i}^{*} = 0$ （乘子为零）
若 $λ_{i}^{*} > 0$ ，则 $f_{i} (x^{*}) = 0$ （约束在边界处）

这体现了”只对活跃约束付钱”的经济学直觉。

几何解释：在最优解处，梯度 $\nabla f_{0} (x^{*})$ 可以表示为约束梯度的非负线性组合（在仿射等式约束子空间内），且约束在边界处必须”夹住”梯度方向。

KKT条件应用：支持向量机

SVM 原问题： $min \frac{1}{2} ∥ w ∥^{2} s.t. y_{i} (w^{T} x_{i} + b) \geq 1$ KKT 条件给出 $\sum_{i} α_{i} y_{i} x_{i} = w$ （ $w$ 是支持向量的线性组合）， $\sum_{i} α_{i} y_{i} = 0$ （间隔约束的对偶约束），且 $α_{i} \geq 0$ ，互补松弛 $α_{i} (y_{i} (w^{T} x_{i} + b) - 1) = 0$ 。这导致稀疏解：只有支持向量（ $y_{i} (w^{T} x_{i} + b) = 1$ ）的 $α_{i} > 0$ ，其他 $α_{i} = 0$ 。

3.5 鞍点理论

(狭义) 鞍点（Saddle Point）：点 $(x^{*}, λ^{*}, ν^{*})$ 是 $L$ 的鞍点，当且仅当：

$\forall x : L (x^{*}, λ^{*}, ν^{*}) \leq L (x, λ^{*}, ν^{*})$ $\forall λ \geq 0, \forall ν : L (x^{*}, λ^{*}, ν^{*}) \geq L (x^{*}, λ, ν)$

鞍点与最优性： $(x^{*}, λ^{*}, ν^{*})$ 是拉格朗日函数鞍点的充要条件是：

$x^{*}$ 是原始可行解
$(λ^{*}, ν^{*})$ 是对偶可行解
原-对偶目标函数值相等（即 $f_{0} (x^{*}) = g (λ^{*}, ν^{*})$ ，对偶间隙为零）

因此，鞍点存在等价于强对偶性成立且存在最优解。

四、梯度下降与收敛性分析

4.1 梯度下降法

梯度下降是最基本的迭代优化方法：

$x_{k + 1} = x_{k} - η_{k} \nabla f (x_{k})$

其中 $η_{k} > 0$ 是步长（学习率）。

收敛性分析的基本假设：

Lipschitz连续梯度： $∥\nabla f (x) - \nabla f (y) ∥ \leq L ∥ x - y ∥$ ，即Hessian有界： $∥ \nabla^{2} f (x) ∥ \leq L$ （若 $f$ 二阶可微）
步长选择：固定步长 $η \leq \frac{1}{L}$ 或随迭代变化

梯度下降的一步分析：由 Taylor 展开和 Lipschitz 条件：

$f (x_{k + 1}) \leq f (x_{k}) + \nabla f (x_{k})^{T} (x_{k + 1} - x_{k}) + \frac{L}{2} ∥ x_{k + 1} - x_{k} ∥^{2} = f (x_{k}) - η (1 - \frac{L η}{2}) ∥\nabla f (x_{k}) ∥^{2}$

取 $η \leq 1/ L$ ，有 $f (x_{k + 1}) \leq f (x_{k}) - \frac{η}{2} ∥\nabla f (x_{k}) ∥^{2}$ ，故函数值单调下降。

4.2 凸函数的收敛率

一般凸函数（Lipschitz连续，步长 $η_{k} = \frac{∥ x _{0} - x ^{*} ∥}{L k + 1}$ ）：

$f (x_{k}) - f (x^{*}) \leq \frac{L ∥ x _{0} - x ^{*} ∥ ^{2}}{2 k + 1} = O (\frac{1}{k})$

对于凸函数， $O (1/ k)$ 是梯度方法能达到的最优收敛率（复杂度下界为 $Ω (1/ k^{2})$ ？——不对，这是 Nesterov 加速后的结果，无加速的下界是 $Ω (1/ k)$ ）。

强凸函数：设 $f$ $μ$ -强凸，即 $f (x) - \frac{μ}{2} ∥ x ∥^{2}$ 是凸的。强凸性意味着函数”下有二次下界”：

$f (y) \geq f (x) + \nabla f (x)^{T} (y - x) + \frac{μ}{2} ∥ y - x ∥^{2}$

取 $η = 1/ L$ ，则：

$f (x_{k}) - f (x^{*}) \leq (1 - \frac{μ}{L})^{k} (f (x_{0}) - f (x^{*}))$

收敛率为 $O ((1 - \frac{μ}{L})^{k})$ ，即线性收敛（每一步误差乘以一个小于1的常数因子）。这意味着为达到 $ϵ$ 精度，需要 $O (lo g (1/ ϵ))$ 次迭代。

条件数的影响

收敛速度依赖于条件数 $κ = L / μ$ 。条件数越大，收敛越慢。这解释了为什么预处理（preconditioning）可以加速优化——通过改善条件数来加速收敛。

收敛率总结：

函数类型	假设	收敛率	迭代复杂度
一般凸	Lipschitz $L$	$O (1/ k)$	$O (1/ ϵ^{2})$
凸 + 平滑	Lipschitz $L$	$O (1/ k)$	$O (1/ ϵ)$
强凸 + 平滑	$μ$ -强凸, Lipschitz $L$	$O ((1 - μ / L)^{k})$	$O (κ lo g (1/ ϵ))$
强凸 + 平滑 + 加速	Nesterov	$O (1/ k^{2})$	$O (1/ ϵ)$

4.3 非凸函数的收敛性

对于非凸函数，梯度下降保证：

梯度范数收敛到0： $∥\nabla f (x_{k}) ∥ \to 0$
收敛到稳定点（梯度为零的点），不一定是全局最优

在深度学习中，损失函数是非凸的，但梯度下降（配合 SGD）仍能有效找到好的局部最优解。实践中发现，这些局部最优解往往接近全局最优——可能因为在高维空间中，局部最优和全局最优的函数值差距不大（参见 Choromanska et al. 2015 的理论分析）。

非凸优化的挑战：

可能收敛到鞍点而非局部极小
存在”坏”局部最优，其函数值远高于全局最优
景观（landscape）可能非常复杂

逃离鞍点：使用随机梯度下降（SGD）的噪声可以帮助逃离鞍点。也有方法主动处理鞍点，如带有扰动的梯度下降。

4.4 随机梯度下降（SGD）

当目标函数是有限和问题 $f (x) = \frac{1}{n} \sum_{i = 1}^{n} f_{i} (x)$ 时，计算全梯度 $\nabla f (x) = \frac{1}{n} \sum_{i} \nabla f_{i} (x)$ 代价高昂（ $O (n)$ ）。SGD 在每步只使用一个（或一小批）样本的梯度：

$x_{k + 1} = x_{k} - η_{k} g (x_{k}, ξ_{k})$

其中 $g (x, ξ)$ 是基于随机样本 $ξ_{k}$ 的梯度估计，满足 $E [g (x, ξ)] = \nabla f (x)$ 。

收敛性：SGD 在适当步长衰减策略下可以达到 $O (1/ k)$ 的收敛率（与非凸 GD 类似）。对于强凸函数，SGD 可达到 $O (1/ k)$ （统计学习率）。

五、一阶优化方法

5.1 动量法与Nesterov加速

动量法（Momentum）累积历史梯度方向，加速收敛并减少震荡：

$v_{k + 1} = β v_{k} + \nabla f (x_{k})$ $x_{k + 1} = x_{k} - η v_{k + 1}$

直观理解：动量项使得更新方向包含了过去梯度的指数加权平均，从而在高曲率方向抑制震荡，在低曲率方向加速。

Nesterov 动量（Nesterov Accelerated Gradient, NAG）更激进，先”看”一步的方向再校正：

$v_{k + 1} = β v_{k} + \nabla f (x_{k} - η β v_{k})$ $x_{k + 1} = x_{k} - η v_{k + 1}$

等价形式（使用”速度” $y_{k} = x_{k} + β^{k} (x_{k} - x_{k - 1})$ 的表述）：

$y_{k + 1} = x_{k} - η \nabla f (x_{k} + β_{k} (x_{k} - x_{k - 1}))$ $x_{k + 1} = y_{k + 1} + \frac{k - 1}{k + 2} (y_{k + 1} - y_{k})$

Nesterov 加速梯度（NAG）的收敛率：

强凸函数： $O ((1 - 1/ κ)^{k})$ ，显著优于标准 GD 的 $O ((1 - 1/ κ)^{k})$ （线性收敛，但常数更优）
一般凸函数： $O (1/ k^{2})$ ，优于标准 GD 的 $O (1/ k)$

Nesterov 加速的直观理解

想象一个小球从山坡滚下。普通梯度下降每次只看当前坡度，而 Nesterov 先借助动量”预测”未来位置，然后在那里看坡度，相当于”向前看”。这使得小球在下坡时更快，在上坡时及时减速。

5.2 自适应学习率方法

AdaGrad（Adaptive Subgradient）：

$g_{k} = \nabla f (x_{k})$ $G_{k} = G_{k - 1} + g_{k} ⊙ g_{k}$ $x_{k + 1} = x_{k + 1} - \frac{η}{G _{k} + ϵ} ⊙ g_{k}$

AdaGrad 对稀疏特征有优势，因为更新会除以历史梯度平方和的平方根。但问题是 $G_{k}$ 随 $k$ 单调增长，导致学习率不断衰减。

RMSProp：引入指数加权移动平均来解决 AdaGrad 的问题：

$G_{k} = β G_{k - 1} + (1 - β) g_{k} ⊙ g_{k}$ $x_{k + 1} = x_{k + 1} - \frac{η}{G _{k} + ϵ} ⊙ g_{k}$

Adam（Adaptive Moment Estimation）结合了动量和自适应学习率：

$m_{k} = β_{1} m_{k - 1} + (1 - β_{1}) \nabla f (x_{k}) （一阶矩，带指数衰减）$ $v_{k} = β_{2} v_{k - 1} + (1 - β_{2}) (\nabla f (x_{k}))^{2} （二阶矩，带指数衰减）$ $\overset{m}{^}_{k} = \frac{m _{k}}{1 - β _{1}^{k}}, \overset{v}{^}_{k} = \frac{v _{k}}{1 - β _{2}^{k}} （偏差校正）$ $x_{k + 1} = x_{k} - η \frac{m ^ _{k}}{v ^ _{k} + ϵ}$

Adam 自动调整每个参数的学习率，在实践中效果极佳，是深度学习的主流优化器之一。但 Adam 也有缺陷（如可能不收敛，泛化性能不如 SGD 等），AdaBound、LAMB 等变体尝试改进。

5.3 近端梯度法

近端算子（Proximal Operator）：对于函数 $h$ （可能是非光滑的），其近端算子定义为：

$prox_{τ h} (x) = ar g min_{y} {h (y) + \frac{1}{2 τ} ∥ y - x ∥^{2}}$

近端算子可以理解为”软阈值”操作的推广。

近端梯度法（Proximal Gradient Method, PGM）处理复合目标函数：

$min_{x} f (x) + h (x)$

其中 $f$ 光滑（可微）， $h$ 可能是非光滑的凸函数（如 $L_{1}$ 范数）。

迭代格式：

$x_{k + 1} = prox_{τ h} (x_{k} - τ \nabla f (x_{k}))$

ISTA（Iterative Shrinkage-Thresholding Algorithm）是 PGM 的一个特例，用于 LASSO：

$prox_{τ ∥ \cdot ∥_{1}} (x) = soft (x, τ) = sign (x) ⊙ max (∣ x ∣ - τ, 0)$

FISTA（Fast ISTA）：Nesterov 加速版本的 ISTA，达到 $O (1/ k^{2})$ 收敛率。

5.4 交替方向乘子法（ADMM）

ADMM（Alternating Direction Method of Multipliers）用于分布式凸优化，是大尺度问题的主流方法。

考虑问题：

$min f (x) + g (z)$ $s.t. A x + B z = c$

增广拉格朗日：

$L_{ρ} (x, z, y) = f (x) + g (z) + y^{T} (A x + B z - c) + \frac{ρ}{2} ∥ A x + B z - c ∥^{2}$

ADMM 交替最小化 $x$ 和 $z$ ：

$x^{k + 1} = ar g min_{x} L_{ρ} (x, z^{k}, y^{k})$ $z^{k + 1} = ar g min_{z} L_{ρ} (x^{k + 1}, z, y^{k})$ $y^{k + 1} = y^{k} + ρ (A x^{k + 1} + B z^{k + 1} - c)$

收敛性：ADMM 在适当条件下以 $O (1/ k)$ 速率收敛到原始-对偶最优解。对于强凸函数，收敛率可提升为线性。

分布式实现：ADMM 的天然优势是可以分布式执行。目标函数 $f (x) = \sum_{i = 1}^{n} f_{i} (x_{i})$ 可以每个节点独立计算 $x_{i}$ 的更新，仅通过一致性约束 $x_{i} = x_{j}$ 进行协调。这使得 ADMM 非常适合 MapReduce 或 parameter-server 架构。

5.5 镜像下降（Mirror Descent）

镜像下降通过 Bregman 散度而非欧氏距离来测量步长：

$x_{k + 1} = ar g min_{x} {⟨ \nabla f (x_{k}), x ⟩ + \frac{1}{η} D_{ϕ} (x, x_{k})}$

其中 $D_{ϕ} (x, y) = ϕ (x) - ϕ (y) - ⟨ \nabla ϕ (y), x - y ⟩$ 是由凸函数 $ϕ$ 定义的 Bregman 散度。

特殊情形：

$ϕ (x) = \frac{1}{2} ∥ x ∥_{2}^{2}$ ： $D_{ϕ}$ 是欧氏距离，镜像下降退化为标准梯度下降。
$ϕ (x) = ∥ x ∥_{1}$ ：产生类似于 AdaGrad 的自适应学习率行为。

六、二阶优化方法

6.1 牛顿法

牛顿法：

$x_{k + 1} = x_{k} - (\nabla^{2} f (x_{k}))^{- 1} \nabla f (x_{k})$

牛顿法的收敛率：对于强凸函数，达到 $O (e^{- c k^{2}})$ （二次收敛），远超线性收敛。二次收敛意味着每一步有效数字位数大约翻倍。

几何直觉：牛顿法不是沿梯度方向走固定步长，而是将目标函数在当前点二阶近似（用 Hessian 作为曲率信息），然后跳到二次近似的最小点。

但牛顿法的问题：

需要计算 Hessian 矩阵（ $O (n^{2})$ 存储）
需要求解 Hessian 线性系统 $(\nabla^{2} f)^{- 1} \nabla f$ （ $O (n^{3})$ 计算，若用直接法）
Hessian 可能不正定（对于非凸问题）

阻尼牛顿法与信赖域法：为保证收敛，可以加入步长控制（阻尼牛顿）或信赖域约束（限制步长范围）。

信赖域法（Trust Region Method）：

$min_{m} f (x_{k}) + \nabla f (x_{k})^{T} p + \frac{1}{2} p^{T} B_{k} p s.t. ∥ p ∥ \leq Δ_{k}$

其中 $B_{k} \approx \nabla^{2} f (x_{k})$ ， $Δ_{k}$ 是信赖域半径。相对于线搜索方法，信赖域法在处理非凸问题时更稳定。

6.2 拟牛顿法

拟牛顿法用低秩矩阵逼近 Hessian 或其逆，避免直接计算 Hessian。

BFGS（Broyden-Fletcher-Goldfarb-Shanno）直接逼近 Hessian：

$B_{k + 1} = B_{k} + \frac{y _{k} y _{k}^{T}}{y _{k}^{T} s _{k}} - \frac{B _{k} s _{k} s _{k}^{T} B _{k}}{s _{k}^{T} B _{k} s _{k}}$

其中 $s_{k} = x_{k + 1} - x_{k}$ ， $y_{k} = \nabla f (x_{k + 1}) - \nabla f (x_{k})$ 。

Sherman-Morrison 公式使 BFGS 可以 $O (n^{2})$ 更新（而非 $O (n^{3})$ 求逆）：

$H_{k + 1} = H_{k} + \frac{s _{k} s _{k}^{T}}{y _{k}^{T} s _{k}} - \frac{H _{k} y _{k} y _{k}^{T} H _{k}}{y _{k}^{T} H _{k} y _{k}}$

其中 $H_{k} = B_{k}^{- 1}$ 。

L-BFGS（Limited-memory BFGS）：只存储最近 $m$ 对 $(s_{i}, y_{i})$ ，逼近 $H_{k}$ 通过这些历史信息，达到 $O (mn)$ 存储（而非 $O (n^{2})$ ）。

OWL-QN（Orthant-Wise Limited-memory Quasi-Newton）：用于 $L_{1}$ 正则化问题，结合 L-BFGS 和正交象限优化。

6.3 牛顿法的实际考量

Hessian-vector 积：在深度学习中，直接计算完整的 Hessian 矩阵不可行，但可以高效计算 Hessian-vector 积： $\nabla^{2} f (x) v$ 通过反向传播两次即可得到（利用雅可比链式法则）。这使得共轭梯度法（CG）可以用于求解牛顿步长 $H_{k}^{- 1} g_{k}$ ：

$H_{k} p_{k} = - g_{k}$

共轭梯度法在 $m$ 步内（在 $H_{k}$ 特征值分布良好的假设下）给出 $m$ 维 Krylov 子空间中的最优解，且无需显式构造 $H_{k}$ 。

自然梯度（Natural Gradient）：在黎曼流形上，牛顿方向对应于在黎曼度量下的最速下降方向。在概率分布空间（由 Fisher 信息矩阵定义黎曼度量），自然梯度方法具有更好的理论性质。Natural Evolution Strategies (NES) 和 Natural Gradient Policy Gradient 等方法体现了这一思想。

七、约束优化的投影方法

7.1 投影梯度法

投影梯度法：

$x_{k + 1} = Proj_{C} (x_{k} - η_{k} \nabla f (x_{k}))$

其中 $Proj_{C} (x) = ar g min_{y \in C} ∥ x - y ∥$ 是到凸集 $C$ 的投影。

投影是度量空间中最近点映射（metric projection），对于闭凸集 $C$ ，投影算子存在且唯一。

投影的性质：

$⟨ x - Proj_{C} (x), y - Proj_{C} (x)⟩ \leq 0, \forall y \in C$

这称为投影定理，等价于变分不等式。

对于简单约束（如箱约束 $x \in [l, u]$ ），投影有闭式解：

$Proj_{[l, u]} (x)_{i} = min (max (x_{i}, l_{i}), u_{i})$

对于球约束 $∥ x ∥_{2} \leq R$ ，投影为 $\frac{R}{m a x ( ∥ x ∥ _{2} , R )} x$ 。

收敛性：对于凸集上的凸函数，投影梯度法达到 $O (1/ k)$ 收敛率（无加速）或 $O (1/ k^{2})$ （Nesterov 加速版本）。

7.2 Frank-Wolfe算法

Frank-Wolfe算法（也称条件梯度法）是处理线性约束凸优化问题的投影自由方法：

初始化： $x_{0} \in D$ （可行域内）

迭代：

线性最小化子问题：求解 $s_{k} = ar g min_{s \in D} \nabla f (x_{k})^{T} s$
步长计算： $γ_{k} = \frac{2}{k + 2}$ （或线搜索）
更新： $x_{k + 1} = (1 - γ_{k}) x_{k} + γ_{k} s_{k}$

Frank-Wolfe 的优势：

投影自由：只需解决线性最小化，而非投影到复杂集合
当 $D$ 是多面体时，线性最小化可能比投影更高效
稀疏解：解天然是原子的凸组合（原子分解）
存储优势：只需存储当前解 $x_{k}$ ，不需要投影算子

Frank-Wolfe 的劣势：

收敛速度较慢： $O (1/ k)$ 而非 $O (1/ k^{2})$
对于非多面体约束集合，线性最小化可能仍困难
收敛到解的边界（可能导致数值不稳定）

SVM与Frank-Wolfe

支持向量机的对偶问题 $max_{α} \sum_{i} α_{i} - \frac{1}{2} α^{T} Y X X^{T} Y α s.t. α \geq 0, y^{T} α = 0$ 可以用 Frank-Wolfe 求解。线性最小化子问题退化为寻找支持向量，复杂度与活跃约束数成正比。

7.3 条件梯度滑动（Conditional Gradient Sliding）

条件梯度滑动（CGS）结合了 Frank-Wolfe 与 Nesterov 加速的思想：

$\tilde{x}_{k} = (1 - θ_{k}) x_{k - 1} + θ_{k} y_{k - 1}$ $y_{k} = ar g min_{y \in D} ⟨ \nabla f (\tilde{x}_{k}), y ⟩$ $x_{k} = 弗兰克 - 沃尔夫步$

通过使用梯度评估次数来衡量复杂度，CGS 在光滑凸优化上达到了最优的复杂度 $O (min {n, 1/ ϵ})$ （其中 $n$ 是维度， $ϵ$ 是精度）。这里的”滑动”体现在解在两步之间平滑移动。

7.4 增广拉格朗日法

增广拉格朗日（Augmented Lagrangian）通过在拉格朗日函数中加入惩罚项来改善对偶函数的曲率：

$L_{ρ} (x, λ) = f_{0} (x) + \sum_{i} λ_{i} f_{i} (x) + \sum_{j} ν_{j} h_{j} (x) + \frac{ρ}{2} \sum_{j} h_{j} (x)^{2}$

二次惩罚项 $\frac{ρ}{2} h_{j} (x)^{2}$ 改善了拉格朗日函数的 Hessian 条件数，使得对偶变量的更新更容易收敛。

ADMM 是增广拉格朗日法的多块推广，已经在第五章讨论。

八、凸优化的计算复杂性

8.1 问题复杂度分类

在理论计算机科学中，优化问题按照其计算难度分为多个类别：

问题类型	示例	多项式时间算法？
P	线性规划、二次规划	是（内点法）
NP-hard	整数规划、组合优化	否（除非 P=NP）
平滑凸优化	Lipschitz 凸函数	是（一阶方法）
一阶 oracle	光滑凸函数	是（梯度法）

一阶 oracle 模型：算法只能通过 oracle 查询（函数值、梯度等）来获取信息，不利用问题的代数结构。

复杂度下界：在一阶 oracle 模型下，光滑凸函数的收敛率下界为 $O (1/ k^{2})$ ，Nesterov 加速梯度达到了这个下界（因而是最优的）。这称为最优一阶方法（optimal first-order method）。

8.2 局部最优与全局最优

非凸优化的现状：在实际机器学习中，绝大多数问题是非凸的（神经网络、协同过滤、围棋等）。但”局部最优即全局最优”的好消息是：

过参数化网络：在过度参数化的神经网络中，梯度下降可以收敛到全局最优（参见 Allen-Zhu, Song 等人 2018-2019 的工作）。
矩阵补全：在 RIP (Restricted Isometry Property) 条件下，可证明不存在”坏”的局部最优。
相位恢复：在 Generic 条件下，损失函数 landscape 的局部最优都是全局最优。

鞍点问题：在高维非凸优化中，鞍点比局部极小更常见（根据随机矩阵理论，Hessian 的负特征值期望约为维度的一半）。逃离鞍点可以通过：

随机扰动
带有噪声的梯度下降（SGD 的隐式正则化效应）
曲率信息（使用 Hessian-vector 积）

8.3 零阶优化

零阶优化（Zero-order Optimization）仅使用函数值 $f (x)$ 来优化，不依赖梯度信息。当梯度不可得时（如模拟优化、超参数调优、黑盒系统）这是唯一选择。

随机估计梯度：

$\overset{g}{^} (x) = \frac{f ( x + ϵ u ) - f ( x )}{ϵ} u$

其中 $u$ 是均匀分布在单位球面上的随机方向。这是一个无偏的梯度估计（ $O (ϵ^{2})$ 偏差）。

坐标采样：在离散决策空间（如神经网络架构搜索）中，可以随机采样有限个子方向进行评估。

零阶方法由于信息利用率极低，收敛速度远慢于一阶和二阶方法，复杂度差距可达 $O (d)$ 倍（ $d$ 是维度）。

九、应用专题

9.1 机器学习中的凸优化

支持向量机（SVM）： $min \frac{1}{2} ∥ w ∥^{2} + C \sum_{i} ξ_{i} s.t. y_{i} (w^{T} x_{i} + b) \geq 1 - ξ_{i}, ξ_{i} \geq 0$ ，这是一个凸 QP。

逻辑回归： $min - \sum_{i} [y_{i} lo g σ (w^{T} x_{i}) + (1 - y_{i}) lo g (1 - σ (w^{T} x_{i}))] + \frac{λ}{2} ∥ w ∥^{2}$ ，凸优化（目标函数是凸的， $L_{2}$ 正则是凸的）。

LASSO（Least Absolute Shrinkage and Selection Operator）： $min \frac{1}{2} ∥ A x - b ∥_{2}^{2} + λ ∥ x ∥_{1}$ ，其中 $L_{1}$ 正则项促进稀疏解。使用近端梯度法（如 ISTA/FISTA）高效求解。

K-means 聚类： $k$ -means 目标函数 $min \sum_{i = 1}^{n} min_{c_{j}} ∥ x_{i} - c_{j} ∥^{2}$ 不是凸的，但 Lloyd 算法是实践中有效的启发式算法。

主成分分析（PCA）： $max_{W^{T} W = I} tr (W^{T} X^{T} X W)$ 等价于 $min ∥ X - W W^{T} X ∥_{F}^{2}$ ，是半正定规划（SDP），虽然非凸但所有局部最优都是全局最优。

9.2 控制理论中的凸优化

线性矩阵不等式（LMI）： $F (x) = F_{0} + \sum_{i = 1}^{m} x_{i} F_{i} ⪰ 0$ 定义了凸约束。LMI 出现在 Lyapunov 稳定性分析、 $H_{2} / H_{\infty}$ 控制、状态估计等问题中。

模型预测控制（MPC）：在约束 MPC 中，每个控制步需要求解一个有限时域优化问题：

$min_{u} \sum_{k = 0}^{N - 1} (x_{k}^{T} Q x_{k} + u_{k}^{T} R u_{k}) + x_{N}^{T} P x_{N}$ $s.t. x_{k + 1} = A x_{k} + B u_{k}, x_{k} \in X, u_{k} \in U$

当 $N$ 较大或控制频率高时，快速求解是挑战。凸优化与定制内点法、fast MPC 是核心工具。

9.3 信号处理中的凸优化

压缩感知（Compressed Sensing）：信号恢复问题 $min ∥ x ∥_{1} s.t. ∥ A x - b ∥_{2} \leq ϵ$ ，在 RIP 条件下， $L_{1}$ 最小化可以精确恢复稀疏信号。

去噪：TV（Total Variation）去噪 $min \frac{1}{2} ∥ x - x_{0} ∥_{2}^{2} + λ ∥\nabla x ∥_{1}$ ，利用图像的梯度稀疏性进行去噪。

矩阵补全： $min ∥ X ∥_{*} s.t. ∥ P_{Ω} (X - M) ∥_{F} \leq ϵ$ ，其中 $∥ X ∥_{*}$ 是核范数（奇异值之和），促进低秩解。应用于推荐系统（协同过滤）、相位恢复、鲁棒 PCA 等。

9.4 博弈论与凸优化

二人零和博弈与线性规划：给定支付矩阵 $A$ ，Player 1 的最优混合策略 $max_{x} min_{y} x^{T} A y = min_{y} max_{x} x^{T} A y$ ，可以通过 LP 求解。

纳什均衡：有限策略空间下的二人零和博弈的纳什均衡等价于一个 LP。多人非合作博弈的均衡计算通常是非凸的，但贸易市场等特殊博弈结构可以转化为凸优化。

社会福利最大化：在市场出清价格计算中，求解竞争均衡可以转化为一个凸优化问题（最大 GDP 等目标）。

十、算法实现细节与数值稳定性

10.1 线搜索与步长选择

Armijo 条件（充分下降条件）：

$f (x_{k} + α_{k} p_{k}) \leq f (x_{k}) + c_{1} α_{k} \nabla f (x_{k})^{T} p_{k}$

其中 $p_{k}$ 是搜索方向， $c_{1} \in (0, 1)$ （通常 $c_{1} = 1 0^{- 4}$ ）。

曲率条件（Wolfe 条件）：

$\nabla f (x_{k} + α_{k} p_{k})^{T} p_{k} \geq c_{2} \nabla f (x_{k})^{T} p_{k}$

其中 $c_{2} \in (c_{1}, 1)$ （通常 $c_{2} = 0.9$ ）。

Armijo 条件保证足够下降，Wolfe 条件避免步长过小。结合两者即为 Wolfe 线搜索。

回溯线搜索：从较大的步长 $α = \overset{α}{ˉ}$ 开始，若不满足 Armijo 条件则按比例缩小 $α \leftarrow ρ α$ （ $ρ \in (0, 1)$ ，如 $ρ = 0.5$ ）。

10.2 数值稳定性的实践考量

病态问题：当 Hessian 条件数 $κ$ 很大时，梯度下降收敛极慢。预处理（Preconditioning）通过变换变量 $z = P^{1/2} x$ 来改善条件数。

NaN/Inf 处理：在高曲率区域，梯度可能极大或极小。使用梯度裁剪（gradient clipping）、学习率衰减、数值稳定公式（对 $e^{x}$ 等使用 safe 版本）是常见实践。

双精度 vs 单精度：深度学习中常用单精度（FP32）甚至混合精度（FP16/BF16），但凸优化求解器通常需要双精度以避免累积误差。

10.3 大规模问题的策略

坐标下降：当目标函数在某个坐标方向上”解耦”时，坐标下降可以非常高效。
随机化：使用随机采样来近似梯度（适用于有限和目标）。
分布式优化：ADMM、一致性优化（consensus optimization）、联邦学习中的凸聚合。
二阶信息的低秩近似：利用 Kronecker 结构、Hessian-free 优化、Krylov 子空间方法。

十一、算法选择指南

11.1 问题类型与推荐算法

场景	推荐算法
小规模光滑无约束	牛顿法、BFGS、L-BFGS
中等规模凸问题	内点法、SCS、OSQP
大规模光滑无约束	L-BFGS、Nesterov 加速梯度
大规模稀疏约束	Frank-Wolfe、随机方法
包含 $L_{1}$ 正则	ISTA/FISTA、近端梯度法
分布式/联邦学习	ADMM、Gradient Descent/ADMM
实时控制	定制内点法、fast MPC
黑盒/仿真优化	零阶方法、贝叶斯优化

11.2 编程工具生态

Python：

scipy.optimize：提供了 SLSQP（序列最小二乘规划）、COBYLA 等约束优化算法。
cvxpy：优雅的凸优化建模语言，支持 LP、QP、SOCP、SDP，自动选择求解器。
osqp、ecos、scs：高效的一阶 SDP/QP 求解器。
mosek、gurobipy、cplex：商业求解器，适合大规模 LP/QP/SOCP/SDP。

MATLAB：

fmincon：通用约束优化（序列二次规划 SQP 是默认算法）。
linprog、quadprog、semidefinite：针对特定问题类型的求解器。
CVX：最流行的凸优化建模工具之一（由 Stanford 的 Grant 和 Boyd 开发）。

Julia：

JuMP：类似 cvxpy 的建模语言，支持多种求解器后端。
Convex.jl：专门面向凸优化。
ProximalAlgorithms.jl：近端算法框架。

十二、历史注记与延伸阅读

12.1 发展简史

1947：Dantzig 提出单纯形法，线性规划进入可计算时代。
1948：von Neumann 提出对偶理论。
1963：Dantzig 和 Wolfe 提出分解原理，处理大规模 LP。
1967：Kuhn 和 Tucker 提出 KKT 条件（实际上 Karush 1939 年已在硕士论文中给出）。
1979：Khachiyan 的椭球法首次证明 LP 的多项式时间可解性。
1984：Karmarkar 的内点法给出比椭球法更实用的多项式时间算法，掀起内点法革命。
1988：Nesterov 提出加速梯度法，达到 $O (1/ k^{2})$ 最优收敛率。
1990s：二阶锥规划和半定规划的内点法成熟。
2000s：伴随机器学习和大数据的兴起，一阶方法（随机优化、近端方法、ADMM）成为大规模问题的主流。
2010s：深度学习优化（Adam、AdamW、LAMB 等自适应方法的广泛使用）。

12.2 经典教材

Boyd & Vandenberghe (2004). Convex Optimization. Cambridge University Press. —— 入门必读，覆盖全面，配套公开课。
Nesterov (2018). Lectures on Convex Optimization (2nd ed.). Springer. —— 深入理论，最优算法设计的权威著作。
Bertsekas (1999). Nonlinear Programming (2nd ed.). Athena Scientific. —— 非线性规划的百科全书。
Rockafellar (1970). Convex Analysis. Princeton University Press. —— 凸分析的数学基础。
Bottou, Curtis & Nocedal (2018). Optimization Methods for Large-Scale Machine Learning. SIAM Review. —— 现代大规模优化的综述。
Nocedal & Wright (2006). Numerical Optimization (2nd ed.). Springer. —— 数值优化的经典教材。

十三、典型习题

习题 1：凸集判定

判断下列集合是否为凸集，并说明理由：

${x \in R^{n} : ∥ x ∥_{1} \leq 1}$ （ $L_{1}$ 范数单位球）

${x \in R^{n} : ∥ x ∥_{0} \leq k}$ （稀疏集合， $L_{0}$ “范数”不超过 $k$ ）

${x \in R^{n} : \prod_{i} x_{i} \geq c, x_{i} > 0}$ （正象限的等积区域）

答案：1 是凸的（ $L_{1}$ 球是多面体）；2 不是凸的（稀疏约束不是凸的）；3 是凸的（因为对数化后为仿射约束 $\sum_{i} lo g x_{i} \geq lo g c$ ， $lo g$ 是凹函数， $\geq$ 凹函数定义的是凸集）。

习题 2：共轭函数

求函数 $f (x) = \frac{1}{2} x^{T} Q x$ （ $Q ≻ 0$ ）的 Fenchel 共轭 $f^{*} (y)$ 。

答案： $f^{*} (y) = \frac{1}{2} y^{T} Q^{- 1} y$ 。由驻点条件 $\nabla_{x} (y^{T} x - \frac{1}{2} x^{T} Q x) = y - Q x = 0$ 得 $x = Q^{- 1} y$ ，代入即得。

习题 3：KKT条件应用

用 KKT 条件求以下问题的最优解： $min x_{1}^{2} + x_{2}^{2}$ $s.t. x_{1} + x_{2} = 1$

答案：引入乘子 $ν$ ，拉格朗日 $L = x_{1}^{2} + x_{2}^{2} + ν (x_{1} + x_{2} - 1)$ 。平稳性： $2 x_{1} + ν = 0$ ， $2 x_{2} + ν = 0$ 。结合约束 $x_{1} + x_{2} = 1$ ，解得 $x_{1} = x_{2} = 1/2$ ， $ν = - 1$ 。最优值 $f^{*} = 1/2$ 。

习题 4：收敛率推导

设 $f$ 为 $μ$ -强凸且 $L$ -Lipschitz 连续梯度。证明梯度下降法在步长 $η = 1/ L$ 下满足： $f (x_{k}) - f (x^{*}) \leq (1 - \frac{μ}{L})^{k} (f (x_{0}) - f (x^{*}))$

提示：使用强凸性 $f (y) \geq f (x) + \nabla f (x)^{T} (y - x) + \frac{μ}{2} ∥ y - x ∥^{2}$ 和 Lipschitz 条件，结合 $x_{k + 1} = x_{k} - \frac{1}{L} \nabla f (x_{k})$ 。

习题 5：ADMM 分布式实现

考虑分布式优化问题 $min \sum_{i = 1}^{n} f_{i} (x)$ （每个 $f_{i}$ 在节点 $i$ 上计算），使用 ADMM 的一致性（consensus）形式。写出分布式更新规则，并说明如何通过消息传递实现。

习题 6：SVM 的对偶推导

从 SVM 原问题 $min \frac{1}{2} ∥ w ∥^{2} + C \sum_{i} ξ_{i} s.t. y_{i} (w^{T} x_{i} + b) \geq 1 - ξ_{i}, ξ_{i} \geq 0$ 推导出其对偶问题，并说明支持向量的几何意义。

十四、进阶专题预告

以下专题因篇幅所限未能详述，列出供进一步研究：

锥规划的内点法：自步 барьер 函数到预测-校正方法，再到专为 SDP 设计的求解器结构。
凸优化的随机近似（SVRG、SAGA、Finito）：方差缩减技术如何帮助 SGD 类方法在有限和问题中达到线性收敛。
分散式凸优化：一致性（consensus）方法、交换-平均（exchange-average）方法、联邦学习中的通信压缩。
鲁棒优化：椭球不确定性集下的 min-max 优化与 SDP 松弛。
割平面法（Cutting Plane Methods）：Delunay 割平面、Kelley’s 方法、Bundle 方法（用于非光滑凸优化）。
机会约束规划（Chance-Constrained Programming）：概率约束下的凸优化。
单调算子与分裂方法：Douglas-Rachford 分割、Primal-Dual 混合梯度（PDHG）。
非凸优化的松弛与近似：《Beyond Convex》——流形优化、矩阵完备化的凸松弛近似比分析。

十五、线性规划的深入专题

15.1 单纯形法的几何与代数

单纯形法的代数框架：将标准形 LP $min c^{T} x s.t. A x = b, x \geq 0$ 的可行域视为多面体。基变量集合 $B$ （大小为 $m$ ）对应一组线性无关列向量 $A_{B}$ ，基矩阵 $B = A_{B}$ ，非基矩阵 $N = A_{N}$ 。

基本可行解（Basic Feasible Solution, BFS）：对于基 $B$ ，设 $x_{B} = B^{- 1} b \geq 0$ ， $x_{N} = 0$ ，则 $x$ 是 BFS。BFS 对应多面体的一个顶点（极点）。

最优性检验：对于基 $B$ ，简约成本 $\overset{c}{ˉ}_{j} = c_{j} - c_{B}^{T} B^{- 1} A_{j}$ 。若所有 $\overset{c}{ˉ}_{j} \geq 0$ ，则当前 BFS 是最优解。

出基/入基规则（Bland 规则避免循环）：选择最小的 $\overset{c}{ˉ}_{j} < 0$ 作为入基变量（消除循环），出基变量由最小比值规则 $min_{i : \overset{a}{ˉ}_{ik} > 0} b_{i} / \overset{a}{ˉ}_{ik}$ 决定。

单纯形法两步走

LP: $min - 2 x_{1} - 3 x_{2} s.t. x_{1} + x_{2} \leq 4, x_{1} + 2 x_{2} \leq 6, x_{1}, x_{2} \geq 0$ 引入松弛变量 $x_{3}, x_{4}$ ，得到标准形。初始基 ${3, 4}$ ， $b = [4, 6]^{T}$ ， $c = [- 2, - 3, 0, 0]^{T}$ 。 $B^{- 1} A$ 和 $B^{- 1} b$ 构成单纯形表。 $\overset{c}{ˉ}_{1} = - 2 - [0, 0]^{T} [1, 1]^{T} = - 2 < 0$ ， $x_{1}$ 入基。比值 $min (4/1, 6/1) = 4$ ， $x_{3}$ 出基。迭代直到所有简约成本非负。

15.2 内点法的完整推导

障碍函数法（Barrier Method）：在原问题中加入对数障碍项，将约束内化：

$min_{x} f_{0} (x) - \frac{1}{t} \sum_{i} lo g (- f_{i} (x))$

当 $t \to \infty$ 时，障碍函数的极小点趋近于原始问题的最优解。

中心路径（Central Path）：随着 $t$ 增大，障碍问题的解序列 ${x^{*} (t)}$ 在可行域内形成一条通向最优解的路径。中心路径的存在性是内点法收敛的关键。

原始-对偶内点法：同时追踪原始变量 $x$ 和对偶变量 $(λ, ν)$ ，通过牛顿法求解 KKT 条件的修正方程：

$H A_{eq} A_{in} A_{eq}^{T} 00 A_{in}^{T} 0 - S Λ Δ x Δ ν Δ λ = - g - h - μ e$

其中 $S = diag (λ_{i})$ ， $Λ = diag (μ / λ_{i})$ ， $μ$ 是对偶间隙的度量参数。

预测-校正（Predictor-Corrector）：在内点法中，正则方程的数值稳定性至关重要。Mehrotra 的预测-校正方法通过两步（预测方向和校正方向）改善了收敛速度和数值稳定性。

15.3 整数规划与分支定界

整数线性规划（ILP）：LP 变量限制为整数。当变量数为布尔型时（0-1 规划），问题为 NP-hard。

分支定界法（Branch and Bound）：

根 LP 松弛：忽略整数约束，求解 LP 得到上界（对于最大化问题）
分支：选择非整数变量 $x_{j} = x_{j}^{*}$ ，创建两个子问题 $x_{j} \leq ⌊ x_{j}^{*} ⌋$ 和 $x_{j} \geq ⌈ x_{j}^{*} ⌉$
定界：每个子节点求解 LP 松弛，更新全局界
剪枝：若子问题的 LP 解是整数解（或 LP 下界超过当前最优），则剪枝
递归直到所有分支被剪枝

割平面法（Cutting Plane）：Gomory 割从 LP 最优表中提取有效不等式，逐步切割非整数可行解空间。

现代 ILP 求解器（CPLEX、Gurobi）：结合分支定界、割平面、启发式（rounding、fix-and-optimize）、预处理（probing、tightening）和并行计算，在实际问题上可求解百万变量规模。

十六、非线性规划的深入理论

16.1 约束品性条件的完整讨论

约束品性（Constraint Qualification, CQ）确保 KKT 条件与最优性之间的桥梁。

线性约束独立（LICQ）：在可行点 $x^{*}$ 处，所有有效约束的梯度 ${\nabla f_{i} (x^{*}), \nabla h_{j} (x^{*})}$ 线性无关。LICQ 是最强也最常用的 CQ。

Mangasarian-Fromovitz CQ（MFCQ）：对于等式约束的梯度线性无关；对于不等式约束，存在方向 $d$ 使得 $\nabla f_{i} (x^{*})^{T} d < 0$ （活跃不等式）。

Slater 条件（凸优化 CQ）：存在点 $x$ 使得所有不等式约束严格成立、所有等式约束成立。Slater 条件 $⟺$ MFCQ。

Abadie CQ：可行方向锥等于线性化可行方向锥。

Cottle CQ：活跃约束的梯度张成的空间与积极锥的极锥有非零交集。

16.2 二阶最优性条件

二阶必要性条件：若 $x^{*}$ 是局部极小点且满足适当 CQ，则存在 KKT 乘子使得：

$d^{T} \nabla_{xx}^{2} L (x^{*}, λ^{*}, ν^{*}) d \geq 0, \forall d \in C (x^{*})$

其中 $C (x^{*})$ 是可行方向锥（Critical Cone）。

二阶充分性条件：若存在 KKT 乘子使得 Hessian 在 Critical Cone 上正定，则 $x^{*}$ 是严格局部极小。

16.3 增广拉格朗日的深层性质

Uryasev 方法：对不等式约束 $f_{i} (x) \leq 0$ ，使用指数型惩罚：

$ϕ_{ρ} (x) = f_{0} (x) - \frac{1}{ρ} \sum_{i} lo g (- f_{i} (x))$

这在障碍函数和惩罚函数之间建立联系。

精确惩罚（Exact Penalty）：若 $x^{*}$ 是局部极小且满足强二阶充分条件，则存在 $\overset{ρ}{ˉ}$ 使得原始约束问题等价于惩罚问题 $min f_{0} (x) + ρ \sum_{i} max (0, f_{i} (x))$ 。

十七、流形优化与结构化优化

17.1 流形优化的基础

流形是局部同构于欧氏空间的拓扑空间。在优化中，我们经常遇到约束在流形上的问题，如正交约束（ $X^{T} X = I$ ）、锥约束（ $X ⪰ 0$ ）、秩约束（ $rank (X) = r$ ）。

黎曼几何基础：

流形 $M$ 上的点 $x$ 处的切空间 $T_{x} M$
黎曼度量 $g_{x} : T_{x} M \times T_{x} M \to R$
黎曼梯度： $grad f (x)$ 是切空间中使得 $f$ 上升最快的方向
黎曼 Hessian： $Hess f (x)$ 是切空间上的线性算子

** retraction**（回撤）：将切向量映射回流形： $R_{x} : T_{x} M \to M$ ，满足 $R_{x} (0) = x$ ，且在零点的一阶导数为恒等映射。常见 retraction：正交投影到 Stiefel 流形、QR retraction on 鸟。

17.2 典型流形

球面流形 $S^{n - 1}$ ：单位向量集合 ${∥ x ∥ = 1}$ 。切空间是 ${v : x^{T} v = 0}$ ， retraction 是 $R_{x} (v) = (x + v) /∥ x + v ∥$ 。

Stiefel 流形 $St (p, n) = {X \in R^{n \times p} : X^{T} X = I_{p}}$ ：正交列框架。正交投影到其法空间给出 retraction。

广义 Stiefel 流形：如固定秩矩阵流形 ${X : rank (X) = r}$ ，或固定行列式流形。

正定矩阵流形 $S_{++}^{n}$ ：对称正定矩阵。黎曼度量通常选为仿射不变度量 $g_{X} (S, S) = tr (X^{- 1} S X^{- 1} S)$ ，对应自然梯度 $\nabla_{R} f (X) = X \cdot sym (X^{- 1} \nabla f (X))$ 。

17.3 流形上的优化算法

黎曼梯度下降： $x_{k + 1} = R_{x_{k}} (- η_{k} grad f (x_{k}))$

黎曼共轭梯度：在流形上定义共轭方向，需使用并行传输（parallel transport）将梯度从一点传输到另一点。

随机梯度流形下降（RSGD）：用于矩阵分解（如推荐系统中的非负矩阵分解）等问题。

Barzilai-Borwein 步长：一种无需线搜索的梯度下降步长选择规则，在欧氏空间和流形空间均有应用。

十八、凸优化的概率与统计视角

18.1 随机凸优化

当目标函数是随机函数的期望 $F (x) = E [f (x, ξ)]$ 时，梯度下降需要用随机梯度 $\nabla f (x, ξ_{k})$ 近似真实梯度 $\nabla F (x)$ 。

SGD 的收敛性：对于强凸 $F$ ，适当步长 $η_{k} = O (1/ k)$ 给出 $O (1/ k)$ 收敛率（噪声是 $O (1/ k)$ 量级）；对于恒定步长 $η$ ，给出 $O (1/ k)$ 的最终收敛半径。

方差缩减：SVRG、SAGA、Finito 等方法通过周期性重置或平均历史梯度，将方差降低到 $O (1/ k)$ ，从而实现线性收敛。

18.2 鲁棒优化与随机规划

鲁棒优化：优化问题中参数不确定，构造不确定性集 $U$ ，求解 $min_{x \in X} max_{u \in U} f (x, u)$ 。

椭球不确定性： $U = {u : ∥ u ∥_{2} \leq ρ}$ ，导致 SOCP 或 SDP 可处理的鲁棒 LP。
盒不确定性： $U = [- 1, 1]^{n}$ ，导致顶点检查。

两阶段随机规划（Stochastic Programming）： recourse 决策在观测到随机变量后执行：

$min_{x \geq 0} c^{T} x + E_{ξ} [Q (x, ξ)]$ $Q (x, ξ) = min_{y} {q (ξ)^{T} y : W (ξ) y \geq h (ξ) - T (ξ) x}$

使用 Benders 分解处理大尺度问题。

18.3 分布式凸优化

参数服务器架构：多个 worker 节点计算局部梯度，server 节点聚合并广播更新。

环 AllReduce：在环形拓扑中，每个节点只与两个邻居通信，适合 GPU 集群的高效通信。

梯度压缩：量化（Quantization）、稀疏化（Sparsification）、熵编码等方法将通信量从 $O (n)$ 降低到 $O (n)$ 或更低，同时保持收敛性。

联邦学习中的凸聚合：各客户端有本地数据，各自优化本地模型。服务器通过加权平均聚合。差分隐私和通信压缩是联邦学习的核心挑战。

十九、凸优化与机器学习的深度结合

19.1 正则化与稀疏优化

LASSO 的几何解释： $L_{1}$ 范数约束的等值面是旋转对称的钻石形，与误差椭球 ${(x, y) : ∥ A x - b ∥_{2} \leq δ}$ 的交点倾向于落在坐标轴上，从而产生稀疏解。

Elastic Net： $min ∥ A x - b ∥_{2}^{2} + λ_{1} ∥ x ∥_{1} + λ_{2} ∥ x ∥_{2}^{2}$ ，结合 $L_{1}$ 和 $L_{2}$ 正则化，对高相关特征组有更好的选择稳定性。

Group Lasso：对特征分组施加组间稀疏性（ $L_{1, 2}$ 混合范数），用于选择相关的特征组。

Fused Lasso：促进解的空间平滑性（相邻系数接近），适用于时间序列或空间数据的去噪。

近端算子的实际计算：

函数 $h$	近端算子 $prox_{τ h} (x)$
$∥ x ∥_{1}$	$soft (x, τ)$
$∥ x ∥_{2}$	$max (1 - τ /∥ x ∥_{2}, 0) x$
$∥ x ∥_{*}$ （核范数）	对奇异值做软阈值
$δ_{C} (x)$ （指示函数）	投影到 $C$

19.2 稳健回归

Huber 损失： $ρ_{δ} (r) = {r^{2} /2 δ ∣ r ∣ - δ^{2} /2 ∣ r ∣ \leq δ ∣ r ∣ > δ$ ，结合了 $L_{2}$ （小残差）和 $L_{1}$ （大残差）的优点。

Tukey biweight：在深度学习对抗训练中用于鲁棒优化。

$ℓ_{\infty}$ 回归（Chebyshev 拟合）：使用切比雪夫范数最小化最大误差，可转化为 LP。

19.3 相位恢复与低秩矩阵恢复

相位恢复：从幅度测量 $y_{i} = ∣ a_{i}^{T} x ∣$ 恢复信号 $x$ 。 $ℓ_{1}$ 最小化在稀疏先验下是有效的。

低秩矩阵补全： $min ∥ X ∥_{*} s.t. P_{Ω} (X) = M$ ，由组稀疏性（秩）推动。使用奇异值阈值（SVT）迭代求解：

$X_{k + 1} = S_{τ} (X_{k} + P_{Ω} (M - X_{k}))$

其中 $S_{τ}$ 是奇异值软阈值算子。

Robust PCA： $min ∥ L ∥_{*} + λ ∥ S ∥_{1} s.t. L + S = M$ ，将观测矩阵分解为低秩分量（ $L$ ）和稀疏噪声（ $S$ ）。应用于背景建模（视频监控）、异常检测、协同过滤去噪。

二十、凸优化的软件工具与实践

20.1 建模语言

CVX（MATLAB/Python）：Disciplined Convex Programming (DCP) 规范。通过 CVXIF 接口集成到其他语言。

cvx_begin
    variable x(n)
    minimize(norm(A*x - b, 2))
    subject to
        x >= 0
        sum(x) == 1
cvx_end

CVXPY（Python）：CVX 的 Python 版本，支持 NumPy 和 SciPy。

import cvxpy as cp
x = cp.Variable(n)
objective = cp.Minimize(cp.norm(A @ x - b, 2))
constraints = [x >= 0, cp.sum(x) == 1]
prob = cp.Problem(objective, constraints)
prob.solve(solver=cp.SCS)

JuMP（Julia）：高性能建模语言，支持 LP、QP、SOCP、SDP、混合整数规划。

20.2 求解器选择指南

问题类型	开源求解器	商业求解器
LP	CLP, HiGHS, GLPK	Gurobi, CPLEX, MOSEK
QP	OSQP, qpOASES	Gurobi, CPLEX
SOCP/SDP	SCS, ECOS	MOSEK, Gurobi
非线性规划	Ipopt	KNITRO, FILTERSD
ILP/MILP	CBC, GLPK, HiGHS	Gurobi, CPLEX

SCS（Splitting Conic Solver）：一阶方法，支持 LP、SOCP、SDP 的中等规模问题。GPU 加速版本使大规模问题处理更快。

OSQP：专门针对 QP 的一阶求解器，使用 ADMM，在控制理论和 MPC 中广泛使用。

20.3 数值稳定性实践

缩放：对系数矩阵 $A$ 和右端项 $b$ 进行均衡缩放（如按列缩放使条件数改善）
热启动：从一个可行的初始点开始，而非从零开始
精度设置：理解求解器的 tolerance 设置（primal feasibility、dual feasibility、duality gap）
结果验证：解出后验证 KKT 残差

参考文献

Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Nesterov, Y. (2018). Lectures on Convex Optimization (2nd ed.). Springer.
Bertsekas, D. P. (1999). Nonlinear Programming (2nd ed.). Athena Scientific.
Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press.
Bottou, L., Curtis, F. E., & Nocedal, J. (2018). Optimization Methods for Large-Scale Machine Learning. SIAM Review, 60(2), 223-311.
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Grant, M., & Boyd, S. (2014). CVX: Matlab Software for Disciplined Convex Programming. Version 2.1.
Domke, J. (2012). Generic Methods for Optimization-Based Modeling. AISTATS, 1162-1170.
Goemans, M. X., & Williamson, D. P. (1995). Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM, 42(6), 1115-1145.
Tieleman, T., & Hinton, G. (2012). Lecture 6.5 - RMSProp. COURSERA: Neural Networks for Machine Learning.
Kingma, D. P., & Ba, J. (2015). Adam: A Method for Stochastic Optimization. ICLR.
Beck, A., & Teboulle, M. (2009). A Fast Iterative Shrinkage-Thresholding Algorithm. SIAM J. Imaging Sciences, 2(1), 183-202.
Glowinski, R., & Marrocco, A. (1975). Sur l’approximation par éléments finis d’ordre un, et la résolution par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires. Rev. Française Automat. Informat. Recherche Opérationnelle, 9(R2), 41-76.
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends in Machine Learning, 3(1), 1-122.
Choromanska, A., Henaff, M., Mathieu, M., Arous, G. B., & LeCun, Y. (2015). The Loss Surfaces of Multilayer Networks. AISTATS, 192-204.
Allen-Zhu, Z., Li, Y., & Song, Z. (2019). A Convergence Theory for Deep Learning via Over-Parameterization. ICML, 242-252.

人工智能知识库

探索

凸优化深度指南

凸优化深度指南

关键词

一、凸集与凸函数

1.1 凸集的定义与性质

1.2 凸函数的定义

1.3 凸函数的判别与性质

1.4 函数的共轭与Fenchel对偶

二、典型优化问题

2.1 线性规划（LP）

2.2 二次规划（QP）

2.3 二阶锥规划（SOCP）

2.4 半定规划（SDP）

2.5 锥规划统一框架

三、对偶理论与KKT条件

3.1 拉格朗日函数

3.2 拉格朗日对偶函数

3.3 对偶问题

3.4 KKT条件

3.5 鞍点理论

四、梯度下降与收敛性分析

4.1 梯度下降法

4.2 凸函数的收敛率

4.3 非凸函数的收敛性

4.4 随机梯度下降（SGD）

五、一阶优化方法

5.1 动量法与Nesterov加速

5.2 自适应学习率方法

5.3 近端梯度法

5.4 交替方向乘子法（ADMM）

5.5 镜像下降（Mirror Descent）

六、二阶优化方法

6.1 牛顿法

6.2 拟牛顿法

6.3 牛顿法的实际考量

七、约束优化的投影方法

7.1 投影梯度法

7.2 Frank-Wolfe算法

7.3 条件梯度滑动（Conditional Gradient Sliding）

7.4 增广拉格朗日法

八、凸优化的计算复杂性

8.1 问题复杂度分类

8.2 局部最优与全局最优

8.3 零阶优化

九、应用专题

9.1 机器学习中的凸优化

9.2 控制理论中的凸优化

9.3 信号处理中的凸优化

9.4 博弈论与凸优化

十、算法实现细节与数值稳定性

10.1 线搜索与步长选择

10.2 数值稳定性的实践考量

10.3 大规模问题的策略

十一、算法选择指南

11.1 问题类型与推荐算法

11.2 编程工具生态

十二、历史注记与延伸阅读

12.1 发展简史

12.2 经典教材

十三、典型习题

十四、进阶专题预告

十五、线性规划的深入专题

15.1 单纯形法的几何与代数

15.2 内点法的完整推导

15.3 整数规划与分支定界

十六、非线性规划的深入理论

16.1 约束品性条件的完整讨论

16.2 二阶最优性条件

16.3 增广拉格朗日的深层性质

十七、流形优化与结构化优化

17.1 流形优化的基础

17.2 典型流形

17.3 流形上的优化算法

十八、凸优化的概率与统计视角

18.1 随机凸优化

18.2 鲁棒优化与随机规划

18.3 分布式凸优化

十九、凸优化与机器学习的深度结合