数学优化

数学优化（Mathematical Optimization）问题，也叫最优化问题，是指在一定约束条件下，求解一个目标函数的最大值（或最小值）问题．数学优化问题的定义为：给定一个目标函数（也叫代价函数）𝑓 ∶ 𝒜 → ℝ，寻找一个变量（也叫参数）𝒙∗ ∈ 𝒟 ⊂ 𝒜，使得对于所有 𝒟 中的 𝒙，都满足𝑓(𝒙∗ ) ≤ 𝑓(𝒙)（最小化）；或者𝑓(𝒙∗ ) ≥ 𝑓(𝒙)（最大化），其中𝒟 为变量𝒙的约束集，也叫可行域；𝒟 中的变量被称为是可行解．

1. 数学优化的类型

1.1 离散优化和连续优化

根据输入变量 𝑿 的值域是否为实数域，数学优化问题可以分为离散优化问题和连续优化问题．

1.1.1 离散优化问题

离散优化（Discrete Optimization）问题是目标函数的输入变量为离散变量，比如为整数或有限集合中的元素．离散优化问题主要有两个分支：

（1） 组合优化（Combinatorial Optimization）：其目标是从一个有限集合中找出使得目标函数最优的元素．在一般的组合优化问题中，集合中的元素之间存在一定的关联，可以表示为图结构．典型的组合优化问题有旅行商问题、最小生成树问题、图着色问题等．很多机器学习问题都是组合优化问题，比如特征选择、聚类问题、超参数优化问题以及结构化学习（Structured Learning）中标签预测问题等．

（2） 整数规划（Integer Programming）：输入变量 𝒙 ∈ ℤ𝐷 为整数向量．常见的整数规划问题通常为整数线性规划（Integer Linear Programming，ILP） ．整数线性规划的一种最直接的求解方法是：1）去掉输入必须为整数的限制，将原问题转换为一般的线性规划问题，这个线性规划问题为原问题的松弛问题；2）求得相应松弛问题的解；3）把松弛问题的解四舍五入到最接近的整数．但是这种方法得到的解一般都不是最优的，因为原问题的最优解不一定在松弛问题最优解的附近．另外，这种方法得到的解也不一定满足约束条件．

离散优化问题的求解一般都比较困难，优化算法的复杂度都比较高．

1.1.2 连续优化问题

连续优化（Continuous Optimization）问题是目标函数的输入变量为连续变量𝒙 ∈ ℝ𝐷，即目标函数为实函数．本节后面的内容主要以连续优化为主．

1.2 无约束优化和约束优化

在连续优化问题中，根据是否有变量的约束条件，可以将优化问题分为无约束优化问题和约束优化问题．无约束优化（Unconstrained Optimization） 问题的可行域通常为整个实数域𝒟 = ℝ𝐷，可以写为

min 𝒙 𝑓(𝒙),

其中𝒙 ∈ ℝ𝐷 为输入变量，𝑓 ∶ ℝ𝐷 → ℝ为目标函数．

约束优化（Constrained Optimization）问题中变量𝒙需要满足一些等式或不等式的约束．约束优化问题通常使用拉格朗日乘数法来进行求解．

1.3 线性优化和非线性优化

如果在公式 (C.1) 中，目标函数和所有的约束函数都为线性函数，则该问题为线性规划（Linear Programming）问题．相反，如果目标函数或任何一个约束函数为非线性函数，则该问题为非线性规划（Nonlinear Programming）问题．在非线性优化问题中，有一类比较特殊的问题是凸优化（Convex Optimization）问题．在凸优化问题中，变量 𝒙 的可行域为凸集（Convex Set），即对于集合中任意两点，它们的连线全部位于集合内部．目标函数 𝑓 也必须为凸函数，即满足

凸优化问题是一种特殊的约束优化问题，需满足目标函数为凸函数，并且等式约束函数为线性函数，不等式约束函数为凸函数．

2. 优化算法

优化问题一般都可以通过迭代的方式来求解：通过猜测一个初始的估计𝒙0，然后不断迭代产生新的估计 𝒙1 , 𝒙2 , ⋯ 𝒙𝑡，希望 𝒙𝑡 最终收敛到期望的最优解 𝒙∗．

一个好的优化算法应该是在一定的时间或空间复杂度下能够快速准确地找到最优解．同时，好的优化算法受初始猜测点的影响较小，通过迭代能稳定地找到最优解𝒙∗ 的邻域，然后迅速收敛于𝒙∗．

