0%

6-梯度分析于最优化问题

六、梯度分析与最优化问题

最优化问题是信息科学中经常遇到的一类问题,无约束最优化问题:

minxRf(x)

目标函数的极小化

定义1.1点x称为函数f(x)的全局极小点,若

f(x)f(x),xR

大多数最优化算法只能求出局部极小点,也就是说求得函数在该邻域内的最小值。

定义1.2给定一个点xR,则点x的(闭)邻域是满足|xx|δ(δ>0)的所有点x的集合。

推广到向量xRnΔ邻域。

定义1.3点x称为函数f(x)的局部极小点,若存在某个标量δ>0,使得f(x)f(x)对所有满足0<∥xx∥≤δ的邻域x均成立。

定义1.4点x称为函数f(x)的严格局部极小点,若存在某个标量δ>0,使得f(x)<f(x)对所有满足0<∥xx∥≤δ的邻域x均成立。

局部极小点和严格局部极小点有时也分别称为函数f(x)的弱局部极小点(weak local minimizer)和强局部极小点(strong local minimizer)。

如果函数具有连续的二阶导数,那么在x的一个很小的邻域Δx内,就可以用Taylor级数展开

f(x+Δx)=f(x)+f(x)Δx+12f(x)(Δx)2+

作为函数f(x+Δx)的逼近,其中f(x)=df(x)dxf(x)=d2f(x)dx2分别表示f(x)的一阶和二阶导数。由于Δx很小,式中忽略了Δx的高阶项。

满足f(x)=0的点x称为函数f(x)平稳点,它有可能是极小(大)点或拐点。

如果函数f(x)是二阶连续可微的,求该函数的局部极小点最基本的方法是逐次联合求解

f(x)=df(x)dx=0

f(x)=d2f(x)dx20

若没有第二个方程,则第一个方程的解只是平稳点。以上两个方程只是目标函数取局部极小点的充分条件,而不是必要条件(求局部极大值类似)。

f(x)是实值函数,则有以下定义:

  1. 函数f(x)称为凸函数,对任意选择的点x1,x2及标量α0,满足f(αx1+(1α)x2)αf(x1)+(1α)f(x2)

  2. 函数f(x)称为严格凸函数,对任意选择的点x1,x2及标量α0,满足f(αx1+(1α)x2)<αf(x1)+(1α)f(x2)

  3. 函数f(x)称为(严格)凹函数,若f(x)为(严格)凸函数。

实值函数相对于实向量的梯度

n×1实向量x为变元的实标量函数f(x)相对于x的梯度为一n×1列向量,定义为

Δxf(x)=[f(x)x1,f(x)x2,,f(x)xn]T=f(x)x

梯度方向的负方向称为变元x的梯度流,记作

x˙=Δxf(x)=f(x)x

从梯度的定义可以看出:

  1. 一个以向量为变元的标量函数的梯度为一向量;

  2. 梯度的每个分量给出了标量函数在该分类方向上的变化率;

类似地,实值函数f(x)相对于1×n行向量xT的梯度为1×n行向量,定义为:

f(x)xT=[f(x)x1,f(x)x2,,f(x)xn]

m维行向量函数F(x)=[f1(x),f2(x),,fm(x)]1×m相对于n维实向量x的梯度为一n×m矩阵,定义为:

F(x)x=[f1(x)x1f2(x)x1fm(x)x1f1(x)x2f2(x)x2fm(x)x2f1(x)xnf2(x)xnfm(x)xn]n×m

向量函数的两个特例:

  1. m×1向量函数f(x)=y=[y1,y2,,ym]T,其中y1,y2,,ymx的标量函数,则一阶梯度为

yxT=[y1x1y1x2y1xny2x1y2x2y2xnymx1ymx2ymxn]m×n

  1. 称为向量函数[y1,y2,,ym]TJacobi矩阵

  2. f(x)=(x1,x2,,xm)T,则f(x)x=xTx=I

实值函数f(x)相对于列向量x的下述一些常用的梯度公式:

  1. f(x)=c为常数,则梯度cx=0;

  2. 线性法则: 若f(x)g(x)都是向量x的实值函数,c1,c2为实常数,则

