六、梯度分析与最优化问题
最优化问题是信息科学中经常遇到的一类问题,无约束最优化问题:
目标函数的极小化
定义1.1点
大多数最优化算法只能求出局部极小点,也就是说求得函数在该邻域内的最小值。
定义1.2给定一个点
推广到向量
定义1.3点
定义1.4点
局部极小点和严格局部极小点有时也分别称为函数
如果函数具有连续的二阶导数,那么在
作为函数
满足
如果函数
若没有第二个方程,则第一个方程的解只是平稳点。以上两个方程只是目标函数取局部极小点的充分条件,而不是必要条件(求局部极大值类似)。
设
函数
称为凸函数,对任意选择的点 及标量 ,满足函数
称为严格凸函数,对任意选择的点 及标量 ,满足函数
称为(严格)凹函数,若 为(严格)凸函数。
实值函数相对于实向量的梯度
以
梯度方向的负方向称为变元
从梯度的定义可以看出:
一个以向量为变元的标量函数的梯度为一向量;
梯度的每个分量给出了标量函数在该分类方向上的变化率;
类似地,实值函数
向量函数的两个特例:
- 若
向量函数 ,其中 是 的标量函数,则一阶梯度为
称为向量函数
的Jacobi矩阵。若
,则
实值函数
若
为常数,则梯度 ;线性法则: 若
和 都是向量 的实值函数, 为实常数,则
.
乘法法则:若
和 都是向量 的实值函数,则
- 商法则:若
,则
- 链式法则:若
是 的向量值函数,则
式中
为 矩阵。若
向量 是常量向量,与向量 无关,则
- 若
向量 是常数向量,与向量 无关,则
- To be continued...
迹函数的梯度矩阵
二次型目标函数的迹等于函数本身,即
迹的梯度矩阵的常用公式:
- 单个矩阵的迹的梯度矩阵,
是 矩阵时,有 是 可逆矩阵时,对于两个向量的外积,有
- 两个矩阵乘积的迹的梯度,若
则
- 特别地当
为对称矩阵,有
- 若
则
若
,则若
,则若
,并且 非奇异,则
- 三个矩阵乘积的迹的矩阵
若
则特别地,当
为对称矩阵时,有 .若
则
当
为对称矩阵时,若
,并且 非奇异时,则有
Hessian矩阵
实值函数
或者简写为梯度的梯度
其中
所以当
局部极小点的条件
如果
下面介绍判断一个局部极小点的条件。
定理8.1(一阶必要条件) 若
定理6.2(二阶必要条件)若
其中
定理6.3(二阶充分条件)假设
则
定理6.4凸函数
当
考虑一个特殊的优化问题,所谓线性约束的二次规划问题
满足约束条件
其中
利用Lagrange乘子法,定义目标函数
则有
也就是最优解
令
其中
这里矩阵
称为Karush-Kuhn-Tucker(KKT)矩阵,方程组(7.4)称为KKT系统,有时也称为鞍点问题(系统)。所以解二次规划问题的核心就转化为如何求解对称不定问题(7.4)。
主要介绍以下几种方法
- 秩空间方法
- 假设系数矩阵
和子矩阵 均非奇异,则根据分块矩阵求逆的公式可以求出KKT矩阵的逆矩阵为
- 其中
解方程组(1)即得
从而得到二次规划问题的解为 , 为 的任一解。这个方法的缺点是需要多次矩阵求逆和矩阵相乘。由于假设
非奇异, 行满秩,故 非奇异,这样我们用 左乘(7.4)的第一个方程,然后减去第二个方程得
- 解得
,然后代入第一个方程得到
- 解得向量
. 这一方法称为秩空间方法。
- 对称不定分解方法
由于KKT系统的系数矩阵
是非奇异的对称不定矩阵,这时有对称不定矩阵分解,其中
为排列矩阵, 为单位下三角矩阵, 为块对角矩阵,其每个子块为 或者 矩阵。 这样
原方程组就变为
这样,得到用对称不定分解求KKT系统的算法:
- 利用(7.6)构造矩阵
,对 作对称不定分解,得到排列矩阵 ,单位下三角矩阵 ,对角块矩阵 ,使得
- 利用(7.6)构造矩阵
解
,得到 ;解
得到 ;解
得到 ;KKT系统的解为
- 对称不定矩阵的广义Cholesky分解
- 假设
是对称正定矩阵, 为行满秩矩阵,这时KKT系统的系数矩阵 为对称不定矩阵。由于矩阵 为对称正定,故 有Cholesky分解
,
为 的下三角矩阵。令
,故 .这就推得 是 对称正定矩阵,故存在Cholesky分解,即 ,其中 是 下三角矩阵。综合起来得
这就称为对称不定矩阵的广义Cholesky分解.
完成以上的分解后,就能由下列两个步骤解方程组(7.4):
由
解得 .由
,解得
这个方法可以推广到更一般的情况,即
其中
的假设与前面相同, 为对称正定矩阵。类似前面的广义Cholesky分解,可以得到下列分解式
由
得到 下三角矩阵 ;由
得到 ;由对称正定矩阵
的holesky分解得到 的下三角矩阵 :