（运筹学与控制论专业论文）大规模非光滑优化的信赖域算法.pdf

摘要 信赖域方法是处理非线性优化的一种相对较新的方法。该方法 良好的可靠性、稳定性和收敛性使得它在数值优化算法领域占有重 要地位我们在本论文的第一章中首先介绍它处理光滑优化问题的 基本求解策略以及理论结论 非光滑优化是非线性优化的一个重要的组成部分。我们在第二 章中首先介绍非光滑优化产生的背景其与其他学科之间的紧密联 系，主要的理论及两类重要的数值算法随后我们对于一类在工程 和经济问题中经常出现的非光滑问题一一半无限极小极大问题进 行理沦分析，并给出一个新的信赖域算法我们还给出了算法的收 敛性分析和数值试验结果 在信赖域方法的每一步迭代中，我们都要求解一个信赖域子问 题，即在一个椭睡体中极小化一个二次函数。传统的算法在处理大 规模问题时常常出现各种问题我们在第三章中先探讨这些问题产 生的根源，并针对信赖域算法给出信赖域子问题的更新策略随后 我们讨论了信赖域子问题的结构，着重介绍了一种有效的算法一一 序列自空间方法，并分析了对于不同的子空间序列，该算法所具有 的性质随后我们在以上分析的启发下，给出序列自空间方法的一 种改进算法，改进后的算法不仅是全局收敛的，而且进一步减少了 矩阵运算量同时，我们给出一些初步的数值试验报告 最后，我们总结了信赖域方法的特点，并介绍了一些信赖域方 法近期的研究成果和发展方向。 a b s t r a c t i y u s tr e g i o nm e t h o di sar e l a t i v e l yn e wa k o l i t h mf o rn o n l i n e a r o p t i m i z a t i o n t h ef i n ep r o p e r t i e so fr e l i a b i l i t y ，r o b u s t n e s sa n ds t r o n g c o n v e r g e n c ee n a b l et r u s tr e g i o nm e t h o dt op l a ya ni m p o r t a n tr o l ei n t h en u m e r i c a lo p t i m i z a t i o n w ei n t r o d u c e dt h eb a s i cs t r a t e g yo ft h i s m e t t a ) di nd e a l i n gw i t hs m o o t ho p t i m i z a t i o na n dt h ec o n v e r g e n c ep r o p e r t i e si nt i mf i r s tc h a p t e r t h e b a c k g r o u n d o fn o n s m o o t h o p t i m i z a t i o n ni m p o r t a n tc o n l p o - n e n to fn o n l i n e a ro p t i m i z a t i o n a n di t sa p p l i c a t i o n st oo t h e rd i s c i p l i n e s w e r es h o w ni nt h es e c o n dc h a p t e r m a i nt h e o r e t i c a lr e s u l t sa n dt w o s o r t so fn u m e r i e mm e t h o d sw e r eb r i e f l yi n t r o d u c e da tt h eb e g i n n i n g t h e n w ec o n s t r u c t e dat r u s tr e g i o na l g o r i t h mf o rs e m i i n f i n i t em i n i m a xp r o b l e m sw h i c ho c c u rw i d e l yi ne n g i n e e r i n ga n de c o n o m i c s t h e c o n v e r g e n c ep r o p e r t i e sw e r ep r o v e da n dn u m e r i c a le x p e r i m e n t sr e s u l t s s h o wt h ea l g o r i t h mi ss a t i s f a c t o r y i ne v e r yi t e r a t i o no ft r u s tr e g i o na l g o r i t h m ) w el n u s ts o l v eas o - c a l l e d2 _ r u s tr e g i o ns u b p l o b l e m ，ie ，m i n i m i z i n gaq u a d r a t i cf u n c t i o n c o n s t r a i n e di na ne l l i p s o i d i nt h el a r g es c a l ec s s e s ，t h i ss u b p r o b l e m i s q u i t ed i f f i c u l tt ob es o l v e db yt h ec l a s s i c a la l g o r i t h m s i nt h et h i r d c h a p t e r ，w ed i s c u s s e dt h eu p d a t i n gm e t h o da n ds t r u c t u r eo ft r u s tr e g i o n s u b p r o b l e ma tf i r s t t h e nw ei n t r o d u c e das e q u e n t i a ls u b s p a c em e t h o d a n da n a l y z e dt h ec o n v e r g e n c er e s u l t so ft h em e t h o db a s e do nd i f f e r e n t c h o i c e0 ft h es u b s p a e e s i n s p i r e db yt h ea b o v ea n a l y s i s am o d i f i c a t i o n o ft h es e q u e n t i ms u b s p a c em e t h o dw a nm a d e lw h i c hn o to n l yp r o v i d e s t h eg l o b a lc o n v e r g e n c e ，b u ta l s od e c r e a s e st h en u m b e ro fm a t r i x - v e c t o r p r o d u c t s f i n a l l y , w es h o w e ds o m en u m e r i c a lr e s u l t sw i t hc o m p a r i s o n a tt h ee n do ft h i st h e s i s ，w ec o n c l u d e ds o l r l es p e c i a lf e a t u r e st h a t t r u s tr e g i o ns t r a t e g yp o s s e s s e ds o m er e c e n tr e s e a r c l lr e s u l t sa n dd i r e c t i o n so ff u t u r er e s e a r c hw e r ea l s op r e s e n t e d 致谢 在本论文完成之时，我首先衷心感谢我的导师侯定丕教授三年来对我的 辛勤培育和无微不全的关怀侯老师渊博的知识和严谨的治学态度给一直深 刻地影响着我，他对科学研究的热诚和勇气也激励着我的学习和研究上作。 侯老师给予我的精神力量将会使我收益终生 感谢成立庚和陈秋贵老师对我生活的关心以及黄稚新老师对我学爿的帮 助我的师兄杨周旺、欧良贵、乇惠文、刘琼林和师弟牛爱光、张国新、刘建 伟在研究工作方面给我很多启发，让我受益匪浅 感谢夏源明教授和程永宽师兄在我研究生学习的起步阶段作我的向导。 我的室友张庆海、李亮、工建飞、王文杰和我一起分事r 单纯美好的校园生 活，感谢科大为我们提供了宽松的学习、生活环境 最后还要感i 9 我的家人和朋友，正足他( 她) 们的支持和鼓励使我得以完 成学业特别感谢晏沛泗同学两年来陪伴我共同成长! 吕立波 2 0 0 549 引言 一般的非线性优化问题可以表达成以下形式 。r a i n m ) s t 印( z ) = ( j c x 扛) 0 其中f ( x ) ：r n ，r ，兜( z ) ：r ”一醒8 ，e z ( z ) ：1 驴一酞2 是实函数，并且其中至少 有一个函数实非线性的 非线性优化问题对于我们来说并不陌生早在1 8 4 7 年，c a u e h y 就讨沦过 这类问题第二次世界大战以后，随着“运筹学”的建立和发展，非线性优化 开始逐渐独立成为一个研究领域并吸引了众人的目光在k a r u s h 于1 9 3 9 年以 及k u h n 和t u c k e r 于1 9 5 1 年研究了一般光滑非线性优化的最优性条件之后， 人们开始更多地关心如何针对不同的光滑问题构造实用并且具有良好收敛效 果的数值算法 非线性优化的数值算法大都是迭代的在迭代的第女步，我们利用一个近 似解z k ，通过特定的方法计算出下一个新的近似解这样循环计算，直到近 似解在某种条件下可以被视为是原问题的解回顾我们所熟悉的优化算法。如 共轭梯度法( e o l q u g a t ag r a d i e n ta l g o r i t h m ) 、拟牛顿法( q u a s i n e w t o na l g o r i t h m ) 和序列二次规划( s e q u e n t i a lq u a d r a t i cp r o g r a m m i n g ) 等，本质上都属于线搜索 法，即算法在每次迭代时都计算出一个搜索方向，再沿着这个搜索方向找到一 个使得目标函数敢值更小的点 另一类重要的数值方法就是信赖域方法同经典的线搜索法相同的是，信 赖域方法也是通过求解原问题的逼近模型( 也称子问题) 得到步长但不同的 是，这个模型仅仅在当前迭代点附近的特定区域内被接受这个可以被接受的 区域就叫做信赖域信赖域一般是当前迭代点的某个邻域，并且是随着每一次 迭代不断调整的如果上一次的计算显示子问题与原问题逼近的效果很好， 则我们可以扩大信赖域，否则就缩小信赖域虽然大部分对于这种算法的研究 工作是从上世纪7 0 年代末才开始，但是由于信赖域方法有良好的可靠性、稳 定性和收敛性，在这方向上的研究成果层出不穷 在研究光滑优化问题的同时，研究工作者们也发现很多实际中的优化问 题，比如经济学中分段线性的税收模型，最优控制中的约束问题等，难以满足 目标函数的光滑胜甚至存在理论上解析但数值上确非光滑的刚性问题这些 由实际应用提出的问题促使对非光滑优化问题的研究步步深入在理论研究 2 0 0 5 年中邑科学技术大学硕士学位论文 2 方面，以c l a r k e 为首的学者推广了一系列基本概念和结论，为非光滑优化的 理论分析奠定了基础而在数值算法的研究方面，则主要可以分为由p o l y a k 和s h o r 的研究成果为代表的次梯度法( s u b g r a d i e n tm e t h o d ) 和山l e m a r 4 c h e i 和k i w i e l 的研究成果为代表的捆集法( b u n d l em e t h o d ) l 垦f 类 以上的算法主要是针对一般的l i p s c h i t z 连续函数而构建的对于某些具 有更好性质的非光滑问题，如复合优化问题，我们还可以根据目标函数特殊的 性质建立信赖域算法在本论文的第一章简要介绍信赖域算法的起源、发展以 及一些相对比较成熟的理论之后，我们将在第二章中讨论一类在工程和经济 金融领域经常出现的复合优化问题一一半无限极小极大问题我们首先介绍 p o l a k 提出的最优函数的性质，并以此为基础建立信赖域算法。最后我们给出 了算法的收敛性质和数值试验结果 数值优化算法在实际应用中遇到的另一个不盯忽视的挑战是由于f 尤化问 题规模过大而带来的数值计算方面的困难在解决这一难点的研究中，最优 化算法的求解策略与矩阵计算技巧被巧妙地结合起来，给出了很多高效、稳 定的解决方案由于问题规模的大4 , x , f 信赖于方法的框架结构并没有本质影 响，主要的困难产生在子问题的更新与求解上，所以在第三章中，我们要讨论 用信赖域方法解决大规模问题的具体计算方法我们首先给出信赖域子问题 的更新策略，随后介绍由s o r e n s e n 证明的子问题的最优性条件和h a g e r 提出 一类行之有效的求解算法在对h a g e r 的算法进行了一些修改之后，我们汪明 了得到的新算法不仅具有原算法良好的局部收敛性，而且还是全局收敛的 在本文的最后一章中，我们将结合上面对大规模非光滑优化的研究丁作， 总结自已在学习和实践中的体会并介绍信赖域算法最新的研究成果和发展 方向 第一章信赖域方法概述 1 1l c v e n b e r g - m a r q u a r d t 方法 最简单的非线性优化是无约束优化问翘 。r a r i n 。m ) ( 1 11 ) 而最经典的无约束优化问题莫过于非线性最小二乘i 、口j 题 。m i n i i f ( ) 艟( 1 l 2 ) 其中f ( z ) = ( f l ( x ) ，一，厶( z ) ) 7 ， ( ) ( z = 1 ，m ) 是豫“上的连续可微函数 g a u s s n e w t o n 法求解。k + l 的方法是 。k + 1 = x k + d k = 。r a 0 k ) + f ( x k )( 1 l 3 ) 其中a ( x ) = v f ( ：。) 7 是j a c o b i 矩阵，a + 是a 的广义逆矩阵这里的d 同时 也是问题 d r m i n 。i i f ( x k ) + a ( z k ) d | | l ( 11 4 ) 的解问题( 1 14 ) 是原问题( 1 1 2 ) 在当前迭代点z k 的近似但是我们注意 到，当j a c o b i 矩阵a ( x ) 几乎奇异时，步长d k 可能会非常大，从而会出现数 值计算困难为了克服这一困难，l e v e n b e r g l b j 和m a r q u a r d t m q 】提出的方 法是通过引入参数a ，保证a ( x k ) 7 a ( z k ) + h j 可逆，并且可以避免j i d | 1 过 大l e v e n b e r g m a r q u a r d t 方法有很多实现算法，m o r 6 m o 】通过以下方法计算 步跃 d k = ( a ( x k ) 。a ( x k ) 4 - h d 。a ( x k ) 1f ( 。k )( 1 i 5 ) 其中h 0 是一参数实际上，我们不难发现d k 是问题 d m r i n 。l i f ( z k ) + a 0 k ) d l l l + a k l d l j ； ( 1 16 ) 的解h 删；可以被视为罚项，从而可以避免l i d k l l 过大 另一方面，若k ：= f i ( a ( x k ) ( z ) + h ，) 一1 a ( z ) 7 f ( 。 ，则不难证明 出也是如下问题的解 ( 1 l 7 ) ( 1 l 8 ) d 岫 乱拯 。 f d船n 2 0 0 5 年中国科学技术大学磅士学位论文4 丽约束条件( 1l8 ) 正是现在人们所称的信赖域约束。p o w e l l p w l ，p w 2 1 在信 赖域方法领域作出了开创性的工作f 面，我们以无约束优化问题为例介绍信 赖域方法的思想 1 2无约束优化的信赖域算法 如果问题( 1 1 1 ) 中的，) 是r “上的光滑丽数，我们在算法的第k 步通 过解决信赖域子问题 黜羽+ ；d t 巩d = 州d ) ( 1 2 | 1 ) s c 1 2 s “ 来计算试探步以上问豚中肌= v f ( 。女) ，n n 对称矩阵仇是对，( z ) 的 h e s s e 阵的逼近，k 是信赖域半径信赖域子问题的求解是信赖域方法重要 的组成部分，我们将在第三章重点讨论这种子问题的性质和求解办法 设以是问题( 1 2 1 ) 的解，我们记预估下降量p r e d k = ( o ) 一( 血) ，实际下 降量a r e d k = ，( z k ) 一f ( x k + 以) 除非k 是稳定点或者凤是半正定的，否则 必然有p r e 以 0 我们记实际下降量和预估下降量之比n = a r e d * p r e d k ， 它将决定试探步是否可以接受以及是否需要修正信赖域半径以下是无约束 优化问题最基本的信赖域算法 算法1 2 1 步j给定2 7 1 r “，i 0 ，f o ，b l 职”。“i 0 丁3 r 4 1 r l ，0 曼r 0 0 ，南：= 1 i 步2 若i l y k l l 2 e ，则停止； 则求解问题“2 j ) ，得到d k ； 步了计算仉，若“ r o ，则k + l = 。k ； 若否，则。 + l = z 女十出； 步4 r k o ( v 女) ，则存在 常数口 0 使得女2t # m k ( v 女) 其中m = j 十m a x i ； 1 ，下4 1 ，有m + l 曼t 1 a k ( v k j ) ，e + l q k ( v 七聋，) ，m 抖l m k ( v k ) 以及k j m k m i n l j d i ，! 。恢+ a d l l 2 ，d ；是r ，刀，r ，纠的解，则存在 l a g r a n g e 乘子罐0 ，畦0 ，使得 ( b + a ：，十# ；a k a t ) d 。= 一0 + 卢 a k “) ( 1 39 ) 【k l d ；t 1 2 】_ 0 成一i l a 嗾+ c b l2 】= 0 ( 13 l o ) ( 13 1 1 ) 进一步，如果畦，t ：存在唯一，则矩阵( k ，雌) = b k + 坨+ “一* 。a 。7 至多只 有一个负特征根 我们可以通过计算摊，“i 来求解c d t 子问题 除了直接对约束问题构造信赖域子问题之外，f l e t c h e r p t l l 首次基于罚函 数的思想给出了以下子问题 瓣g d + i d t b “+ 一k l l ( 针a 1 = c k ( d ) 0 , 3 - 1 2 ) l i d t l 2 曼k( 1 3 1 3 ) 袁亚湘( y 】对( 1 3 1 2 ) 中价值函数取无穷范数的情况进行了讨论他们的方法 将约束优化问题转化为等价的无约束优化问题进行求解，这种思路在非线性 优化领域中非常重要 以下对于以上几种子问题统一的倍赖域算法框架 算法1 3 2 步给定。1 r ”，i 0 ，e 0 b i 艘“。“i 0 - 3 7 - 4 1 7 - 1 ，0 s - t - 2 0 ，鬼：= l ， 步2若怕k j l 2 e ，则停止； 则求解相应的子问题，得到靠； 2 0 8 5 年中国科学技术太学硕士学位论文 8 步3计算? k ，若7 t t o ，则x k 1 = ：o k ； 若否，则z i = x k + 如； 步 y ( z k )3 k k 0( 1 31 6 ) 其中是任意正整数这种现象揭示了对于很多罚函数，试探步可能不被接 收，从而破坏算法的收敛性为了消除m a r a t o s 现象，我们可以在算法构建中 使用折线步技术【b s s 】或二阶校正步算法【f t 2j 第二章非光滑优化的信赣域算法 2 1 非光滑优化 对于无约束优化问题，我们已经有r 很多成熟、高效的信赖域方法对于 约束优化问题，我们可以利用通用并且重要的罚函数思想i b s 将其转化成一 个无约束优化问题f l e t c h e r 在 f t 】讨论了必下复合函数的极小化问题 。m e r l n 。，( ) 十 ( 。( 。) ) = ( 。) ( 211 ) 其中，) ：艘n r 和c ( x ) ：r n 一豫”是光滑函数，h ( x ) ：廊”一r 是凸函数。 我们可以将( 2l1 ) 视为光滑优化问题的统一表达形式 对于等式约束问题，我们可以令h ( c ) = 叫1 ，对于不等式约束问题，我们町 以令f 。( c ) = _ | c + 其中c j = m a x e l ，o ) 。我们注意到，当i i 取”1 l l 或”【| 。 时，问题( 211 ) 就是一个非光滑优化所以，对非光滑优化阃题的研究是解 决非线性优化问题一个重要组成部分 非光滑优化问题的研究成果最早可追溯到k e l t y k e 对凸规划提出的割平 面法随后，关于非光滑分析的理论迅速发展起来，人们开始尝试将经典的导 数、微分等基本概念推广到凸分析中，r o c k a f e l l a r r 】把凸分析的主要研究成 果进行了总结对于非凸函数，研究的对象是l i p s c h i t z 连续函数这方面理论 代表性的工作主要是由a u b i n 和c l a 一 k e 带领进行的下面我们结合优化理论 的需要，对非光滑理论的基本概念进行简要介绍 定义2 1 1 称函数，：r n 一】r 是在z 附近局部l i p s c h i t z 连续的，如果存在7 1 - 数k o ，s o ，使得 f ( z 1 ) 一，( z 2 ) l 忙t ；c 2 l iv x l ，x 2 b ( z ；) 对于非光滑函数，c l a r k e c 1 1 推广r 导数的定义 定义2 1 _ 2 我们称 ，。( 。；d ) ：l i r as u p 地型掣 v z b “0 为，在z 处的广义方向导数； 引理2 1 3 设，( z ) 在z 附近是l i p s c h i t z 连续的，k 是l i p s c h i t z 常数。则我 们有 j ，。( 叫d ) 5 耳心j v d 皿“ 9 2 0 u 5 年中国科学技术大学硕学位论文 l o 证明由l i p s e h l t z 连续的定义易证 定义2 1 4 我们称集合 d ，( z ) ：= ( g 嚏“ ( g ，d ) y o ( z ；“) ，v d 醍“) 口 为f 在z 处的广义梯斑若o 8 ，( z ) ，则称z 为，的稳定点， 定理2 1 5 设，在z 处附近l i p s c h i t z 连续，若，在z 赴达到局部最小值，则 有0 0 ，( t ) ，即z 是，的稳定点 证明若否，则j d7 豫n 使得 。( 删卜l i ms u p 迎型 型 o ，使得 f ( z 十r o d7 1 f ( z ) 与假设矛盾 以上我们简要介绍r 一些非光滑分析的基本概念i c 2 和f a u j 对非光滑 分析理论及其与最优控制和博弈沦的联系进行丁全面的阐述 针对一般的局部l i p s c h i t z 函数的线搜索法主要可以分成由p o l y a k 和s h o t 的研究成果为代表的次梯度法( s u b g r a d i e n tm e t h o d ) 和由l e m a r d c i l e j 和k i w i e l 的研究成果为代表的捆集法( b u n d l em e t h o d ) 两类 次梯度法的基本思想是把求解光滑问题的最速下降法和拟牛顿法中的梯 度用非光滑问题的次梯度代替并且对拟牛顿法矩阵风的校正稍作改进，得到 空间扩张法和椭球法但是由于并非所有次梯度都是下降方向，而且一般不可 微点处的次梯度集合包含无限元素，所以次梯度算法并不是一个下降算法，加 之次梯度法没有理论上可行的停止准则，所以该算法缺乏有力的理论基础， 但是结合算法的调整，次梯度算法在一些实际问题应用中仍然取得丁较好的 计算结果，p i 叫和【s h i 对这方面的研究成果进行了全面的总结 为了克服次梯度法的上述弱点，l e m a r d c h e l l e l 在1 9 7 8 年首次提出了捆 集法的概念其基本思想是通过一簇次梯度来构造对l i p s e h i t z 函数的分片线 性逼近，然后通过构造的逼近函数找到一个较好的下降方向在算法的每次 迭代中，捆集法引入了严格步长和零步妖的概念。并保证两个严格步长之问只 有有限个零步长当出现零步长或小步长h 十，采用次梯度方法的策略移动到 附近某个可微点处并计算该点处的梯度，再把该梯度加人到以前计算的梯度 集合一捆集中，形成一个新捆集，以便在下次迭代中利用新捆集在当前造代点 2 0 0 5 年中国科学技术大学硕士学位论文 附近对目标函数构造更好的线性逼近。l e m a r & ：h e l 指出捆集法可有两种基本 形式：源f 最速下降算法的次梯度捆集法和源于割平面法的割甲面捆集法。 k i w i e l k i 给出r 一系列实用的捆集法由于捆集法有良好的理沦背景，实际 计算效果也要由于次梯度法，因此该算法目前是求解一般非光滑优化问题的 重要方法 与此蒯时，优化学家f f 也肘利用信赖域方法解决l i p s c h i t z 问题进行了很 多有效的探讨对下复合优化问题( 2 1 1 ) ，f l e t c h e r 在【f t l 】中首次给出了信 赖域算法，并证明了它的全局收敛性他令子问题为 州d ) ：v m 卅；d t ( v 2 m 甜妻h 口2 如瑚d 十忡( + a i d ) 2 ) t = i s t l t d l ls 女( 2 13 ) 其中a k 是约束的j a c o b i 矩阵，a ：女是对解的l a g r a n g e 乘子的逼近。但是很 快，袁亚湘 y 2 证明了f f t l 的算法不是超线性收敛的f l e t c h e r f t 2 1 利用二 阶校正方法对f t l l 的算法进行了改进，并证明了新算法可以消除m a r a t o s 效 应，袁亚湘 y a l 随后证明了l f t 2 中的二阶校正算法是超线性收敛的与此同 时，袁亚湘f y 4 j 还将p o w e l l p w 3 ，p w 4 i 的结论推广到非光滑问题，即如果令对 v 2 ，( z * ) + 銎，a * v 2 c ( z k ) 的逼近段满足( 1 , 2 4 ) 或( 】，25 ) ，则信赖域算法满 足全局收敛性 对于各种复合优化问题的特殊形式，不少学者还给出了各自的信赖域算 法d e n n i s ，l i 和t a p i a d l t j 利用正则函数统一讨论了当时六种有代表性的信 赖域算法的全局收敛性在此基础之上，q i 和s u n 陶s ；对局部l i p s c h i t z 连续 函数提出了信赖域算法，并将袁亚湘y 4 1 的结论进一步推广到局部l i p s c h i t z 连续函数他们的研究成果为以后信赖域方法在非光滑优化中的应用奠定了 坚实的理论基础 2 2 半无限极小极大问题 如果问题( 21 1 ) 中的f ( x ) = 0 ， ) = j 】o 。，则我们得到j r 经典的有限 m i n i m a x 问题这是一类在现实中应用及其广泛的非光滑优化问题比如在期 权投资组合的管理中，投资经理人所感兴趣的问题之一是如何减少由于灭卖 期权而带来的风险对投资组台带来的损失以f 这个模型是基于欧式看涨期 权的，交易品是股票我们给出以下记号：b = 日t ) 代表买入价格，鼠代 表股票在时刻t 的价格，s “代表s t 的下界，s h 代表& 的上界，t 代表现 2 0 0 8 年中国科学技术大学硕士学位论文 1 2 在的时刻，n t 代表持有的股票种类，k 代表持有的看涨期权的种类。于是我 们可以建立如下优化模型 “tsr 模型中的目标函数代表由于投资失误可能带来的损失，其具体的描述和表达 式呵参阅【h r s 】另外，【v z l 还结合最优控制理论，介绍了非光滑优化还在 其他的金融问题中的应用 p o l a k p 0 1 针对工程技术中出现的菲光滑优化问题，提出了半无限极小极 大模型 p ：。m r i n 。妒( 。) 2 m e ( o a x 、l l ，( 。，。) ( 2 2 - 1 ) 其中八，) ：黔1 0 ，】一豫是连续可微函数p o l a k 首先给出了求解这类问题 的次梯度方法在这一章里，我们要对这个问题构建一个超线性收敛的信赖域 算法。 我们首先把原问题参数t 的取值区间t ：= i o ，1 】离散化，得到以下有限极 小极大问题： p ：r a i n 。p n ( 。) 2 * n l ? 5 h x m ，。) ( 222 ) 其中7 1 ：= 川t = 嘉，= 0 ，1 ，2 ，) 我们先给一些假设，这些条件弱十 p o l a k 的假设 假设2 , 2 1 ( i ) 存在n o n ，当n o ，n 1 n ，问题p 都有最优解x ；v ； ( i i ) 在有界域b 上，f ( x ，) ，v 7 1 连续可微； ( i i i ) 问题俾2 剀有解z 奢，且( v 。，( 矿，) ) 满秩 ( i v ) 问题偿2 圳在# 满足二阶充分条件 对任意n n o ，n n ，我们都可以利用f f t 2 j 所给出的超线性收敛的信 赖域算法求得p w 的最优解随着的不断增大，理论上我们可以得到一个 最优值序列 z ) 随后，我们利用最优函数可以把序列 z ) 与问题( 2 2 】) 的最优解z 联系起来，从而建立新的算法 在上一节中，我们简单介绍了非光滑分析理论判别最优值常用的准则。 由定理( 21 5 ) 町知，问题( 2 2 1 ) 的最优解z 和( 2 22 ) 的最优解z 所要满足 的一阶条件分别是0 却( z + ) 和0 o o u ( z n ) 而在这里我们要通过最优函 数给出最优解的另一种判别准则 + s ) s 乩 一 n + ，s 2 0 ( 1 5 年中国科学技术大学硕士学位论文 对于问题( 2 21 ) ，令 ( z ，d ) 。t m a l a x o , 1 ( ，( x , o + ( v z m ，o , d ) + i i l d l l 2 ) d ( z ) ：2 d r a r i n 。痧( 。d ) 妒( z ) 定理2 2 2 【p 0 2 】( 2 24 ) 式定义的p ( c ) 满足 ( i ) v z 爬“，有 o ( x ) 0 ( i i ) v z 豫“，有0 却( z ) 当且仅当日( z ) = 0 ( i i i ) 函数目：r ”一r 连续 我们称函数目：袋“一豫是问题偿o j 最优函数 同理我们可以定义问题( 2 2 2 ) 的最优函数o n ( x ) ( 2 23 ) f 22d ) ( 225 ) 油( z d ) = 蹴( m ，t ) + ( v 。m ，f ) ，d ) + ；i l d l l 2 ) ( 2 26 ) 目( 。) ：。d m r i n 。乒( 。，d ) 一妒( 。) ( 227 ) 在进一步讨论之前，我们在假设( 2 2 i ) 的基础之上对问题p 作进一步 假设 假设2 2 3 ( i ) 存在严格单调递减函数：一r ，使得当n o 。时，有a ( n ) 一( 】； ( j i ) 存在n o n ， 。，使得对所有的n o ，t t ，存在t m ， 使得 ”一t t i k a ( n )( 2 , 2 8 ) 以下我们要分别在问题p 和问题p k 的目标函数之间及最优函数之间建 立联系这种联系将在问题p 的信赖域算法中发挥关键作用 定理2 2 4 若假设口2j j ，f 22 圳成立，c p n ( z ) 由偿2 到定义，口( z ) 由偿2 定义。令b r ”是一个有界域，则存在常数c ( j ，口 2 ，e 0 i n ，f o r ”，七：= 0 、n ：= n o ，p k 0 ，县o 熙删。 步2计算目( z k ) i 若 步芎 步名 步5 步疗 步7 步8 步9 帝口 步j j