最优化核心概念导览：Convexity、Duality、KKT 与数值优化

最优化是机器学习、数据挖掘、运筹、控制和 AI infra 里都会反复出现的一条主线。训练模型是在最小化 loss，推荐系统是在优化排序目标，推理系统是在优化吞吐和延迟；即使问题表面很不一样，背后经常都可以抽象成“目标函数 + 约束 + 求解算法”。

这篇文章根据 AMA4850 的复习材料整理，但这里不按考试提纲写，而是把它改写成一篇最优化知识导览：从凸性出发，接到对偶理论、KKT 最优性条件，再到梯度下降、拟牛顿法、罚函数和 barrier method。原 PDF 保留在这里，方便对照完整材料。

原 PDF：AMA4850 Final Exam Review

1. 最优化问题到底在研究什么

一个标准的最优化问题可以写成：

$$\min_x f(x)$$

subject to：

$$g_i(x)\le 0,\quad i=1,\ldots,m$$

$$h_j(x)=0,\quad j=1,\ldots,p$$

这里 $f(x)$ 是目标函数，$g_i(x)$ 是不等式约束，$h_j(x)$ 是等式约束。最优化的核心问题有三个：

1. 这个问题有没有比较好的数学结构，比如是否凸？
2. 如果找到一个候选解，怎么判断它是不是最优？
3. 如果问题很大，怎么用算法一步步逼近解？

这三个问题分别对应本文的三条线：convex analysis、optimality conditions、numerical algorithms。

2. 凸性：为什么 convex problem 特别重要

凸优化之所以重要，是因为它把“局部最优”和“全局最优”连接起来。一般非凸问题里，一个点附近看起来很好，不代表它是全局最优；但在凸优化里，只要满足合适条件，局部最优就可以成为全局最优。

一个集合 $C$ 是 convex set，意思是任意两个点之间的线段仍然在集合里：

$$\theta x+(1-\theta)y\in C,\quad \forall x,y\in C,\ \theta\in[0,1]$$

一个函数 $f$ 是 convex function，意思是：

$$f(\theta x+(1-\theta)y) \le \theta f(x)+(1-\theta)f(y)$$

直观上，凸函数的图像不会“向下凹出一个坑又再爬出来”。这也是为什么凸优化问题更容易分析：没有很多互相竞争的局部极小点。

如果 $f$ 一阶可微，凸性等价于一阶下界条件：

$$f(y)\ge f(x)+\nabla f(x)^T(y-x),\quad \forall x,y$$

这句话的意思是：凸函数在任意一点的一阶切平面，都是整个函数图像的全局下界。

如果 $f$ 二阶可微，则可以用 Hessian 判断：

$$f \text{ convex} \quad \Longleftrightarrow \quad \nabla^2 f(x)\succeq 0,\ \forall x\in \mathrm{dom}(f)$$

所以在实际判断时，常见路线是：

1. 先检查定义域是否是凸集。
2. 能求 Hessian 时，检查 Hessian 是否 positive semidefinite。
3. 如果函数由 norm、max、log-sum-exp、quadratic form 等常见结构组成，就用已知结论和 composition rule。
4. 如果函数不可微，可以看 epigraph：

$$\mathrm{epi}(f)=\{(x,t): f(x)\le t\}$$

若 epigraph 是凸集，则 $f$ 是凸函数。

3. PSD 矩阵：凸性的矩阵语言

Positive semidefinite matrix，简称 PSD，是最优化里非常高频的概念。对称矩阵 $A\in S^n$ 满足：

$$A\succeq 0 \quad \Longleftrightarrow \quad x^TAx\ge 0,\ \forall x$$

它可以理解为：矩阵 $A$ 定义出来的二次型在任何方向上都不为负。

PSD 矩阵和凸性之间的关系非常直接。对 quadratic form：

$$q(x)=x^TAx$$

如果 $A\succeq 0$，则 $q(x)$ 是 convex；如果 $A\succ 0$，则 $q(x)$ 是 strictly convex。

常见判断方法包括：