优化算法中常用的迭代方法有线性搜索和置信域方法等．线性搜索的策略是寻找方向和步长，具体算法有梯度下降法、牛顿法、共轭梯度法等．

2.1 全局最小解和局部最小解

对于很多非线性优化问题，会存在若干个局部最小值（Local Minima），其对应的解称为局部最小解（Local Minimizer）． 局部最小解𝒙∗ 定义为：存在一个𝛿 > 0，对于所有的满足‖𝒙 − 𝒙∗‖ ≤ 𝛿 的𝒙，都有 𝑓(𝒙∗ ) ≤ 𝑓(𝒙)．也就是说，在𝒙∗的邻域内，所有的函数值都大于或者等于𝑓(𝒙∗)．对于所有的 𝒙 ∈ 𝒟，都有 𝑓(𝒙∗ ) ≤ 𝑓(𝒙) 成立，则 𝒙∗ 为全局最小解（Global Minimizer）．

求局部最小解一般是比较容易的，但很难保证其为全局最小解．对于线性规划或凸优化问题，局部最小解就是全局最小解．

要确认一个点 𝒙∗ 是否为局部最小解，通过比较它的邻域内有没有更小的函数值是不现实的．如果函数𝑓(𝒙)是二次连续可微的，我们可以通过检查目标函数在点𝒙∗ 的梯度∇𝑓(𝒙∗)和Hessian矩阵∇2𝑓(𝒙∗)来判断．

证明*.* 如果函数 𝑓(𝒙) 是连续可微的，根据泰勒公式（Taylor’s Formula），函数𝑓(𝒙)的一阶展开可以近似为

假设∇𝑓(𝒙∗ ) ≠ 0，则可以找到一个 Δ𝒙（比如 Δ𝒙 = −𝛼∇𝑓(𝒙∗)，𝛼 为很小的正数），使得

这和局部最小的定义矛盾．

函数 𝑓(𝒙) 的一阶偏导数为 0 的点也称为驻点（Stationary Point）或临界点（Critical Point）．驻点不一定为局部最小解．

证明*.* 如果函数𝑓(𝒙)是二次连续可微的，函数𝑓(𝒙)的二阶展开可以近似为

由一阶必要性定理可知∇𝑓(𝒙∗ ) = 0，则

即∇2𝑓(𝒙∗)为半正定矩阵．

2.2 梯度下降法

梯度下降法（Gradient Descent Method），也叫作最速下降法（Steepest Descend Method），经常用来求解无约束优化的最小值问题．

对于函数𝑓(𝒙)，如果𝑓(𝒙)在点𝒙𝑡 附近是连续可微的，那么𝑓(𝒙)下降最快的方向是 𝑓(𝒙)在𝒙𝑡 点的梯度方法的反方向．

根据泰勒一阶展开公式，有

要使得 𝑓(𝒙𝑡+1) < 𝑓(𝒙𝑡)，就得使 Δ𝒙T∇𝑓(𝒙𝑡 ) < 0．我们取Δ𝒙 = −𝛼∇𝑓(𝒙𝑡)．如果𝛼 > 0为一个够小数值时，那么 𝑓(𝒙𝑡+1) < 𝑓(𝒙𝑡)成立．

这样我们就可以从一个初始值𝒙0 出发，通过迭代公式

生成序列 𝒙0 , 𝒙1 , 𝒙2, ⋯ 使得

如果顺利的话，序列 (𝒙𝑛)收敛到局部最小解𝒙∗．注意，每次迭代步长 𝛼 可以改变，但其取值必须合适，如果过大就不会收敛，如果过小则收敛速度太慢．梯度下降法的过程如图C.1所示．曲线是等高线（水平集），即函数𝑓 为不同常数的集合构成的曲线．红色的箭头指向该点梯度的反方向（梯度方向与通过该点的等高线垂直）．沿着梯度下降方向，将最终到达函数𝑓 值的局部最小解．

梯度下降法为一阶收敛算法，当靠近局部最小解时梯度变小，收敛速度会变慢，并且可能以“之字形”的方式下降．如果目标函数为二阶连续可微，我们可以采用牛顿法．牛顿法（Newton’s method）为二阶收敛算法，收敛速度更快，但是每次迭代需要计算Hessian矩阵的逆矩阵，复杂度较高．相反，如果我们要求解一个最大值问题，就需要向梯度正方向迭代进行搜索，逐渐接近函数的局部最大解，这个过程则被称为梯度上升法（Gradient Ascent Method）．

