漫步最优化十三——驻点

从遇见你的那刻起，
我的世界开始改变。
从听到你的那句话，
我的信心开始萌芽。
我知道这份爱值得拥有，
我会在这里等待，
等待亲口说出那三个字。
——畅宝宝的傻逼哥哥

如果考虑的极值点类型(即极大值，极小值)位于可行域的内部，那么我们称为它们驻点，因为在这些点上g(x)=0，还有一种驻点是鞍点。

定义1：R是可行域，我们称x¯∈R为鞍点，如果

g(x¯)=0
x¯既不是极大值，也不是极小值。

E2中的鞍点如图1所示。

图1

鞍点x¯附近的任意点x=x¯+αd∈R，根据泰勒级数可得

f (x) = f (x) + 12 α 2 d T H (x ¯) d + o (α 2 ∥ d ∥ 2)

其中g(x¯)=0。根据鞍点的定义，必须存在方向d1,d2使得

f (x ¯ + α d 1) < f (x ¯) f (x ¯ + α d 2) < f (x ¯)

因为x¯既不是极小值也不是极大值，所以当α→0时我们有

d T 1 H (x ¯) d 1 < 0 d T 2 H (x ¯) d 2 > 0

因此，矩阵H(x)是不定的。

驻点是局部的并通过下面方法得到：

找出使得g(xi¯)=0的点xi
求出海森矩阵H(xi)
对于每个点xi确定H(xi)的特征

如果H(xi)是正(负)定的，那么xi是极小(大)值；如果H(xi)是不定的，那么xi是鞍点。如果H(xi)是半正(负)定的，那么xi可能是极小(大)值；如果H(xi)=0，那么xi可能是极大值也可能是极小值，因为必要条件都满足。很明显，如果H(xi)是半定的，那么我们没有充分的信息来判断驻点的特征，一个可行的方法是推导出f(x)的三阶导数，然后计算泰勒级数的第四项，如果这项等于零，那么就需要计算第五项，依次下去。另一种更实际的方法是计算f(xi+ej),f(xj−ej)，其中j=1,2,…,n,ej是一个向量，其元素为

e j k = {0 ε f o r k \neq j f o r k = j

然后判断是否满足极大值或极小值的定义。

通过前面的讨论可以看出，判别函数f(x)驻点的问题可以变成表征海森矩阵的问题，这个问题可以用下面的定理求解。

定理1：实对称n×n矩阵H是正定，半正定等，如果对每个相同阶数的非奇异矩阵B，

H ̂ = B T HB

给出的矩阵H是正定，半正定等。

证明：如果H是正定，半正定等，那么对所有的d≠0

d T H ̂ d = d T (B T HB) d = (d T B T) H(B d) = (B b) T H(B d)

因为B是非奇异的，Bd=d̂ 是非零向量，那么对所有d≠0，

d H ̂ d = d ̂ T H d ̂ > 0, \geq 0, e t c

因此

H ̂ = B T HB

是正定，半正定等。

定理2：

如果n×n矩阵B是非奇异的且
$H ̂ = B T HB$

对称矩阵，对角元素为h1^,h2^,…,hn^，那么H是正定，半正定，负定，半负定矩阵，如果对i=1,2,…,n,ĥ i>0,≥0,≤0,<0。否则的话，如果一些ĥ i是正的，一些是负的，那么H是不定的。

(a)的逆也为真，即如果H是正定，半正定等，那么ĥ i>0,≥0等，如果H是不定的，那么某些ĥ i是正的，某些是负的。

证明：(a)对所有d≠0

d T H ̂ d = d 21 h ̂ 1 + d 22 h ̂ 2 + \dots + d 2 n h ̂ n

因此如果ĥ i>0,≥0等，那么

d T H ̂ d > 0, \geq 0, e c t

即Ĥ 是正定，半正定等。如果某些ĥ i是正的，一些是负的，那么我们能找到d产生正的或负的dTĤ d，那么Ĥ 是不定的。接下来因为Ĥ =BTHB，根据上面的定理得到如果ĥ i>0,≥0,ect，那么H是正定，半正定等。

(b)假设H是正定，半正定等，因为Ĥ =BTHB，根据上面的定理可知Ĥ 是正定，半正定等。如果d是一个向量，元素dk为

d k = {01 f o r k \neq i f o r k = i

那么

d T H ̂ d = h i^> 0, \geq 0

如果H是不定的，根据上面的定理可知Ĥ 是不定的，因此某些ĥ i必须为正，某些必须为负。

通过在矩阵H上执行行运算或列运算就能得到对角矩阵Ĥ ，例如某行的k倍加到其他行，某列的k倍加到其他列，对于对称矩阵，这些运算通过应用初等变换就能实现，即Ĥ 通过如下方式得到

H ̂ = \dots E 3 E 2 E 1 H E T 1 E T 2 E T 3 \dots

其中E1,E2,…是初等矩阵，典型的初等矩阵如

E a = ⎡ ⎣ ⎢ ⎢ 100 01 k 001 ⎤ ⎦ ⎥ ⎥

与

E b = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ 1000 m 100 00100001 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥

如果Ea左乘一个3×3的矩阵，效果就是第二行的k倍加到第三行，如果Eb右乘一个4×4的矩阵，效果就是第一列的m倍加到第二列。如果

B = E T 1 E T 2 E T 3 \dots

那么

B T = \dots E T 3 E T 2 E T 1

因此

H ̂ = B T HB

因为初等矩阵是非奇异的，所以B是非奇异的，故Ĥ 是正定，半正定等，如果H是正定，半正定等。

另一个表征海森矩阵的定理如下：

定理3：

如果H是实对称矩阵，那么存在正交矩阵U使得
$Λ = U T HU$

是对角矩阵，其对角元素就是H的特征值。

H的特征值是实数。

对于实酉矩阵，我们有UTU=In，其中

I n = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ 10 ⋮ 0 01 ⋮ 0 \dots \dots \dots 00 ⋮ 1 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥

是n×n单位矩阵，因此detU=±1，即U是非奇异的。根据定理1，如果H是正定，半正定等，那么Λ是正定，半正定，因此H通过求出其特征值，然后检查它们的符号就能进行表征。

另一种表征方阵H的方法是基于它的主子式与顺序主子式，该方法的细节具体如下：

定理4：

如果H是半正定或正定矩阵，那么
$det H \geq 0 o r > 0$
H是正定矩阵，当且仅当其所有顺序主子式均为正，例如detHi>0 for i=1,2,…,n
H是半正定矩阵，当且仅当其所有主子式均为正，例如对{l1,l2,…,li}所有可能的选择detH(l)i≥0 for i=1,2,…,n
H是负定矩阵，当且仅当−H的所有顺序主子式均为正，例如det(-Hi)>0 for i=1,2,…,n
H是半负定矩阵，当且仅当−H的所有主子式均为正，例如对{l1,l2,…,li}所有可能的选择det(-H(l)i)≥0 for i=1,2,…,n
H是不定矩阵，如果(c)(e)都不满足。

漫步最优化十三——驻点

相关推荐