1. 所有特征值非负，则 $A\succeq 0$。
2. 所有 principal minors 非负，则 $A\succeq 0$。
3. 若所有 leading principal minors 大于 0，则可用 Sylvester criterion 判断 $A\succ 0$。

PSD 不是一个孤立概念，它会在 Hessian、SDP、KKT second-order condition、Schur complement 里反复出现。

4. Stationary Point：梯度为零代表什么

对无约束问题：

$$\min_x f(x)$$

如果 x^\* 是局部极小点，并且 $f$ 可微，那么必须满足：

\nabla f(x^\*)=0

这样的点叫 stationary point。它的含义是：在一阶近似里，函数没有继续下降的方向。

但 stationary point 不一定是极小点。若 $f$ 二阶可微，可以用 Hessian 做进一步分类：

• \nabla^2 f(x^\*)\succ 0：strict local minimizer。
• \nabla^2 f(x^\*)\prec 0：strict local maximizer。
• Hessian indefinite：saddle point。
• Hessian semidefinite：二阶信息不足，需要更高阶分析或其他方法。

Saddle point 很重要，尤其在深度学习里经常出现。它的特点是梯度为 0，但某些方向上函数值增加，另一些方向上函数值减少，所以它不是一个真正稳定的最小点。

5. Schur Complement：把非线性约束变成矩阵约束

Schur complement 是把某些非线性约束转成 LMI，也就是 linear matrix inequality 的重要工具。设：

$$M= \begin{bmatrix} A & B\\ B^T & C \end{bmatrix}$$

如果 $C\succ 0$，则：

$$M\succeq 0 \quad \Longleftrightarrow \quad A-BC^{-1}B^T\succeq 0$$

如果 $A\succ 0$，则：

$$M\succeq 0 \quad \Longleftrightarrow \quad C-B^TA^{-1}B\succeq 0$$

一个典型例子是：

$$t\ge x^TP^{-1}x,\quad P\succ 0$$

可以改写成：

$$\begin{bmatrix} t & x^T\\ x & P \end{bmatrix} \succeq 0$$

这样原本带有逆矩阵和二次项的约束，就变成了 PSD matrix constraint。这就是很多 SDP reformulation 的基本套路。

6. LP Duality：从另一个角度看同一个问题

对偶理论的核心思想是：每个优化问题都可以构造一个 dual problem。dual problem 给出 primal problem 的界，有时还能和 primal 得到同样的最优值。

线性规划的一个常见 primal 形式是：

$$\min_x c^Tx \quad \text{s.t. } Ax=b,\ x\ge 0$$

对应 dual 是：

$$\max_y b^Ty \quad \text{s.t. } A^Ty\le c$$

Weak duality 说明 dual 最优值不会超过 primal 最优值：

d^\* \le p^\*

Strong duality 则说明在满足条件时，两者相等：

d^\*=p^\*

学习 duality 时，与其死记每一种标准形式，不如理解构造步骤：

1. 把 primal 写成清楚的目标和约束。
2. 为约束引入 Lagrange multiplier。
3. 构造 Lagrangian。
4. 对 primal variable 取 infimum，得到 dual function。
5. 写出让 dual function 有意义的 dual feasible condition。

Duality 的价值不只是求解，还包括证明最优性、推导下界、解释约束价格，以及分析 primal-dual algorithm。

7. SDP Duality：把 LP 推广到矩阵世界

Semidefinite programming，简称 SDP，可以看作 LP 的矩阵版本。LP 中的变量通常是向量，SDP 中的变量可以是矩阵，并且带有 PSD 约束。

一种常见 primal SDP 是：

$$\min_X \mathrm{Tr}(CX)$$

subject to：

$$\mathrm{Tr}(A_iX)=b_i,\quad i=1,\ldots,m$$

$$X\succeq 0$$

对应 dual 是：

$$\max_y b^Ty$$

subject to：

$$C-\sum_{i=1}^{m}y_iA_i\succeq 0$$

