计算机科学的数学基础-02：最优化理论

预备知识

优化的定义

优化旨在从所有可行的配置方案中寻找最佳解。优化问题通常被形式化为在满足一定约束条件（$x \in \mathcal{X}$）的前提下，最小化或最大化一个目标函数 $f(x)$。优化问题可以基于多维度进行分类，包括是否带有约束条件（无约束与有约束）、变量的连续性（连续与非平滑）以及函数的凸性（凸优化与非凸优化）。计算机科学与机器学习领域主要关注有约束、连续的凸优化问题。

线代基础

• 向量与内积： 向量 $x$ 及其转置 $x^T$ 构成了空间中的点或方向。两个向量的内积定义为 $x^T y = \sum_i x_i y_i$。若内积为 0，则两向量正交。
• 向量范数： 用于衡量向量的“长度”，常用作损失函数中的正则化项。常用的包括 $L_1$ 范数（绝对值之和 $||x||_1 = \sum |x_i|$）和 $L_2$ 范数（欧几里得距离 $||x||_2 = \sqrt{\sum x_i^2}$）。
• 半正定与正定矩阵： 对于对称矩阵 $A$，若对任意向量 $x$，均有二次型 $x^T Ax \ge 0$，则称 $A$ 为半正定矩阵（PSD，记为 $A \ge 0$）。若严格有 $x^T Ax > 0$，则为正定矩阵（PD，记为 $A > 0$）。
• 半正定性： 在优化中，目标函数的二阶导数矩阵（海森矩阵）如果是半正定的，则证明该目标函数是凸函数。矩阵的半正定性是判断多元函数凸性的核心数学工具。

凸优化

凸优化研究一类结构良好的优化问题：目标函数是凸函数，可行域是凸集。它的重要性质是局部最优解一定是全局最优解，因此算法不需要在多个局部极小值之间做额外选择。

一个标准的最小化问题可写为：

$$\begin{aligned} \min_x \quad & f_0(x) \\ \text{s.t.}\quad & f_i(x)\le 0,\quad i=1,\dots,m \\ & h_j(x)=0,\quad j=1,\dots,p \end{aligned}$$

若 $f_0,\dots,f_m$ 都是凸函数，且等式约束 $h_j(x)=a_j^T x-b_j$ 是仿射函数，则该问题是凸优化问题。这里要求等式约束必须是仿射的，因为一般非线性等式 $h(x)=0$ 往往会破坏可行域的凸性。

判断凸性的常用条件如下：

• 凸集： 对任意 $x,y\in C$ 与 $\lambda\in[0,1]$，若 $\lambda x+(1-\lambda)y\in C$，则 $C$ 是凸集。
• 凸函数： 若定义域是凸集，且对任意 $x,y$ 与 $\lambda\in[0,1]$，有 $f(\lambda x+(1-\lambda)y)\le \lambda f(x)+(1-\lambda)f(y)$，则 $f$ 是凸函数。
• 一阶条件： 若 $f$ 可微，则 $f$ 凸当且仅当对任意 $x,y$，有 $f(y)\ge f(x)+\nabla f(x)^T(y-x)$。这表示凸函数图像始终在任意切平面之上。
• 二阶条件： 若 $f$ 二阶可微，则 $f$ 凸当且仅当 Hessian 矩阵满足 $\nabla^2 f(x)\succeq 0$。若进一步有 $\nabla^2 f(x)\succ 0$，通常可得到严格凸性，从而最优解至多一个。

无约束可微凸优化的最优性条件非常简单：若 $x^\star$ 是可行点且 $\nabla f(x^\star)=0$，则 $x^\star$ 是全局最优解。带约束时，最优解不一定满足梯度为 0，因为约束边界会限制下降方向，此时需要使用 KKT 条件或内点法等工具。

线性规划

线性规划 Linear Programming, LP 的目标函数和约束条件均为线性函数。

• 规范形式： 最大化 $c^T x$，且满足不等式约束 $a_i^T x \le b_i$ 与非负约束 $x_j \ge 0$。所有线性规划都可以通过变量代换、符号翻转等操作转化为规范形式。
• 几何视角： 每一个线性不等式约束 $a_i^T x \le b_i$ 在几何上定义了一个半空间，多个半空间的交集构成了一个多面体，即优化的可行域。优化过程等价于在这个多面体上沿着目标方向 $c$ 寻找极值点。
• 补充前置知识： 线性规划的最优解必然出现在多面体的顶点上。经典的单纯形法正是基于这一几何性质，通过在多面体的相邻顶点间不断跳跃来快速搜索最优解。