3. 拉格朗日乘数法与KKT条件

拉格朗日乘数法（Lagrange Multiplier） 是一种有效求解约束优化问题的优化方法．

约束优化问题可以表示为

其中ℎ𝑚(𝒙)为等式约束函数，𝑔𝑛(𝒙)为不等式约束函数．𝒙的可行域为

其中dom(𝑓)是函数𝑓 的定义域．

3.1 等式约束优化问题

如果公式(C.10)中只有等式约束，我们可以构造一个拉格朗日函数Λ(𝒙, 𝜆)

其中 𝜆 为拉格朗日乘数，可以是正数或负数．如果 𝑓(𝒙∗) 是原始约束优化问题的局部最优值，那么存在一个𝜆∗ 使得(𝒙∗ , 𝜆∗)为拉格朗日函数Λ(𝒙, 𝜆)的驻点．因此，只需要令 𝜕Λ(𝒙,𝜆)/𝜕𝒙= 0和 𝜕Λ(𝒙,𝜆)/𝜕𝜆= 0，得到

上面方程组的解即为原始问题的可能解．因为驻点不一定是最小解，所以在实际应用中需根据具体问题来验证是否为最小解．

拉格朗日乘数法是将一个有𝐷个变量和𝑀 个等式约束条件的最优化问题转换为一个有 𝐷 + 𝑀 个变量的函数求驻点的问题．拉格朗日乘数法所得的驻点会包含原问题的所有最小解，但并不保证每个驻点都是原问题的最小解．

3.2 不等式约束优化问题

对于公式(C.10)中定义的一般约束优化问题，其拉格朗日函数为

其中𝒂 = [𝑎1 , ⋯ , 𝑎𝑀]T 为等式约束的拉格朗日乘数，𝒃 = [𝑏1 , ⋯ , 𝑏𝑁 ]T 为不等式约束的拉格朗日乘数．

当约束条件不满足时，有 max𝒂,𝒃 Λ(𝒙, 𝒂, 𝒃) = ∞；当约束条件满足时并且𝒃 ≥ 0时，max𝒂,𝒃 Λ(𝒙, 𝒂, 𝒃) = 𝑓(𝒙)．因此，原始约束优化问题等价于

这个min-max优化问题称为主问题（Primal Problem）．

对偶问题 主问题的优化一般比较困难，我们可以通过交换 min-max 的顺序来简化．定义拉格朗日对偶函数为

Γ(𝒂, 𝒃)是一个凹函数，即使𝑓(𝒙)是非凸的． 当𝒃 ≥ 0时，对于任意的 ̃ 𝒙 ∈ 𝒟，有

令𝒑∗ 是原问题的最优值，则有

即拉格朗日对偶函数Γ(𝒂, 𝒃)为原问题最优值的下界．

优化拉格朗日对偶函数 Γ(𝒂, 𝒃) 并得到原问题的最优下界，称为拉格朗日对偶问题（Lagrange Dual Problem）．

拉格朗日对偶函数为凹函数，因此拉格朗日对偶问题为凸优化问题．

令𝒅∗ 表示拉格朗日对偶问题的最优值，则有𝒅∗ ≤ 𝒑∗，这个性质称为弱对偶性（Weak Duality）．如果𝒅∗ = 𝒑∗，这个性质称为强对偶性（Strong Duality）．

当强对偶性成立时，令𝒙∗ 和𝒂∗, 𝒃∗ 分别是原问题和对偶问题的最优解，那么它们满足以下条件：

这 5 个条件称为不等式约束优化问题的KKT 条件（Karush-Kuhn-Tucker Condition）．KKT 条件是拉格朗日乘数法在不等式约束优化问题上的泛化．当原问题是凸优化问题时，满足KKT条件的解也是原问题和对偶问题的最优解． 在KKT条件中，需要关注的是公式(C.26)，称为互补松弛（ComplementarySlackness）条件．如果最优解 𝒙∗ 出现在不等式约束的边界上 𝑔𝑛(𝒙) = 0，则𝑏∗𝑛 > 0；如果最优解𝒙∗ 出现在不等式约束的内部𝑔𝑛(𝒙) < 0，则𝑏∗𝑛 = 0．互补松弛条件说明当最优解出现在不等式约束的内部，则约束失效．