SDP 的关键是把约束写成矩阵半正定形式。它在控制、组合优化松弛、机器学习和矩阵补全里都有应用。很多看似非线性的问题，如果能通过 Schur complement 或 lifting 改写成 SDP，就能用成熟的 convex optimization 工具处理。

8. KKT Conditions：约束优化的最优性语言

KKT conditions 是约束优化里最重要的一组条件。考虑：

$$\min_x f(x)$$

subject to：

$$g_i(x)\le 0,\quad i=1,\ldots,m$$

$$h_j(x)=0,\quad j=1,\ldots,p$$

先写 Lagrangian：

$$L(x,\lambda,\nu) = f(x)+\sum_{i=1}^{m}\lambda_i g_i(x)+\sum_{j=1}^{p}\nu_j h_j(x)$$

KKT 条件包括四组：

Primal feasibility

g_i(x^\*)\le 0,\quad h_j(x^\*)=0

候选解必须满足原问题约束。

Dual feasibility

\lambda_i^\*\ge 0

不等式约束对应的 multiplier 必须非负。

Complementary slackness

\lambda_i^\*g_i(x^\*)=0

这句话很有信息量：如果一个不等式约束没有卡住，也就是 g_i(x^\*)<0，那么它的 multiplier 必须为 0；如果 multiplier 大于 0，则说明这个约束在最优点处是 active 的。

Stationarity

\nabla_x L(x^\*,\lambda^\*,\nu^\*)=0

目标函数梯度和约束梯度在最优点处达到一种平衡。

对一般非凸问题，KKT 通常只是 necessary condition，而且还需要 constraint qualification。对 convex optimization，在满足合适条件时，KKT 可以成为 necessary and sufficient condition，也就是既必要又充分。

9. MFCQ 与 Slater Condition：为什么 KKT 和 Strong Duality 成立

KKT 和 strong duality 不是无条件成立的。它们背后需要一些 regularity condition。

MFCQ，全称 Mangasarian-Fromovitz constraint qualification，常用于一般约束优化。它的作用是排除一些病态约束结构，从而保证局部最优点满足 KKT necessary condition。

Slater condition 更常出现在 convex optimization 里。对凸问题，如果存在严格可行点：

$$g_i(x)<0,\quad h_j(x)=0$$

那么 strong duality 通常成立，KKT 条件也会表现得很好。

可以这样理解：

• MFCQ 主要服务于一般约束优化中的 KKT 必要性。
• Slater condition 主要服务于凸优化中的 strong duality 和 KKT 充分性。

10. Gradient Descent：最基本的一阶算法

Gradient descent 是最优化里最基础的一阶方法。它只使用梯度信息，更新公式是：

$$x_{k+1}=x_k-\alpha_k\nabla f(x_k)$$

其中 $-\nabla f(x_k)$ 是当前位置函数下降最快的方向，$\alpha_k$ 是 step size。

如果使用 exact line search：

$$\alpha_k = \arg\min_{\alpha>0} f(x_k-\alpha\nabla f(x_k))$$

这表示每一步都沿着负梯度方向找最好的步长。但 exact line search 计算成本可能很高，所以实际算法中更常用固定步长、递减步长或 backtracking line search。

对 $L$-smooth 函数，固定步长常见要求是：

$$0<\alpha<\frac{2}{L}$$

如果 $f$ convex 且 smooth，梯度下降可以保证函数值下降；如果 $f$ strong convex，收敛速度还会更好。

11. Armijo Rule：不追求完美步长，只追求足够下降

Armijo rule 是 backtracking line search 的常见准则。给定下降方向 $d_k$，希望找到 $\alpha_k$ 满足：

$$f(x_k+\alpha_k d_k) \le f(x_k)+c\alpha_k\nabla f(x_k)^Td_k$$

其中 $c\in(0,1)$。

典型流程是：

1. 从 $\alpha=1$ 开始。
2. 如果 Armijo 条件不满足，就令 $\alpha\leftarrow \beta\alpha$，其中 $\beta\in(0,1)$。
3. 重复直到条件满足。