[c1f(x)+c2g(x)]x=c1f(x)x+c2g(x)x

  1. .

  2. 乘法法则:若f(x)g(x)都是向量x的实值函数,则

[f(x)g(x)]x=g(x)f(x)x+f(x)g(x)x

  1. 商法则:若g(x)0,则

[f(x)/g(x)]x=1g2(x)[g(x)f(x)xf(x)g(x)x]

  1. 链式法则:若y(x)x的向量值函数,则

f(y(x))x=yT(x)xf(y)y

  1. 式中yT(x)xn×n矩阵。

  2. n×1向量a是常量向量,与向量x无关,则

aTxx=a,xTax=a

  1. n×1向量a是常数向量,与向量x无关,则

aTy(x)x=yT(x)xa,yT(x)ax=yT(x)xa

  1. To be continued...

迹函数的梯度矩阵

二次型目标函数的迹等于函数本身,即f(x)=xTAx=tr(xTAx).利用迹的性质,又可以将目标函数进一步表示成

f(x)=xTAx=tr(xTAx)=tr(AxxT)

迹的梯度矩阵的常用公式:

  1. 单个矩阵的迹的梯度矩阵,
  • Wm×m矩阵时,有tr(W)W=Im

    Wm×m可逆矩阵时,tr(W1)W=(W2)T

    对于两个向量的外积,有

tr(xyT)x=tr(yTx)x=y

  1. 两个矩阵乘积的迹的梯度,若WRm×n,ARn×m,

tr(WA)W=tr(AW)W=AT

  • 特别地当W为对称矩阵,有

tr(WA)W=tr(AW)W=A+ATdiag(A)

  • WRm×n,ARn×m,

tr(WTA)W=tr(AWT)W=A

  • WRm×n,则tr(WWT)W=tr(WTW)W=2W

    WRm×m,则tr(W2)W=tr(WW)W=2WT

    W,ARm×m,并且W非奇异,则

tr(AW1)W=(W1AW1)T

  1. 三个矩阵乘积的迹的矩阵
  • WRm×n,ARm×m,tr(WTAW)W=(A+AT)W

    特别地,当A为对称矩阵时,有tr(WTAW)W=2AW.

    WRm×n,ARn×n,

tr(WTAW)W=W(A+AT)

  • A为对称矩阵时,tr(WTAW)W=2WA

    W,A,BRm×m,并且W非奇异时,则有

tr(AW1B)W=(W1BAW1)T

Hessian矩阵

实值函数f(x)相对于n×1实向量x的二阶梯度是一个由n2个二阶梯度组成的矩阵(称为Hessian矩阵),定义为

2f(x)xxTx[f(x)xT]

或者简写为梯度的梯度

x2f(x)=x(xTf(x))

其中(i,j)元素是

[2f(x)xxT]ij=2f(x)xixj

所以当xn×1的向量时,f(x)的二阶导数矩阵,也就是Hessian矩阵是n×n的对称的。

局部极小点的条件

如果Δx2=(Δx)T(Δx),则函数f(x)的Taylor级数展开为

f(x+Δx)f(x)+(Δx)Txf(x)+12(Δx)Tx2f(x)(Δx)

下面介绍判断一个局部极小点的条件。

定理8.1(一阶必要条件) 若x是一个局部极小点,并且f(x)在点x的一个开邻域Δx里是连续可微分的,则xf(x)=0.

定理6.2(二阶必要条件)若xf(x)的局部极小点,并且x2f(x)x的开邻域Δx内连续,则

xf(x)=0,x2f(x)0

其中x2f(x)0表示矩阵x2f(x)半正定。

定理6.3(二阶充分条件)假设f(x)x的开邻域内连续,并且

xf(x)=0,x2f(x)>0

x是函数f(x)的严格局部极小点。

定理6.4凸函数f(x)的任何局部极小点x都是该函数的一个全局极小点。若凸函数f(x)是可微分,则满足xf(x)=0的平稳点xf(x)的一个全局极小点。

An阶对称正定矩阵时,函数f(x)=xTAx是严格凸函数。

考虑一个特殊的优化问题,所谓线性约束的二次规划问题