以计算最大利润的问题为例：

线性规划属于凸优化，因为线性函数既是凸函数也是凹函数，线性不等式约束定义的半空间也是凸集。若目标函数方向 $c$ 与可行多面体的某条边平行，则可能出现一整条边或一个面上的点都达到相同最优值；否则最优解通常出现在某个顶点。

LP 的对偶问题也很重要。以原问题 $\min c^T x,\ Ax\ge b$ 为例，可以引入非负乘子 $y\ge 0$，把约束加权进目标中。对偶变量可理解为每个约束的“影子价格”：若某个资源约束被放宽一点，目标值能改善多少。弱对偶保证任意对偶可行解都给出原问题的下界；在常见正则条件下，强对偶成立，原问题最优值与对偶问题最优值相同。

二次规划与二次约束

• 二次规划 QP：
  在多面体可行域内最小化一个凸二次目标函数。其标准形式为 $\min x^T P x + c^T x + d$，且满足 $Ax \le b$，其中矩阵 $P$ 必须为半正定矩阵（$P\succeq 0$）以保证问题的凸性。带约束的最小二乘回归是典型的 QP 问题。

• 二次约束二次规划 QCQP：
  在 QP 的基础上，将线性约束扩展为二次约束。不仅目标函数是二次的，其约束条件 $(1/2)x^T P_i x + q_i^T x + r_i \le 0$ 也构成了椭球体交集的可行域。

图的最大割问题可以化成这种形式：

QP 的凸性来自二次项。对函数 $f(x)=x^T P x+c^T x+d$，其 Hessian 为 $2P$，因此只要 $P\succeq 0$，目标函数就是凸函数。若 $P\succ 0$，目标函数严格凸，在可行域非空时最优解唯一。

QCQP 需要同时检查目标函数和所有二次不等式约束。若约束函数写作 $f_i(x)=\dfrac{1}{2}x^T P_i x+q_i^T x+r_i$，则要求 $P_i\succeq 0$，这样集合 $\{x\mid f_i(x)\le 0\}$ 才是凸集。若某个 $P_i$ 不是半正定，则该二次约束可能产生非凸可行域，问题也就不再是凸优化。

几何规划

几何规划 Geometric Programming, GP 常用于最小化体积或面积等物理量。目标函数与约束由单项式（$f(x) = c x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$，$c \ge 0$， $x_i > 0$，$a_i \in \mathbb{R}$）与正多项式（$f(x) = \sum_{k=1}^K c_k x_1^{a_{k1}} x_2^{a_{k2}} \cdots x_n^{a_{kn}}$，约束与单项式相同）构成。原生的几何规划不是凸优化，但可以通过对数变换（如令 $y = \log x$）将其隐式转化为凸优化问题，从而实现高效求解，常用于工业设计如行李箱尺寸优化。一个标准的几何规划问题形式化定义如下：

$$\begin{aligned} \min_x \quad & f_0(x) \\ \text{s.t.}\quad & f_i(x) \le b_i,\quad i \in \mathcal{C}_1 \\ & h_i(x) = b_i,\quad i \in \mathcal{C}_2 \\ & x > 0 \end{aligned}$$

目标函数 $f_0(x)$ 和不等式约束函数 $f_i(x)$ 必须是正多项式；等式约束函数 $h_i(x)$ 必须是单项式；常数 $b_i > 0$。

原生的几何规划问题通常是非凸的，这意味着直接对其进行求解易陷入局部最优解。不过它可以通过对数变量代换，完全转化为一个标准的连续凸优化问题。设新变量 $y_i = \log x_i$，即 $x_i = e^{y_i}$。对单项式和正多项式同时取对数：

$$\log\left(c\prod_{i=1}^n x_i^{a_i}\right) =\log c+\sum_{i=1}^n a_i y_i$$

$$\log\left(\sum_{k=1}^K c_k\prod_{i=1}^n x_i^{a_{ki}}\right) =\log\sum_{k=1}^K e^{a_k^T y+\log c_k}$$

第一式说明单项式取对数后变成仿射函数；第二式说明正多项式取对数后变成 Log-Sum-Exp 函数。Log-Sum-Exp 是凸函数，因此对数变换后的 GP 可以转化为凸优化问题。需要注意的是，变量必须满足 $x_i>0$，否则 $\log x_i$ 不存在。