Armijo rule 的思想很实用：没有必要每次都求最优步长，只要这一步真的带来了足够下降，就可以继续迭代。这种思路在很多实际优化算法里都很重要，因为工程中往往更在意稳定、便宜、可持续的下降，而不是每一步的局部完美。

12. Newton、Quasi-Newton 与 BFGS

Gradient descent 只用一阶信息。Newton method 使用二阶信息，也就是 Hessian：

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

Newton method 的优点是局部收敛很快，缺点是 Hessian 计算和求逆可能非常贵，尤其是变量维度很大时。

Quasi-Newton 的想法是：不用真正计算 Hessian，而是用迭代过程中的信息逐步构造 Hessian 或 inverse Hessian 的近似。

BFGS 是最常见的 quasi-Newton 方法之一。定义：

$$s_k=x_{k+1}-x_k$$

$$y_k=\nabla f(x_{k+1})-\nabla f(x_k)$$

更新矩阵需要满足 secant equation：

$$B_{k+1}s_k=y_k$$

这里 $s_k$ 描述参数移动了多少，$y_k$ 描述梯度变化了多少。BFGS 试图从这些信息里推断曲率。若满足 $s_k^Ty_k>0$，BFGS 通常可以保持正定性，这对下降方向和算法稳定性都很重要。

13. Penalty Method：把约束压进目标函数

Penalty method 的思想是把有约束问题转成无约束问题。比如等式约束：

$$h(x)=0$$

可以改写成：

$$\min_x f(x)+\frac{\rho}{2}\|h(x)\|^2$$

其中 $\rho$ 是 penalty parameter。如果违反约束，罚项会变大；随着 $\rho\to\infty$，算法会越来越强迫解接近可行域。

它的优点是形式简单，可以直接使用无约束优化方法。缺点也很明显：当 $\rho$ 很大时，问题容易变得 ill-conditioned，数值求解会更困难。

Penalty method 的直观理解是：先允许你“不完全守规矩”，但违反约束要付出代价，而且这个代价会越来越高。

14. Barrier Method：在可行域内部逼近边界

Barrier method 主要用于不等式约束：

$$g_i(x)<0$$

常见 logarithmic barrier 是：

$$\phi(x) = -\sum_{i=1}^{m}\log(-g_i(x))$$

构造问题：

$$\min_x tf(x)+\phi(x)$$

或者：

$$\min_x f(x)+\frac{1}{t}\phi(x)$$

当 $x$ 靠近约束边界时，$-g_i(x)$ 接近 0，$\log(-g_i(x))$ 趋向负无穷，所以 barrier term 会趋向正无穷。这样算法会被“挡”在可行域内部。

Penalty method 和 barrier method 的区别可以这样记：

• Penalty method 可以从不可行点出发，用罚项把解推向可行域。
• Barrier method 通常从严格可行点出发，在可行域内部逼近最优解。
• Penalty parameter 往往越来越大；barrier formulation 里的参数方向要根据写法区分。

15. 一条完整的知识主线

把这些概念连起来，最优化的学习路线可以概括成：

$$\text{Convex Analysis} \rightarrow \text{Duality} \rightarrow \text{Optimality Conditions} \rightarrow \text{Numerical Algorithms}$$

Convexity 让我们知道问题结构是否友好；duality 让我们从另一个角度解释和验证最优值；KKT conditions 给出约束优化的最优性语言；gradient descent、Newton、BFGS、penalty 和 barrier method 则告诉我们怎样实际求解。

对机器学习来说，这些内容不是孤立的数学符号。训练 loss 的曲率、正则项的约束含义、SVM 的 KKT 条件、深度模型的梯度下降、推荐系统里的约束优化、AI infra 里的资源调度问题，都能在这套语言里找到对应位置。

所以学习最优化时，最好不要只背公式。更有效的方式是每看到一个公式，都问三个问题：

1. 它在判断问题结构，还是在判断最优性？
2. 它适用于凸问题，还是一般非凸问题也能用？
3. 它是理论条件，还是可以转化成实际算法？

能把这三个问题想清楚，最优化就会从一堆公式变成一套可以迁移到机器学习和工程问题里的分析工具。