（应用数学专业论文）一种变尺度的uv分解算法.pdf

摘要 内容摘要：2 0 0 0 年，l e m a r e c h a l ，m i f f l i n ，s a g a s t i z a b a l 等提出的“让分解 理论，给出了研究非光滑凸函数的二阶性质的新方法“让分解理论的 基本思想是将册分解为两个正交的子空间“和y 的直和，使原函数 在“空间上的一阶逼近是线性的，而其不光滑特征集中于1 夕空间中， 借助于一个中间函数，g - l g a r n a g e 函数，来得到函数在切于甜的某个光 滑轨道上的二阶展式随后在此基础上m i f f l i n 等人又提出了甜y 一算法 理论，是利用m o r e a u - y o s i d a 正则化定义了迫近点函数的一种算法，用 l 以解决一般凸函数的最优化问题沐文是基于上述算法的理论，提出的 、 一种变尺度的“1 夕一算法，是通过新的m o r e a u - y o s i d a 正则化来定义变尺 度迫近点函数，并使用拟牛顿法中的s r i 校正公式对新的迫近点函数 中的矩阵进行校正，使算法中的函数在b u n d l e 子程序中有更稳定的下 降量 本文的基本内容如下： 1 第一章介绍了纠协分解理论的研究背景及基本理论 2 第二章介绍“y 分解理论及甜一l a g r a n g e 函数 3 第三章介绍“弘算法的相关概念及基本理论 4 第四章提出一种变尺度的纠谚分解算法 5 第五章给出了算法的收敛性证明 关键词：非光滑最优化；纠弘分解算法；m o r e a u - y o s i d a i e 贝l j 化；快速轨道 a b s t r a c t c o n t e n t ：l e m a r e c h a ，m i f f l i n ，s a g a s t i z a b a l ( 2 0 0 0 ) i n t r o d u c e dt h e 所协 t h e o r y , w h i c ho p e n saw a y t od e f i n i n gas u i t a b l er e s t r i c t e ds e c o n d - o r d e r d e r i v a t i v eo fac o n v e xf u n c t i o nfa tan o n d i f f e r e n t i a b l ep o i n t 雹t h e b a s i ci d e ai st od e c o m p o s e pi n t ot w oo r t h o g o n a ls u b s p a c e s 甜a n d vd e p e n d i n go n 爱s ot h a t | ! sn o n s m o o t h n e s si l e a l t h ep o i n ti sc o n - c e n t r a t e de s s e n t i a l l yi nr ac e r t a i nl a g r a n g i a na s s o c i a t e dw i t ht h e c o n v e xf u n c t i o nw a si n t r o d u c e d 。c a l l e d d l a g r a n g i a n w h e n1s a t i s - t i e sc e r t a i ns t r u c t u r a lp r o p e r t i e s ，i ti sp o s s i b l et of i n ds m o o t ht r a j e c t o - t i e s ，v i at h ei n t e r m e d i a t ef u n c t i o n ，y i e l d i n gas e c o n d - o r d e re x p a n s i o n f o r 。o nt h i sb a s e 、t h e d r - d e c o m p o s i t i o na l g o r i t h mg i v e nb ym i f - f l i na n ds oo n ，i saa l g o r i t h mu s e dm o r e a u - y o s i d ar e g u l a r i z a t i o nt o d e f i n et h ep r o x i m a lp o i n tf u n c t i o n t h ea l g o r i t h mi su s e dt os o l v e t h eo p t i m i z a t i o np r o b l e mo fg e n e r a lc o n v e xf u n c t i o n i nt h i sp a p e r ， w ei n t r o d u c eav a r i a b l em e t r i c “y a l g o r i t h mb a s e do nt h ea b o v et h e - o r y t h em e t h o du s e sn e wm o r e a u - y o s i d ar e g u l a r i z a t i o nt od e f i n et h e m o d i f i e dp r o x i m a lp o i n tf u n c t i o n ，a n du s e st h es r lf o r m u l ao fq u a s i - n e w t o nt ou p d a t et h em a t r i xo fn e wp r o x i m a lp o i n tf u n c t i o n t h e n t h ef u n c t i o ni nb u n d l es u b r o u t i n ed e c r e a s e ss t a b l y i nt h i sp a p e r ，w eb r i e f l ys t a t ei t sc o n t e n t sa sf o l l o w s 1 i nc h a p t e r1 w er e c a l lt h eh i s t o r i c a lb a c k g r o u n da n dr e l a t i v ek n o w l e d g ea b o u tt h e d r - d e c o m p o s i t i o nt h e o r y 2 i nc h a p t e r2 w er e c a l lt h e “v d e c o m p o s i t i o nt h e o r y a n dt h e 所一l a g r a n g i a n 3 i nc h a p t e r3 w ei n t r o d u c et h er e l a t i v ek n o w l e d g ea n dt h e o r ya b o u t t h e d r - a l g o r i t h m 1 1 4 i nc h a p t e r4 w ei n t r o d u c eav a r i a b l em e t r i c p - a l g o r i t h m 5 i nc h a p t e r5 ，w ep r o o ft h ec o n v e r g e n c ep r o p e r t i e so ft h ea l g o r i t h m k e yw o r d s ：n o n s m o o t ho p t i m i z a t i o n ；h p - d e c o m p o s i t i o nt h e o r y ；u p - d e c o m p o s i t i o na l g o r i t h m ；m o r e a u - y o s i d ar e g u l a r i z a t i o n ；f a s tt r a c k u 1 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特 别加以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其 他同志的研究成果对本人的启示和所提供的帮助，均已在论文中做了明确的声明并表示 谢意。 学位论文作者签名：圣望：篁 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名： 响彩 指导教师签名： 签名e t 期： 2 。万年妇3 d 日 1 引言 一种变尺度的纠y 一分解算法 1 1历史概述及研究背景 由于科学和经济的飞速发展，非光滑现象经常出现在许多科学技术、管理 技术和经济学理论中由于传统光滑假设下所进行的大量的最优化和分析不能 直接应用于非光滑的情况中，所以八十年代c l a r k e ( 1 9 8 3 ) 2 】关于l i p s c h i t z i 函数的 微分学的研究成果使得非光滑微分学取得了突破性的进展，以l i p s c h i t z 函数为 主的非光滑分析与优化已形成独立的研究领域到目前为止，非光滑分析已经在 很多方面取得许多重要的结果但是目前，对于非光滑函数的研究主要存在以下 两个问题： 1 一般来说，次微分( 或c l a r k e 意义下的广义梯度) 较大且难以确定，其运算多 以包含形式来刻划，换言之，广义方向导数较大，即 厂o ( z ；d ) ，。( z ；d ) 对一阶近似的余项结构或性态不能清楚的表达出来； 2 另一个问题是关于函数的二阶近似，即二阶展开，它关系到算法的二阶 收敛问题并涉及到集值映射的微分学或近似这一问题成为自八十年代以来非 光滑分析与最优化研究中的一个核心课题 近些年，在函数的二阶近似这一专题的研究中有两项重要的结果，其一 为r o c k a f e l l a r ( 2 0 0 0 ) 关于非光滑函数的h e s s e 阵的研究成果，另一为l e m a r e c h a l ， m i f f l i n ，s a g a s t i z a b a l 及o u s t r y 等人提出的关于凸函数次微分的“1 夕一理论所弘 分解理论是一种研究非光滑凸函数二阶近似结构的新方法，其理论背景是基于 如下的问题： 当我们将凸函数厂在其不可微点牙做二阶t a y l o r 展开时，主要困难是来自 微分( 梯度) 已不再是一个向量而是一个集合，因此必须处理两个集合的差商，如何 给出一个合理的表达是一个不容易解决的问题在此之前的许多结果都还只是抽 象性的尝试( 【3 ， 4 】， 5 】， 6 ， 7 】) ，而没有形成较为有效的理论体系，但是这些研究工作 可以给我们带来许多启示 j 一b h i r i a r t u r r u t y 和c l e m a r e c h a l ( 1 9 9 3 ) 指出，厂( z ；) 的线性空间甜满足如 下性质：，( z ；) 在所上的限制是线性的且等于 ，其中s 是次微分o f ( x ) 中的任意元素换句话说，“是这样的元素h 的集合，使得函数h f ( x - t - h ) 1 一种变尺度的甜让分解算法 在点h = 0 是可微的，而o f ( x ) 在4 上的投影是单点集( 即沿着“的方向，c o f ( x ) 具有0 一宽度】由此可以得到如下两个事实： 第一，存在舻的一个子空间“，使得厂( 牙) 在甜上是线性的； 第二，定义，的二阶展开式无需沿着“以外的方向。例如，考虑情况 ，= m a x t 五，其中五是光滑的，即使仅知道，在“上的二阶性态，其序列二次规 划型的最小化算法仍是超线性的( 【8 】，【9 】) 在此基础上，2 0 0 0 年c l e m a x e c h a l ，f o u s t r y , 和c s a g a s t i z a b a l 关于“协分解 理论的奠基性文章 t h e 甜一l a g r a n g i a no fac o n v e xf u n c t i o n ”1 0 发表，文章 以f 1 1 1 ，i t 2 的研究成果为基础，其主要思想是将空间形分解成两个正交的子空间 “和v 的直和，使函数在甜上的一阶逼近是线性的，而其不光滑特征集中于v 中，借助于一个中间函数，甜一l a g r a n g e 函数，来得到函数在切与“的某个光 滑轨道上的二阶展式这样，设计非光滑最优化的算法可以在此光滑轨道上考虑 文章给出了凸函数，相对于某一点的牙的4 1 2 - 空间分解的三种等价形式和弘 l a g r a n g e 函数的基本形式，并对其基本性质进行了研究得出的主要结果有： 在某些条件下，点牙附近的厂在“上的限制与4 l a g r a n g e 函数直到二阶一 致，可以借助于4 - l a g r a n g e 函数的展开式得到函数厂在切与甜空间的某个轨 道上的二阶展开式： “y 一分解理论在非线性规划及一类半定规划上的简单应用： 应用“y 分解理论设计了一种概念型的超线性收敛的最小化算法 文 1 0 m 给出了凸函数的4 - l a g r a n g e 函数的一些基本性质，随后得到了推广 f 1 1 中对“一l a g - r a n g e 函数和对应的最优解集的特征进行了深入的研究，并把明让分 解理论应用在了几类函数中f 1 3 1 中提出了快速轨道的概念所谓的快速轨道，是 指由“一l a g r a n g e 函数的最优解集产生的光滑轨道，可通过所一l a g r a n g e 函数的二阶 性质得到厂在这条轨道上的二阶展开，进而设计相应的算法 在1 3 1 中还给出了这样的结论，一个有原始一对偶梯度( p d g ) 结构的凸函数有 一条快速轨道这种类型的一般函数有一组原始一对偶轨道逼近于一个( 极小值 点，零次梯度) 对原始轨道是一个c 2 函数，而对应的对偶轨道是一个c 1 的次梯 度函数，这个函数是由对应原始轨道点的次微分中模最小的向量所定义的 2 0 0 5 年r m i f f l i n 和c s a g a s t i z a b a l 在甜协分解理论的基础上提出了翻弘算 法1 4 1 ，算法中使用b u n d l e 子程序生成了一个逼近迫近点的点的序列当存在一 组指向解和零次梯度对的原始一对偶轨道时，这些点逼近于原始轨道点算法中 使用所一牛顿法对点进行迭代，其中所需的“一梯度也是通过子程序得到的 2 一种变尺度的“y 一分解算法 1 2 本文的主要工作 在第二章中主要介绍了“弘空间分解和- l a g r a n g e 函数的基本理论，在此 基础上定义了原始一对偶轨道，并给出了一些相关的性质 在第三章中主要是在甜1 夕一分解理论的基础上，介绍了“协分解算法的基本思 想其中定义了迫近点函数并讨论了迫近点函数与原始轨道关系 在第四章，首先通过更具一般性的m o r e a u - y o s i d a 正则化来定义了新的迫近 点函数，并证明了新的迫近点函数与原始轨道的关系随后给出了一种变尺度 的“1 夕一分解算法，算法中的b u n d l e 子程序使用了变尺度的b u n d l e 算法，且算法中 还使用了拟牛顿法中的s r l 校正公式对变量进行迭代 第五章给出了变尺度“让分解算法的收敛性证明，证明了算法具有全局收 敛性和超线性收敛 3 一种变尺度的“弘分解算法 2 甜协分解理论及原始对偶轨道 本章中我们讨论佗维欧式空间舻上的函数，舻中的内积记作( ，) ，由内 积导出的范数为i i 1 1 对于耙中的子空间e ，诱导出的e 上的内积和范数分 别记作( ，) e 和| i 怯设x 即，6 0 ，记舻中以z 为中心，6 为半径的开球为 b ( z ，6 ) ，而在子空间e 中对应的开球为b e ( x ，6 ) ，向量x 在子空间e 中的投 影为z e 2 1 “y 空间分解 设，是定义在彤上的有限值凸函数，在点z 舒的次微分集合记 为o f ( x ) 给定点牙形，使得i n t o f ( 牙) 0 ，且g a 厂( 牙) 定义空间形 在点牙处的甜让分解为舻= i i y ，其中，正交子空间“，v 可以通过三种方式 来定义 定义2 1 1 0 1 ( i ) 设矾是使得方向导数，7 ( 孟；) 为线性函数的子空间，：- - - 甜因为 ，( 牙；) 是次线性的，所以，有 矾：= u 月：t l ：厂( 牙；u ) = 一，7 ( 牙；一让) ( i i ) 设忱是平行于a ，( 牙) 所生成的仿射包的子空间，：= 谤即： 协：= l i n ( o f ( 牙) 一雪) 其中，雪a 厂 ) 是任意的 ( i i i ) 设和协分别是a 厂( 牙) 在点g 。r i o f ( 牙) 的法锥和切锥，其中扩是 任意的此时，和忱必为子空间 注：l i n m 表示由m 生成的线性空间 上面不同方式定义的空间分解，其结果是等价的 命题2 2 1 1 0 】由定义2 1 可得： ( i ) 当夕。r i o f ( 牙) ， b t 3 = d r n ：( g g 。，d ) = 0 ，v g a ，( 牙) ) = n o s e 孟) ( 9 。) ， 且与矿的选取无关 ( i i ) 矾= = u 3 ：= “； ( i i i ) 一般地，对雪a ，( 牙) ，有1 1cn o z t 孟) ( 雪) 设驴，矿分别是空间纠，y 的基矩阵，其中驴是正交矩阵贝i j 任意x 舻可分解 为： 4 一种变尺度的“协分解算法 毋弓z = 0 ( 0 t z ) + 矿( 矿t 刃- 1 矿丁z ) = u x u + v x v =xuoz v 2 栌m “2 栌m v o 表示由b l 1 夕到舻上的线性映射记作： “y 弓( u ，秒) 一“。 = c ) 舻 其中“，1 夕分别看作由让，口组成的向量空间 按照i v 中的数量积，有 ( g ，z ) = ( g uog v ，oz y ) = ( g u ，x u ) u + ( g v + x v ) v 注：考虑如下定义的三个函数分别为： “弓u _ h a ( u ) ：= ，( 牙+ 乱ou ) ，v v v y 弓u h 2 ( v ) ：= ，( 牙+ uo 秽) ，v u “ “1 夕弓一 ( u ，v ) ：= f ( x + uov ) 它们的次微分分别有如下的表达式： o h l ( u ) = 鲫：g f ( x + uo 秒) ) o h 2 ( v ) = a v ：g f ( e + uou ) o h ( u ， ) = 鲫og v ：g 厂 + uou ) 】 2 2 1 4 l a g r a n g e 函数 给定次梯度雪a 厂( 牙) ，其中协分量为如，则f 相对于咖的4 - l a g r a n g e 函l 数定义为 “弓u _ 上，甜u ) ：= i n f 厂( 牙- i - uou ) 一( 雪v ，口) v ) 伴随于弘空间的最优点集为： w ( u ) ：= a r g m i n ( f ( ：云+ 钆。口) 一( 9 v ，u ) v ) 由于协分量如= ( 矿t 同_ 1 f - t ) 雪，f 依赖于如的弘l a g r a n g e 函数可以定义 为： 舻硝弓u _ 切( “；如) _ 砌m 棚i n v m + 口让+ 讥) 一9 t 9 ) ( 2 2 1 ) 5 一种变尺度的甜让分解算法 相应的让空间的最优解集为： ( u ；如) = 矿 ：l u ( u ；0 v ) = f ( x + o u + 矿u ) 一耍t 矿口)( 2 2 2 ) 由【1 0 】，如果雪r i i ) f ( 孟) ，则( u ；咖) 非空每似一l a g r a n g e 函数都是一个凸函 数，且在钆= 0 处可微即 v l u ( 0 ；g v ) = 9 u = 驴t 雪= 驴t g ，v g a ，( 牙) 当孟是极小值点时，有0 a 厂( 孟) ，所以对于任意雪a ，( 孟) ，v l u ( 0 ；9 v ) = 0 ，有u = o 是切( 钍；雪v ) 的极小值点，且有l u ( 0 ；0 ) = ，( 牙) 2 3 原始对偶轨道 定义2 3 1 4 1 称( x ( u ) ，y ( “) ) 是逼近于( 牙，o ) 的原始一对偶轨道，牙是厂的极小值 点，对于足够小的u r d i n 讲， 原始轨道x ( u ) = 牙+ uov ( u ) 和对偶轨道，y ( “) = a r g m i n g 2 ：g a 厂( x ( 乱) ) ) ， 满足如下条件： ( i ) v ：r 出删_ r 出m y 是c 2 函数且对于任意雪r i o f ( 牙) ，有矿秒( u ) w u ( u ；如) ( i i ) j a c o b i a n 阵j x ( u ) 是y ( x ( u ) ) 上的一个c 2 函数 ( i i i ) h - l a g r a n g e i 函数切( 乱；o ) 是一个c 2 函数 当我们记u ( 乱) 时，是假设d i m h 1 当d i m h = 0 时，我们定义原始对 偶轨道为点对( 孟，o ) 当d i m h = 礼时，有( x ( u ) ，7 ( u ) ) = ( 牙+ u ，v 厂 + 钆) ) ，其 中u 在0 舻的一个球邻域里任取 当定义2 3 中条件( i ) 成立时，m 1 0 得，v ( o ) = 0 ，j v ( o ) = o r v ( u ) = o ( 1 u 1 2 ) ， 所以x ( 让) 是一条轨道，在牙点处与甜空间相切 引理2 4 1 4 1 ( x ( 钍) ，y ( 乱) ) 是逼近于( 牙，o ) 的原始一对偶轨道，使豆= v 2 l u ( 0 ；0 ) 假设0 r i o f ( z ) ，则当u 充分小时有以下结论成立： ( i ) x ( u ) 是一个c 2 函数 i j x ( u ) = 驴+ o ( 1 u 1 ) ， ( i i ) l u ( u ；0 ) = ，( 孟+ uo 秽( 乱) ) = 厂( 牙) + 互1 钆t b u + o ( 1 u 1 2 ) ， ( i i i ) v l u ( “；0 ) = h u + o ( 1 u 1 ) ( i v ) x ( u ) 是f 在仿射集x ( u ) + y ( ) ( ( 也) ) 上唯一的极小值点 ( v ) 7 ( 让) = j x ( u ) j x ( u ) t j x ( u ) _ 1 v l u ( 钍；0 ) r i o f ( x ( u ) ) ，是一个c 1 函数， ( v i ) 7 ( u ) = u h u + d “u 1 ) = u v l u ( u ；0 ) + o ( 1 u 1 ) 6 一种变尺度的“让分解算法 3 甜y 一分解算法的相关理论 3 1迫近点与原始轨道关系 给定一个正的标量参数p ，定义与函数，相关的迫近点函数为 1 鲰( z ) = a r g m i n z 舻 o k 正, ( z ) l z 一牙l _ o 则有m ( z ) = x ( ( z ) ) = 2 + u p ( x ) e v ( u p ( z ) ) ，其中( z ) = ( 巩( z ) 一牙h ，且当z _ 牙时，仳p ( z ) _ n 3 2 算法的基本理论 “弘分解算法是建立在“让理论和对原始一对偶轨道点逼近的基础上当原 始一对偶轨道存在时，算法在原始轨道上的逼近使用了一种弘牛顿步来进行校 正，而谚步是由b u n d l e 子程序所得到的迫近点来估计的因为当原始一对偶轨道 存在时，“v 一算法需要迫近点不但要在原始轨道上，还要在对偶轨道1 ( u ) 上所以 在b u n d l e 子程序中，通过两个二次规划问题解决了上述问题两个二次规划问题 记为x q p ，y q p 由定理3 1 可知，原始轨道的二次规划问题可以由迫近点函数来代替原始轨 道，即有 1 m i n r + 去p l p x 1 2 ：( r ，p ) r 1 + 竹，r y ( x ) 一e i + 订p z ) ，v z 召 ( x q p ) 对偶轨道的二次规划问题为 1 m i n r + 去i p z 1 2 ：( r ，p ) r 1 + n ，r 订p z ) ，舀) ( ，y q p ) 两个二次规划问题的计算输出分别为( 详见第四章4 2 ) ， ，庐) = x q p ( 弘，z ， ( e t ，吼) ) t 8 ) ，( ，u ) = 7 一q p ( g i t 廖) 每一次甜一步都是一个为了使l “( u ；0 ) 最小化的逼近牛顿步每次确定变量钆都 需要依赖如下几个变量， 7 一种变尺度的“弘分解算法 一个七一次梯度s 凫逼i 丘- y ( u ) = o v l u ( u ；0 ) + o ( 1 u 1 ) ， 一个矩阵巩逼近于y ( x ( 让) ) 上的一个基矩阵， 一个矩阵风逼近于v 2 切( u ；0 ) 经过弘步和让步后，可以得到一个候选的原始轨道点蚝牟，如果候选点满足 一个，一值的下降准则，则称这个候选点是“足够好的 对于不满足下降准则的候 选点，可以使用一种可行的线搜索方法，以确保迭代点收敛到极小值点 8 一种变尺度的“协分解算法 4 一种变尺度的纠y 算法 4 1 变尺度迫近点函数 为了适应更广泛的函数，并且使函数在b u n d l e 子程序中有更稳定的下降量 我们对“让算法中的迫近点函数进行改进，给出变尺度迫近点函数 设m 是几佗对称正定矩阵，定义函数厂相对于m 的变尺度迫近点函数为 p m ( x ) = a r g m i n ：r n f ( z ) + 去( z z ) lm ( z z ) ) z p 则有如下性质【1 2 】： ( i ) g m ( x ) = m ( x p m ( z ) ) o f ( p m ( x ) ) ， ( i i ) 如果牙是，的极小值点，葡m ) = 牙且i p m ( z ) 一引2 i z 一牙1 2 一i z 一 斯( z ) 1 2 ，t p 定理4 1 设x ( 钆) 是一个逼近于一个极小值点牙形的原始轨道0 r i o f ( 牙) ，假 设点z 充分接近孟，则有p m ( x ) = x ( u m ( z ) ) = 牙+ u m ( x ) ou ( 钆m ( z ) ) ，其中u m ( z ) = ( p m ( x ) 一牙) “，且当z _ 牙时，u m ( x ) _ o 证明：当z 一牙时，我们对迫近点m ( z ) 进行“弘分解，p m ( x ) = 牙+ u m ( x ) o v m ( x ) 其中钆m ( z ) = ( p m ( x ) 一牙) “，v m ( x ) = ( p m ( x ) 一牙) y 由上述性质( i i ) ，i p m ( x ) 一 牙1 2 i z 一牙1 2 ，于是有 p m ( x ) 一牙i i z 一引所以当z 一牙时，u m ( x ) _ o 同理 当z _ 牙时，有( 牙一x ) v 一0 ，v m ( x ) _ 0 因为v ( u ) = o ( 1 u 1 2 ) 【1 0 l ，所以当z 一 牙时，v ( u m ( x ) ) 一0 定义w m 为舻一冗啦m y ， w m ( z ) = 矿t 矿】_ 1 矿t m f ( x 一牙) v 一皋矿t 矿r _ 1 矿t m 矿( u ( u m ( z ) ) + 秒m ( z ) ) 厶 当z 一牙，有w m 一0 由“v 一分解理论中的对y 空间的定义可得，当点z 充分接 近牙时，有w = o o w m ( x ) r i o f ( “2 ) 由切的定义，变量( u ，百) 可等价于( 乱m ( z ) ，w ) r d i w r i o f ( 牙) 即l u ( 乱m ( z ) ，训m ( z ) ) = ，( x ( 钆m ( z ) ) ) 一w t 矿口( 钆m ( z ) ) 当u m ( z ) r 出m v ，l u ( 钆m ( z ) ，伽m ( z ) ) 厂( 牙+ u m ( z ) ov m ( x ) ) 一w t 矿 m ( z ) 由上述两式得， ，( x ( 饥m ( z ) ) ) 一w t f v ( u m ( z ) )f ( p m ( z ) ) 一w t 9 v m ( z ) ( 4 1 1 ) 由迫近点映射的定义得 ，m ( z ) ) + 互1 ( p m ( z ) 一z ) t m m ( z ) 一z ) s ，( ) ( ( u m ( z ) ) ) + 丢( x ( 钍m ( z ) ) 一z ) t m ( x ( 乱m ( z ) ) 一z ) ( 4 1 2 ) 9 一种变尺度的甜弘分解算法 联合不等式( 4 1 1 ) ，( 4 1 2 ) 得 石1p m ) - x ) t m ( v m ( z ) - x ) 一言( x ( u m ( z ) ) 一z ) t 订( x ( u m ( z ) ) - x ) w t 矿( 口( m ( z ) ) 一t 砌- ( z ) ) ( 4 1 3 ) 为了计算方便，不等式中u 小p m 、v m 、移( u m ( z ) ) ，改写为u m 、p m 、v m 、v ( u m ) 由z j = p m 与x ( 乱m ) 有相同的弘分量， 去 p m z ) m m z ) 一( x ( u m ) 一z ) 。m ( x ( u m ) 一z ) 】 1 = 去 f x ( u m ) ) m ( p m + x ( t t m ) 一2 x ) 1 = 去( y ( 口m v ( u m ) ) 。m v ( v m + v ( u m ) ) 一2 ( z 一牙) v ) =石1 口五矿t m f f u m u ( u m ) t v m v v ( u m ) 】+ ( v ( u m ) 一u m ) t 矿t m v ( x 一牙) v 因为矿t w = 矿t ( 0 0 + ? w m ) = 矿t 矿叫m ，不等式( 4 1 3 ) 右边可得， w t 矿( 秒( 乱m ) 一u m ) = ( v ( u m ) 一v m ) t 矿t w = ( v ( u m ) 一v m ) t 矿t 矿叫m = ( v ( u m ) 一v m ) t 矿t 矿( 矿t 矿】- 1 矿t m v ( x 一牙) y 一皋矿t 矿】_ 1 矿t m 矿( u ( 钆m ) + v m ) ) = ( v ( u m ) 一v m ) t 矿t m v ( x 孟) v 一去( 秒( u m ) + v m ) t 矿t m f ( v ( u m ) + 秒m ) =却u 五矿t m v v m 一钉( 缸m ) t 矿t m 矿v ( u m ) 】+ ( v ( u m ) 一u m ) t 旷t m 订d ( x 一牙) y 由上述结果可知，不等式( 4 1 3 ) 为等式即( 4 1 3 ) 不可能为严格不等式所以不等 式( 4 1 1 ) ，( 4 1 2 ) 都不满足严格不等当p m 唯一，由( 4 1 2 ) 可得p m ( z ) = x ( 乱m 0 ) ) 此 时v m ( x ) = u ( u m ( z ) ) 4 2b u n d l e 子程序 与“y 一算法相同，改进的算法中的b u n d l e 子程序，也是通过b u n d l e 算法分别 解决原始一对偶轨道的两个二次规划问题这两个二次规划问题分别记为x m q p , 7 m q p 在此之前给出如下定义： 给定一个容差盯( 0 ， ) ，一个对称正定的礼礼的矩阵m 和一个逼近中心z 形b u n d l e 子程序从过去的迭代点玑中积累的信息表示为 ( 厂( 玑) ，g i a 厂( 仇) ) ) 召 b 是指标集，其中包含一个指标歹，有协= z 定义线性误差项，= e ( x ，犰) = f ( x ) 一( w ) 一订( z 一玑) ，i 1 3 对应的，定义厂的切平面函数妒( 名) ， 妒( z ) = f ( x ) + 嘴 f ( x ) 一e i + 订( 声一x ) r ( 4 2 1 ) 妒( 痧) = ，( z ) + 如( - e t + 订p z ) ) = ，( z ) 一色e t 一扩m 一1 雪 ( 4 2 2 ) i e bt 召 以上结果在计算输出时记为：，严) = x m q p ( m ，z ， ( e t ，吼) i 诞b ) 向鄞是迫近点的一个估计量，这里定义新的信息：一个新的指标i + ，使得犰+ = 庐， h g i + o f ( 1 5 ) 在p 点定义舍= ，p ) 一妒 ) = 厂 ) 一庐定义新的指标集舀= z b ：庐= f ( x ) 一e t + 订 一z ) ) u i + ) 与对偶轨道相关的二次规划问题伽一q p ， m 礼 r + 丢 p - - x 1 2 ：( r ，p ) r l + n ，r 订。一z ) ，v i 廖) ( 7 m q p ) 对偶问题为：r a i n ；1e o l 锄1 2 ：锄o ，i 雪，e 叱= 1 ) i e 8i e 8 对应的解记为( f ，箩) 和a ，满足 一一z = 一，6 = f 画吼(423p 8 ) 一z = 一s ，5 夕，啦吼 【j j - _ ， t 雪 值得注意的是，是一个逼近对偶轨道的点，它是在 吼：i 为) 的凸包中欧 几里德范数最小的向量如果p m ( x ) ：是- - 个由p 逼近的原始轨道x ( u ) ，则有 吼： i 廖) 的凸包逼近a 厂( x ( 让) ) 由对偶轨道定义，用来估计，y ( 钆) ，痧近似于y ( x ( u ) ) 上的 一个基矩阵，定义一个非空的积极指标集，站= z 廖：f = 订p z ) 】- 由( 4 2 3 ) 得f = 一订，v i 晚。t 所以( 肌