等式约束优化 | 彩潭有鲤的札记

有约束非线性优化问题

其中，。

利用向量进行表示，可写为如下所示的标准型：其中，。

满足所有约束条件的点称为可行点，所有可行点组成的集合称为可行集

极大化问题可转化为极小划问题

这里讨论仅含等式约束的优化问题：

其中，。

对于满足约束的点，如果梯度向量是线性无关的，则称点为该约束的一个正则点。其中假定函数连续可微，即。

令为向量在处的雅可比矩阵：

则，当且仅当（即雅可比矩阵行满秩）时，是正则的。

线性约束的集合定义的是一个曲面：如果上的所有点都是正则点，则曲面的维数为。

曲面上的曲线，是由连续参数化的一组点构成的集合，即是连续函数。

由曲线定义可知，曲线上的所有点都满足曲面方程。如果曲线通过一个点，则必然存在，使得。

可以把曲线当作某个点在曲面上运动时经过点的路径，表示点在时刻的位置。

如果对于所有，都存在，则曲线线性可微

如果对于所有，都存在，则曲线二次可微

和均是维向量。可以把和分别视为运动路径为的某个点在时刻的速度和加速度。向量指向的瞬时运动方向。因此向量在处与曲线相切。

曲面中的点处的切线空间为集合

切线空间是矩阵的零空间

因此，切线空间是的子空间。

假设是正则点，则切线空间的维数为，是等式约束的数量。切线空间经过原点，但常被描绘为一个经过点的平面。点处的切平面定义为

假设是一个正则点且是处的切线空间，当且仅当曲面中存在一条经过点的可微曲线，其在处的导数为时，有成立。

曲面中的点处的法向量空间定义为

法线空间可表示为即法线空间是矩阵的值域。

法线空间是由向量张成的子空间，即：

当是正则点时，法线空间的维数为。

处的法平面为

切线空间和法线空间互为正交补。

可以对进行直和分解即对于任意向量，存在仅有的一对向量和，使得。

令为约束函数，已知函数定义域中的点处的梯度与通过该点的水平集正交。选择点，使得，且，经过点的水平集为集合。

利用曲线在邻域内对水平集进行参数化，为一个连续可微的向量函数

由于在曲线上是常数，即对于任意，有：因此，对于任意有：

利用链式法则，可得：因此，，即与正交。

构造关于的复合函数

该函数在时取得极小值。根据无约束极值问题的一阶必要条件可知

利用链式法则，可得因此，与正交。

由于与曲线在点处相切，因此与曲线在点处正交。

由于，与正交，且与正交，因此与平行，即等于与一个标量之积。

设点是函数的一个极小点，约束条件是，那么与平行，即如果，则存在标量，使得其中，称为拉格朗日乘子。

拉格朗日定理是局部极小点的一阶必要条件，即拉格朗日条件，包括两个方程:

拉格朗日条件是必要条件而不是充分条件

推广到一般情况，设点是函数的一个极小点，约束条件是。如果是正则点，那么存在，使得

拉格朗日定理表明，如果是极值点，则目标函数在该点处梯度可表示为关于约束函数在该点处梯度的线性组合。向量称为拉格朗日乘子向量，其组成元素称为拉格朗日乘子。

拉格朗日条件更加紧凑的形式是。如果不满足这一条件，那么不是极值点。需要注意的是，正则性是拉格朗日定理的必需假设，该假设的作用至关重要。

引入拉格朗日函数

可利用拉格朗日函数表示局部极小点的拉格朗日条件，即存在一个向量，满足。拉格朗日定理给定的必要条件，等价于将拉格朗日方程视为无约束优化问题的目标函数对应的一阶必要条件。

令表示关于的导数，表示关于的导数

有，，局部极小点的拉格朗日条件可以表达为存在，满足即

这说明拉格朗日条件确实可以写为

通过求解拉格朗日条件

可找出可能的极值点。。这一方程组包括个方程和个未知数。注意：拉格朗日条件是必要非充分条件，即满足上述方程的点不一定是极值点。

例：考虑约束集为椭圆的优化问题，求目标函数的极值。

目标函数和约束条件函数的梯度分别为：代入拉格朗日条件，可得令和，可得 3 个方程组成的方程组：方程组包括 3 个末知数。可以证明，所有可行点都是正则点。根据第 1 个方程，可得或。当时，根据第2个和第3个方程可得。当时，由第2个和第3个方程可得和。由此可得所有满足拉格朗日极值条件的点由于

因此，如果存在极小点，那么就是和；如果存在极大点，就是和。实际上，和的确是极小点，而和是极大点。

已知和是二次连续可微函数，即。

拉格朗日函数为：

记是关于的黑塞矩阵：其中，是在处的黑塞矩阵；是在处的黑塞矩阵

记：

可将拉格朗日函数写为

二阶必要条件 设是在约束条件下的局部极小点。如果是正则点，那么存在使得

二阶充分条件 函数，如果存在点和使得

那么，是在约束条件下的严格局部极小点。

考虑优化问题：

其中。此问题是二次规划的一个特例（一般形式的二次规划问题还包括约束），这一约束集包括无限多个可行点。利用拉格朗日定理可以证明，该优化问题存在唯一解

构造拉格朗日函数

导出拉格朗日条件

整理得

等式两边同时左乘矩阵，有

由于，且的秩为，可得

由此可得

由于拉格朗日函数在处的黑塞矩阵黑塞矩阵正定，因此是严格局部极小点。实际上也是全局极小点。

问题描述

切线空间和法线空间

切线空间

法线空间

拉格朗日条件

时的拉格朗日定理

拉格朗日定理

二阶条件

线性约束下二次型函数的极小化