（计算数学专业论文）非线性约束最优化若干算法理论及应用研究.pdf

摘要 本文首先利用r o s e n 投影矩阵，对求解无约束规划的记忆梯度算法中的参 数给定某些限制条件，确定参数的取值范围，使其在取值范围内取值均能得到 目标函数的记忆梯度r o s e n 投影下降方向，建立了解带线性或非线性约束最优 化问题的记忆梯度r o s e n 投影算法，并在较弱条件下证明了算法的收敛性同 时给出了具有好的收敛性质和较快收敛速度的结合f r ，p r ，h s 共轭梯度参数的 记忆梯度r o s e n 投影算法，从而将经典的共轭梯度法推广用于求解约束规划问 题 其次，利用广义投影校正技术，通过改进假设条件对搜索方向进行修正， 运用一种新型的一阶修正方向并结合s q p 技术，建立了求解非线性不等式约 束最优化问题的一个新型s q p 可行下降算法，在相对较弱的假设条件下证明 了算法的全局收敛性和强收敛性 上述两类新算法具有较小的计算量和存储，而且收敛速度快，适合大规模 最优化问题的计算数值例子表明算法是有效的 关键词：非线性约束最优化，记忆梯度，r o s e n 投影，序列二次规划，收 敛性 a b s tr a c t f i r s t ，i nt h i sp a p e r ，b vu s i n gr o s e np r o j e c t i o nm a t r i x ，t h ec o n d i t i o n sa r eg i v e no n t h es c a l a r si nm e m o r yg r a d i e n td i r e c t i o nt oe n s u r et h a tt h em e n t o r yg r a d i e n tp r o j e c t i o n d i r e c t i o ni sd e s c e n t an e wm e m o r yg r a d i e n tr o s e np r o j e c t i o nm e t h o df o rn o n l i n e a rp r o g r a m n f i n gw i t hl i n e a ro rn o n l i n e a rc o n s t r a i n t si sp r e s e n t e d t h eg l o b a lc o n v e r g e n c ep r o p - e r t i e so ft h en e wm e t h o da r ed i s c u s s e d c o m h i n i n gw i t hc o n j u g a t eg r a d i e n ts c a l a ra n d o u rn e wm e t h o d ，t h r e en e wc l a s s e s ( f r ，p r ，h s ) o fm e m o r yg r a d i e n tr o s e np r o j e c t i o n m e t h o d sw i t hc o n j u g a t eg r a d i e n ts c a l a ra r ep r e s e n t e d s e c o n d ，b yu s i n gg e n e r a l i z e dp r o j e c t i o nr e c t i f yt e c h n i q u e ，c o r r e c t i n gs e a r c hd i r e c t i o n b yi m p r o v e ds u p p o s ec o n d i t i o n s ，an e wo n eo r d e rc o r r e c t i n gd i r e c t i o na n dc o m b i n i n gw i t h t h es q ps k i l l ，an e ws q pf e a s i b l ed e s c e n ta l g o r i t h mf o rn o n l i n e a ri n e q u a l i t yc 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 ( p ) i sp r e s e n t e d ，a n du n d e rw e a k e rc o n d i t i o n s ，w ep r o v e dt h a tt h e n e wm e t h o d sa r es t i l lg l o b a lc o n v e r g e n c ea n di t ss t r o n gc o n v e r g e n c e t h en e wm e t h o d sl l s el i t t l es t o r a g e ，t h u st h em e t h o d sa r ea t t r a c t i v ef o rl a r g e - s c a l e p r o b l e m s ，t h en u m e r i c a lr e s u l t si l l u s t r a t et h a tt h eh e wm e t h o d sa r ee f f e c t i v e k e yw o r d s ：n o n l i n e a r l yc o n s t r a i n e do p t i m i z a t i o n ，m e m o r yg r a d i e n t ，r o s e n p r o j e c t i o n ，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 ；c o n v e r g e n c e i i 前言 本文主要研究了解非线性约束最优化问题的结合共轭梯度参数的记忆梯 度罗申( j b ，r o s e n ) 投影算法及其全局收敛性，以及非线性不等式约束最优化问 题的序列二次规划( 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 ，简记s q p ) 可行下降算法 及其全局收敛性和强收敛性 r o s e n 梯度投影算法是求解非线性约束最优化问题的有效方法之一 1 9 6 0 年，罗申提出了梯度投影法的基本思想 1 ，2 】，即当光滑最优化问题的一个可行 点位于可行域的边界上时，目标函数的负梯度方向未必是可行方向，此时选取 负梯度方向在可行域的投影为搜索方向，以保证其可行性与下降性罗申方法 提出后的2 0 多年间，关于它的收敛性问题一直没有得到解决，虽然有不少人 进行了研究，但通常是在对罗申方法做出某些修正后才能证明其收敛性，直到 1 9 8 9 年，堵丁柱与章祥荪( d ud z a n dz h a n gx s1 9 8 9 ) 才完整地证明r o s e n 梯 度投影法的全局收敛性【3 j 近年来，陈广军、赖炎连，孙麟平，赵庆贞等，将 梯度投影算与其它方法结合，也得到了许多有效算法【4 - 。，在最优化领域占有 重要地位如陈广军1 4 】，利用r o s e n 投影建立了解带线性或非线性约束最优化 问题的计算量小、相对稳定的梯度投影算法，但存在收敛速度慢的缺陷 目前，记忆梯度算法是求解无约束规划较为有效的算法由于这类方法 在迭代中较多地利用了已经得到的目标函数的某些信息，具有较快的收敛速 度，若能将此法推广用于求解约束化问题，可望改善现有梯度投影算法的收敛 速度为此我们利用r o s e n 投影矩阵，对求解无约束规划的记忆梯度算法中的 参数给定某些限制条件，确定参数的取值范围，使其在取值范围内的取值均能 得到目标函数的记忆梯度r o s e n 投影下降方向，从而建立了求解带线性或非线 性约束最优化问题的记忆梯度r o s e n 投影算法，并在较弱条件下证明了算法的 收敛性同时给出了具有好的收敛性质和较快收敛速度的结合弗莱彻一里弗茨 ( f l e t c h e r - r e e v e s ，简记f r ) ，波拉克一理彼埃( p o l a k - r i b i e r e ，简记p r ) ，海斯特恩 一斯坦弗( h e s t e n e s - s t i e f e l ，简记h s ) 共轭梯度参数的记忆梯度r o s e n 投影算法， 从而将经典的共轭梯度法推广用于求解约束规划问题【8 1 共轭梯度法具有不需 要存储迭代矩阵，并且使得最速下降方向具有共轭性，较快的收敛速度，以及 】 精确线性搜索产生二次终止性的特点，从而提高算法的有效性和可靠性，适合 大规模最优化问题的计算 在非线性约束最优化问题的算法研究中，由于快速收敛类方法，如s q p 方 法能在尽可能短的时间内以及较少的计算量下求出满足一定精度的最优解， 因而具有相当广泛的应用领域和广阔的发展前景它在经济计划、生产管理、 国防、结构优化设计、交通运输、电力分配、化学反应设计、石油开采、政府 决策等许多重要领域内都有直接的应用，倍受政府部门、科研机构、科研人员 以及产业部门的青睐，其研究十分活跃 s q p 方法是一类研究快速收敛很有效的算法，最早的研究工作是w i l s o n 于1 9 6 3 年在其博士论文t 1 4 1 中提出的s o l v e r 算法早期s q p 算法的迭代点与 近似解不能满足可行性要求，而近期的s q p 算法大多采用罚函数作为效益函 数，要求初始点必须可行，成为一个新缺陷，为满足许多实际问题对近似解甚 至迭代点的可行性的严格条件，p a n i e r - t i t s 于1 9 8 7 年首先采用每次迭代解三个 二次规划的技术建立了约束优化问题的一个初始点和迭代点都可行的可行方 法 1 s l ，随后这一思想得到进一步的研究和发展 1 7 - 2 2 2 0 世纪8 0 年代以来，s q p 方法虽然得到了进一步的研究和发展，但由 于s q p 方法中每个迭代步需求解一个甚至多个二次规划，不具有强收敛性和 全局收敛性，且计算量也比较大，所以，目前已有成果都或多或少地存在以下 困难问题：( 1 ) 早期s q p 算法的迭代点与近似解不能满足可行性要求，而近期 的可行s q p 算法要求初始点必须可行；( 2 ) 需提出新的、广泛适用的s q p 算 法模型，并建立其超线性与二次收敛性条件；( 3 ) 每次迭代需解多个二次规划 ( q p ) ；( 4 ) 对近似h e s s i a n 阵作一个很严的一致正定要求；( 5 ) 当q p 无解或解 不满足要求时，这些方法所采用的辅助算法及其辅助方向或仍较复杂，或较简 单，只能获得算法的局部收敛性，但不能保证强收敛性，不适于大规模最优化 问题的计算；( 6 ) 需要严格互补条件；( 7 ) 无强收敛性和二次收敛率，收敛性 和收敛速度也不具有全局性 我们以上述困难和缺陷问题为主线，利用广义投影校正技术，通过改进假 设条件，对搜索方向进行某种修正，采用新型一阶修正方向并结合s q p 技术， 2 建立了一个有效的s q p 可行下降算法新算法可看作是一个主算法和一个辅 助算法的组合，在计算主算法搜索方向时只需解一个总有可行解的二次规划， 并采用广义投影技术产生克服玛拉托斯( m a r a t o s ) 效应的修正方向( 主算法不 需作线性搜索) ，从而简化了结构，降低了计算量在相对较弱的假设条件下， 分析和论证了算法的全局收敛性和算法的强收敛性 以上两类新算法具有较小的计算量和存储，而且收敛速度快，适合大规模 最优化问题的计算在每一章最后，还对各算法进行了数值试验，数值结果表 明本文所建立的算法在实际计算中是行之有效的 3 第一章预备知识 在这一章里，对后面各章节的讨论所涉及到的最优化问题中的概念、定义 和相关的结论，以及一些常用的记号等做一些简单介绍，以保证全文的系统 性、完整性和独立性 光滑最优化问题( p ) 1 1问题与记号 m i ny o ( z ) ， s t a ( x ) s0 ，i ，= 1 ，2 ，m ) ， ( 1 1 ) 厶( 。) = o ，j e = m + 1 ，m ) 其中z 舻，f o ， ：形一r ，i ，u e 为连续可微函数，y o ( x ) 为目标函数， a ( z ) 为约束函数，a ( z ) o ，i ，= 1 ，2 ，m 称为不等式约束五( z ) = o ，j e = m i + 1 ，m ) 称为等式约束 ( z ) 0 ，厶( z ) = 0 称为约束条件 s t 是 s u b j e c tt o 的缩写，表示优化变量x 受约束条件的限制 称集合d = ( z ： ( z ) 0 ，i ，西( z ) = o ，j e ，z 舻) 为约束集合，约束区 域或可行域；若x d ，则称x 为可行点或可行解 记可行集贾，不等式约束的积极约束集，( z ) ，以及l a g r a n g e 函数l ( x ，札) 分 别为 x = z r r 。l ( z ) 0 ，i j ；厶( z ) = o ，j e ) ， l ( z ) = i l f i ( x ) o ， l ( x ，仳) = f o ( x ) + 厶( z ) ， ，( z ) = 矗( z ) ，j l = e u ) 任意给定n n 阶矩阵p ，若p = 矽且p 2 = p ，则称p 为投影矩阵投影 矩阵p 具有下列性质： ( 1 ) 若p 为投影矩阵，则p 为半正定矩阵； 4 ( 2 ) p 为投影矩阵的充要条件是j p 为投影矩阵； ( 3 ) 设p 为n 阶投影矩阵，令q = ，一p ，则l = p x ：z r ”) ，l 上= 啦：z 舻 是互相正交的线性子空间，且任一z 形可唯一地分解为 x = p + q ，p l q l 上 1 2概念及定理 定义1 1 设x + 霄，( 1 ) 称矿为问题( p ) 的全局( 整体) 最优解，若f o ( x + ) 矗( z ) ，地x ； ( 2 ) 称矿为问题( p ) 的局部最优解( 极小点) ，若存在矿的邻域以。， 使得而( 矿) ，o ( z ) ，贾o 以 定义1 2 设矿贾，称x 为问题( p ) 的严格局部最优解，若s o ( x ) 0 ，使得 ，( - + a d ) 0 令b = ( a 幺a 以) 一1 a z ；p 以= e ，一a j k b j 。；p = ( p ，j 以) t = b j k g ；其中i k 为n 阶单位矩阵， 称为r o s e n 投影矩阵 引理2 2 1 4 1 设扩r ，对于以厶r a n k ( a ( 矿) ) = l 以l ，若p 以g = 0 ，p k t n ( 扩) = 0 ，“0 ，则z 为( p ) 之k t 点 对问题( p ) 的非k 一丁点矿r ，令：跳= p j k ( x 2 ) ( 夕( 矿) + 俄驴- 1 ) ，为了得 到目标函数，0 ( z ) 在矿点的下降的记忆梯度r o s e n 投影方向，我们按下面条件 选取参数： j g ( x k ) r p j t ( x k ) 9 ( z ) i 俄g ( z ) 丁p j k d 一1 i ， ( 2 1 ) l1 9 ( z ) 勺以( z ) o ( 。) + 雠舻一1 ) l ( 1 + 1 ) i 雠1 1 i p 以( z ) 夕( z 。) 0 i i p j 。d k 一1 m 其中- 0 为常数，例i 为f 。范数，即i = i z = ( 妻耽) ，z 舻；雠是一 参数，不同参数对应不同的共轭梯度法，具体的选取方法在本节最后的注释部 分给出；投影矩阵鼽为半正定，无须正定严格条件，若j k = j ，则算法的快 速收敛性结论依然成立 条件( 2 1 ) 实质上给出了俄的一个取值范围，使得雠在此范围内取值 均能保证砩为目标函数f o ( x ) 在扩处的r o s e n 投影下降方向即 1 9 ( z ) ? 鼽( z 。) 0 ( z ) + 俄d k 一1 ) i ( 1 + 。) i 威i f | p ( z ) g ( z ) l i l i p j k d k 一1 ( 2 2 ) 9 ( i ) 当俄 0 时，由( 2 2 ) 得 雠而骊万貉黼喾耙丽 ( i i ) 当俄 0h e ， 9 ( z ) r s ：i l p ( z ) ，( z ) 1 1 2 一i r j = - ：j ：- ：碗 ；：! f 舌；辫9 ( z 。) r p j 。( z ) d 。一1 = i i p j a z ) 9 ( z ) 1 1 2 一( i + a ! 竺1 旦) ! + l c o s 0 2 i i p 以( z ) g ( z ) 1 1 2 由f f i l l - 1 ，a x l 】砰研t - - 丽1 及上式知，结论成立 ( 2 ) 当9 ( z ) t p j 。( z ) d 一1 0 ，p 1 ，1 0 ，c 0 ，0 0 使得+ a 扩r ，v a i n o ，r k 】 若算法在有限次迭代后没有停止，则产生无穷点列 扩) v ，下面分两种情况 考虑 ( 1 ) 若存在k o n ，使得i d e t ( a 乏( x ) a j k ( x 。) ) i 0 ，使得以芝e ，v k n 3 引理2 8 f 2 j 设j k ( k n 3 ) 满足以正( 矿) ，且有 d e t ( a 炙( 妒) a j 。( ) ) i r ，v 南 3 由以n 3 ) 取法的有限性，存在4 3 ，使得以；z v k n 4 ，其中心为 3 之无穷子列，由于 扩 4 一矿，由引理2 8 得 i d e ( a 复( 矿) a j k ( x ) ) l 矿 0 ， 于是r a n k ( a s ( x ) ) = ， 所以b j ( 矿) 存在，且由锄( ) ( i 一1 ，2 ) ；g ( ) ，q ( ) ，j j 之连续性知b j ( x ) 一 b j ( z ) ，( 岛j v j ) 1 3 我们再根据驴的构造及引理2 4 ，不难得到 扩) 4 有界并且 有界，令 9 ( g + 雠扩。) + p 铲时 4 扩 地一d 4 g k t p g j , ( g + 磁扩一1 ) + 所k t t y r j k ，1 5 。m ， 丽1 + a 1 l p j 矿1 1 2 + # j k t 叼k ) 一，( 5 4 ) 因此，当k 充分大时，有 9 ( 矿+ 雠扩一1 ) - i - p 铲盼=g k t p ，( 矿+ 饿d 一1 ) 一心k l 妒l 一心k ) ) 砖 o 糕川m 川2 一磊彬，) ) 一圬( z ( 蟛) ) 厶( ) 一 o 0 其中艏= ( 力，j j ) t = b j ( x + ) 9 ( 矿) ，故有 m 2 糕川舢川2 一丢喇t ( 刮 一嵋( 妒。( 圬) ) 办( z + ) 嵋 o 0 若m = 0 ，则i i p j k g ( x + ) 1 1 = o ，彤2o ，膨力( 矿) = 0 因而矿为( p ) 之k t 点， 矛盾因而m + 0 ，进而n 0 引理2 9 存在” 0 及，使扩+ a d k r ，v a i n 0 ，叫，v k k o ，七n 5 证明( 1 ) 因为缈 5 一d ，故存在o l 0 ，使得 q 8 u p i 巧( 扩) d k l ，w 厶南5 1 4 又因为v j l j 有竹五。，5 ，故有 h ( x + a d ) = f ( x 。) + a ( z 。) d k + d ( a ) 一矿+ a q + o ( a ) ，v 七n 5 因此存在可 0 ，使得 h ( x + a d ) o ，v a 【o ，_ 】，v j l j , v k 5 ( 2 ) 因为m + 0 ，故存在，使得当v k ，5 时，有 矿r p ，( g k + 扩1 ) + p 铲咖等， 对于j ，亦有 巧( ) 扩= ( 1 + l p 铲w ，i ) 盼一( 9 灯p j ( 9 24 - 饿扩- 1 ) + p f 时) 叻， 我们记艇= 删p 5 0 ，k n 5 ) ，设聪= 七l p 0 ，岛5 ，并且设m 0 为 妒z ( 卫) 在 扩) 5 上的下界分两种情形讨论： ( i ) 考虑，若j l l ，对a 0 ，有 ，j ( z + a d ) = h ( x 2 ) 一a ( 1 - 4 - l p 罗仰哆i ) 妒，( 砖) 一a ( g t p j ( g 。 4 - 雠d 一1 ) + p 字时) 妒1 ( z ) 0 ，v k 蚝 若j l 2 ，当v k o ，k 吃时，有 五( 矿+ a 驴) = 厶( 扩) 一a ( 1 4 - l p 铲叻i ) 庐( 一心) 一a ( 9 舸p j ( 矿+ 磁扩1 ) + p 铲盼) 妒2 ( 矿) 4 - d ( a ) 一；a m 世+ m ) ， 所以存在面 0 使得a 【o ，吃】时， 厶( z 4 - a 扩) o ，v k k o ，k 赋 1 5 ( i i ) 考虑联，记目”= i n f i ( 1 + i p j k t t r z r r ，k i ) 咖。( 蝣) 】一1 i j j , k 聪) ，则r 0 若j l 1 ，对v a 【0 ，q ”】，有 厶( + a d ) = 0 ，另一方面，由引理2 9 ，存在 7 0 及如，使得 z + a d r ，坝【o ，町】，v k ，k 5 现在分两种情况讨论： ( 1 ) 若 n ， 舻) 5 0 ，在不等式f o ( x 。) 一而( z 蚪1 ) 丁妒g t d k 的两边，令 k o 。，( k 5 ) ，得9 t ( 矿) 矿0 ，矛盾； 1 6 ( 2 ) 若i n f a u s 0 ，不妨设k l 。i m 5 = 0 ，又由 x 七+ a d k r ，v a 【0 ，叩】，v k k o ，k n 5 及胪的取法知，当k n 5 充分大时，有 2 7 a 知g 知丁d i o ( 2 ：七) 一f o ( 2 ：膏+ 1 + 2 a 七d k ) = 2 a g r ( 扩+ 2 靠妒d ) 扩， 其中靠 0 ，1 】，令k 一， n s ) ，得g t ( 矿) 扩t g r ( 矿) d ，由0 7 1 知 ，( 矿) 矿0 矛盾故矿必为( p ) 之k t 点 证毕 2 3数值例子 本节我们选择了文【4 】中的几个算例，对本文算法进行数值实验，在c p u 为p i i l 9 3 3 机器上利用m a t l a b 编制程序，一维搜索全都采用a r m i g o 搜索，计算 结果表明算法是有效的 我们用i t 表示算法的迭代次数，t 表示所用时间，x + 表示最优解，0 表示最优值，在p c g m ( 仇= 压) ，p f r m ，p p r m ，p h s m 算法中，取= o 4 ，u l = 0 5 ，c = 1 ，也( t ) = 1 0 t ( i = 1 ，2 ) ，咖1 ( 舻) = 0 ，2 ( 妒) = 1 0 0 表1 - 3 分别为例1 - 3 在 精度要求慨z t ) 9 ( z k ) | | 1 0 ，1 0 - 3 下的计算结果，表4 和表5 分别为例4 在 i i p ( x ) g ( 砜) | | 2 ，_ r ( 2 ，3 ) ，k ：= 1 ； s t e p2 对于当前可行点扩及矩阵b 女，求p ，的k t 点对( d 6 ，u k + 1 ) 若始= 0 ，则扩为( p ) 的k t 点，停止若，无k t 点对，或l i b d k o 1 c | 【始胆，则 转入s t e p6 ； s t e p3 根据( 3 6 ) 一( 3 ，1 2 ) 计算 n k = n ( x ) ，d k = d ( x 。) 仉= q ( x ) ，芦= 7 ( x ) ，以= d p ) ； s t e p4 若 ( g o ( x ) ) 丁罐m j n 一j l 始| f 6 ，一l f d 。j f 6 ) ，( 3 1 8 ) 作试探搜索s t e p5 ，否则，转入s t e p6 ； s t e p5 若 f o ( x + d k ) sf o ( z ) 4 - a g o ( x ) 瑶( 3 1 9 ) j ( x + d k ) 0 ，j i 2 3 令k = 1 ，转入s t e p8 ，否则，进入s t e p6 ； s t e p6 根据( 3 1 3 ) 一( 3 1 7 ) 计算方向矿= 畦，若p k = 缱= 0 ，则矿为( p ) 的 一r 点，停止；否则，令d k = q k ； s t e p7 作a m i j o 非精确线性搜索；计算 1 ，p ，p 2 ，) 中满足 i o ( z 十a d r 。) a ( x ) + g o ( x ) r d ( 3 2 0 ) 力( + a d 。) o ，j j 的最大值h 令1 = 一= 砖； s t e p8 令z 七十1 = 扩+ 九扩，采用某种方法计算新对称矩阵最+ l ，或通过修 正最产生鼠+ 1 ，令k 一k 十1 ，转回s t e p2 算法a 中的矩阵鼠可按适当的计算公式产生 1 a - 1 e 1 算法的适定性及其性 质如下： 弓i 理3 2 【1 钉( 1 ) ( 跏( z ) ) t q 。一一+ f ，( g j ( x ) ) t q 一p 1 + f ，f ( ) ； ( 2 ) 若序列( ) 有界，则存在常数c - 0 ，使得 ( o o ( x ) ) 丁口一c 1 l j g | j 1 + f ，( 毋( z ) ) t q 。一e l i i q j 1 1 十f 一1 ，i ( x ) ； 称其有( 1 ) ，( 2 ) 性质的q 为一阶可行下降方向 3 3算法的收敛性 3 3 1 全局收敛性 引理3 3 若妒一矿，k k ，i k i = 0 0 ，且对批k ，z 。+ 1 = 扩+ d 均由s t e p5 及 s t e p8 产生，则1 i md 3 = 0 m 证明由( 3 1 8 ) ，( 3 1 9 ) 有 厶( z + 1 ) = f o ( x + d k ) sf o ( x 2 ) + n g o ( x 。) t 稚 y o ( x ) 一n i i 姑忾 2 4 又有( 3 i s ) ( 3 2 0 ) 及引理3 3 知，序列 南( 矿) 单调下降，且有 1 i r af o ( x 。) = f o ( 矿) 于是u ms o ( x ) = s o ( z + ) 令k k ，k o 。，则有，l i m 姑= 0 证毕 定理3 4 ( 全局收敛性) ：算法a 或有限步停止于问题( p ) 的k t 点z ，或 产生无穷点列 ) ， 扩 的任意聚点均为( p ) 之k t 点 证明：若算法a 终止于，则d 6 = 0 或p k = 0 ，由引理3 1 知为k r 点 若算法a 产生无穷点列 扩 ，x + 为其任意给定的聚点，记二次规划p ，的积 极约束集为 l = d i i y j ( z ) + ( 卯0 ) ) t d = o 由于厶，不妨假设存在无穷子列k ，使得 矿一矿，k k ，厶兰，v k k ， 下面分两种情况讨论： ( 1 ) 存在无穷子列k lck ，使得y k k 1 ，d 2 = q k , v k k ，z + 1 = + k 扩均 由s t e p 6 - s t e p 8 产生，由收敛性定理可知矿为( p ) 的k t 点 ( 2 ) v k k ，矿+ 1 = 扩+ a k 扩均由s t e p5 及s t e p8 产生，由引理3 3 有恕罐= 0 记 a b = ( g j ( z 。) ，j f ) ，a 。= ( 缈( z ) ，j ，7 ) 面+ 1 = ( u k + l , j ，7 ) ，面+ = 一( a t a 。) 一1 a t 。跏p + ) = ( 嵋，j f ) 由t 条件得到 9 0 ( x 。) + b k d k o + a 舻+ 1 = 0 ， 逆 厶( ) + ( g j ( x ) ) 丁罐= o ，歹， 于是，由稚一0 ，( k k ) 及( 3 2 2 ) 式，得厶( 矿) = o j ， 从而j j ( 矿) ，故a 列满秩序，当充分大时a t a ，可逆， ( 3 2 2 ) 雒如亦可 由s t e p2 中的 r b k d 5 l l c | | 罐”知，鼠d 3 0 ；再由( 3 2 2 ) 式，有面= - ( a t a 。) 。a t ( g o ( x + ) + 毋稚) 一( 面，k 我们注意到( 研d 占，d 占) 一( o ，o ) ，q k + 1 = o ，j ，在( 3 3 ) 一( 3 5 ) 中，令z = 矿，也= d 占，= 札 k + 1 ，k k ，k 一o 。，则有 g o ( x ) + q 缈( 矿) = 0 ， j e l 矗( ) 0 ， q 厶( z + ) = 0 ，q o ，j ， 当嵋= o 时，j j j 7 ，故而，( 矿，矿) 为问题( p ) 的k t 点对 证毕 3 3 2 强收敛性 本节将在相对较弱的假设条件下，分析和论证算法的强收敛性，即其产生 的点列 矿) 整列收敛到问题) 的局部最优解 定义3 5 称算法a 在解集q 内是强收敛的，若对于任意的初始迭代点z - 研，或满足一定可行性的任意初始点z - ，存在矿q ，使得1 i m 扩= 矿 假设也：算法a 产生的点列 扩 有界，且有一个聚点矿满足二阶充分条 件和严格互补条件 在假设玩下，由定理3 4 知z 为问题) 的k t 点设相应的k t 乘 子为”+ = ( u j ，j n 则矿为问题0 ) 的严格局部最优解 引理3 6 若假设研和假设现成立，则有 l i m 。桫+ 1 一矿| | = 0 证明由( 3 a s ) ，( 3 2 0 ) ，引理3 2 ( 1 ) 及假设凰可知，序列 ，( 扩) 单调下降，且 有聚点( x ) 从而有 。l i ef ( z ) = ( z ) ， ( 3 2 3 ) * + o o 当步长由s t e p5 产生时，由( 3 1 7 ) ，( 3 1 8 ) 有， 南( z + 1 ) 一y o ( x ) 一q a i l d | 1 5 ，( 3 2 4 ) 2 6 当步长由s t e p7 产生时，由( 3 2 0 ) 及引理3 2 ( 2 ) 有 f 0 ( x + 1 ) 一向( z ) 一c 1 7 a i t d l i l + ( 3 2 5 ) 注意到参数6 2 ，f 0 ，由( 3 2 4 ) ，( 3 2 5 ) 知而 1 ，o o 0 使得讹有 知( z ) 一f o ( x ) 墨a o a i i d 2 l i 6 ( 3 2 6 ) 由( 3 2 3 ) 及( 3 2 6 ) 可推得 l i m 。圳砌0 因此，。l i mi i x m 一旷= ，l i mk i l d k l l 。= 。l i m 砥_ 1 ( a k l l d 证毕。 叶o o e - o o o 月_ o o 引理3 7 若形中的序列 扩，满足l i x m 一l i 一0 ，且有一个孤立点矿， 则l i mx k + 1 = 矿， 定理3 8 ( 强收敛性) 若假设风和假设也成立，则1 i r a = 矿即算法a 是 强收敛的 证明易知序列 扩) 的聚点矿是问题( p ) 的一个孤立k t 点，因此，由全 局收敛性定理3 4 可知，矿是序列 扩) 的一个孤立聚点，又由引理3 6 和引理 3 7 知1 i m 舻= 矿，故算法是强收敛的 。 证毕 3 4数值例子 本节我们给出算法a 在几何规划中的一个直接应用考虑下列非线性不 等式约束的几何规划问题) ， i | l i 以“幻， ( 3 2 7 ) is t 吼( t ) s1 ，i ，t 0 其中h i ( t ) = 量6 l 鱼垆，i = o ，1 ，m ，v a i j 曲l r 作变换 岛= 矿= e x p ( x j ) ，j = l ，m 得到 记 a t = ( a i j l ：j = 1 ，n ；f = 1 ，) 。k 。，i = 0 ，1 ，m b i = ( b i l ，玩女。) 丁，酽= e x p ( x ) = ( 矿1 ，e x n ) t d i a g ( x ) = d i a g ( x ，i = 1 ，- ，礼) 我们通过适当的变换可使问题p 等价于问题( p ) 先经过简单计算和变形 h i ( t ) 一1 = 6 i l e 印( o 明巧) 一1 = 6 ，e a 2 1 = ( z ) ，i f 七t“ h o ( t ) = b 珊e x p ( a o j j ) = 曙e a 。2 = 矗( z ) 于是，几何规划问题) 等价于( p ) ( 3 2 8 ) 其中函数五( z ) 无穷次可微，且梯度及海森阵具有以下简单的表达和计算公式 m 0 ) = a t d i a g ( b 1 ) e a 。，i = 0 ，1 ，m h i ( x ) = v 2 a ( x ) = a ，d i a g ( b ) d i a g ( e 船) a ，i = 0 ，1 ，m 下面通过两个数值试验来进一步说明算法a 的有效性取参数c = 4 0 0 ， f = o 1 4 = 0 4 ，= 0 6 ，7 = 0 5 ，6 = 3 ，7 _ = 2 5 ，u 1 = ( 1 ，1 ) r 例1 m i n f o ( x ) = z ；一1 5 0 x l + z ；一2 0 0 0 x 2 ， s t ( z ) = z 1 + 2 x 2 5 0 0 0 0 ， ( 3 2 9 ) ，2 ( z ) = z ；+ z ! 一4 0 0 0 0 0 0 0 取几种不同的初始可行点z 1 ，运用算法a 对例1 进行求解，其运算结果反 映在表1 k 一嘶删 - 罾 时 例2 初始点z t终止近似解矿 ，0 ( z ) ( 2 ，3 )( 7 5 0 0 0 0 0 0 ，1 0 0 0 0 0 0 0 0 0 ) 一1 0 0 5 6 2 5 0 0 0 0 0 0 ( 1 0 0 0 ，2 0 0 ) ( 7 5 o 0 0 0 0