非线性规划——等式约束的最优化方法（四）-526互联

对非线性规划来说，大多数情况下我们是不可能无限制求其理想情况下的最优值的，总是存在一些约束生成了一部分可行解域。从机器学习上来说，我们的可行解域就被限制住了，直接求解起来事实上是有一定困难的，我们更希望求解的是无约束的优化问题，就衍生出拉格朗日乘子法。拉格朗日乘子法主要用于解决约束优化问题，它的基本思想就是通过引入拉格朗日乘子来将含有$n$个变量和$k$个约束条件的约束优化问题转化为含有$n+k$个变量的无约束优化问题。总的思想是**将等式约束条件代入目标函数，把约束优化问题转化为无约束优化问题。

一、等式约束的最优化模型

等式约束问题

\begin{array}{ll} \underset{\boldsymbol{x}}{\operatorname{minimize}} & f(\boldsymbol{x}) \\ \text { subject to } & g_i(\boldsymbol{x}) = 0, i=1,2, \cdots, m \end{array}

假设优化变量是$x_1$和$x_2$，图中的蓝色虚线是目标函数$f(x_1, x_2)$的等高线，其中$d_1>d_2>d_3$，绿线代表了约束条件 $h(x_1,x_2)$= 0。这个优化问题的解$x_1^*$和$x_2^*$ 一定满足$h(x_1^*,x_2^*) = 0$，所以解 $x_1^*$和$x_2^*$一定在绿线上。我们可以看到，绿线和三条等高线都有交点，而我们要求的是能使目标函数最小的点，那么绿线上的那个点才是优化问题的解呢？
我们来看绿线和蓝色等高线的关系，绿线和某条蓝色等高线可能相交、相切或者没有交点。没有交点当然就代表没有解啦。如果相交的话，说明绿线上存在点在这条等高线的内部和外部，也就说明存在点使得目标函数的值更大或者更小，所以相交的情况也不会是优化问题的可行解。所以就只剩下了相切的情况，可能会是优化问题可行解。如果代表约束条件的绿线和某条蓝色等高线相切，那么它们的切线相同，且法向量是相互平行的，这样就可以得到：

\[\nabla_x f(x)+\lambda \nabla_xh(x)=0 \\ \nabla_x f(x)+\lambda \nabla_xh(x)=0 \]

即目标函数和约束条件中的函数关于$x$的偏导数的方向是平行的，这就是拉格朗日函数$L(x, \lambda)$ 求解无约束优化问题的数学基础。

二、拉格朗日乘数法

作拉格朗日函数

\[L(\boldsymbol{x},\boldsymbol{\lambda}) = f(\boldsymbol{x}) - \sum_{i=1}^m\lambda_ih_i(\boldsymbol{x}) \]

拉格朗日定理（一阶必要条件）：假设 $\boldsymbol{x}^*$ 是上述等式约束优化问题的局部极小值点，若向量组

\[\nabla g_i(\boldsymbol{x^*})(i=1,2,...,m) \]

线性无关，则存在乘子向量 $\boldsymbol{\lambda}^*$，使得 $$\nabla_x L\left(x^*, \lambda^*\right)=0$$，即

\[\nabla f\left(\boldsymbol{x}^*\right)-\sum_{i=1}^m \lambda_i^* \nabla g_i\left(\boldsymbol{x}^*\right)=0 \]

上式为拉格朗日定理，描述了具有等式约束的优化问题取极小值的一阶必要条件，也就是通常所说的KKT条件。
当目标函数和约束条件的二阶连续可微时，我们还可以使用Lagrange函数的海塞矩阵来判断极值是否为极小值。Lagrange函数的二阶充分条件在实际问题中有着广泛的应用。例如，在机器学习中，我们经常需要求解带有约束条件的优化问题，例如支持向量机和逻辑回归。使用Lagrange函数的二阶充分条件可以帮助我们判断模型的最优解是否为极小值，从而提高模型的准确性和稳定性。