优化问题小结

LP、QP、QCQP 和 GP 都可以放入统一的约束优化框架中：目标是寻找一个满足约束的 $x^\star$，使目标函数 $f_0$ 取得最小值。

$$\begin{aligned} \min_x \quad & f_0(x) \\ \text{s.t.}\quad & g_i(x)\le 0,\quad i=1,\dots,m \\ & h_j(x)=0,\quad j=1,\dots,p \end{aligned}$$

其中 $f_0$ 的等值线表示目标函数取同一数值的点集，$-\nabla f_0(x)$ 给出局部下降方向，约束函数 $g_i,h_j$ 则共同定义可行域。无约束问题只需考虑如何沿下降方向移动；有约束问题还必须保证迭代点留在可行域内，或在接近边界时正确处理约束影响。

优化算法

课件中的算法部分按问题类型分为两类：无约束最小化主要讨论梯度下降法和牛顿法；有约束最小化主要讨论罚函数法和内点法。

无约束最小化

无约束最小化研究 $\min_x f(x)$，通常假设 $f$ 是凸函数且二阶连续可微。若 $x^\star$ 是无约束可微优化问题的最优点，则必须满足 $\nabla f(x^\star)=0$；若 $f$ 是凸函数，这个条件也是充分条件。

一维情形中，最优点可通过 $f'(x^\star)=0$ 找到；多维情形中，对应的“平坦点”就是梯度向量为 0 的点。梯度定义为 $\nabla f(x)=(\partial f/\partial x_1,\dots,\partial f/\partial x_n)^T$，它同时描述函数增长最快的方向和增长速度。

很多问题无法直接解析求解 $\nabla f(x^\star)=0$，因此需要迭代法：从初始点 $x_0$ 出发，生成点列 $x_0,x_1,\dots$，使目标函数值逐步接近最优值。

梯度下降法

梯度不仅给出最优性条件，也给出最速上升方向。因此，最直接的下降策略是沿负梯度方向移动。梯度下降法的目标和迭代式为：

$$x_{t+1}=x_t-\eta_t\nabla f(x_t)$$

其中 $\eta_t$ 是步长。若 $\eta_t$ 过小，每次移动距离有限，收敛会很慢；若 $\eta_t$ 偏大，迭代点可能在极小值两侧来回震荡；若 $\eta_t$ 过大，目标函数值可能发散。实际算法通常通过固定步长、回溯线搜索或随迭代衰减的步长来控制更新幅度。

从局部模型角度看，梯度下降是在 $x_t$ 附近用一阶近似描述目标函数，并加入一个二次正则项限制移动幅度。近似目标可写为 $f(x_t)+\nabla f(x_t)^T(x-x_t)+\dfrac{1}{2\eta_t}\lVert x-x_t\rVert_2^2$。对该近似目标求极小值，就得到 $x_{t+1}=x_t-\eta_t\nabla f(x_t)$。因此，步长 $\eta_t$ 也可以理解为对“允许离开当前点多远”的控制。

梯度下降的主要问题是对变量尺度敏感。例如函数 $f(x)=0.01x_1^2+x_2^2-0.5x_1-x_2$ 的梯度为 $(0.02x_1-0.5,\ 2x_2-1)^T$，两个维度的曲率相差很大。此时迭代点会在高曲率方向频繁摆动，而在低曲率方向缓慢推进，形成锯齿形轨迹。这也是牛顿法、拟牛顿法和预条件方法要自动调整尺度的原因。

牛顿法

牛顿法的核心是：下一步移动到当前位置处二阶近似函数的极小点。设 $g_t=\nabla f(x_t)$，$H_t=\nabla^2 f(x_t)$，令 $v=x-x_t$。在 $x_t$ 附近对 $f(x_t+v)$ 做二阶近似：

$$\hat{f}(x_t+v)=f(x_t)+g_t^T v+\dfrac{1}{2}v^T H_t v$$

要使二阶近似取得极小值，令其对 $v$ 的梯度为 0，即 $g_t+H_t v=0$。因此牛顿方向为：

$$\Delta x_{\mathrm{nt}}=-H_t^{-1}g_t$$

对应的更新式为：

$$x_{t+1}=x_t+\Delta x_{\mathrm{nt}} =x_t-[\nabla^2 f(x_t)]^{-1}\nabla f(x_t)$$

