优化是机器学习流程中的核心环节，它直接影响模型最佳参数的求解质量。本教程将系统介绍优化问题的基本概念、凸优化的关键特性，并深入讲解拉格朗日乘子法这一强大工具。通过理论与实践相结合，你将掌握如何利用这些方法高效解决带约束的优化问题。
优化问题
优化问题通常定义为：
优化问题包含一个目标函数以及可选的不等式约束和等式约束。一般的优化问题属于NP难问题，但许多类别的凸优化问题可以在多项式时间内求解。
凸函数与凸集
当我们将f(x₁)和f(x₂)相连形成下方红线时，如果f是一个凸函数，那么对于它们之间的任意点，红线始终位于f的上方，即 yᵢ ≥ f(xᵢ)。
一个凸优化问题具有凸目标函数和凸可行集的特征。可行集是满足所有约束条件的x的集合。在凸集中，集合内任意两点之间的任何值也必须属于该凸集。
凸优化问题的数学形式
从另一个角度看，在凸优化问题中，f和l是凸函数，
并且等式约束是仿射函数，其一般形式为：
提示：仿射函数本身也是凸函数，这一性质在后续的拉格朗日乘子法中会用到。
机器学习中的常见优化模型
最小二乘优化
在机器学习中，线性回归的目标函数通常表示为最小二乘误差。最小二乘优化问题已被广泛研究。除非遇到可扩展性限制，否则它们可以通过解析方法（如正规方程）直接求解，这类问题在优化领域相对容易处理。
线性规划
如果机器学习问题可以转化为线性规划问题，我们就能直接应用成熟的线性规划解法。这也是一类研究充分的优化模型。线性规划中x的可行集是一个多面体。
在上面的例子中，虚线表示目标函数的等高线，最优解x*出现在其中一个顶点上。
一般来说，如果问题是凸优化问题，我们可以通过数值方法求解。一个函数是凸函数，当且仅当它的二阶导数对于所有x都是非负的。
在机器学习中，我们经常将原本复杂的问题通过转换、近似或松弛处理，归约为上述更简单的优化模型之一。
拉格朗日乘子法
现在让我们专注于寻找一般优化问题的解。考虑代价函数为f=x+y，等式约束为h: x² + y² = 25，如下图所示红色圆圈。
为了满足约束条件，我们沿着约束面法线的正交方向移动，即垂直于∇x h。为了降低代价，我们选择沿着f的负梯度方向移动。当无法进一步降低代价时，就达到了最优点。这发生在∇h与代价函数的梯度方向对齐时。
即：
h(x) = 0也意味着-h(x) = 0。λ的符号取决于h的定义方式，因此λ可以是正数、负数或零。
拉格朗日函数的定义
接下来，我们定义拉格朗日函数为：
如果我们分别对拉格朗日函数关于x和λ求导，并将它们设为零，如下所示，就能同时满足前面描述的最优点条件以及等式约束。
因此，通过找到关于x和λ的拉格朗日函数的最优点，我们可以确定在强制执行等式约束情况下的最优解。拉格朗日函数也可以包含多个约束以及不等式约束。优化问题的形式可写为：
拉格朗日函数的定义如下：
不等式约束的处理
现在不等式约束要求最优点位于阴影区域内（包括边界）。当解达到最优时，f和l的梯度方向相同，即αᵢ ≥ 0。
让我们再对不等式约束进行另一种观察。下面的左图表示一个代价函数f，其最优解位于圆圈中心。
在中间的图中，我们为优化问题添加了一个不等式约束。但这个约束是多余的，因为无约束最优点已经满足该约束条件。因此，αᵢ可以简单地取为零，表示约束不起作用。
在右边的图中，无约束最优解落在约束l的外部。我们必须增加代价（红色圆圈）直到它与l相交。此时对应的最低代价会使约束l恰好等于0。
因此，αᵢ lⱼ(x) 总是等于0。
实际例子：最大化 f(x, y) = x + y，满足 x² + y² = 32
拉格朗日函数为：
为了求解这个优化问题，我们需要分别对x、y和λ求偏导并设为零：
- ∂L/∂x = 1 + 2λx = 0 → x = -1/(2λ)
- ∂L/∂y = 1 + 2λy = 0 → y = -1/(2λ)
- ∂L/∂λ = x² + y² - 32 = 0
将x和y代入第三个方程：( (-1/(2λ))² + (-1/(2λ))² ) = 32 → 2/(4λ²) = 32 → 1/(2λ²) = 32 → λ² = 1/64 → λ = ±1/8。取λ = -1/8（此时x和y为正，实际计算可得x=y=4，满足约束）。最优解为x=4,y=4，最大值为8。
提示：拉格朗日乘子法不仅适用于等式约束，也能推广到不等式约束（即KKT条件），在求解带约束的机器学习模型时经常被使用。
常见问题
Q1: 如何判断一个优化问题是否是凸优化问题？
需要满足三个条件：① 目标函数是凸函数；② 不等式约束函数是凸函数；③ 等式约束函数是仿射函数。此外，可行集必须是凸集。常见的凸函数包括线性函数、二次型（半正定矩阵）、指数函数等。
Q2: 拉格朗日乘子法中的λ可以是负数吗？
可以。对于等式约束，λ可以是正、负或零，其符号取决于约束函数h的定义方式（例如h(x)=0与-h(x)=0等价）。对于不等式约束，对应的乘子αᵢ必须满足非负条件（αᵢ ≥ 0），这是KKT条件的一部分。
Q3: 当约束是多余时，拉格朗日乘子为什么是0？
因为无约束最优解已经满足该约束，约束实际上不起作用，乘子αᵢ自然为零。此时互补松弛条件αᵢ lⱼ(x)=0依然成立。
总结
本教程从优化问题的基本定义出发，介绍了凸优化的核心概念，并深入讲解了拉格朗日乘子法在等式和不等式约束下的应用。通过实例计算，你将能够熟练运用这些方法解决机器学习中的常见优化问题。下一部分我们将继续探讨对偶分解方法，进一步拓展你的优化工具集。