（应用数学专业论文）有限最大值凸函数uv—算法的一个注记.pdf

摘要 在非光滑最优化中，非光滑函数的二阶展开对于最优性条件的研 究以及设计具有高阶收敛性的算法都是不可缺少的工具因此，对 非光滑函数的二阶性质与展开的理论研究一直备受关注2 0 0 0 年， c l e m a r d c h a l ，f o u s t r y 和c 。s a g a s t i z 5 b a l ( 2 0 0 0 ) 提出u y 一分解理 论 1 1 】，其主要思想是将空间毋分解成两个正交的子空间u 和y 的 直和，使函数在矿上的一阶逼近是线性的，而其不光滑特征集中于y 中，借助于一个中间函数，u - l a g r a n g e 函数，得到函数在切于u 的某 个光滑轨道上的二阶展式这样，设计非光滑最优化的算法可以在此 光滑轨道上考虑 本文针对一类有限最大值凸函数的u y 一分解理论以及在u 弘分 解理论基础之上的u y 一算法进行了论述本文共分三章第一章是 引言，主要介绍了u u 分解理论的研究背景第二章研究的是一类 有限最大值凸函数的u y 分解理论在此，给出了两种不同的条件 假设，在这两种条件假设下，分别引入了有限最大值凸函数的空间 分解、u l a n r a n g e 函数及其一阶、二阶展开性质第三章在引入 m o r e a u - y o s i d a 正则化的概念的同时并提出了在算法中如何选取迭代 信息的一种新方法，最后给出了有限最大值凸函数的u y 一算法以及该 算法的收敛性 关键词：非光滑最优化，u 弘分解理论，u l a g r a n g e 函数，迫近点， b u n d l e 算法，m o r e a u y o s i d a 正则化 a b s tr a c t i nn o n s m o o t ho p t i m i z a t i o n ，s e c o n d - o r d e re x p a n s i o nt h e o r yl ss i g - n i f i c a n tb o t hf o rd e r i v i n go p t i m a l i t yc o n d i t i o n sa n dd e v e l o p i n ga l g o - r i t h m s t h e r e o f r e ，t h es t u d yc o n c e r n i n gt h e o r yo ft h es e c o n d - o r d e r p r o p e r t i e so fn o n s m o o t hf u n c t i o n sh a v eb e e np a i dm u c ha t t e n t i o n c l e m a r d c h a l ，f o u s t r ya n dc s a g a s t i z d b a l ( 2 0 0 0 ) i n t r o d u c e dt h e 矿y 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 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 er ni n t ot w oo r t h o g o n a ls u b s p a c e sua n dv d e p e n d i n go n 牙s ot h a tf sn o n s m o o t h n e s sn e a rt 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 n 矿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 ec 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 du - l a g r a n g i a n w h e nfs a t i s f i e s c 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 r 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 nf o r | i nt h i sp a p e rw ed i s c u s st h eu v s p a c ed e c o m p o s i t i o nt h e o r yo f t h el i m i t e dc o n v e xm a x - f u n c t i o n t h e r ea r et h r e es e c t i o n si nt h i sp a - p e r i nt h ef i r s ts e c t i o n ，w ei n t r o d u c et h er e s e a r c hb a c k g r o u n do ft h e u v - d e c o m p o s i t i o nt h e o r y i nt h es e c o n ds e c t i o n w es t u d yt h eu v _ d e c o m p o s i t i o nt h e o r yo ft h el i m i t e dc o n v e xm a x - f u n c t i o n i no r d e rt o d i s c u s st h i sp r o b l e m ，w eg i v et w od i f f e r e n th y p o t h e s e so fc o n d i t i o n s ， i nt h e s et w ok i n d so fh y p o t h e s e s ，w el e a di n t ot h es p a c ed e c o m p o - s i t i o n 、u - l a n r a n g ef u n c t i o na n dt h ec h a r a c t e ro ft h eo n eo r d e ra n d t w oo r d e ro ft h el i m i t e dc o n v e xm a x - f u n c t i o n i nt h et h i r ds e c t i o n ， w eg i v eac o n c e p t i o no fm o r e a u - y o s i d ar e g u l a r i z a t i o na n da l s og i v ea m e t h o dh o wt oc h o o s eap o i n ti nt h ea l g o r i t h m l a s t w eg i v et h e y a l g o r i t h mo ft h el i m i t e dc o n v e xm a x - f u n c t i o na n dt h ec o n v e r g e n c eo f t h i sa 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 ；u v d e c o m p o s i t i o nt h e o r y ； u l a g r a n g ef u n c t i o n ；p r o x i m a lp o i n t s ；b u n d l ea l g o r i h m ；m o r e a u - y o s i d ar e g u l a t i o n 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特 别加以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其 他同志的研究成果对本人的启示和所提供的帮助，均已在论文中做了明确的声明并表示 谢意。 学位论文作者签名：委越， 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：翘 指导教师签名： 签名同期： 姗呵年5 月弓d 日 有限最大值凸函数u y 一算法的一个注记 1引言 1 1 u y 分解理论的研究背景 我们在当今的科学技术发展和应用中，经常会碰见非光滑现象然而传统的光 滑假设下所进行的大量的最优化和分析不能直接应用于非光滑的情况中，这就需 要建立新的理论体系( 非光滑分析) 来很好的处理这类非光滑最优化问题七十年 代c l a r k e ( 1 9 8 3 ) 2 】关于l i p s c h i t z 函数微分学的研究成果使得非光滑微分学取 得了突破性的进展，以l i p s c h i t z 函数为主的非光滑分析与优化已形成独立的研 究领域( 方向) 这一时期直至八十年代初，研究工作十分活跃，其内容也迅速地扩展 到各个专题 此时，对于非光滑函数的研究主要存在以下两个问题： 1 一般说来，次微分( 或c l a r k e 意义下的广义梯度) 较大且难以确定，其运算 多以包含形式来刻画，换言之，广义方向导数较大，即 ，u ( z ；d ) f ( 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 色c h a l ，m i f f i l i n ，s a g a s t i z a b a l 及o u s t r y 等人提 出的关于凸函数次微分的u y 一理论u y 一分解理论是一种研究非光滑凸函数二 阶近似结构的新方法，其理论背景是基于如下的问题：当我们将凸函数厂在其不 可微点牙做二阶t a y l o r 展开时，主要困难是来自微分( 梯度) 已不再是一个向量而 是一个集合，因此必须处理两个集合的差商，如何给出一个合理的表达不是一个容 易解决的问题在此之前的许多结果都还只是抽象性他尝试( 4 】， 5 】， 6 ， 7 】， 8 】) ，而 没有形成较为有效的理论体系，但是这些研究工作可以给我们带来许多启示 j 一b h i r i a r t u r r u t y 和c l e m a r d c h a l ( 1 9 9 3 ) $ 旨出，。，( z ；) 的线性空间u 满足如 下性质：f ( z ；) 在u 上的限制是线性的且等于 ，其中s 是次微分o f ( x ) 中的任意元素换句话说，u 是这样的元素h 的集合，使得函数h f ( x + h ) 在 点h = 0 是可微的，而c o f ( x ) 在上的投影是单点集( 即沿着u 的方向，o f ( x ) 具 有0 一宽度) 由此可以得到如下两个事实： 1 有限最大值凸函数u y 一算法的。个注记 第一，存在r n 的一个子空间u ，使得，7 ( 牙；o ) 在上是线性的： 第二，定义，的二阶展开式无需沿着u 以外的方向例如，考虑情况f = m a x 五，其中五是光滑的，即使仅知道，在u 上的二阶性态，其序列二次规划型的 最小化算法仍是超线性的( f 9 1 ，f 1 0 1 ) 在此基础上，c l e m a r d c h a l ，f o u s t r y , 和c s a g a s t i z 5 b a l ( 2 0 0 0 ) 提出u y 一分解 理论i n ，其主要思想是将空间舻分解成两个正交的子空间u 和y 的直和，使函 数在u 上的一阶逼近是线性的，而其不光滑特征集中于y 中，借助于一个中间函 数，u l a g r a n g e 函数，来得到函数在切与u 的某个光滑轨道上的二阶展式这 样，设计非光滑最优化的算法可以在此光滑轨道上考虑 事实上，u l a g r a n g e 函数的思想来源于c l e m a r e c h a l 和c s a g a s t i z a b a l ( 1 2 】， 1 3 ) 对于凸函数的一阶展开式中的余项问题以及凸函数与它的m o r e a u - y o s i d a 正则化的二阶性质之间的关系的研究 2 0 0 0 年c l e m a r 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 关于u y 一分解理论的奠 基性文章”t h eu - l a g r a n g i a no fac o n v e xf u n c t i o n 1 1 发表，文章以 1 2 】， 1 3 】的 研究成果为基础，给出了凸函数厂相对于某一点的牙的u v - 空间分解的三种等 价形式和u l a g r a n g e 函数的基本形式，并对其基本性质进行了研究得出的主要 结果有： 在某些条件下，点牙附近的厂在矿上的限制与u l a g r a n g e 函数直到二阶一 致，可以借助于u l a g r a n g e 函数的展开式得到函数厂在切与u 空间的某个轨道 上的二阶展开式； u y 一分解理论在非线性规划及一类半定规划上的简单应用； 应用u y 一分解理论设计了一种概念型的超线性收敛的最小化算法 1 2 本文的研究工作 这篇文章针对一类有限最大值凸函数进行了讨论首先给出有限最大值凸函 数的有关y 一空间分解方面的理论知识，在此基础上给出两个不同的条件来构 造有限最大值凸函数的矿一l a g r a n g e 函数以及在这两种不同的假设条件下讨论 矿一l a g r a n g e 函数的一阶、二阶的展开其次，提出了一种迭代信息中迭代点的选 取方法最后给出有限最大值凸函数的u y 一算法并证明其收敛性 2 有限最大值凸函数u y 一算法的一个注记 2有限最大值凸函数的u y 一理论 2 1基本概念 定义2 1 1 f 是有限最大值凸函数，若，有如下的表示形式： f = m a x 五( z ) ：i = 0 ，m ) ( 2 1 1 ) 其中五：舻一兄是c 1 的凸函数，则f 也是凸的并且是处处可微的 设厂是如上定义函数，我们记： i ( x ) ：= z _ 【o ，m ) ：k ( x ) = 厂( z ) ) 是函数厂在点z 的积极约束指标集我们给定牙舻，记，= ，( 牙) 为了不失一 般性假设0 j 记： 吼( z ) t ：= v y , ( x ) 昴：= v 六( 牙) 于是得到： o f ( e ) = c o n v g j ，j j ( 牙) ( 2 1 2 ) 命题2 1 2 ( 2 1 1 ) 中函数，在牙形处的u y 一空间分解如下： y ( 孟) = l i n ( t 易一面) b j u ( 牙) = d r n ：( d ，易一面) = o ，j ，( 牙) ) 证明：因为如o f ( 5 ；) = c o n v g j b f ，由 1 1 】中的定理2 1 中的( i i ) 便可得到 取定雪a 厂( 牙) ，则相应的u l a g r a n g i a n 函数和最优解集为： r d l m u 弓让一l u ( u 洲_ 锄m 渤i ny m + 驴饥+ 讥) 一严讯一 ( 2 1 3 ) w ( 让；雪y ) ：= e v ：l u ( u ；如) = f ( x + o u + 矿u ) 一雪丁矿可) ( 2 1 4 ) 其中矿是y 的基矩阵，驴是u 的正交基矩阵 定义2 1 3 【17 】设p 是舻的一个子集，我们称集合p 是仿射集，若满足： ( 1 一a ) x + 入可p ) 比尸，v y 尸；a r 定理2 1 4 1 1 r r n 的子空间是包含原点的仿射集 定义2 1 5 【17 】礼+ 1 个点b o ，b 1 ，b n 是仿射无关的，若： a f f b o ，b l ，) 3 有限最大值凸函数u y 一算法的一个注记 是n 维的 命题2 1 6 b o ，b 1 ，k 是仿射无关的当且仅当 是线性无关的 6 1 6 0 ，厶n 一6 0 2 2 一个特殊的例子 命题2 2 1 f 1 5 】 给定牙，取雪a 厂( 孟) ， 或) i f 是f 在点牙的积极约束梯度，假 设 ( 1 ) f 在点牙的积极约束梯度 或) t j 是仿射无关的即： 有唯一解 ( 2 ) 对于下列问题： 它的( 唯一) 解 满足 啦或= 0 ， i e l 叱= 0 i e i 叱= 0 ，v i i o i = 雪， i e i q 产1 i e i o q = 龟) j 画 0 ，v i i 由以上的( 1 ) 和命题2 1 2 可知，子空间v 的维数是i i i 一1 定理2 2 2 【1 5 】假设命题2 2 1 成立对于充分小的u u ，式( 2 1 4 ) 所定义的 最优解集w ( u ) 是单元素集u = v ( u ) v 且满足： 五( 孟+ 钆o ) = ，o ( 牙+ 钆ou ) ，i ， 证明：由 1 1 】中的定理3 2 可知： w ( 乱) 兮j 夕= g uo0 a 厂( 牙+ uo 训) 记：z = 牙十钆ow ，有： w ( 钆) j q 0 ：啦= 1 ，q i 仇( z ) 矿 i ，l ， 4 有限最大值凸函数矿y 一算、法的一个注记 由此可以得到命题2 2 1 中的( 2 ) 有非负解当u 充分小时z 一牙也很小，由命题 2 2 1 得到 五( 牙- fuou ) = f o ( 牙+ uo 口) ，i i 进一步，由 或) i ，仿射无关可知 俄) 州是仿射无关的由隐函数存在定理：对 足够小的u ，上述问题有唯一解v ( u ) 得证 l u ( u ；如) 是凸的，并且在u = 0 是可微的如果l u ( u ；o ) 在u = 0 存在 h e s s i a n 阵，则u - l a g r a n g e 函数就可以进行二阶展开为了和厂有很好的二阶近 似，我们定义下面的一对轨道： 定义2 2 3 【1 6 1 称( x ( ) ，7 ( u ) ) 是厂的原始对偶轨道，如果u f t d i m u 且u 足 够小时， x ( u ) ：= 牙+ 让ov ( u ) 趋于牙，其中牙是厂的极小值点 7 ( 钆) ：= a r g m i n ( 1 l g u 2 ：g a 厂( x ( u ) ) ) 趋于。梯度 且满足： ( 1 ) v ：r d 妇uh h n y 是c 2 函数且对所有的雪r i o f ( n 2 ) 都满足 v v ( u ) 勺( u ；雪y ) ； ( 2 ) j x ( u ) 是味) 的基矩阵，这里y ( x ( u ) ) 上是u y 一分解的v 空间 ( 3 ) l v ( u ；0 ) 是c 2 的 下面我们考虑原始轨道 x ( u ) ：= 厉- m - uo v ( 2 2 1 ) 的一些性质首先我们给出一些概念： 命题2 2 4 1 5 】给定一组列向量集合 q 1 ，q m ) ，它们所生成的矩阵我们 用： q 1 i 一，q m ) 】 来表示相应的，我们记： k o ) ：= 或一面) o 靴疗 是子空间v 的基如果职o ) 是子空间u 的基，我们有如下结果： u v 弓( u ，移) huov = u ( o ) u + v ( o ) v r n ( 2 2 2 ) 同样，我们记作： k u ) ：= 0 v i i v l u ( u ) = q t ( u ) ( 吼( x ( 乱) ) ) t 敞。) v 2 l v ( u ) = j x ( u ) t ( o t t ( u ) v 2 以( x ( u ) ) ) 圾( 札) t ， 因此，厂在牙有u h e s s i a n ： 嘞m ) = v 2 l u ( o ) = ) ( a v 2 以) = ( 诧v 2 f t ) u v ，i ， 7 有限最大值凸函数u y 一算法的一个注记 2 3一般的例子 这一节我们将给出一个要弱于命题2 2 1 的条件，然后研究在这个假设条件 下u h e s s i a n 的存在性 同样地，我们给定 雪a 厂( 孟) 我们考虑积极约束指标集的一个子集，记k 命题2 3 1 【1 5 】我们称一个非空子集k ，是基本可行指标集，若： ( 1 ) 集合 玩) k 是仿射无关的 ( 2 ) 下列问题 fceioi=雪，f=1曲，vikoqgi o t i v ik 乙 2 9 乙2 l q l ， i e ki e k 有唯一解 q l = 也) k 引理2 3 2 【1 5 】若固定牙和雪a ，( 牙) ( 1 ) 至少存在一个基本可行指标集k ，满足命题2 3 1 ( 2 ) 若命题2 2 1 成立，则，是唯一的基本可行指标集 在以后的内容里，我们固定k ，并且不失一般性，我们假设k 包含0 为了求出最优解集中点的性质，我们给出一些概念： 命题2 3 3 1 5 】首先给定基本可行指标集k ，令 是子空间坛的基，且坛为： k o ) ：= 或一0 0 o i r 】 v k ：= l i n 0 i 一珈) o 氧露 若子空间坛是整个空间y ，则令z ( o ) ：= 嗍是个空矩阵否则z ( o ) ：- - - - = y 坛无 论哪种情况我们都- jp a 将向量集合 或一蜘) o 粕r 扩充成一组可以生成空间v 的向量组，此时记y 的基矩阵为 y ( o ) l 互o ) 】 在命题2 2 2 中，我们是通过一个隐函数v = u f u l 来反映最优解集w ( u ) 的性 质的因为我们通过 或一蜘) o 缸霞只能生成空间y 的子空间坛所以下面我将 会用到 ( v ，0 ) i 么xr d l m y d i m v k ：v 相应地原始轨道在这里就可以记作： x ( u ) ：= 牙+ 钆o ( k u ) ，0 ) = 牙+ u ( o ) u + o ) k u ) ( 2 3 1 ) 8 有限最大值凸函数u y 一算法的。一个注记 其中：口：u 一坛将会在下面的定理中给出定义我们记： k ) ：= 【 或( ) ( ( 仳) ) 一面( x ( u ) ) ) o 拒露 特别地，当k 是单元素集时，坛= o ) 并且o ) 是一个空矩阵此时，我们定义原 始轨道为： x ( u ) ：= 牙+ uo0 = 孟+ u ( o ) u ( 2 3 2 ) 并且j x ( u ) 三阢o ) 定理2 3 4 1 1 5 1假设k 是命题2 3 1 中所定义的基本可行指标集并且不是单 点集对于钆u 且充分小，则： ( 1 ) 下列问题： 五( 牙+ uo ( k ) ，o ) ) = 矗( 牙+ o ( k u ) ，o ) ) ，0 i k ( 2 3 3 ) 有唯一解移= u ( 仳) 坛冬y ； ( 2 )钞( ) 有连续的雅可比行列式： j r ( ) = 一( 唱k o ) ) 。1 嗡职o ) ； ( 3 )原始轨道x ( u ) 有连续的雅可比行列式： t j r ) ( ( 乱) = 玖o ) + o ) j k 牡) ( 4 ) 特别地： k o ) = 0 ，了k o ) = 0 ，j x ( o ) = 圾o ) 根据定理2 2 6 中的q tu ) ，我们作如下定义： q ( 乱) 是由向量组 啦( 让) 】- k 所组成的包含。的i k | _ 维列向量，e t 是i k i l 维的行向量，i l g l l 是( i k i 一1 ) ( i k l 一1 ) 维的单位矩阵令c ( u ) 是一个他l k i 的矩阵函数： g ( u ) ：= 【o l k u ) 】+ 9 0 ( x ( u ) ) 1 l e t 】= 9 t ( ) ( ( 乱) ) ) 诞k 】( 2 3 6 ) 定理2 3 5 令k 是基本可行指标集对于牡u 且充分小，有： ( 1 ) 下列线性问题： ( ；kq t ( 阢( x ( u ) ) 一雪) = 0 i i k 啦= 1 9 有限最大值凸函数u y 一算法的一个注记 有唯一解 有如下形式： 啦= 啦( 乱) k k ， q t ( u ) 】o 判k = 一( 联西k “) ) 一1 联昌( 9 0 ( x ( u ) ) 一雪) q o ( 钆) = 1 一q t ( u ) o i c k 特别地对所有的i k 我们有q t ( 0 ) 一盈 ( 2 ) 另外，如果每个函数五都是c 2 的凸函数，则我们得到： o ( u ) j a ( u ) = o l v i u ) 】j q ( u ) ， 其中q ( ) 的雅可比行列式为： 坤) = 2 。懈绀1 p v 2 触圾( u ) ( 2 3 7 ) ( 2 3 8 ) 并且若k 是单点集的话，j a ( u ) = 0 命题2 3 6 满足命题2 3 1 所有的k ，至少存在一个集合露，当乱充分小 时，有： ( 1 )f j ( x ( u ) ) f o ( x ( “) ) ，w i k ( 2 ) 定理2 3 5 中的算子 0 f i ( u ) ) 讵露是非负的 ( 2 ) z ( o ) t t 露q i ( 乱) ( 矶( x ( 乱) ) 一雪) = 0 下面我们来总结一下此时的最优解集w ( u ) 的有关性质 定理2 3 7 1 5 假设命题3 3 6 成立，令u ) 是定理2 3 4 ( 1 ) 中所定义对于 u u 且充分小，有： ( 1 )( “) ，0 ) 坛r d h n 弘出m 喙= v 是最优解集w ( u ) 中的元素 ( 2 )u l a g r a n g e 函数可以写成下列形式： l u ( u ) = ( ) ( ( “) ) 一( 雪，o ) k “) ) ，v i k ( 3 ) 若命题2 2 1 成立，则露= j ，并且w ( u ) 是单点集 k u ) ) 我们给出此时厂的u 一梯度和u h e s s i a n 阵 定理2 3 8 假设命题2 3 6 成立对于u u 且充分小，有： ( 1 ) l 【，的梯度有如下形式： v l u ( 钆) = q l ( u ) 仂( ) ( ( 钆) ) 丁 f 露 1 0 有限最大值凸函数u y 一算法的一个注记 特别地有 v l u ( o ) = o r v ( o ) = g t v ( o ) ，v g a ，( 孟) ( 2 ) 若每个函数五是c 2 的凸函数，l u 的h e s s i a n 阵有如下形式： v 2 l u ( 札) = 则函数厂在点牙的u - h e s s i a n 阵可以表示为： ，( 牙) = v 2 l u ( o ) = 哪) ( ( 面v 2 五( 牙) ) 阢。) = ( i e k 1 l t k诧v 2 ( 牙) ) 耐 u x ， - 一= = 、0x v 口 i ； ，、 r ，：、q x j 有限最大值凸函数u y 一算法的一个注记 3 有限最大值凸函数的u y 一算法 这种极小化算法可以从任何一个初始点出发，在b u n d l e 技术中利用线搜索 来完成，它是b u n d l e 算法的一种新的表示方法，因为在算法中它利用了一个新的 b u n d l e 子程序另外，这种算法也可以看成是一种加快的迫近点算法，因为它在每 个迫近点的迭代信息中加入了二阶信息 3 1 基本概念和定理 首先介绍有关m o r e a u - y o s i d a 正则化和迫近点的有关概念 定义3 1 1 1 1 6 1 f 在z 处的m o r e a u - y o s i d a 正则化为： f ( z ) 2 笑盘 ，( z ) + 主p j i z z i l 2 ) p 0 其中f ( x ) 是连续可微的凸函数 记点z 的迫近点函数为： p a x ) ：= a r g m i n f ( z ) + 圳z z 怫 其中它们有如下关系： v f ( x ) = 肛( z 一鼽( z ) ) a ，( 钆( z ) ) 下面给出的是原始轨道和迫近点的关系以及迫近点理论和u y 一理论之间 的关系定理首先我们给出下列迫近点与原始轨道的关系定理： 定理3 1 2 【1 6 】令x ( u ) 如定义2 2 3 所述是趋于，的极小值点牙的原始 轨道，则0 o f ( e ) ，当z 和牙充分接近的时候，并且p 0 ，当z 一牙时，有 s i x 一孟i 叫o 则对所有的和牙充分接近的z ，我们有： 巩( z ) = x ( u p ( z ) ) = 牙- f ( z ) ov ( u p ( z ) ) ，u p ( z ) ：= ( 巩( z ) 一牙) u 并且当x 一牙，有( z ) 叫0 证明略 3 2 迭代信息选取 下面将给出最大值函数在b u n d l e 子程序中次梯度的有效选取方法 设当前迭代点是o ，对于下一个迭代点的选取，在b u n d l e 子程序中我们要用 到以前的迭代信息： ( 厂( 玑) ，g i o f ( y i ) ) i b 19 有限最大值凸函数u y 一算法的一个注记 其中b 是满足如下条件的指标集： 习b ，协= z 我们设，( 犰) 是，在犰的积极约束指标集即 i ( y i ) ：= d o ，m ) ：厶( 轨) = ，( 珑) ) 则 a f ( y 1 ) = c o n v g j ，易a 乃( 玑) ，j i ( y i ) 则该如何选取 俄o f ( y i ) ， 使得迭代信息更好? 因为 f ( z ) 厂( 犰) + 毋( z 一玑) ，v z r n ， 可以得到 ，( z ) 办( 犰) + 方( z 一犰) ，j j ( 犰) 所以 ，( z ) f ( y i ) + 9 z 一犰) ，j i ( y i ) 由此构造下列二次规划问题来选取仇： m i n r + 专i i z y i l l 2 ：r ，p ) r l + n , r ，( 犰) + 鳄( z 一犰) ，j j ( 玑) ) ( 3 2 1 ) 定理3 2 1 令乏是( 3 2 1 ) 的解，则有下列结果： ( 1 ) 乏= y 一雪，其中雪= j 地；) 嘞缈 ( 2 )a = ( 西，q | j 如) l i ) 是下列问题的解： ( 3 2 2 ) 证明将问题( 3 2 1 ) 写n - t 2 下列形式： 曼涮1 - y , ) , j 酽e 地，2 劫 l ( z ，呻) = r + 钏z 一玑1 1 2 + o g ( ( f ( y i ) + g f ( z y i ) 一r ) ， 蚓 = 哟 触 矧 码。| 一 有限最大值凸函数u y 一算法的一个注记 即 l ( z ，r ，q ) = 丢i z - 轨1 1 2 + ，( 犰) 一 j e i ( y i ) 由于( 2 1 ) 中的目标函数是强凸的，所以下列问题等价： 其中 g t ( z 一玑) ， z m r i n 。a m r l i a ，( x 巩川l ( 可，q ) = n m r a ，( x 巩) hz m r i n 。l ( 可，q ) 己( z ，a ) = 三i z - 犰1 1 2 - t - f ( y i ) 一 则我们可以知道 的充分必要条件是 即 特别的是，当 可以得到 方( z 一犰) ， j e i ( v i ) z ( q ) = a r g m i n l ( z ，q ) ： 0 = v 名l ( z ( 口) ，0 f ) 0 = 名( a ) 一玑+ i e i ( v i ) 0 f = o l q j g j ， 用名( q ) 一y i 和g j 分别乘以( 2 4 ) 的两端，得到： 由此我们可以得到 所以得到 0 = i i z ( q ) 一犰1 1 2 + o , j ( g j ，z ( 0 f ) 一耽) ， 0 = j e l ( w ) z ( a ) 一玑) + l | z ( o l 、一v , 1 1 2 = l ( z ( q ) ，0 1 ) = _ 厂( 玑) 一 综上所述，a 是下列问题的解： m a xl ( z ( 及) ，0 1 ) = a f ( y i ) y j l g j i j e l ( y t ) 三i i 缈i f 2 j e l ( y i ) 一赠n 扣g j j e l ( y i ) 1 4 ( 4 2 4 ) ( 4 2 5 ) 有限最大值凸函数u y 一算法的一个注记 得证 则我们选取g i = 雪= 邑，( 玑) a j g j 为我们所选取的迭代信息 ( 厂( 轨) ，g i a ，( 犰) ) k b 我们可以知道g i 在 o f ( y , ) = c o n v g a ，劬a 力( 孟) ，j ，( 牙) 中具有最小的欧几里德范数 ，定理3 2 2 历具有下面的性质： g i o f ( 2 ) 证明：由最优性条件得到： 得证 0 0 s ( z ) + ( 乏一轨) = o f ( 2 ) 一奶毋= o f ( 2 ) 一g i j e l ( y t ) 3 3b u n d l e - 子程序 对于前面所选的迭代信息： ( ，( 犰) ，g i o f ( y i ) ) i b 其中b 是满足如下条件的指标集： 3 j b ，协= z x 为当前的迫近中心 记 e i ：= e ( z ，y ) ：= f ( x ) 一f ( y i ) 一谚( z 一犰) ，i b 由于，是凸的，有 y ( z ) ，( z ) + 订( z z ) 一e i ，v z r n 则迭代信息可以用以下的形式来表示： ( e i ，g i 晓；厂( z ) ) k b 下面构造关于厂的逼近函数 砂( z ) ：= ，( z ) + 建警 一e i + 订( z z ) ) ，v z 1 5 有限最大值凸函数u y 一算法的一。个注记 然后利用两个二次规划问题x q p 和，y q p ，进行迭代信息的选取其中二次 规划问题x q p 为： m i n r + 百1 pi i q - = 1 1 2 ：( r ，口) r 1 + 他，r ，( z ) 一e t + 夕_ ( q - x ) ，z b ) ) 其中b 为上述定义指标集它的对偶问题如下： m i n 去i | 砚俄1 1 2 + e i 锄：砚o ，啦= 1 ) 。p i e bi e bi e b 记由此问题得到的解为： ( 户，尊) 和 ， 、 q 2 【q 1 ，a i b t ) 并且它们满足： 庐= 矽( 伽- - - - x - - 瓦1 多 其中雪= d i g i ，i b ，我们记由此问题得到的解为： ( 庐，香) = x q p ( p ，z ，_ 【( e i ，g i 侥；厂( z ) ) ) t b ) y i + ：2 牙， 则由定理3 1 2 知道口是迫近点的逼近二次规划问题，y q p 为： m i n ( r + 去i i q z i | 2 ：( r ，q ) r 1 + n ，r 毋( 口一z ) ，i 仓) ) 其中 雪：= i b i 庐= y ( x ) 一e + 夕( 香一z ) ) u + ) 它的对偶问题为： m i n 吉i i o t 吼1 1 2 ：锄0 ，吼= 1 ，i 宫) 。 i 台 t 雪 它们相应的解为：( f ，国和a ，满足： 记 则在 虿一z = 一，8 “= 画吼，i 雪 ( 3 3 1 ) t 亩 ( ，u ) = 7 一q p ( ( g i l 台) c o n v ( g i ：i b ) 1 6 有限最大值凸函数u y 一算法的一个注记 中具有最小的欧几里德范数 其中痧是根据 吼) ；亩的信息得到的它们的构造如下： 记万的积极约束指标集为： 如：= i 雪：于= 毋( 口一z ) ) 由( 3 1 ) 可以得到： f = 一谚，v i 8 如( 4 3 2 )r = 一簖，-【4 5 z j 又可以得到： ( g i 一研) t = 0 其中，z s a d 是固定的，i 如是任意的选择满足( 3 2 ) 的最大的i ，使得g 一g t 是线性无关的，并令它们构成矿的列向量 定义矿的零空间为： 亿= 8 ：矿t 8 = o ) 取的正交基作为痧的列向量并且如果痧= i ，则矿是空的 由此得到下面的性质： 命题3 3 1 若香接近于原始轨道) ( ( 乱) 中的点巩 ) ，则c o n v g t ：i 台) 接 近于o f ( x ( u ) ) ，由对偶轨道的定义可以得到： 接近于对偶轨道中的点7 ( 让) ，并且痧接近于y ( x ( u ) ) 上的基矩阵 记 己：= ，( 香) 一矽( 盆) 当 拿翱2 ( 3 3 3 3 ) “ b u n d l e 子程序停止，我们说香是巩( z ) 的盯一近似其中选取仃( 0 ，1 2 引理3 3 2记由b u n d l e 子程序得到的解为 ( 户，牙) = x q p ( 肛，z ， ( e t ，g i 侥；厂( z ) ) ) b ) ( ，u ) = ，y q p ( g i t 亩) 令乏：= 厂( 蜃) 一矽( 香) 则下列结果成立： ( 1 )仂馥厂( 尊) ，i b ( 2 )侥厂( 香) 肛ij 昏一耽( z ) 1 1 2 三 = 痧驴丁，当痧空时，= 0 ( 5 )i 引i 鸯i ，其中互= p ( z 一多) 1 7 有限最大值凸函数u y 一算法的一个注记 3 4 u v 一算法 利用以上的迭代信息以及b u n d l e 子程序我们给出最大值函数的u y 一算 法： 1 初始化选择正的变量，p 及m 1 给出初始点口0 及相应的次梯度 g o o f ( q o ) ，令是礼一维规范正交矩阵，记s o ：= g o ，k = ：0 2 停止准则若1 8 后i e ，停止 3 u h e s s i a n 选择n k n k 阶正定矩阵风，其中n 惫是巩的列数 4 u s t e p由最优性条件得到： 风札= 一昭，a u = a u 七r k 令z + 1 ：= q k + 玩u 后= q k 一巩何1 昭s k 5 原始对偶轨道候选信息的选取选择p 如+ 1 丝，o k + l ( 0 ，i 2 】，并且初始 化b 和令z = z ；+ 1 进行b u n d l e 子程序，得到： ( 产，尊) = x q p ( p ，z ， ( e l ，g i 晓；，( z ) ) 诞b ) ( ，u ) = 7 一q p ( 俄 i 雪) 其中雪如