牛顿法利用 Hessian 矩阵描述局部曲率：曲率大的方向自动缩小步长，曲率小的方向自动放大步长。对严格凸二次函数，二阶近似与原函数完全一致，因此牛顿法一次迭代即可到达精确最优点。它通常比梯度下降收敛更快，但每一步需要计算并求解 Hessian 相关线性系统，计算代价更高；当 Hessian 不正定时，还需要阻尼、修正 Hessian 或使用拟牛顿方法。

有约束最小化

有约束优化需要在下降目标函数的同时保持可行性。课件重点讨论不等式约束问题：

$$\begin{aligned} \min_x \quad & f_0(x) \\ \text{s.t.}\quad & f_i(x)\le 0,\quad i=1,\dots,m \\ & Ax=b \end{aligned}$$

其中 $f_i$ 通常假设为凸且二阶连续可微。处理约束的基本思路是把约束影响并入目标函数：罚函数法允许暂时违反约束，但对违反约束的点施加惩罚；内点法则让迭代点始终留在可行域内部，并通过障碍项阻止它越过边界。

指示函数与罚函数

不等式约束 $f_i(x)\le 0$ 可以用指示函数写进目标函数。定义 $I_-(u)=0$ 当 $u\le 0$，$I_-(u)=+\infty$ 当 $u>0$。原问题可以等价改写为：

$$\begin{aligned} \min_x \quad & f_0(x)+\sum_{i=1}^m I_-(f_i(x)) \\ \text{s.t.}\quad & Ax=b \end{aligned}$$

该形式准确表达了“违反约束不可接受”，但 $I_-$ 不连续且不可微，不能直接配合梯度下降或牛顿法。因此需要用可微函数近似它，形成罚函数法或障碍函数法。二次罚函数法通常对违反约束的程度加二次惩罚；对数障碍函数则只在可行域内部定义，用于内点法。

对数障碍函数

对数障碍函数用 $-\mu\log(-u)$ 近似指示函数 $I_-(u)$，其中 $\mu>0$ 控制近似精度。由于定义域要求 $u<0$，所以它会把迭代点限制在严格可行域内部。对原问题中的约束 $f_i(x)\le 0$，障碍项为：

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

当 $x$ 接近某个约束边界时，$f_i(x)\to 0^-$，于是 $-\log(-f_i(x))\to+\infty$，目标函数会产生很大的惩罚，阻止迭代点越过边界。

中心路径与内点法

使用对数障碍函数后，可以把不等式约束问题近似为只带等式约束的问题：

$$\begin{aligned} \min_x \quad & f_0(x)+\mu\phi(x) \\ \text{s.t.}\quad & Ax=b \end{aligned}$$

当 $\mu$ 较大时，障碍项影响强，解会远离边界；当 $\mu\to 0$ 时，障碍项影响逐渐减弱，近似问题的解会逼近原约束问题的最优解。但 $\mu$ 越小，目标函数在边界附近越陡，用牛顿法求解也越困难。

内点法的策略是路径跟踪：先取较大的 $\mu$ 求解一个容易的问题，再逐步减小 $\mu$，例如令 $\mu:=\beta\mu$ 且 $0<\beta<1$，每次以上一轮解作为下一轮初始点。由不同 $\mu$ 对应的最优解 $x^\star(\mu)$ 构成的集合称为中心路径。

内点法之所以称为 interior point method，是因为迭代点始终位于可行域内部，不直接在边界或顶点之间跳转。它与单纯形法的几何路径不同：单纯形法沿多面体顶点移动，内点法则沿中心路径从可行域内部逼近最优边界。

最优性条件补充

带约束凸优化常用 KKT 条件刻画最优解。对约束 $f_i(x)\le 0$ 和 $h_j(x)=0$，拉格朗日函数为 $\mathcal{L}(x,\lambda,\nu)=f_0(x)+\sum_i\lambda_i f_i(x)+\sum_j\nu_j h_j(x)$，其中 $\lambda_i\ge 0$。KKT 条件包括原问题可行性、对偶可行性、驻点条件 $\nabla_x\mathcal{L}(x^\star,\lambda^\star,\nu^\star)=0$，以及互补松弛 $\lambda_i^\star f_i(x^\star)=0$。在满足正则条件的凸问题中，KKT 条件既是必要条件，也是充分条件。