（应用数学专业论文）黎曼流形上的带armijo步长准则的一般下降方法及其应用.pdf

黎曼流形上的带a r m i j o 步长准则的一般下降方法及其应用 摘要 本学位论文拟建立求解约束优化问题的黎曼流形上带a r m i j o 步长准则的 一般下降算法并给出算法的收敛性和收敛速率分析，最后将该算法应用于若干 实际问题计算 我们首先通过分析欧氏空间上一般下降算法归结出构成算法的三大基本要 素，并给出将这些要素推广到黎曼流形上的一般方案，从而顺利建立黎曼流形上 带址m i j o 步长准则的一般下降算法；然后在一定的假设条件下证明了算法的全 局收敛性，并在目标函数满足凸性条件时，证明了算法的几何收敛性我们将 算法用于两个实际问题计算，其中第一个问题为金融领域的组合投资问题；在 假设投资者是一个理性投资者的前提下，我们首先提出了一个新的组合投资策 略，然后通过适当的变换，将其转化为超球面流形上的优化问题，利用前面提 出的一般算法框架，通过显式计算相应的测地线等要素，给出了求解该问题算 法的具体执行步骤；数值模拟结果说明了算法的有效性和可靠性，另外，我们 也数值比较了理性投资和非理性投资的差异第二问题为机器人识别工具柄问 题，我们建立了工具柄为椭球面时相应的数学模型，并给出了求解该问题的黎 曼几何算法的具体实现步骤，从而为机器人识别给定形状的客观物体这一实际 飞 问题提供了一个新的解决途径厂 关键词：约束优化问题，一般下降法，a r m i j o 步长准则 黎曼流形，测地线，下降方向 g e n e r a ld e s c e n ta l g o i u t h m w i t ha r m i j or u l eo nr i e m a n n i a nm a n i f o l d a n di t sa p p l i c a t i o n s a b s t r a c t i nt h i st h e s i s ，w ee s t a b l i s hag e n e r a ld e s c e n ta l g o r i t h mw i t ha r m i j o r u l eo nr i e m a n n i a nm a n i f o l dt os o l v ec o n s t r a i n e do p t i m i z a t i o np r o b l e m s a n dt h e ng i v et h er i g o r o u sc o n v e r g e n c ea n dc o n v e r g e n c er a t ea n a l y s i so f t h i s a l g o r i t h m f i n a l l y w ea p p l yi tt os o l v es o m ep r a c t i c a l p r o b l e m s n u m e r i c a l l y c o n c r e t e l ys p e a k i n g ，b yt h ed e e pa n a l y s i so ft h eg e n e r a l d e s c e n t a l g o r i t h mi ne u c l i d e a ns p a c e ，w es u m m a r i z et h r e eb a s i ci n g r e d i e n t s o f t h ea l g o r i t h m ，a n df u r t h e rp r o v i d ea g e n e r a ls t r a t e g yt og e n e r a l i z et h e m t o t h ec a s eo fr i e m a n n i a nm a n i f o l d i nt h i sm a n n e r , w en a t u r a l l ye s t a b l i s ha g e n e r a ld e s c e n ta l g o r i t h mw i t ha r m i j or u l eo nr i e m a n n i a nm a n i f o l d u n d e rs o m er e a s o n a b l ea s s u m p t i o n s ，w ep r e s e n tag l o b a lc o n v e r g e n c e t h e o r y f o rt h i s a l g o r i t h m ；m o r e o v e r , w h e n t h e o b j e c t i v e f u n c t i o ni s c o n v e x ，w ep r o v e i ti sc o n v e r g e n tw i t h g e o m e t r i cc o n v e r g e n c e r a t e a tl a s t ，w es h o wt h ee f f i c i e n c ya n dr e a s o n a b i l i t yo ft h ea l g o r i t h mb y s o l v i n gt w op r a c t i c a lo p t i m i z a t i o np r o b l e m s t h ef i r s tp r o b l e mc o m e s f r o mt h ef i e l do ff i n a n c i a li n v e s t m e n t a tf i r s t ，w ep r o v i d ean e wo p t i m a l i n v e s t i n gs t r a t e g y f o rar a t i o n a l i n v e s t o r , w h i c h ，b y s o m e p r o p e r t r a n s f o r m a t i o n ，y i e l d sa no p t i m i z a t i o np r o b l e mo n t h eu n i th y p e rs p h e r e s u r f a c e a c c o r d i n gt ot h ea b o v eg e n e r a la l g o r i t h m ，w et h e no b t a i n i t s n u m e r i c a la l g o r i t h mc o n c r e t e l ya f t e rt h ep r e s e n t a t i o no f t h ee x p l i c i tf o r m s o ft h e g e o d e s i c c u r v e sa n do t h e r i n g r e d i e n t s t h ec o r r e s p o n d i n g n u m e r i c a lr e s u l t sa r e d e s i r a b l e ，a n d m o r e o v e rw ea l s o c o m p a r e n u m e r i c a l l yt h ed i f f e r e n c eo f t h eo p t i m a lp o r t f o l i o sb e t w e e nar a t i o n a l a n da ni r r a t i o n a li n v e s t o r t h es e c o n dp r o b l e mi sc o n c e r n e dw i t ht h e c o m p u t e rv i s i o n - h o wt oi d e n t i f yt h et o o lc o n t o u rf o rar o b o t ，w eg i v ea m a t h e m a t i c a lm o d e lo f i d e n t i f y i n ga ne l l i p s o i db y t h eo b s e r v e dd a t aa n d p r o v i d e ar i e m a r m i a nm a n i f o l d a l g o r i t h mt os o l v ei t t h i sg i v e su sa n e w a p p r o a c h t oa t t a c k i n gs u c hau s e f u lp r o b l e m k e y w o r d s ：c o n s t r a i n e d o p t i m i z a t i o np r o b l e m ，g e n e r a ld e s c e n ta l g o r i t h m ， a r m i j or u l e ，r i e m a n nm a n i f o l d ，g e o d e s i cc l r v e ，d e s c e n td i r e c t i o n 引言 大量的实际应用问题可归结为约束优化问题的求解传统的约束优化问题求 解方法有l a g r a n g e 乘子法，罚函数法，既约梯度法等 1 - 4 ，近年来，一种新型的 求解算法r i e m a r m 几何方法颇受重视【5 - l ”其核心思想为将约束集视为r i e m a r m 流形，原约束优化问题就变为r i e m a n n 流形上的无约束优化问题，最后结合 r i e m a r m 几何技巧即可构造优化算法在这种观点下，求解约束优化问题的著名 的内点法可有非常深刻的解释 r i e m a r m 流形上一般情形的下降算法在 8 】， 9 】中有深入研究，其步长选取采 用的是w j l f e p o w e l l 准则在r i e m a n n 流形的推广本文拟研究取a r m i j o 步长准 则时的一般情形下降算法由于常规的a r m i j o 步长准则是基于一般欧氏空间情 形给出的，因此我们首先给出该准则在r i e m a n n 流形情形的推广，然后给出相 应算法的收敛性、收敛速度分析我们通过一个约束集为三维球面的数值算例具 体说明算法的有效性和合理性 本文最后将r i e m a r m 流形优化算法应用于两个有应用背景的实际问题的计 算( 一为金融中组合投资决策，一为机器人视觉问题) 第一章预备知识 在这一章中我们首先简单介绍一下优化问题的一般框架，并就构造下降算法 的一些基本要素进行分析从而类似构造黎曼流形上的下降算法一般框架这就 需要知道黎曼流形上的一些基本概念，完备黎曼流形的性质和黎曼流形上函数的 t a y l o r 展开公式等有了这些我们就可以在后面章节中建立黎曼流形上的优化算 法 1 1 最优化问题的一般框架分析 为了建立在黎曼流形上的下降算法，我们首先来研究建立一个下降算法的一 般步骤详细论述见文献叫1 最优化问题的一般模型为： r a i nf ( x ) s h a x ) = 0 ，i = 1 , 2 ，3 ，m( p ) g ，( x ) 0 ，= 1 , 2 ，3 ，一， 其中x = ( x 1 ，x 2 ，x 3 ，x ”) 7 r “，即x 是n 维向量实际问题中也常把变量 x = ( x 1 ，x 2 ，x 3 ，x ”) 7 称为决策变量( x ) ，h a x ) ，i = 1 ，2 ，3 ，m ，g j ( x ) ，= 1 ，2 ，3 ，l 等为 x 的函数s t 为英文s u b j e c tt o 的缩写，表示受限制于 求极小值的函数，( x ) 称为目标函数，h i ( x ) ，i = 1 ，2 ，3 ，m ，g ( x ) ，j = l ，2 ，3 ，称 为约束函数，其中h i ( x ) = o ，f = 1 ，2 ，3 ，m 称为等式约束，g y ( o ，= 1 ，2 ，3 ，称为 不等式约束记d 为( x ：h i ( x ) = o ，i = 1 ，2 ，3 ，m ，g j ( x ) o ，= l ，2 ，3 ，) ，称为之可行 域 求解问题( p ) 的基本方法是给定一个初始的可行点z 。d ，由这个初始可行点 出发，按照某种规则依次产生一个可行点列 机) ，使得或者某个“恰好是问题 的一个最优解，或者该点列 靠) 收敛到问题的最优解z 。这就是我们平时所说的 迭代算法在迭代算法中由点“迭代到点x 时，要求目标函数满足 f ( x ) f ( x ) ，称这种算法为下降算法而迭代点列 ) 的产生，通常采取两 步来完成首先在可行域内靠处求一个可行方向p 女使得，( z ) 沿方向p i 移动时函 数值有所下降，一般称这个可行方向为下降方向或搜索方向其次以“为出发 点，以p t 为方向作射线。+ 舻女，其中t 0 ，在此射线上求一点。m ， x i + l = 瓢+ “p t ，使得f ( x ) f ( x t ) ，其中t t o 称为下降步长 定义1 1 1 在点“处，对于向量p t 0 ，若存在实数f 0 ，使得任意 a ( o ，f ) 有： f ( x k + 口p t ) f ( x k ) 成立，则称p t 为函数，( x ) 在点“处的一个下降方向 当，( x ) 具有一阶连续偏导数时，并记，( z ) 在点x 女处的梯度为w ( x t ) = g 女由 t a y l o r 公式 f ( x 女+ 印女) = f ( x 女) + 昭k t p 女+ d ( 口) 当gt p 女 o 时，有f ( x i + 印i ) 0 ，使得f ( x t + “p t ) f ( x i ) i i i ) 令。 + l = 。女+ t k p t i v ) 若瓢+ l 满足某种给定的终止准则，则停止迭代，以x 为近似最优解否 贝0 令k = k + l 转i ) 根据不同的原则选取不周的搜索方向肌和步长“，0 ，就可以得到各种不同 的算法由h 沿方向p i 求步长“) 0 的过程叫一维搜索或线性搜索它是求解最 优化问题的基本步骤之一当搜索方向确定后，一维搜索的优劣便成为求解最优 化问题的关键 我们在算法当中提到了终止准则，这里我们给出常用的三种判别算法迭代终 止的准则； i ) i x k - - x k i i “或瞀 ， i i l i f ( x k * 1 ) - - 弛刮q 或紫 0 是预先给定的适当小的实数 仔细分析上面算法的过程，我们发现要建立一个最优化下降算法，一般要做 如下几个方面的工作： 1 ) 确定下降方向： 2 ) 确定产生迭代点列的规则，即如何根据点x 。和下降方向得到下一个近似 点瓢+ i i 这一步在不同的空间中有很大的差异 3 1 描述迭代算法的终止准则 我们要在黎曼流形上建立一般的下降算法，就应考虑推广上面3 个基本要素，在 下面一节当中我们将给出黎曼流形上的一些基本概念并进而给出如上三个要素 在黎曼流形上的推广 s1 2 黎曼流形上的基本概念 为使我们能在严格的数量描述下将以上三个基本要素推广到黎曼流形上 去，在此先给出黎曼流形和黎曼度量及测地线的定义和性质 黎曼流形在一个n 维微分流形肘上，对每一个点x m 的切空间l m ，赋予 一个正定的双线性内积函数g ，使其成为一个内积空间并对吖上的点x 来说，内 积函数g ，是光滑的，便说：在m 上给出了一个黎曼结构，m 成为一个黎曼流形 我们今后将记为( m ，g ) 简单的说，黎曼流形就是附加了黎曼度量的微分流形 若( 己，幻( u ) ) 为m 上的一个坐标卡，a _ s ，f - 1 ，2 ，n 便是u 上n 个独立的光滑向 量场，所以 州加蹦参，争 是u 上的光滑函数在m 上任何一点x u ，( 勋( x ) ) 是一个二阶协变张量g ，代 表一个二阶协变张量场换句话说，黎曼度量g 可表示为 g = g q ( x ) d x l d r j 由于岛( z ) = g ( z ) ，习惯上把( 出。o d x 。+ d r o 出) 写作斑出7 ，所以占又常写作 g = gq d x t d x j 在嵌入到欧氏空间的黎曼流形中，我们常用的黎曼度量就是普通的欧氏空间中 的标准的诱导度量 令( m ，g ) 是一个连通完备黎曼流形，疋m 是对应于点x e m 的切空间在切 空间上定义指数映射e x p ，：疋肘_ m 如下 v h e x p ( r - v ) = y ( f ，x ，v ) 其中，r r 表示在方向v 上移动的步长 给定置z 为m 上的两点，我们定义从x 到z 。的距离如下 d ( x ，z ) _ 。i n f ( 1 ( a 。) ) a r 其中1 2 。：( 口b l - + m 是一个分段光滑函数，即是连接x ，x + 的分段光滑曲线它满足 并且 a 矗- ( 口) = z ，a - ( 6 ) = x 。扣；| | 0 【。怯 是曲线a 。一的长 另外，我们给出连接点x 和x 。的测地线为，。( f ) ，te 【a ，6 】满足曲线的端点条 件并且其初始点出的切方向，即在点x 指向x 。的切方向为y 。( o ) ，表示为 下面我们给出测地线和曲线弧长的性质 1 ) ，( a 。- ) 蜥。) ； 2 ) 对任意f 口，6 】，有扩( f ) _ | = 】| y 。( 口) | i = c o l l $ t 性质1 ) 说明在连接点x 和x + 的曲线中最短的弧必是测地弧也就是说普通欧 氏空间中的线段到黎曼流形上对应为测地线因此我们利用测地线来定义迭代点 列生成的规则性质2 ) 说明测地线上的切方向的长度是常数这两个性质在以后 的证明中都会用到 在后面的证明中我们会经常涉及到将黎曼流形上的任意两点用最4 , n 地线 连接如下的( h o p f a n dr i n o w ) 定理给出了黎曼流形上的任意两点间最小测地线 的存在性 ( h o p f a n dr i n o w ) 定理如果( 膨，占) 是一个连通有限维黎曼流形，则下面的三 个命题是等价的： 1 ) 对任意一点x m ，e x p ，在整个切空间t f 上有定义，也就是说( m 培) 是 完备的 2 ) ( m ，d ) 作为度量空间是完备的，其中d 如s 1 2 中定义：即( m ，d ) 上的任何 c a u c h y 序列是收敛序列更进一步，上面的两个命题表明： 3 ) 黎曼流形( 肘，g ) 上任意两点五x 可以用长度为蜥) = d ( x ，x ) 的测地线连接； 具有这种性质的测地线称为最4 n 地线 有t ( h o p fa n dr i n o w ) 定理，我们在后面的证明中不再讨论连接两点置x 的 最小测地线的存在性在此基础上给出黎曼流形上的梯度和h e s s i a n 的定义 现在我们具体阐述在黎曼流形上建立下降算法的三个基本要素： 1 ) 下降方向 我们这里研究的目标函数都满足一阶偏导数连续条件，根据上节的讨论，我 们定义黎曼流形上x t 点处下降方向为满足g ( w ( x 女) ，p t ) o ，使得，( e x p ( t k p 女) ) ，( 靠) i i i ) 令。“1 = e x p a ( t k p k ) i v ) 若x 满足某种给定的终止准则，则停止迭代，以x 为近似最优解 否则令k = k + 1 转i ) 第二章算法的提出和理论分析 2 1 黎曼流形上函数的t a y l o r 展开公式 在这一节中我们给出黎曼流形上c 2 函数，jm 卜r 的t a y l o r 展开公式因为 般的t a y l o r 展开公式要求变量呈线性变化但在黎曼流形上变量的变化不再呈 线性性这时我们通常利用测地线将非线性变量转化为欧氏空间中的线性变量 任给黎曼流形m 上的两点五z ，我们给出连接这两点的测地线为y 。( f ) ， f o ，1 ，且满足曲线端点条件在这条测地线上我们固定点y = 7 ( f ) ，0 r 1 则 连接z ，y 的测地弧为y ( ”) ，u o ，f 】作代换“= s j 【o ，1 并令a ( s ) = y ( s f ) ， s o , 1 1 ，则有a ( o ) = y ( o ) = x ，a ( 1 ) = y ( f ) = _ y ，型兰( s ) ：f 粤( s f ) 记( p ；f 。0 【，此时常规 a sa u 的t a y l o r 公式为： 甲( 1 ) = ( p ( o ) + 平( o ) + 亡( p ( s o ) ，j o 0 , 1 ( 2 1 1 ) 我们知道平( 1 ) = ，( y ) ，币( o ) = ，( x ) ，所以，我们只要将( p 。( o ) + 圭平”( s o ) 写成，0 【的关 系式即可为此给出如下引理： 引理2 1 妒和，如上定义则我们有： 1 ) ( p ( t ) = g ( g r a d f ( y ( t ) ) ，t ( f ) ) = a t ( t ( f ) ) 2 ) ( p ”( f ) = h e s s f ( y ( f ) ，7 ( r ) ) 证明：1 ) 中( f ) ：蔓丛掣：d f ( y ( r ) ) ：g ( g r a d f ( y ( f ) ) ，y ( f ) ) a t 2 ) 币”( f ) ：掣：盟亟堕墼必 d td t y ( f ) g ( g r a d f ( y ( t ) ) ，y ( ，) ) 2 9 ( v t 。( ，) g r a d f ( y ( t ) ) ，y ( f ) ) + g ( g r 口够( y ( f ) ) v t ( f ) y ( f ) ) 2 9 ( v y ( ，) g r a d f ( r ( t ) ) ，y ( 啪 ；m 啊( t ( f ) ，t ( r ) ) 至此引理证完 结合式( 2 1 1 ) i i p 引理2 1 我们有t a y l o r 公式如下： ，( y ) = ( x ) + d f ( a ( o ) ) + ；日i j 矿( a 。( j 。) ，0 。( j 。) ) ，j 。 o , 1 1 将c 【( j ) = y ( s t ) ，s o ，1 1 代入上式，我们得到： ( y ) ：( x ) + ，( y 。( o ) ) + 霎月如旷( y + ( s 。) ，y 。( 5 。) ) j 。 o ，1 】( 2 1 2 ) 给出的公式( 2 i 2 ) 在我们后面的证明中要经常用到 2 2 黎曼流形上带a r m i j o 步长准则的一般下降算法 令( m ，g ) 是完备有限维黎曼流形，函数，是适当光滑的( 在本文中要求 是c 2 函数) 集合r + 表示，的极小点集合并且厂= ；i 。n 村f ，( x ) 表示的极小值我 们的问题是估计f ，如果f + ，我们还要给出集合r + 中的一个点 我们提出的解决这类极小化问题的数值算法大都基于如下形式的迭代过程： x k + 12e x p 札( t k x k ) 其中x 疋。m 表示瓢点处的下降方向，“2 0 表示从点出发沿切方向扎的测 地线上的下降步长这与线性空间中的表述基本一致，因而类似于线性空间中的 情况，我们选取不同的x 。和t 。就得到不同的算法 为应用下降算法解决上面提出的问题，我们首先给出下降方向的一般判别准 则在黎曼流形上，如果不是临界点，我们就能找到x 女疋。m 使得 g ( g r a d f ( x t ) ，x ) 0 或者等价地要求： d f ( h ) ( x ) = d f ( z t ) 0 这时，切方向x 女就是“点处的下降方向这一结论可根据s 1 2 的论述容易得到 算法2 1 黎曼流形上带a r m i j o 步长准则的一般下降方法 如果是极小值点x f 的第k 次估计，则黎曼流形上带a r m i j o 步长准则的 一般下降方法有如下公式： 1 ) 令k = 1 ，给定0 p ： 2 ) 计算切向量以使得d f ( x t ) 0 ； 3 ) 计算下降步长t 。使之满足： 3 1 ) f ( x t + 1 ) - f ( x t ) p t k ( 以) ； 3 2 ) f ( x ) - f ( x k ) ( 1 一p ) “d f ( x k ) ； 4 ) 根据迭代公式。川= e x p “( t k x k ) 计算坼+ l ； 5 ) 如果+ l 满足给定的收敛准则，算法终止；否则转第六步； 6 1 令k = k + l ，转第二步 2 3 算法基本性质分析 本节讨论算法2 1 的收敛性定理2 1 给出了保证算法终止的条件，算法在 如下意义下终止：对任意给定的正数，存在一整数k o n 使得 jj a o 知) | | = | j ( x ) i j ce 序列 g r a d f ( x 。) ) 的收敛性 定理2 1 设f ? m + r 是定义在黎曼流形m 上的开凸集d 上的二阶光滑函 数如果下列条件成立： 1 ) 给出初始点。l d ； 2 ) 设s = 协m l f ( x ) f ( x 1 ) ) 是开凸集d 的一个子集； 3 ) 存在( - o o ，o o ) 使得，( x ) l ，v x s ； 4 ) 胁5 矿( ，- ) 的特征值满足x j ( x ) 6 ，= ，2 ，”，v x s ； 5 ) 选择切方向以使得 g ( x i ，g r a d f ( x t ) ) 一e l ! i x i i g r a d f ( x i ) f ，v 女n 6 ) 给定o c p c ；使得 6 1 ) f ( x + i ) - f ( x k ) sp “d f ( x t ) ， 6 2 ) f ( x 川) - f ( x k ) ( 1 一p ) t k d f ( x , ) 那么我们有对任意给定的正数e ，存在一整数k d n 使得 g r a d f ( x o ) 忙| | ( x b ) f c e ，使得算法终止 证明：我们来研究第k 次迭代的性态，设曲线y ( f ) ，y ( o ) = ，v ( t t ) = 1 c 川是连接 x 女和x 点的测地线，它满足7 ( o ) = 以令( p ( f ) = ，( y ( f ) ) 如第二节中定义，我们 有( p ( o ) = f ( x 女) ，币( “) = f ( x ) 以及币+ ( o ) = d f ( x 女) o ( 这是因为切方向以同目标函 数，的负梯度方向一g r a d f ( x ) 的夹角处在区间( o ，罢) 中) 根据定理的条件6 2 ) 以及算法2 1 是下降算法，我们有 f ( x k ) 一f ( x k + 1 ) 一( 1 9 ) g a f ( x k ) = ( 1 一p ) “l ( 以) i 于是我们可以得到如下的不等式： 丝牟霉掣( 1 一p ) 即 业掣( 1 一p )( 2 3 1 ) t k 旧( o ) 又因为目标函数f ? m _ r 是定义在黎曼流形m 上的开凸集d 上的二阶光滑 函数，所以我们根据2 1 节的结论可知： 平( f 女) = 甲( o ) + t k ( p ( o ) + 等甲”( s o ) ，s oe o ，f 女 该式表明： ( p ( 0 ) 一币( ，i ) = 。t ( p ( 0 ) 一t = k 一平”( s o ) ，5 0 0 ，t 即有： ! ! 掣：1 一，；! q ；f t ，。 o ，f i 】 ( 2 3 2 ) t k ( p ( o )2 睁( o ) 比较式( 2 3 1 ) 和( 2 3 2 ) 我们发现： 掣掣”。 根据引理2 1 和假设条件4 ) 可以得到： 错”膂”翱”。 再根据1 2 节给出的测地线的性质2 ) 即：护( f ) 蚓i y ( a ) ! _ = c 。n s t ，对任意，e 【a ，6 】 o 掣”p 这样我们就得到了步长“的估计式 2 p 弦( o ) l k 靠亭 圳x t l 将上式代入假设条件6 1 ) 得到： m 沪m 川御划= 等i , 2 再结合假设条件5 ) 得到： 厂( x t ) 一，( x t + 1 ) 2 p 2 6 e 1 2 a d r 、x ) _ | 2 ( 2 3 3 ) 至此，因为我们知道序列 厂( ) 是单调递减的，而且有下界工( - - o o ，o o ) 从而序 列 厂( ) ) 收敛，也就有序列 ，( x ) 一f ( x ) ) 收敛于零从而得到序列 g r a d f ( x 。) 收敛于零，算法2 1 终止证毕 注1 在上回给出日可算法甲，有一个亘要阴| 口j 咫就是步长t k 阴仔征怔辛u 迓取 方法为解决这一问题，我们观察t a y l o r 公式： f ( x k + 1 ) = ，( ) + “( x 女) + 譬胁s 矿( 丫( r 。) ，丫( ) ) ，f 0 。，“】 ( 2 3 4 ) 在将( 2 3 4 ) 与假设6 ) 结合起来有： ( 1 一p ) f 女( 以) 一譬胁珂( t 。( f o ) ( ) 陬够( 以) ，r 0 f o ，州 即有： 叭j a y ( 以) 旧t 2 2h e s s f ( y 。( r 。) ，t ( r o ) ) ( 1 一p ) l a f ( 以) “ 考虑假设4 ) 我们有：t a - h e s s f ( y ( f 0 ) ，y ( r 0 ) ) 了t k 26 ( f 0 ) i2 = 了t k 26 i i 以1 1 2 ，此时我们 选取步长“满足霉6 一| 以2 ( 1 一p ) l d f ( x 女) 则有 p l a f ( x k ) i f t b _ t k 21 , x ki 1 2 ( 1 一p ) i d f ( x k ) l f l 化简为： 裂掣 眨s 勖 至此我们得到步长“的存在性，在选取步长的时候，我们可以直接在( 2 3 5 ) 给 出的区间中任意选一点 注z 上面给出的定理的假设条件4 ) 可以减弱为一阶导数一致连续，即 l d f ( x 。) 一a f ( x ) 忙耐2 ( x ，x ) ，其中x , x 是黎曼流形m 上的任意两点，0 r 1 但 frf 在一般问题中黎曼流形m 是紧的，假设条件4 ) 直接满足，而新条件则不易判断 序列 机 的收敛性 上面的定理只给出了算法终止性的证明，这里我们要讨论由算法产生的点列 的收敛性我们要得到序列) 的收敛性必须在定理2 】的基础上给出更强 条件比如我们假设假设条件2 ) 中的水平集s 是紧的，即是闭有界的我们能得 到如下定理来判断序列 机) 的收敛性 定理2 2 假设定理2 1 的条件成立，并且我们还令假设条件2 ) 中的水平集 s 是紧的，则序列 磁) 的每个聚点都是目标函数，在水平集s 中的临界点 证明：因为水平集s 是紧的，序列 “ c s 包含一个收敛于点x s 的子列 协h 假设点x 不是目标函数，在水平集s 中的l 临界点，即a f ( x ) 0 ，那么 l i ma f ( 。h ) = a f 0 ) 0 该式与定理2 1 的结果等式j j mg r a d f ( x i ) = o 相矛盾这说明z 是一个临界点 注我们在定理2 2 中给出的附加条件“假设条件2 ) 中的水平集s 是紧的” 加上目标函数，的连续性保证了定理2 1 中假设3 ) 的成立因此此时定理2 1 中的假设3 ) 是多余的 在线性空间中，目标函数的局部凸性能得到估计序列) 的收敛性于是我 们得到黎曼流形上类似的结果如下： 定理2 3 令j m _ r 是个二阶光滑函数，如果有一个临界点x 满足在 这一点的h e s s f ( - ，- ) 是正定的( 因此x 是一个严格局部极小点) ，那么存在z 的个 邻域u 使得下式成立： 2 骢。t 一t - 其中 ) 为邻域c ，上满足等式t 1 i m 。g r a a f ( x 女) = o 的序列 证明：令t 。“： o ，1 斗m 是黎曼流形m 上连接点x 和点的测地线，满足条 件： 丫h 以( o ) = x h ，丫知札( 1 ) = x q 那么我们有： 矽( x 矗) 一( z 。) = l 丢矿( k n ( f ) 妙 2 h e s s f ( r 。“( r ) ，y 挑( f ) ) 西 = 她厂( 丫“( f o ) ，丫靠耳( ) ) ，f 0 0 ，1 等式两边取极限我们得到： 0 - h e s s f ( l i my “靠( o ) ，熙y - 靠( r 0 ) ) 另一方面，h e s s i a n 的连续性表明存在x 的一个邻域u ，在其上h e s s i a n 是正定 的因此关系h u 表示 t l i m 7 x x k ( f 0 ) 2 0 将上式结合不等式： o d ( x * , x k ) l y 。h ( f o ) 我们得到： 2 。i md ( x , , x k ) = 0 ，吼舢l i r a 2 m 定理2 3 仅仅给出了局部收敛性，我们可以在更强的条件下给出点列( 的 整体收敛性比如目标函数f 的强凸性作为附加条件，我们就可以得到点列 札) 的整体收敛性 推论2 3 在定理2 3 的条件下，我们假设目标函数，是强凸的，即： 口i l x l l 2 h e s s f ( x ，x ) s b i l x l l 2 ，o 口6 o o ，v x x ( f ) ( 2 3 6 ) 其中，x ( m ) 是黎曼流形m 上的光滑向量场 则我们得到点列 ) 的整体收敛性j i m 磁= x 证明：我们直接观察下面的t a y l o r 公式： ( x ) = ，( x ) + ( ，。( 0 ) ) + h e s 矿( ，。( 5 。) ，y 。( 5 。) ) ，5 。 o ，1 其中y 。( f ) ，t 0 ，1 是连接点z 和点z 的测地线，根据条件( 2 3 6 ) 我们可知， 临界点z 。有性质： f ( x ) f ( x ) ，v x m 事实上，我们可以得到下式： ，( 班：( x 。) ( x ) + ( y 。( o ) ) + 引y 。( r o ) | | 2 ( 2 3 7 ) 也即有： ( y 。1 ( o ) ) + ；睁。( f 0 ) 旷o 即： ；陟。( f 0 ) f 2 k ( 哟r ( x ) ，y 。( o ) ) 卜l l g m a f ( z ) y 。( 0 ) 再考虑到等式：d ( 一x ) = l y 。( o ) | ，我们有 0 d ( x ，x ) 兰_ | 9 7 ( i 国r ( j ) | 】 由定理2 1 我们知道i i mg r a a f ( x 女) = 0 ，因而得到序列( 收) 的整体收敛性，即 l i mx k = j + 算法收敛速率的估计 在前述定理2 1 - 2 3 以及推论2 3 中，我们不但证明了算法的可终止性，并 且通过加强假设条件：“目标函数的强凸性”给出了算法的收敛性，即由算法产 生的序列 收敛这时由于目标函数，是连续的，所以，我们得到所求的极小 值： l i mf ( x k ) = ，o ) + 其中 “ 由算法根据任意给定的初值z o 产生 下面的定理给出了加强假设条件时算法收敛速率的估计 定理2 4 令，? m _ r 是一个二阶光滑函数，且在定义域中函数，的h e s s i a n 满足条件( 2 3 6 ) ，则我们有如下结论： 1 ) 函数有唯一的极小值点x ； 2 ) 在给定条件下，如下的收敛速率估计式成立： f ( x 女) 一f i x ) qk - i ( 厂( 。1 ) 一f ( x ) ) d ( x ，h ) q ( 。一1 心，c o o , o q i 证明：1 ) 由条件( 2 3 6 ) 知，h e s s f ( ，) 是黎曼流形m 上的黎曼度量并在每个 切空间上导出的范数与原来的黎曼度量g 在每个切空间上导出的范数等价这就 保证了函数厂的强凸性，因此有且只有一个极小值点显然x 。是函数，的临界点 2 ) 我们观察不等式( 2 3 7 ) 有： f ( x ) - - f ( x ) s 1 矽( y 。( o ) ) 卜引y 。( f o ) lf o s o i l 再根据等式d ( x ，x ) = i l ，。( o ) ，我们得到： ，( x ) 一，( x ) s o 肜渺( 珊卜。( r o ) _ | 一a ，d 2 ( ) ，f o ( 0 ，l 】 ( 2 3 8 ) 其中t 。( f ) ，r e o ，l 】是连接点x + 和点x 的测地线另一方面即( x 。) = 0 表明： ，( z ) 一f ( x ) = ；z 蕊矿( p 。( s o ) ，b 1 ( 5 0 ) ) ，s oe o ，1 】 其中g x ( f ) = 7n ( 1 一f ) ，t o ，1 】，再引入假设条件式( 2 3 6 ) 我们有 ；d 2 ( x ，z 。) s ，( x ) 一，( z ) _ 2 b d 2 ( x ，z )( 2 3 9 ) 根据式( 2 3 8 ) 和( 2 3 9 ) 得到： 2 a d 2 ( x ，x ) _ ：i g r a d f ( x ) i l d ( x ，x ) 一a 2 d 2 ( z ，z ) 讹。) s 型( 2 3 10 ) 而由( 2 3 9 ) 又可得到 ( f ( x ) 一f ( x ) ) d 2 ( x ，x )( 2 3 1 1 ) 0 至此，我们根据式( 2 3 8 ) 一( 2 3 10 ) 可以得到： ，( ，) ，( 。) s i 叟! ! 巡一导( ，( ，) 一，( ，) ) ao 口( 1 + 譬) ( ，( x ) 一( x 。) ) sj k 7 - c n ( j ) 1 1 2 0 由于z 是临界点z 。某邻域内任意一点，所以我们可将( 2 3 3 ) 式中的坼，“+ l 看作 ( 2 3 1 1 ) 中的z 因而有： f ( x k + 1 ) 一，( 。t ) 一三兰l ；生二。( 1 + 詈) ( 厂( 。女) 一厂( ，) ) ( 2 3 1 2 ) d0 在( 2 3 1 2 ) 式的两边同时减去f ( x 。) ，得到： f ( x k + l 卜，) ( 1 一华口( 1 + 弘几沪m ) )dd 即是：f ( x k + t ) 一厂( j 。) g ( ( 机) 一厂( z 。) ) 其中o q = l - 2 了1 2 p 一2 口( 1 + i a ) o ，i = 1 ，2 ，3 的对角阵，6 = ( 6 l ，b 2 ，b 3 ) 7 以后我们仍记爿l 为a ，这里参 数q ，a ，b 待定这时我们引入如下的偏差度量函数： 厂( g ，a ，b ) = “e 。爿) 一1 ) 2 这里耳= 掣，+ b ，f = 1 ，2 ，3 ，m 为了得到最佳拟合曲面，实际上就是使得偏差 函数最小化，我们给出如下得最优化i ；q 题： s 州x 苫搿i z 力 q 。9 = 。 这就是说，问题转化为在正交约束下得最优化问题而所有满足q 7 q = ，的正交 矩阵q 构成黎曼流形记为( m ，g ) ，其中g 是般的欧式空间的度量，即 g ( q lq 2 ) = t r a c e ( q l r q