三、实例

例1：给定椭球 $\frac{\mathrm{x}^2}{\mathrm{a}^2}+\frac{\mathrm{y}^2}{\mathrm{~b}^2}+\frac{\mathrm{z}^2}{\mathrm{c}^2}=1$ ，求这个椭球的内接长方体的最大体积。
这个问题实际上就是条件极值问题，即在条件 $\frac{\mathrm{x}^2}{\mathrm{a}^2}+\frac{\mathrm{y}^2}{\mathrm{~b}^2}+\frac{\mathrm{z}^2}{\mathrm{c}^2}=1$ 下求 $f(x, y, z)=8 x y z$ 的最大值。
当然这个问题实际可以先根据条件消去 $\mathrm{z}$ ，然后带入转化为无条件极值问题来处理。但是有时候这样做很困难，甚至是做不到的，这时候就需要用拉格朗日乘数法了。通过拉格朗日乘数法将问题转化为:

\[\mathrm{L}(\mathrm{x}, \mathrm{y}, \mathrm{z}, \lambda)=\mathrm{f}(\mathrm{x}, \mathrm{y}, \mathrm{z})+\lambda \mathrm{g}(\mathrm{x}, \mathrm{y}, \mathrm{z})=8 \mathrm{xyz}+\lambda\left(\frac{\mathrm{x}^2}{\mathrm{a}^2}+\frac{\mathrm{y}^2}{\mathrm{~b}^2}+\frac{\mathrm{z}^2}{\mathrm{c}^2}-1\right) \]

对L $(\mathrm{x}, \mathrm{y}, \mathrm{z}, \lambda)$ 求偏导:

\[\begin{aligned} & \frac{\partial \mathrm{xL}(\mathrm{x}, \mathrm{y}, \mathrm{z}, \lambda)}{\partial \mathrm{x}}=8 \mathrm{yz}+\frac{2 \lambda \mathrm{x}}{\mathrm{a}^2}=0 \\ & \frac{\partial \mathrm{xL}(\mathrm{x}, \mathrm{y}, \mathrm{z}, \lambda)}{\partial \mathrm{y}}=8 \mathrm{xz}+\frac{2 \lambda \mathrm{y}}{\mathrm{b}^2}=0 \\ & \frac{\partial \mathrm{xL}(\mathrm{x}, \mathrm{y}, \mathrm{z}, \lambda)}{\partial \mathrm{z}}=8 \mathrm{xy}+\frac{2 \lambda \mathrm{z}}{\mathrm{c}^2}=0 \\ & \frac{\partial \mathrm{xL}(\mathrm{x}, \mathrm{y}, \mathrm{z}, \lambda)}{\partial \lambda}=\frac{\mathrm{x}^2}{\mathrm{a}^2}+\frac{\mathrm{y}^{2^2}}{\mathrm{~b}^2}+\frac{\mathrm{z}^2}{\mathrm{c}^2}-1=0 \\ & \text { 最终得到 } \mathrm{x}=\frac{\sqrt{3}}{3} \mathrm{a}, \mathrm{y}=\frac{\sqrt{3}}{3} \mathrm{~b}, \mathrm{z}=\frac{\sqrt{3}}{3} \mathrm{c} \\ & \text { 最大体积为 } \mathrm{V}_{\max }=\mathrm{f}\left(\frac{\sqrt{3}}{3} \mathrm{a}, \frac{\sqrt{3}}{3} \mathrm{~b}, \frac{\sqrt{3}}{3} \mathrm{c}\right)=\frac{8 \sqrt{3}}{9} \mathrm{abc} \\ & \end{aligned} \]

例2：求解下面非线性规划。

\[\begin{array}{l} \min f(X) = {x_1}^2 - {x_1}{x_2} + {x_2}^2 - 10{x_1} - 4{x_2} + 60\\ s.t.\;\;\;h(X) = {x_1} + {x_2} - 8 = 0 \end{array}\]

参考文献