《最优化理论与应用-6》由会员分享，可在线阅读，更多相关《最优化理论与应用-6（56页珍藏版）》请在金锄头文库上搜索。
1、最优化理论与应用最优化理论与应用第6讲-信任域方法第 讲 信任域方法电子科技大学电子科技大学自动化工程学院自动化工程学院彭晓明彭晓明彭晓明彭晓明1内容提内容提要要要要回忆一下信任域方法回忆一下信任域方法信任域方法求解的问题信任域方法求解的问题怎样选择信任域的大小怎样选择信任域的大小的精确解的精确解pk的精确解的精确解柯西点柯西点(Chi t)柯西点柯西点(Cauchy point)p 的近似解的近似解pk的近似解的近似解椭球形的信任域椭球形的信任域椭球形的信任域椭球形的信任域举例举例2回忆一下信任域方法回忆一下信任域方法信任域方法求解的问题信任域方法求解的问题怎样选择信任域的大小怎样选择信任域
2、的大小的精确解的精确解pk的精确解的精确解柯西点柯西点(Chi t)柯西点柯西点(Cauchy point)p 的近似解的近似解pk的近似解的近似解椭球形的信任域椭球形的信任域椭球形的信任域椭球形的信任域举例举例3回忆一下信任域方法回忆一下信任域方法?对于目标函数对于目标函数f,建建立一立一个个模型函模型函对于目标函数对于目标函数 ,建个建个模型函模型函数数(model function)mk，使得在以，使得在以当前点当前点为中心的个为中心的个信任域信任域当前点当前点xk为中心的为中心的一一个个信任域信任域R(xk)里面里面， f mkR(xk)里面里面， f mk?寻找寻找一一个个位位于于信
3、任域信任域R(xk)中的中的向向寻找个寻找个位信任域位信任域 (k)中的中的向向量量p，使得下式成立，于是下一个，使得下式成立，于是下一个点是点是点是点是xk+1= xk+p4回忆一下信任域方法回忆一下信任域方法?通常模型函数可以是下面的通常模型函数可以是下面的二二次次通常模型函数可以是下面的次通常模型函数可以是下面的次函数函数当前点当前点xk处处的函数值的函数值当前点当前点xk处处的梯度值的梯度值Hessian矩矩阵或其近阵或其近的函数值的函数值的梯度值的梯度值阵或其近阵或其近似值似值5回忆一下信任域方法回忆一下信任域方法?一一般选择信任域为般选择信任域为一一个球体个球体，即即般选择信任域为
4、个球体般选择信任域为个球体，即即2 p信任域信任域半径半径半径半径6线线搜索方法与信任域方法之比较搜索方法与信任域方法之比较线线mk的极小点的极小点xkk的极小点的极小点p7线线搜索方法与信任域方法之比较搜索方法与信任域方法之比较线线?注意图中注意图中模型函数模型函数mk的等值线是的等值线是注意图中注意图中模型函数模型函数k的等值线是的等值线是一些椭圆（一些椭圆（why?）?线搜索方法的搜索方向是线搜索方法的搜索方向是沿着指沿着指向模型函数向模型函数m 的极小点的方向的极小点的方向向模型函数向模型函数mk的极小点的方向的极小点的方向，但，但对目标函数对目标函数f的减少有的减少有限限对目标函数对
5、目标函数 的减少有的减少有?而信任域方法的搜索方向可以而信任域方法的搜索方向可以在在信任域中的任何方向信任域中的任何方向，因此可能，因此可能对目标函数对目标函数f减少得更多减少得更多对目标函数对目标函数f减少得更多减少得更多8回忆一下信任域方法回忆一下信任域方法信任域方法求解的问题信任域方法求解的问题怎样选择信任域的大小怎样选择信任域的大小的精确解的精确解pk的精确解的精确解柯西点柯西点(Chi t)柯西点柯西点(Cauchy point)p 的近似解的近似解pk的近似解的近似解椭球形的信任域椭球形的信任域椭球形的信任域椭球形的信任域举例举例9信任域方法求解的问题信任域方法求解的问题?信任域方
6、法其实是求解下面的问信任域方法其实是求解下面的问信任域方法其实是求解下面的问信任域方法其实是求解下面的问题题(Nocedal, p.68, 公式公式(4.3)?由于约束条件可以写成由于约束条件可以写成与前面第与前面第5页相比省略了页相比省略了xk?由于约束条件可以写成由于约束条件可以写成?因此目标函数和约束条件都是因此目标函数和约束条件都是二二因此目标函数和约束条件都是因此目标函数和约束条件都是次的次的(quadratic)10信任域方法求解的问题信任域方法求解的问题?如果如果：上：上面问题中的面问题中的Bk是是正正定的定的如果如果面问题中的面问题中的k是定的是定的，且，则，且，则1B?目标函
7、数目标函数mk(p)的极小点的极小点就是该问题的最优解就是该问题的最优解1Bkkkg= pB就是该问题的最优解就是该问题的最优解?这时我们称这时我们称是是一一个个整步整步(fullBkp?这时我们称这时我们称是个是个整步整步(full step)kp?当然，问题往往没有这么简单当然，问题往往没有这么简单11回忆一下信任域方法回忆一下信任域方法信任域方法求解的问题信任域方法求解的问题怎样选择信任域的大小怎样选择信任域的大小的精确解的精确解pk的精确解的精确解柯西点柯西点(Chi t)柯西点柯西点(Cauchy point)p 的近似解的近似解pk的近似解的近似解椭球形的信任域椭球形的信任域椭球形
8、的信任域椭球形的信任域举例举例12怎样选择信任域的大小怎样选择信任域的大小?选择得过小选择得过小，会影响收敛到目会影响收敛到目选择得过小选择得过小会影响收敛到目会影响收敛到目标函数标函数f极小解的速度极小解的速度?选择得过大，模型函数选择得过大，模型函数mk不能不能很好地代表目标函数很好地代表目标函数f使得使得m 的的很好地代表目标函数很好地代表目标函数f，使得使得mk的的极小极小解解并并不不是是f的极小的极小解解极小并是极小并是 的极小的极小?事实上，可以根据上一次迭代的事实上，可以根据上一次迭代的结果调整信任域的大小结果调整信任域的大小13怎样选择信任域的大小怎样选择信任域的大小?定义下面
9、的比值定义下面的比值分子是目分子是目标函数实标函数实定义下面的比值定义下面的比值标函数实标函数实际的减少际的减少值值值值分母是模型函数的减少值，分母是模型函数的减少值，且一定是非负的且一定是非负的(why?)14怎样选择信任域的大小怎样选择信任域的大小?因此因此：因此因此?如果如果k0但显著小于但显著小于1,不改变信不改变信任域的范围任域的范围?如果如果接近接近0或者是负数或者是负数 说明模说明模?如果如果k接近接近0或者是负数或者是负数,说明模说明模型函数不能够代表目标函数型函数不能够代表目标函数，在在型函数不能够代表目标函数型函数不能够代表目标函数，在在下次迭代时要缩小信任域的范围下次迭代
10、时要缩小信任域的范围(减小减小k)16怎样选择信任域的大小怎样选择信任域的大小?可以用下面的算法描述上述思想可以用下面的算法描述上述思想见见”信任域信任域见见 信任域信任域方法其实方法其实是求解下是求解下是求解下是求解下面的问题面的问题”中的公式中的公式中的公式中的公式(4.3)17怎样选择信任域的大小怎样选择信任域的大小?算法中的是信任域半径能够达算法中的是信任域半径能够达到的最大值到的最大值?只有当只有当比较大比较大且且达到了信任达到了信任?只有当只有当k比较大比较大且且pk达到了信任达到了信任域的边界时域的边界时才会增大信任域半径才会增大信任域半径域的边界时域的边界时才会增大信任域半径才
11、会增大信任域半径?只有当只有当k时才接受时才接受pkkpk?选择是为了确保选择是为了确保0,1/4)即使得即使得xk能够收敛到驻点。能够收敛到驻点。18回忆一下信任域方法回忆一下信任域方法信任域方法求解的问题信任域方法求解的问题怎样选择信任域的大小怎样选择信任域的大小的精确解的精确解pk的精确解的精确解柯西点柯西点(Chi t)柯西点柯西点(Cauchy point)p 的近似解的近似解pk的近似解的近似解椭球形的信任域椭球形的信任域椭球形的信任域椭球形的信任域举例举例19pk的精确解的精确解pk?定理定理1：向量：向量p*是下面问题是下面问题的全局最优解，当且仅当下面的的全局最优解，当且仅当
12、下面的条件成立条件成立（其中的其中的0）条件成立条件成立（其中的其中的0）条件条件(a)条件条件(a)条件条件(b)20条件条件(c)pk的精确解的精确解pk条件条件(a)条件条件(a)条件条件(b)?条件条件(b)要求要求和和 | *|中至少中至少条件条件(c)?条件条件(b)要求要求和和- |p*|中至少中至少一一个为个为0个为个为0?因此当因此当|p*|0两种情况两种情况27柯西点柯西点(Cauchy point)(y p)?计算柯西点计算柯西点?情况情况gkTBkgk0 在在gk0 时，时，mk(pks)是一个关于是一个关于的的单调递减函数单调递减函数因此因此最大可以最大可以的的单调递
13、减函数单调递减函数，因此因此最大可以最大可以取取128柯西点柯西点(Cauchy point)(y p)?计算柯西点计算柯西点?情况情况gkTBkgk 0 这时这时mk(pks)是一个关于是一个关于的凸二的凸二次函数次函数极小点是极小点是1和和次函数次函数，极小点是极小点是1和和之中较小的那个之中较小的那个( h ?)之中较小的那之中较小的那一一个个(why?)29柯西点柯西点(Cauchy point)(y p)?计算柯西点计算柯西点?总结这两种情况，我们有总结这两种情况，我们有30柯西点柯西点(Cauchy point)(y p)?举例举例柯西点的方向与柯西点的方向与mk的负梯度方向一致的
14、负梯度方向一致31柯西点柯西点(Cauchy point)(y p)?柯西点的意义柯西点的意义可以证明柯西点所导致的目标函可以证明柯西点所导致的目标函数的减少程度满足数的减少程度满足(Nocedal p 78数的减少程度满足数的减少程度满足(Nocedal, p.78, Lemma 4.3) )?其中其中T的最大特征值32T=AA A的最大特征值回忆一下信任域方法回忆一下信任域方法信任域方法求解的问题信任域方法求解的问题怎样选择信任域的大小怎样选择信任域的大小的精确解的精确解pk的精确解的精确解柯西点柯西点(Chi t)柯西点柯西点(Cauchy point)p 的近似解的近似解pk的近似解的
15、近似解椭球形的信任域椭球形的信任域椭球形的信任域椭球形的信任域举例举例33pk的近似解的近似解pk?注意：柯西点对应的其实是注意：柯西点对应的其实是最速最速下降方向下降方向，因此收敛速度是线性，因此收敛速度是线性的的的的?为了获得更快的收敛速度为了获得更快的收敛速度，可以可以?为了获得更快的收敛速度为了获得更快的收敛速度，可以可以在柯西点基础上做出改进：在柯西点基础上做出改进：每当每当Bk是正定矩阵且是正定矩阵且整步整步pkB=-Bk-1gk满足满足| pB| 时时选取选取p = pB满足满足| pkB |k时时，选取选取pk= pkB?当当Bk是是Hessian矩阵时矩阵时，可以获得可以获得
16、?当当Bk是是Hessian矩阵时矩阵时，可以获得可以获得超线性收敛速度超线性收敛速度34pk的近似解的近似解pk?Dogleg方法方法?二维子空间最小化二维子空间最小化(2-dimensional bi iiti)subspace minimization)?以下为了方便起见以下为了方便起见去掉去掉p?以下为了方便起见以下为了方便起见，去掉去掉k, pk, mk和和Bk中的中的k,并记并记p* 为为p*()以以kk,pp ( )表示表示p*依赖于依赖于 35Dogleg方法方法g g?适用条件：适用条件： B是正定矩阵是正定矩阵?在分析在分析定理定理1时，我们已经注意到时，我们已经注意到当当
17、| *|时必须有时必须有 0这时有这时有当当|p*|时，与信任域边时，与信任域边( )p ?|p |界只有一个交点界只有一个交点( )p40Dogleg方法方法g g?对于后一种情况，为了计算对于后一种情况，为了计算 ，需要考虑需要考虑| PU |?如果如果| PU|?如果如果| PU | ，?否则，否则， 是下面二次方程的根是下面二次方程的根41Dogleg方法方法g g?如果选择如果选择B为为hessian矩阵，则得矩阵，则得到了到了Newton-dogleg方法方法42二维子空间最小化二维子空间最小化?目的：解决目的：解决B是非正定的情况是非正定的情况?首先看一下当首先看一下当B是正定的
18、情况是正定的情况?扩大扩大dogleg方法的搜索范围，也方法的搜索范围，也即不只是沿着即不只是沿着方向寻找方向寻找p*( )p ?即不只是沿着即不只是沿着方向寻找方向寻找p*，而是在，而是在pB和和pU生成生成(span)的二维的二维( )ppp( p)子空间子空间里面寻找里面寻找p*43二维子空间最小化二维子空间最小化?首先看一下当首先看一下当B是正定的情况是正定的情况?由于由于pB和和pU方向也即方向也即-B-1g 和和-g的的方向方向因此问题可以描述为因此问题可以描述为方向方向，因此问题可以描述为因此问题可以描述为意思是意思是p可以写成可以写成意思是意思是p可以写成可以写成p=1*g+
19、2*(B-1g)44二维子空间最小化二维子空间最小化?而当而当B是非正定的情况是非正定的情况?只需要修改生成子空间只需要修改生成子空间?1是矩阵是矩阵B的的最小的那个特征值最小的那个特征值145二维子空间最小化二维子空间最小化?特殊情况特殊情况?当时，可以设当时，可以设p*=-(B+I)-1g+vp(B+I) g+v其中其中v满足满足?当矩阵当矩阵B有零特征值而没有负特有零特征值而没有负特?当矩阵当矩阵B有零特征值而没有负特有零特征值而没有负特征值时征值时，可以将可以将p*选为柯西点选为柯西点征值时征值时，可以将可以将p 选为柯西点选为柯西点46二维子空间最小化二维子空间最小化?可以证明可以证
20、明(Nocedal, p.76) ：二维：二维子空间最小化方法和子空间最小化方法和dogleg方法方法所求解的所求解的p 满足满足所求解的所求解的pk满足满足?即能让模型函数即能让模型函数充分减少充分减少47回忆一下信任域方法回忆一下信任域方法信任域方法求解的问题信任域方法求解的问题怎样选择信任域的大小怎样选择信任域的大小的精确解的精确解pk的精确解的精确解柯西点柯西点(Chi t)柯西点柯西点(Cauchy point)p 的近似解的近似解pk的近似解的近似解椭球形的信任域椭球形的信任域椭球形的信任域椭球形的信任域举例举例48椭球形的信任域椭球形的信任域?回忆一下尺度回忆一下尺度(scali
21、ng)问题，例问题，例如如?可以将球形的信任域转换为椭球可以将球形的信任域转换为椭球?可以将球形的信任域转换为椭球可以将球形的信任域转换为椭球形的信任域以解决尺度问题形的信任域以解决尺度问题 pD是一个对角矩阵，其是一个对角矩阵，其 Dp中对角线元素皆为正数，对应中对角线元素皆为正数，对应x中敏感的分量中敏感的分量xi, 的值也相应大的值也相应大49 DpDii的值也相应的值也相应取取大大椭球形的信任域椭球形的信任域?这时，信任域方法要求解的问题这时，信任域方法要求解的问题变为变为?一一种策略是用种策略是用，从而将上从而将上=pDp?种策略是用种策略是用，从而将上从而将上面的问题转化为面的问题
22、转化为pDp50回忆一下信任域方法回忆一下信任域方法信任域方法求解的问题信任域方法求解的问题怎样选择信任域的大小怎样选择信任域的大小的精确解的精确解pk的精确解的精确解柯西点柯西点(Chi t)柯西点柯西点(Cauchy point)p 的近似解的近似解pk的近似解的近似解椭球形的信任域椭球形的信任域椭球形的信任域椭球形的信任域举例举例51举例举例?求解下面问题的极小解求解下面问题的极小解初始解选择初始解选择00,2,1TTxy=初始信任域大小选择初始信任域大小选择0=152举例举例?用求用求pk的精确解的方法的精确解的方法?第一次迭代第一次迭代(2 1)141f (2,1)141152f=1
23、52(2,1)28f=21200(2,1)036f=( , )036f()12-1.266753()121.2667(2,1)(2,1)-0.7778pff= =计算整步计算整步举例举例?用求用求pk的精确解的方法的精确解的方法?第一次迭代第一次迭代由于由于| | 因此需要求解因此需要求解满足满足由于由于|p|0，因此需要求解因此需要求解满足满足()1()12*(2,1)(2,1)ff= +pI|p*|=0得到得到 =42.655 0.9345*0.3560=p540.3560举例举例?用求用求pk的精确解的方法的精确解的方法?第一次迭代第一次迭代计算计算 0126 4204 / 33 8444计算计算0= 126.4204 / 33.8444= 3.7353 ，根据根据算法算法4.1，可以增加可以增加3.7353 ，根据根据算法算法4.1，可以增加可以增加信任域的范围，接受信任域的范围，接受p*，进行下，进行下一次迭代一次迭代?本例也可应用本例也可应用dl方法方法请尝请尝?本例也可应用本例也可应用dogleg方法方法，请尝请尝试试试试55谢谢大家谢谢大家56
