（运筹学与控制论专业论文）求解凸不等式组的一个次梯度算法.pdf

求解凸不等式组的一个次梯度算法 摘要 在数学与物理科学的众多研究领域中，很广泛的一类问题要求在凸集的交集中找到 一点。这类问题通常被称作凸可行问题。凸可行问题的应用广泛存在于最佳逼近理论、 离散模式图象重构、连续模式图象重构和次梯度算法问题之中，解决这类问题较常用的 方法是投影算法。 本文针对凸可行问题中的凸不等式组，结合凸可行问题投影算法的思想与优化算法 中下降迭代算法，利用凸不等式组自身特点，给出了凸不等式组求解算法的一个收敛性 证明。同时介绍了一个如何求解凸不等式组严格解的算法。 在第四和第五章中，介绍了论文主要结果，可概括如下： 第三章：对凸不等式组利用极大值函数将问题转化为求解凸不定方程闯题，然后根 据下降迭代算法将距离函数作为下降函数，结合次梯度的几何性质证明算法生成的数列 收敛于凸不定方程的解，即凸不等式组的解。给出的几个数值试验说明算法的有效性。 第四章：在一些凸不等式组问题中，要求得到严格解。但是，由于算法本身的结 构，只能求得非严格解。我们发现b e r t 8 e o s ( 1 9 8 2 ) 用于计算非光滑精确罚函数的下降方 向的方法可以用来计算凸不定方程零点处的下降方向，该方法只须求解一个二次规划， 从而求得凸不等式组严格解。本章给出该算法的主要证明。 关键词：凸不定方程，凸不等式组，次梯度，极大值函数 求解凸不等式组的一个次梯度算法 a b s t r a c t a v e r yc o l n l n o np r o b l e m i nd i v e r s e8 x e s so fm a t h e m a t i c sa n d p a y r s i c a ls c i e n c e sc o n s i s t s o f t r y i n gt o f i n dap o i n ti nt h ei n t e r s e c t i o no fc o n v e xs e t t h i sp r o b l e mi sr e f e f r e dt oa st h e c o n v e x f e a s i b i l i t yp r o b l e m ；i ti su s u a l l yf o u n d i nb e s t a p p r o x i m a t i o n ，i m a g er e c o n s t r u c t i o no f d i s c r e t em o d e l s ，i m a g er e c o n s t r u c t i o no fc o n t i n u o u sm o d e l sa n d s u b g r a d i e n ta l g o r i t h m s o n e f r e q u e n t l ye m p l o y e da p p r o a c hi ns o l v i n gt h ec o n v e xf e a s i b i l i t yp r o b l e mi st h ep r o j e c t i o n a l g o r i t h m s i nt h i sp a p e r w ep r e s e n ta p r o o fo f c o n v e r g e n c e o fa l g o r i t h mw h i c hs o l v et h ec o n v e x i n e q u a l i t i e sb e l o n g i n gt ot h ec o n v e xf e a s i b i l i t yp r o b l e m t h ep r o o fu t i l i z et h ei d e a so fp r o j e c - t i o na l g o r i t h m ，t h ef r a m eo ft h ed e s c e n ti t e r a t i v ea l g o r i t h ma n dt h ed i s t i n g u i s h i n gf e a t u r e o ft h ec o n v e xi n e q u a l i t i e sp r o b l e m a ts a m et i m e a na l g o r i t h mi sp r e s e n t e dt oo b t a i nt h e s t r i c ts o l u t i o nt ot h ec o n v e xi n e q u a l i t i e s i nc h a p t e r4a n d c h a p t e r5 , t h em a i n r e s u l t st h i st e x th a v ei n t r o d u c e d ，c a d b es l l l n m a ， r i z e da sf o l i o w ： i nc h a p t e r4 ：t h ec o n v e xi n e q u a l i t i e si st r a n s f o r m e di n t ot h ec o n v e xi n d e t e r m i n a t e e q u a t i o nb ym a x i m u mf u n c t i o n kc a l lp r o v et h a tt h en u m e r i c a ls e q u e n c eg e n e r a t e db y g i v e na l g o r i t h mc o n v e r g et ot h er o o to ft h ee q u a t i o n ，w h i c hi st h es o l u t i o no ft h ec o n v e x i n e q u a l i t i e st o o ，w h e nt h ed i s t a n c ef u n c t i o ni su s e da st h ed e s c e n tf u n c t i o na c c o r d i n gt o d e s c e n ti t e r a t i v ea l g o r i t h ma n dt h eg e o m e t r i cp r o p e r t i e so fs u b g r a d i e n ti se x p l o i t e d s e v e r a l n u m e r i c a le x a m p l e ss h o w 也a tt h ea l g o r i t h mi se f f e c t i v e i nc h a p t e r5 ：i ns o m ep r o b l e m s ，t h es t r i c ts o l u t i o no ft h ec o n v e xi n e q u a l i t i e si se x p e c t e d t ob ef o u n d b u t ，w ec a n n tf i n dt h es t r i c ts o l u t i o nb yt h ep r o v e da l g o r i 七h mb e c a u s eo fi t - s e l fr e s t r i c t i o n w ed i s c o v e rt h a tt h ew a yw h i c hw a su s e dt oc a l c u l a t ed e s c e n td j i r e c t i o no f n o n - s m o o t h l ye x a c tp e n a l 够f o n c t i o nb yb e r t s e k a s ( 1 9 8 2 ) c s j lb eu s e dt og e tt h ed e s c e n t d i r e c t i o no fm a x i m u mf u n c t i o na ti t sr o o t t h a tm e a n sm e r e l yt os o l v ea q u a d r a t i cp r o - g r a m m i n g f o rs t r i c ts o l u t i o n t h i 8c h a p ew i l ld e m o n s t r a t et h em a i n p r o o f o ft h a ta l g o r i t h m s k e yw o r d s ：c o n v e xi n d e t e r m i n a t ee q u a t i o n ，c o n v e xi n e q u a l i t i e s ，s u b g r a d i e n t ，m a x i - m u l nf u n c t i o n 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作及取 得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不 包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学或其 他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的 贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：日期： 求解凸不等式组的一个次梯度算法 1 引言 在数学和物理科学中的许多领域中，很多问题的求解要求在一组凸集中找到其交集 中的一点。这个问题通常被称作凸可行问题。它的精确描述如下： 假设x 是希尔伯特空间，q ，q c k 是x 中的闭凸集，并且它们的交集非空： c = 口n c 2 n 翰0 凸可行问题：求解z 使得o c 。 这类问题主要有两中类型： l ：在某种意义上，q 是简单的，即在a 的投影能够被简单的计算，例如g 是超平面 或半空间。 2 ：在a 上的投影不可能被计算，然而计算包含g 的集合上的投影是可能的，典型的 如g 是某些凸函数的水平集。 解决凸可行问题最常用的方法是投影算法。它的主要思想是根据当前迭代点到每 个g ( 或包含a 的集合) 的投影从而得到新的迭代点，这样产生一个序列并保证序列收 敛到凸可行问题的解。其利用的主要工具是压缩映射和f e j e 不等式。详细的方法综述 见 3 l 。 凸可行问题有着广泛的应用，根据它们的应用分为四大类： 1 最佳逼近理论：主要包括偏微分方程，复分析，统计( 线性预测理论) 等参 见【2 3 l ，【2 7 a 2 离散模式图像重构：主要包括数字医学图像等参见【17 ，【1 9 ，【2 0 ，【2 1 ，【3 0 ，【3 3 卜 3 连续模式图像重构：主要包括信号处理等参见【2 8 ， 3 2 1 ，【3 4 】。 4 次梯度算法；主要包括凸不等式组、凸非光滑函数最优化等参见【18 】，【2 2 】，【2 6 ，【2 9 ，【3 1 l 。 本文所考虑的问题是凸可行问题中的凸不等式组问题，这类问题本身就有着广泛的 应用。考虑如下凸不等式组： i ( z ) 0 !( 1 1 ) l 厶( 茁) 0 其中 ：p r 1 ，i 1 m ，是凸函数。 对于这一类凸可行问题，显然通过极大值函数： p ( ) = m 8 。 ( 石) ，2 0 ) ，一，厶( z ) ) 可以将凸不等式组问题转化为求解凸不定方程问题。若求得矿使p ( 矿) = o n x 是凸不等 式组的解。 通过最大值函数，我们把求m 个凸集交集的中一点的问题转化为求解凸集 c = 扣l p ( x ) o ) 1 求解凸不等式组的一个次梯度算法 中一点的问题。 我们引入距离函数： d ( ) = t n ， | lz c | | ic g ) 其中l l 是通常欧式空间距离。 当z g 时，d ( z ) = 0 ，并 l d ( x ) 0 ，妇酽。那么凸不等式组问题又可以看作是 无约束非线性最优化问题： r a i n d ( x ) s ，tz 舻 求解无约束非线性最优化问题有较为成熟的方法，如最速下降法、牛顿法、拟牛顿 法及共轭梯度法等( 在4 3 节将给出简要介绍) 。 这些方法均要求目标函数二次连续可微或至少一次连续可微。但是，由拓扑知识我 们知道，当g 集合为闭集时，我们仅仅能够保证d 和) 是连续函数。并且由于d ( z ) 本身是一 个结构较为复杂的极小化问增加了求解难度。 对于所得到的优化模型，通常的优化算法很难应用，主要有两个原因，一是d ( 。) 不可 微时，下降方向就无法有效的计算得到，二是步长的选取比较困难，来保证足够的下降 量使算法收敛。 但是，我们用几何的方法证明p ( 。) 在茹处的次梯度与d ( z ) 在。处下降方向的关系， 即p ( z ) 的次梯度的反方向是d ( o ) 在茁处的下降方向。那么由次微分的概念我们知道p ( 茁) 在z 处 的次微分就可以构成d ( o ) 在z 处的下降方向的一个集合。对于步长选取。因为d ( z ) 本身的 复杂性，利用一维线搜索得到下一个迭代点比较困难。但是利用投影算法的思想可以解 决步长问题，并且计算量较小。 那么利用凸函数的性质，把凸不等式组转换维优化问题，按下降迭代算法我们就可 以证明算法的收敛性，在第3 章有详细论述并在第4 章给出了详细证明。 有些问题，例如内点罚函数法，要求初始点是严格可行内点，即不等式组严格成 立。按照上述算法求解，由于算法本身结构仅仅能够求出不等式组非严格解，而不能得 到严格解。但是通过b e r t s e k a s ( 1 9 8 2 ) f 4 r o t 计算非光滑精确罚函数的下降方向的方法， 仅需要求解一个二次规划问题可以计算p ( z 1 零点处的下降方向，从而求得不等式组严格 解。在第4 章我们给出其证明。 本论文主要对凸不等式组进行了研究，内容安排如下： 在第二章，主要介绍了凸分析的基础知识，包括了凸集和凸集分离、凸函数及相关 性质和次微分及相关运算三部分，部分定理给出了证明。 在第三章，给出下降迭代算法的完整的概念及收敛性证明，包括算法概念、算法收 敛、算法收敛速度、优化方法概述和求解凸不定方程算法五部分。 在第四章，主要给出了求解凸不等式组的算法收敛性证明，其中包括预备定理、收 敛性证明和数值试验。 2 求解凸不等式组的一个次梯度算法 在第五章，给b e r t s e k a s ( 1 9 8 2 ) 关于计算非光滑精确罚函数下降方向的证明。 3 求解凸不等式组的一个次梯度算法 2 凸分析基础 凸分析，或称凸集和凸函数理论，是数学中相对年轻的一个分支，上世纪3 0 年代才 出现比较系统地研究凸集的著作。上世纪4 0 至5 0 年代，特别是在优化领域中发现了凸集 的许多应用后，便进一步促进了这一理论的的发晨。随着数学规划，对策论，数理经济 学和最优控制理论等学科发展的需要，凸分析日益受到人们的重视。6 0 年代后期出现了 凸分析的奠基性著作，即r t r o c h a f e l l a r 的c o n v e xa n a l y s i s 。本章给出论文主要用到的 凸分析相关概念及定理。 2 1 凸集和凸集分离 凸集是凸分析研究的主要对象之一，下面给出在j p 中凸集的基本概念，可以说一 般扎维空问的凸集概念是平面凸集概念的自然推广。 定义2 1 设集合sc 酽，若对任意的a ( 0 ，1 ) 有 a o + ( 1 一a ) 可sv ，y s 则称s 是凸集或集合s 是凸的。 凸集的相对内部是凸集一个很重要的概念，在下面的定理中将要用到，在此给出相 对内部的概念。 舒中的线段和三角形作为舻中的集合其内部都是空集。但显然它们都有着自然的 内部，这就是相对内部。 把舻中的集合m 看成其仿射包a l l m 中的子集，然后在a h m 中规定m 的内点和 内部，就得到m 的相对内点和相对内部。确切地说，。点叫做m 的相对内点，是指存 在e 0 使得 b ( o ，e ) n o 仃m c m m 的相对内点全体叫m 的相对内部，记作r i m 。于是 r i m = z m l | s 0s tb ( 。，e ) n a h m c m ) 当a l l m = p 时，集合m 的相对内部和其普通的内部相同，即 位m = r i m 。 例如，设。，口为舻中不同的两个点，【。，y 】为连接z 和y 的闭线段，则 r i x ，y 】= a 。+ ( 1 一a ) ! ，10 a 1 ) = ( z ，) 我们给出要用到的凸集的一个简单性质。 性质2 1 任意多个凸集的交仍然是凸集。 凸集的分离是凸分析中最重要的概念之一，它所基于的基本事实是：印中的一个超平 面正好把印一分为二，并且此超平面的补集恰好是与其关联的两个不相交的开凸集( 即 两个半开空间) 之并。下面给出超平面和凸集分离的概念。 定义2 2 设l 是佗一1 维线性子空间，6 j p ，则称仿射集日= l + 6 是r i 中的超平面。 4 求解凸不等式组的一个次梯度算法 我们知道，舻上的任意线性范函，对应于舻中唯一点矿使得 ，( z ) = ，、，z 钟 通常我们把，与x + 等同。注意到册中任意超平面日都可以表示成 h ( x + ，p ) 垒 z r “i = 卢) ， 其中矿舻为非零元，口r 。 给定j 矿中的子集a 和超平面i - i ( = + ，a ) ，我们称集合a 位于超平面h ( x + ，a ) 的一侧， 是指 给定口中两个凸子集以及一个超平面h ( x + ，。) 。我们称a 和b 被超平面日( ，口) 所 分离，是指他们分别位于日的两侧。确切的说，就是 s 口s v a ，v y b ，( 2 1 ) 或者 口曼 v x a ，v y b ( 2 1 ) 这样定义的集合分离似乎并不令人满意，因为，例如在三维空间中位于同一平面中 的两个集合按照这个定义已经算分离了! 因此有必要提出更严格的分离概念。 于是我们称印中的凸集合a 和b 被超平面日( 矿，口) 真分离，是指( 2 1 ) 或者( 2 ，1 ) 成 立，同时式( 2 1 ) 或者( 2 1 ) 不能总是成立等号；称集合a 和b 被超平面日( 矿，) 严格分 离，是指 a v x a ，v y b ( 2 2 ) 或者 a 0 ，使得 o s a + v x a ，v y b ，( 2 3 ) 或者 a 一 护 护 z z 0 ( + 。) n = 一o o ，( 一o o ) 口= + o 。，o 0 0 ( + 。) = 0 ( 一。o ) = 0 ，一( 一o 。) = + o 。， t n 知= + o o ，s t t 阳= 一o 。 ( + o o ) + ( 一o o ) ，( + o 。) 一( + 。) 与( 一。) 一( 一o 。) 都是无意义的，应当避免。 定义2 6 设gc 舻为凸集，f ：c 一面。若对于所有的z ，y c 与所有满足，( 。) 让，_ ，( 们 的让，钉r ，当0 a 1 时均有 ，( a z + ( 1 一a ) 掣) a 钍+ ( 1 一a ) ( 2 7 ) 则称，( z ) 为凸函数。 定理2 1 设c c 舻为凸集，f ：c 一兄。则定义2 3 与定义2 6 等价。 证明：设按定义2 3f ( x ) 是凸函数，且让，u r ，( z ) t ，f ( y ) ，0 a 1 。于是 ，( z + ( 1 一a ) g ) a f ( x ) + ( 1 一a ) ，0 ) 0 均有，( 茹) ，( z ) + ，f ( u ) f ( u ) + e ，所 以 ，( a z + ( 1 一a ) 们 n f ( z ) + 硝+ ( 1 一a ) 【，( ) + 司 = m ( x ) 4 - ( 1 一a ) ，( 掣) + s 令e 一0 得 ，( a z + ( 1 一 ) 掣) m ( z ) + ( 1 一a ) ，( 掣) 因而按定义2 3 ，( z ) 也是凸函数。 定义2 ，7 设gc 舻为凸集，f ：c 一爱为凸函数，则称集合扛lz c ，( z ) + o 。) 为，( z ) 的有效域( e f f e c t i v ed o m a i n ) ，记为d o m ( f ) 。 7 求解凸不等式组的一个次梯度算法 可以直观的看出，位于凸函数，( ) 的图形上方的集合是个凸集。有时利用这个集合 的性质研究函数，( 茁) 的性质更方便，所以引入以下定义，研究函数，( 。) 的凸性。 定义2 8 设c c 口，函数，：c 一西，贝4 称集合 ( z ， ) l ( 茁，a ) cxr ，( z ) sa ) 为，扛) 的上图( ；西g r 印矗) ，记为；研( 如。 定理2 2 设f ( z ) ：v 一面，则下列条件等价： 1 ：，是凸函数； 2 ：印e ( ，) 是凸集； 3 ：a = = ( 。，a ) l ( z ， ) vxr ，( z ) a ) 是凸集。 证明：1 辛2 设，( 。) 是凸函数。再设( $ ，钍) ，( 玑 ) ，二两( ，) ，0 a 1 。 因为0 ，u ) ，( y ，口) e p i ( f ) ，所以，( z ) 札，y ( y ) 口。n 而f ( x ) 让+ ，f ( y ) 0 。再跟据，( 。) 的凸性得 ，( k + ( 1 一a ) 可) a ( u + e ) + ( 1 一 ) 扣+ e ) = x u + ( 1 一a 扣+ 令一0 得 ，( 妇+ ( 1 一 ) 鲈) , x u + ( 1 一a ) 口 于是 a ( 。，u ) + ( 1 一a ) ( ， ) = ( a z + ( 1 一a ) 口，a “+ ( 1 一a ) ) # 川( ，) ， 所以唰( ，) 是凸集。 2 峰3 设e p i ( f ) 是凸集。再设( z ，u ) ，( y ， ) ，a 0 a l 。 因为( z ，u ) ，( y ，口) a ，所以，( z ) u ，f ( y ) 。存在呦，咖r 满足，( z ) u o ，( ) 。因而( z ，锄) ，( y ， f r o ) 二历( ，) 。因为e 川( ，) 是凸集，所以 a 扛，t 幻) + ( 1 一a ) ( 玑如) = ( a z + ( 1 一入) f ，a u d + ( 1 一a ) 咖) 印 ( ，) ， 于是 ，( 地+ ( 1 一 ) 3 ，) sa t 协+ ( 1 一a ) 钉o a u + ( 1 一a ) 口 因而 a ( 。，u ) + ( 1 一a ) ( 弘 ) = ( 茁+ ( 1 一a ) y ，地+ ( 1 一a ) ) a ， 所以a 是凸集。 3 净1 设a 黾凸集。再设，( 盘) ，( ) 口，0 a 1 。于是( 。，珏) ，( 箩，移) a 。 由a 的凸性得 a ( 茁，“) + ( 1 一a ) b ，口) = ( x x + ( 1 一a ) ，a 钍+ ( 1 一a ) 钉) a 于是 ，( 蛔+ ( 1 一 ) ”) q + ( 1 一 ) ， 8 求解凸不等式组的一个次梯度算法 因而，( z ) 为凸函数。 因为函数f ( x ) 的凸性和它的上图e p i ( f ) 的凸性等价，所以也可以把”t 川( ，) 是凸集”作 为凸函数的定义，而把前面的定义作为凸函数的性质。要证明，( 茹) 的凸函数，也可以先 证明，( ) 的上图e p i ( f ) 为凸集，或集合a = ( z ，a ) lf ( x ) 0 。于是有 f ( x ) p 卢+ ，f ( y ) 卢 卢+ ， 根据定义2 6 得 ，( a z + ( 1 一a ) 暑，) 是开集： 3 ：对于每个a r ，b = z 1 ，( z ) sa 是闭集； 4 ：e p ( f ) 是闭集。 有性质2 3 和定理2 4 有一下推论 推论2 2 设，0 ) 是舒上的实凸函数，口r 。则水平集 l = ( ，卢) = ，( z ) 卢) 为闭凸集。 2 3 次微分和相关运算 设，( z ) ：胛一 一。，+ 】为凸函数。称向量矿舻为，( z ) 在点z 处的一个次梯 度，是指它满足 ，( z ) ，0 ) + ， v 石矸 这个条件称作次梯度不等式。当，在z 处存在次梯度矿，并且，( 。) 为有穷值时，必 有，( z ) 一o 。，v z r ，这时它有简单的几何意义：仿射函数 h ( z ) = ，( g ) + 的图像 ( z ， ( z ) ) z 印) 时凸集e p ( f ) 在点( 。，( z ) ) 处的一个非垂直的承托超平面。 j 聱 i 叫国 一 z 一 0 图2 3 次梯度几何解释 ( 矿，一1 ) 是支撑超平面 ( z ) = ，( 髫) + 的法失。单变量可微函数，( 。) 在 点z 的次梯度就是切线的斜率。若，( z ) 在点的次梯度不唯一，爱上图哂( ，) 在点( z ，( 。) ) 1 0 求解凸不等式组的一个次梯度算法 的支撑超平面也不唯一。 次梯度是梯度概念的推广。与此相关的是：支撑超平面可以看作多元函数微分学中 所讨论过的空间曲面切平面的推广。 ，( z ) 在z 处的所有次梯度的集合口q 做，在z 的次微分，记作o f ( x ) ，即 o f ( x ) = 茁rif ( z ) ，( z ) + ，v z r “) 这样，一般说来，o f ：z o f ( x ) 是一个多值映射，称为的次微分映射。当然对某 些。，o f ( x ) 可以是空集，也可以恰好含有一个向量。如果a ，( z ) 不空，则称在g 处是次可 微的。 f j 9 2 设单变量凸函数： m ，= 悟- x ：嚣 贝u f ( x ) 在( 一o 。，+ o o ) 内是次可微的。当。o 时f ( x ) 可导，所以 o f = ，。( 。) ) 当o = 0 时 o f = 【- 1 ，+ 1 】 下面给出次可微的充分条件。 定理2 5 设，( z ) ：e r u + o 。) 的凸函数，且如m ( ，) 0 。 l ：若，( ) 在某一点x o d a m ( ，) 上连续，则在有效域d o m ( f ) 内，( z ) 是次可微的； 2 ：若e = j p ，则在有效域d o m ( f ) 的相对内部时次可微的。 接下来给出一类凸函数次微分表达式的一个一般的定理，论文将要用到这类凸函数 的次微分来构造算法。 定理2 6 设力：j 一r 为凸函数，令 m ) 2 黜办( z ) ，z r “- 那么 o p ( 垆 品九圳目a i = l , d 。，a 胁) ) 其中 l ( x ) 一0 i1 t m ，五0 ) = ，扛) ) 凸分析 i i 求解凸不等式组的一个次梯度算法 3 算法 3 1 算法概念 在求解很多数值问题时，所用的计算方法最常见的是迭代下降法。所谓迭代，就是 从一点善( ) 出发，按照某种规则a 求出后继点o ( + 1 ，用k + 1 代替k ，重复以上过程，这 样便产生点列z ( k ) ；所谓下降，就是对于某个函数，在每次迭代过程中，后继点处的函数 值要有所减小。在一定条件下，迭代算法产生的点列收敛于原闯题的解。 上面所说的对应规则a ，在某个空间x 中点列到点列的映射，即对每一个z ( 的x ， 有点z ( 女+ 1 ) = a ( z ( k ) ) 。更一般地，把a 定义到点到集的映射，即对每一个点o ( 女) x ， 经a 作用，产生一个点集a ( z ( ) ) cx ，任意选取一个点z 1 ) a ( z ( 。) ) ，作为z ( ) 的后继 点。 定义3 1 算法a 黾定义子空间x 上的点到集映射，即对每一个点z x ，给定一个子 集a ( x ) c x 。 定义中的“空间”一词不作严谨的解释，x 可以是，也可以是驴中的一个集合， 还可以是一般的度量空间，要点在于a 是x 中点到集的映射。这样定义算法的好处是， 可用统一方式研究一类算法的收敛性。 为研究算法的收敛性，首先要明确解集合的概念。设计一个算法，如果能使算法产 生的点列收敛于问题的解，当然是很好的。但是，在许多情况下，要使算法产生的点列 收敛的于解是比较困难的。因此，一般把满足某些条件的点集定义为解集合，当迭代点 属于这个集合时，就停止迭代。例如在无约束最优化问题中，可以定义解集合为 q = - ln v ，( _ ) l | - o ) ， 在约束最优化问题中，可以定义解集合为 q = 虿l 薯是耳一t 点， 每当谈到下降算法，总是与某个函数在迭代中函数值减小联系在一起的，因此需要 给出下降函数的概念。 定义3 2 设ncx 为解集合，a 为x 上的一个算法，n ( z ) 是定义在x 上的连续函数，若 满足 1 当簪q 且y a ( z ) 时，n ( ) 1 显然，问题的最优解牙= 1 ，我们设计一个算法a ，透过a 求出这个最优解。 定义算法a 如下： f 1 ，扛+ 1 ) ，z 1 a ( z ) = 【 扛+ 1 ) ，1 ，z 1 这个算法把点写映射成一个闭区间。 运用算法a 时，从一点出发，经a 作用得到一个闭区间，从此区间中任取一点作为后 继点，重复这个过程得n - 个由算法产生的点列，在一定条件下，这个点列收敛于问题 的解。由此过程可知，利用算法a 可以产生不同的点列，现在从中列举几个如下： 3 2 ，瓣) ，瓣) ，；，孙) 这些点列都是以z ( 1 ) = 3 为初始点，运用算法a 得到的，它们尽管各不相同，但是都 以虿= 1 为极限。因此，由算法a 产生的点列，其聚点是问题的最优解。 按定义3 3 ，算法映射a 在每一点。都是闭的。 1 3 求解凸不等式组的一个次梯度算法 如果定义算法为 f 忙+ 3 ) ， ( 2 。+ 3 ) ，z 3 b ( 。) _ l ；( 2 $ + 1 ) ，茹 0 存 在，当k n ( k k ) 时，成立 口0 ) 一d ( 茁) e 特别地，必有 n ( z ( ) 一口( 。) n ( 包括不属于k 的) ，由于a 时下降函数。因此有 口p 磅) 一。忙n ) 0( 3 2 ) 1 4 求解凸不等式组的一个次梯度算法 由( 3 1 ) 和( 3 2 ) 可以推出 n ( 。( ) 一o ( 茁) = o ( z ( ) 一n ( 茹( ) + 。( z ( ) 一口( 。) n 都成立。 另一方面，由a 是下降函数可知 a ( 。( 砷) 一n ( z ) 0 由( 3 3 ) 和上式得到 1 i e 口( 口( ) = 口( z ) 下面证明q 。用反证法。 假设簪q 。考虑序列 嚣铲1 ) ，k k 。由于这个序列含于紧集， 列 节1 ) ，耳c k ，设其极限为虿x 。用上面的方法可以证明 1 i m 口( 。( k + l ) = 口( i ) 根据极限的唯一性，由( 3 4 ) 和( 3 5 ) 知 o ( 却= 口( z ) 此外，由上述分析可知，耳c 耳，对于k 耳，有 z ( k ) _ z ( 3 3 ) ( 3 4 ) 因此存在收敛子序 ( 3 5 ) ( 3 6 ) z ( 十1 ) 呻虿，。( + 1 ) a ( 。( 2 ) ) 由于算法a 在q 的补集上是闭的，z 芒q ，因此a 在。处是闭的，这样便有 面a ( x 1 由于a 是关于n 和a 的下降函数，o q ，则必有 o ( _ ) a ( x ) 这个结果与( 3 6 ) 矛盾。所以z q 。 收敛定理中的三个条件缺一不可，尤其是第3 个条件，要求算法在解集合的补集上是 闭的，显的特别重要，许多算法失效，往往归因于这个条件不满足。 运用迭代下降算法，当z ( ) q 时才终止迭代。实践中，在许多情形下，这是一个 取极限的过程，需要无限次迭代。因此，为解决实际问题，需要规定一些实用的终止迭 代过程的准则，一般称为收敛准刚，或称停步准则，以便迭代进展到一定程度时停止计 算。 常用的收敛准则有一下几种： 1 _ 当自变量的改变量充分小时，即 1 1z ( 蚪1 ) 一z ( 砷0 或者 钟x c k ) s 0i i 求解凸不等武组的一个次梯度算法 时，停止计算。 2 当函数值的下降量充分小时，即 n ( z ( 知) ) 一o ( z ( + 1 ) ) e 或者 等涮产 s io ( z ( 砷) i 、。 时，停止计算 3 在无约束最优化中，当梯度充分接近零时，即 | | v ( m ( ) i i 时，停止计算。 以上各式中，s 为事先给定的充分小的正数。除此以外，还可以根据收敛定理，参照 上述收敛准则，规定其他的收敛准则。 3 3 算法收敛速度 评价算法优劣的标准之一，是收敛速度快慢，通常称为收敛速率，一般定义如下： 定义3 4 设序列 7 ( ) ) 收敛于r ，定义满足 。1 i m 0 。矧= 卢 + 。o* 耐2 卢针。0 的非负数p 的为序列 ，y ( ) ) 的收敛级。 若序列的收敛级为p ，就称序列是p 级收敛的。 若在定义中，p = 1 且口 1 ，或者p = 1 且卢= 0 ，则称序列是超线性收敛的。 例考虑序列 o ( ) ，0 o 1 由于a c k ) 一0 以及 l i m 掣：。 1 。可可_ 2 o 0 ，置k = 0 。 步2 ：求 坼t 一器靠， ( 4 - 2 ) 其中城o f ( x k ) 。 步3 ：如果，( 。+ 1 ) ，则停，否则置= 居+ 1 ，转步2 。 4 1 预备引理 本章假设所讨论函数均为形- + r 1 上的有限实值函数。下面给出主要用到的概念及 引理。 定义4 1 设，( z ) 是凸函数，称向量矿毋为，在。处的一个次梯度，如果 f ( z ) ，( z ) + ( z 一。，z + ) ，v z 口， ( 4 3 ) 成立。，( z ) 在z 处的所有次梯度的集合叫做，( z ) 在z 的次微分，记作o f ( x ) ，即 o f ( x ) = z 。品“i f ( z ) ，( z ) + ( z z ，z ) ，y z 尺“) ( 4 4 ) 性质4 1 设，( 。) 是凸函数，若一矿，蝶o f ( x k