minxRnJ(x)=12xTGx+xTd

满足约束条件

Ax=b

其中ARm×n,rank(A)=m,GRn×n为对称正定,这成为正定二次规划问题。

利用Lagrange乘子法,定义目标函数

q(x)=12xTGx+xTd+λT(bAx)

则有q(x)x=0q(x)λ=0,得到线性方程组

{GxATλ=dAx=b 

也就是最优解x,λ满足方程组

[GATA0][xλ]=[db]

xAx=b的任一解,则取x=x+p,则得

(7.4)[GATA0][pλ]=[hc]

其中c=Axb,h=d+Gx,p=xx

这里矩阵

(7.6)K=[GATA0]

称为Karush-Kuhn-Tucker(KKT)矩阵,方程组(7.4)称为KKT系统,有时也称为鞍点问题(系统)。所以解二次规划问题的核心就转化为如何求解对称不定问题(7.4)。

主要介绍以下几种方法

  1. 秩空间方法
  • 假设系数矩阵K和子矩阵G均非奇异,则根据分块矩阵求逆的公式可以求出KKT矩阵的逆矩阵为

[GATA0]1=[CEETF]

  • 其中

C=G1G1AT(AG1AT)1AG1

E=G1AT(AG1AT)1,F=(AG1AT)1

  • 解方程组(1)即得p=(Ch+Ec) 从而得到二次规划问题的解为x=p+xxAx=b的任一解。这个方法的缺点是需要多次矩阵求逆和矩阵相乘。

    由于假设G非奇异,A行满秩,故AGAT非奇异,这样我们用AG1左乘(7.4)的第一个方程,然后减去第二个方程得

(AG1AT)λ=(AG1)hc

  • 解得λ,然后代入第一个方程得到

Gp=ATλh

  • 解得向量p. 这一方法称为秩空间方法
  1. 对称不定分解方法
  • 由于KKT系统的系数矩阵K是非奇异的对称不定矩阵,这时有对称不定矩阵分解,PTKP=LBLT

    其中P为排列矩阵,L为单位下三角矩阵,B为块对角矩阵,其每个子块为1×1或者2×2矩阵。 这样

K=PLBLTPT

  • 原方程组就变为PLBLTPT[pλ]=[hc]

    这样,得到用对称不定分解求KKT系统的算法:

    1. 利用(7.6)构造矩阵K,对K作对称不定分解,得到排列矩阵P,单位下三角矩阵L,对角块矩阵B,使得

PTKP=LBLT

  1. Ly=PT[hc],得到y;

  2. By=y,得到y;

  3. LTy=y,得到y;

  4. KKT系统的解为[pλ]=Py

  1. 对称不定矩阵的广义Cholesky分解
  • 假设GRn×n是对称正定矩阵,ARm×n为行满秩矩阵,这时KKT系统的系数矩阵K=[GATA0](m+n)×(m+n)为对称不定矩阵。由于矩阵G为对称正定,故G有Cholesky分解

G=L11L11T

  • L11n×n的下三角矩阵。

    L21=AL11TRm×n,故rank(L21)=m.这就推得L21L21Tm×m对称正定矩阵,故存在Cholesky分解,即L21L21T=L22L22T,其中L22m×m下三角矩阵。

    综合起来得

[GATA0]=[L110L21L22][L11TL21T0L22T]

  • 这就称为对称不定矩阵的广义Cholesky分解.

    完成以上的分解后,就能由下列两个步骤解方程组(7.4):

    1. [L110L21L22][y1y2]=[hc]解得[y1y2].

    2. [L11TL21T0L22T][pλ]=[y1y2],解得[pλ]

    这个方法可以推广到更一般的情况,即

K=[GATAC]

  • 其中GRn×n,ARm×n的假设与前面相同,CRm×m为对称正定矩阵。

    类似前面的广义Cholesky分解,可以得到下列分解式

[GATAC]=[L110L21L22][L11TL21T0L22T]

  • G=L11L11T得到n×n下三角矩阵L11;

    L21=AL11T得到L21;

    由对称正定矩阵C+L21L11T的holesky分解得到n×n的下三角矩阵L22: C+L21L11T=L22L22T