（运筹学与控制论专业论文）非线性优化中的一类对偶算法的理论研究.pdf

摘要 本文主要研究非线性优化中的一类对偶算法，包括无约束极大极小问 题的对偶算法和约束非线性规划问题的一类对偶算法的理论与相应的数值 实现本文取得的主要结果可概括如下t 1 第2 章建立求解不等式约束优化问题的一类对偶算法的理论框架在 适当的假设条件下，证明了该类算法的局部收敛性质，并给出近似解 的误差界验证了p o l y a k ( 1 9 9 2 ) 的修正障碍函数算法以及b e r t s e k a s ( 1 9 8 2 ) 的增广l a g r a n g e 函数算法都是这类算法的特例还基于个指 数型势函数建立了相应的对偶算法，它也属于这类对偶算法对这一对 偶算法，给出了精细的收敛性结果，同时估计了势函数的h e s s e 阵的条 件数，它依赖于罚参数 2 第3 章给出无约束极大极小问题的一个对偶算法的收敛理论给出一 个基于b e r t s e k a s ( 1 9 8 2 ) 罚函数的求解无约束极大极小问题的对偶算 法证明罚参数存在一个阀值，当罚参数小于这一阀值时，该对偶算法 产生的序列局部收敛到问题的k u h n t u k e r 点，并建立了参数解的误差 估计式同样估计了罚函数的h e s s e 阵的条件数。它也依赖于罚参数 3 第4 章考虑算法的实现技术与算法的推广首先针对前两章的对偶算 法由于需要精确求解一系列无约束极小化问题，因而实际计算中很难 实现这一缺点，构造修正的对偶算法，即，关于势函数的无约束极小化 问题无需精确求解的对偶算法证明这些修正的对偶算法仍具有同前 两章的概念性对偶算法相同的收敛性结果我们还进一步构造了般 约束非线性规划问题的对偶算法，建立了相应的局部收敛理论最后估 计了修正l a g r a n g e 函数的h e s s e 阵的条件数，它同样依较于罚参数 4 第5 章对第2 章，第3 章及第4 章的对偶算法进行了数值实验用这 些算法计算大量的规模不是很大的不等式约束优化问题，无约束极大 极小同题，一般约束优化问题，数值结果表明它们是有效的同时给出 的各种关于数值结果的表格验证了取得的某些理论结果的正确性 关键询：对偶算法，无约束极大极小问题，约束非线性规划问题，修正l a g r a n g e 函数，势函数，罚参数，条件数，局部收敛性，误差界 a b s t r a c t t h i sd i s s e r t a t i o ns t u d i e sm a i n l yt h e o r i e sa n da c c o r d i n gn u m e r i c a li r a - p l e m e n t a t i o no fac l a s so f d u a la l g o r i t h m sf o rn o n l i n e a ro p t i m i z a t i o np r o b - l e m s ，i n c l u d i n gu n c o n s t r a i n e dm i n i m a xp r o b l e m sa n dc o n s t r a i n e dn o n l i n e a r p r o g r a m m i n gp r o b l e m s t h em a i nr e s u l t s ，o b t a i n e di nt h i sd i s s e r t a t i o n ， m a yb es u m m a r i z e da sf o l l o w s ： 1 c h a p t e r2e s t a b l i s h e st h et h e o r e t i c a lf r a m e w o r ko fac l a s so fd u a la l g o r i t h m sf o rs o l v i n gn o n l i n e a ro p t i m i z a t i o np r o b l e m sw i t hi n e q u a l i t y c o n s t r a i n t s w ep r o v e ，u n d e rs o m em i l da s s u m p t i o n s ，t h el o c a lc o n v e r - g e n c et h e o r e mf o rt h i sc l a s so fd u a la l g o r i t h m sa n dp r e s e n tt h ee r r o r b o u n df o ra p p r o x i m a t es o l u t i o n s t h em o d i f i e db a r r i e rf u n c t i o nm e t h o d so fp o l y a k ( 1 9 9 2 ) a n dt h ea u g m e n t e dl a g r a n g ef u n c t i o nm e t h o do f b e r t s e k a s ( 1 9 8 2 ) a r ev e r i f i e dt ob et h es p e c i a lc a s e so ft h ec l a s so fd u a l a l g o r i t h m s ad u a la l g o r i t h m ，b a s e do na l le x p o n e n t i a lp o t e n t i a lf u n c - t i o n ，i sp r o v e nt ob ei n c l u d e di nt h i sc l a s so fd t l a la l g o r i t h m s d e t a i l e d c o n v e r g e n c er e s u l t sf o rt h ed u a la l g o r i t h ma x eg i v e na n dt h ee s t i m a t eo f t h ec o n d i t i o nn u m b e ro ft h ep o t e n t i a lf u n c t i o n sh e s s i a ni se s t a b l i s h e d ， w h i c hd e p e n d so nt h ep e n a l t y p a r a m e t e r 2 c h a p t e r3i sd e v o t e dt ot h es t u d yo ft h ec o n v e r g e n c et h e o r yo fad u a l a l g o r i t h mf o ru n c o n s t r a i n e dm i n i m a xp r o b l e m s ad u a la l g o r i t h mf o r s o l v i n gu n c o n s t r a i n e dm i n i m a xp r o b l e m s ib a s e do i lt h ep e n a l t yf u n c t i o n o f b e r t s e k a s ( 1 9 8 2 ) ，i sp r e s e n t e d w ep r o v et h a tt h e r ee x i t sat h r e s h o l d o ft h ep e n a l t yp a r a m e t e rs a t i s f y i n gt h a tt h es e q u e n c e s g e n e r a t e db y t h ed u a la l g o r i t h mc o n v e r g el o c a l l yt ot h ek u h n - t u k e rp o i n to ft h e u n c o n s t r a i n e dm i n i m a xp r o b l e m sw h e nt h ep e n a l t yp a r a m e t e ri sl e s s t h a nt h et h r e s h o l d a n dw ee s t a b l i s ht h ee r r o rb o u n d o ft h es o l u t i o 璐 w i t ht h ep e n a l t yp a r a m e t e r f u r t h e r m o r e ，t h ec o n d i t i o nn u m b e ro f p o t e n t i a l f u n c t i o n sh e s s i a ni se s t i m a t e d ，w h i c hd e p e n d so nt h ep e n a l t y p a r a m e t e r 3 c h a p t e r4s t u d i e st h et e c h n i q u e sf o rn u m e r i c a lr e a l i z a t i o no f t h ed u a l a l g o r i t h m sa n dg e n e r a l i z a t i o no ft h ed u a la l g o r i t h m s t og e n e r a lu s c o n s t r a i n e dn o n l i n e a rp r o g r a m m i n g a tf i r s t ，w ec o n s t r u c tm o d i f i e d d u a la l g o r i t h m st oo v e r c o m et h ed r a w b a c kt h a ti tn e e d st or e s o l v ea s e q u e n t i a lu n c o n s t r a i n e dm i n i m i z a t i o np r o b l e m se x a c t l yi n t h es t e p2 o ft h ed u a la l g o r i t h m si nc h a p t e r2a n dc h a p t e r3 i ti sp r o v e nt h a t t h e s em o d i f i e dd u a la l g o r i t h m ss t i l lh a v et h es a m ec o n v e r g e n c er e s u l t s a st h o s eo ft h ec o n c e p t i o n a ld u a la l g o r i t h m si nc h a p t e r2a n dc h a p t e r 3 s e c o n d l y , ad u a la l g o r i t h mi sc o n s t r u c t e df o rg e n e r a lc o n s t r a i n e d n o n l i n e a rp r o g r a m m i n g p r o b l e m sa n dt h el o c a lc o n v e r g e n c et h e o r e m i s e s t a b l i s h e da c c o r d i n g l y t h ec o n d i t i o nn u m b e ro fm o d i f i e dl a g r a n g e f u n c t i o n sh e s s i a ni se s t i m a t e d ，w h i c ha l s od e p e n d so nt h ep e n a l t yp a _ r a m e t e r 4 c h a p t e r5r e p o r t sn u m e r i c a le x p e r i m e n t sf o rt h ed u a la l g o r i t h m si n c h a p t e r2 c h a p t e r3a n dc h a p t e r4 w ea p p l yt h e s ed u a la l g o r i t h m s t os o l v eal a r g en u m b e ro fn o n l i n e a ro p t i m i z a t i o np r o b l e m sw i t hr e l a - t i v es m a l l s c a l e ，i n c l u d i n gi n e q u a l i t y c o n s t r a i n e do p t i m i z a t i o np r o b l e m s ， u n c o n s t r a i n e dm i n i m a x p r o b l e m sa n dg e n e r a lc o n s t r a i n e do p t i m i z a t i o n p r o b l e m s t h en u m e r i c a lr e s u l t sd e m o n s t r a t et h a tt h ed u a la l g o r i t h m s a r ee f f e c t i v ea n dt h e1 i s t e dt a b l e so nt h en u m e r i c a lr e s u l t sc o n f i r mt h e c o r r e c t n e s so fs o m et h e o r e t i c a lr e s u l t so b t a i n e di nt h e p r e v i o u sc h a p t e r s k e y w o r d s ：d u a l a l g o r i t h m ，u n c o n s t r a i n e dm i n i m a xp r o b l e m ，c o n s t r a i n e d n o n l i n e a r p r o g r a m m i n gp r o b l e m ，m o d i f i e dl a g r a n g ef u n c t i o n ，p o t e n t i a l f u n c - t i o n ，p e n a l t yp a r a m e t e r ，c o n d i t i o nn u m b e r ，l o c a lc o n v e r g e n c e ，e r r o rb o u n d 蔓! 童 堕丝l 一 1 绪论 综述对偶方法中的原始一对偶方法及修正l a g r a n g e 函数方法的研究历史及现 状；介绍本文研究的非线性优化中的一类对偶算法的研究背景，并列出取得的主要 结果 1 1 原始对偶方法与修正l a g r a n g e 函数方法 原始对偶方法是求解线性规划及非线性规划的重要方法这一方法在线性规射领 域中的理论已发展得较为完善，参阅s j w r i g h t ( 1 9 9 7 ) t 1 1 与y y y e ( 1 9 9 7 ) 【2 】，这里不 再赘述本节仅对原始对偶方法及修正l a g r a n g e 函数方法在非线性优化领域中的研究 现状进行综述 首先以下述非线性规划问题为例说明对偶方法的含义 其中f ：研h 矾，h ： k u h n t u c k e r 条件是 v ；l ( x ，u ， ) = 0 ， ( z ) = 0 ，g ( x ) 0 ， v i g i ( x ) = 0 ，i ；l ，m ， 挑0 ，i = 1 ，m ， s t h ( x ) = 0 ，( 1 1 ) g ( z ) 0 ， 盈ph 删，g ：删。r _ 胛“是光滑函数问题( 1 1 ) 的 ( 1 2 口) ( 1 2 6 ) ( 1 2 c ) ( 1 2 d ) 其中l ( 。，u ， ) = ，( 。) + 7 1 , t ( 茹) + v t g ( 。) 是( 1 1 ) 的( 线性) l a g r a n g e 函数若某一算法 中的每一迭代点均近似地满足( 1 2 b ) 且使，( z ) 或其效益函数下降。则这一算法属于原 始算法，因为只要求原始变量( 近似) 可行；若某一算法中的每一迭代点均满足( 1 2 a ) 与 ( 1 2 d ) ，逐步迭代到( 1 2 b ) 与( 1 2 c ) 最终被满足，则这一算法为对偶算法，因为它要求对 偶变量u ， 是可行的；若某一算法中的每一迭代点均满足( 1 2 a ) ，( 1 2 b ) 与( 1 2 d ) ，最终 迭代到( 1 2 c ) 被满足或对偶间隙消失，则这一算法是原始对偶算法，因为算法要求原 始变量及对偶变量均可行 最成功的对偶算法当属求解线性规划的对偶单纯形法( 见d a n t z i g ( 1 9 6 3 ) 1 a 1 ) 及g o l d - f a r b i d n a n i ( 1 9 8 3 ) a 求解严格凸二次规划的对偶算法基于w b l f e ( 1 9 6 3 ) 1 5 j 对偶理 论，凸规划的对偶算法往往是从对偶问题出发而构造的。其算法理论也比较成熟，见 r o c k a f e u a r ( 1 9 7 1 ) 悯 1 大连理工大学博士学位论文：非线性优化中的一类对偶算法的理论研究 随着线性规划内点法理论与计算发展的日趋完善，人们把线性规划原始一对偶内点 法的思想用于求解更为广泛的问题，如互补问题，非凸非线性规划问题，等等 m h w r i g h t ( 1 9 9 1 ) 构造了单调非线性互补问题的原始一对偶算法；在此基础上，m o n t e i r o ， p a n g w a n g ( i 9 9 2 ) 进一步考虑了非单调非线性问题的原始一对偶算法；s j w r i g h t ( 1 9 9 2 ) 对线性约束的非线性规划问题进行了探讨，并给出了相应的原始一对偶算法； l a s d o n ，y u & p l u m m e r ( 1 9 9 2 ) 建立了多种求解一般约束非线性规划问题的原始- 对偶 算法；y a m a s h i t a ( 1 9 9 2 ) 建立了一种求解一般约束问题的原始对偶算法，并且进行了 相应的收敛性分析九十年代初期，在非线性优化领域中有关原始对偶方法的研究工 作还有m c c o r m i c k ( 1 9 9 1 ) 建立的非线性原始一对偶算法及其相应的超线性收敛理论； k o j i m a ，m e g i d d o & n o m a ( 1 9 9 1 ) 建立的求解非线性互补问题的同伦方法，等等参见 7 一【1 4 】 九十年代后期，人们对非线性优化中的原始一对偶方法的研究更加深入，e 1 一b a k r y , t a p i a ，t s u c h i y a & z h a n g ( 1 9 9 6 ) 【1 5 】及g a y , o v e r t o n w r i g h t ( 1 9 9 8 ) 1 6 的工作具有代 表性 e 1 一b a k r y 等( 1 9 9 6 ) 考虑了形式为( 1 1 1 ) 的一般约束非线性规划问题他们建立了两 种稍有差异但收敛性结果截然不同的原始一对偶算法第一种算法的思想基于问题( 1 _ 1 ) 的k k t 条件，即( 1 2 a ) 一( 1 2 d ) 的松弛变量形式亦即， x ，y ，s ，z ) = v ；l ( x ，y ，z ) h ( x ) g ( 。) + 8 z s e 一“8 = 0 ，( 5 ，z ) 0 ，( 1 3 ) 其中p 0 为障碍参数， v 。l ( x ，y ，z ) = v f ( x ) + v ( 。) + v 口( z ) z ，z = d i a g l i 。亿) ， s = d i a g ，! i 0 令乃= 一番裔，j = 1 ，m ，则同题 ( 1 4 ) 的k k t 条件为 ，v 捌则瑚、 g p ( $ ，y ，z ) = l ( 茹)l = o ， ( 1 5 ) 勋( 。) + p e 其中z = d i a g 。 。) 基于方程( 1 5 ) ，建立了相应的原始对偶算法，详细分析了算 法具体实施时会遇到的各种问题，如当求解( 1 5 ) 时某些重要矩阵可能会出现非正定情 况。扰动参数_ “如何选取等，并且给出了相应的处理策略g a y 等( 1 9 9 8 ) 进行了大量 的数值实验，取得了数据详尽的实验结果，这些结果充分说明了原始一对偶方法具有很 大的潜力，值得进一步研究 修正l a g - r a n g e 函数往往是根据所解决问题的特点及相应的经典l a g r a n g e 函数( 即 线性l a g r a n g e 函数) 形式而建立的具有光滑增广l a g r a n g e 函数( 包括其在内) 性质的函 数，它可以用来建立对偶算法给定可行的初始对偶变量，迭代过程中保证对偶变量的可 行性对于给定的对偶变量，求解修正l a g r a n g e 函数的极小化问题，得到原始近似解， 然后根据所求得的原始近似解对对偶变量进行修正，然后进行循环，最终得到原始最优 解与对偶最优解可见修正l a g r a n g e 函数方法是一种对偶方法 早期的求解约束非线性规划问题的方法都是罚函数法，如c o u r a n t ( 1 9 4 3 ) ，f d s c h ( 1 9 5 5 ) ，c a r r o l l ( 1 9 6 1 ) 等，见 17 】一 2 0 】它的基本思想是将约束问题非约束化但是由于 这些罚函数法一般要求罚因子趋于无穷大( 或0 ) 或者需要求解非光滑最优化问题，所以 无约束优化的算法在数值上常遇到困难，而且收敛速度也不快针对这些问题，h e s t e n e s ( 1 9 6 9 ) ，p o w e l l ( 1 9 6 9 ) 以及h a a r h o f f b u y s ( 1 9 7 0 ) 分别提出了著名的乘子法，用来解决 等式约束非线性规划问题，见 2 1 - 【2 3 】最初的乘子法是基于二次增广l a g r a n g e 函数( 形 式最简单的修正l a g r a n g e 函数) 建立的，每一次无约柬极小化增广l a g r a n g e 函数之后， 利用前一次求得的解的信息对乘子进行修正，如此重复上述过程，直到满足一定的终止条 件二次增广l a g r a n g e 函数法，即，最早的修正l a g r a n g e 函数方法这一方法的优点在于 它克服了早期罚函数的病态问题以及收敛速度较慢这些弱点但是，这几位学者都没有对 此方法进行收敛性分析，参见v t p o l y a k n v 2 y e t ，y a k o v ( 1 9 7 3 ) 2 4 在一定的条件 下，p 0 1 y a k & t r e t y a k o v ( 1 9 7 3 ) 证明了存在罚参数的阀值，并且当罚参数小于( 或大于) 这一阀值时，这一方法以几何收敛率收敛到原始一对偶最优解，同时给出了依赖于罚参数 的解的误差上界r o c k a f e l l a x ( 1 9 7 3 ，1 9 7 4 ) 刚，嗍把h a a r h o f f & b u y s h e s t e n e s p o w e l l 的 3 盔垄望三盔堂璺圭堂垡堡塞：韭垡丝垡垡塑二鲞塑堡墨鲨箜里堡堡塞一一 思想又进一步推广应用于不等式约束优化问题，得到般约束优化问题的乘子法理论有 关乘子法的详细研究工作可参阅b e r t s e k a s ( 1 9 8 2 ) 2 7 的专著值得一提的是，b e r t s e k a s ( 1 9 s 2 ) 中关于凸规划非二次惩罚函数法也属于修正l a g r a n g e 函数方法 随着人们对修正l a g r a n g e 函数方法的深入研究，该方法的优越性逐渐显示出来，尤 其是函数的形式也由复杂趋向于简单c h a r a l a r a b o u s ( 1 9 7 7 ) 建立了求解不等式约束非 线性规划问题的最小p 阶函数，于1 9 7 9 年又建立了该函数的修正形式用来解决无约束 极大极小问题，见【2 s 一 2 9 最小p 阶函数确实有相当好的性质，并且由此建立的算法有 很好的收敛结果，计算上也有效，但函数形式较复杂，不利于计算p o l y a k ( 1 9 s s ) 3 0 】建 立了形式简单的求解无约束极大极小问题1 2 1 i n $ m a x i 0 为罚参数，q = 如l k m ( x ) + 1 0 ，i = 1 ，m ) ，分析了这两种函数在 k u t m - t n c h e r 点处具有光滑增广l a g r a n g e 函数的性质，并且证明了在适当条件下，罚参 数存在阀值 0 ，当k o 时，基于这两种函数建立的算法均局部收敛于原始最优解 与对偶最优解，同时也给出了近似解的界值估计式p o l y a k & t e b o u l l e ( 1 9 9 7 ) a 2 曾基 于如下一类函数 1 旦 g ( 。，”，曲= ，( o ) + 二 ：铭i 妒( 鳓( 茹) ) ， p 西 建立了求解凸约束优化问题的n r ( n o n l i n e a rr e s a & h n 曲算| 法，其中p 0 为罚参数，妒 为满足一定条件的二次连续可微函数，g 均为凸函数在一些凸性条件下以及一些适 当的假设条件下，证明了n f t 算法产生的对偶序列解全局收敛于最优l a g r a n g e 乘子，而 相应的原始序列解在e r g o d i c 意义下近似原始最优解而这类算法也属于修正l a g r a n g e 函数方法l i & s u n ( 2 0 0 0 ) 嘲对不等式约柬优化同题进行变形： m i n f ( x ) l g i ( x ) 6 j ) ， 4 塑! 童堕丝 其中，( z ) ，b j0 = 1 ，m ) 均太于0 ，g j ( x ) 0 = 1 ，m ) 为非负的，由此建立了p 一幂 l a g r a n g e 函数 i l v ( x ，札) = m ) 他( z ) 】p _ 鸳) j = l 和部分p 一幂l a g r a n g e 函数 ，n 岛( 掣) = m ) + 嘶 胁( 茹) 一圬) j = l 其中p 0 为罚参数由他们对这两个函数性质的分析结果知道这两个函数也是修正 l a g r a n g e 函数由此可见，对于不同类型的优化问题可以建立不同形式的修正l a g r a n g e 函数，而且对于同一类优化问题，也存在不同形式的修正l a g r a n g e 函数，并且可以由此 建立相应的算法另一方面，对于同一类修正l a g r a n g e 函数方法，可以通过应用不同的 修正l a g r a n g e 函数形式来解决不同类型的优化问题，例如。可以应用修正l a g r a n g e 函 数形式( 1 6 ) 来解决无约束极大极小问题，应用修正l a g r a n g e 函数形式( 1 7 ) 或( 1 8 ) 来 解决不等式优化问题等等 1 2 本文的研究背景及取得的主要结果 正如第1 1 节所介绍的，原始对偶方法目前已成为众多学者的研究热点，并且它的 数值表现也颇吸引人但我们容易发现各种原始一对偶算法形式在具体实施时不可避免 地都会遇到许多复杂问题，如它们要求原始变量与对偶变量均严格初始可行，而这一问 题的解决就需要耗费相当大的工作量；寻找搜索方向时，要涉及原始对偶线性系统方 程的形式确定及其求解技巧问题；确定搜索步长时，不仅要考虑到原始变量与对偶变量 均可行而且还要使迭代点满足势函数下降的条件，而势函数又是一个值得研究的问题； 原始一对偶方法还要求在选取障碍参数时不仅需要考虑到使迭代朝障碍轨道进行而且还 需要考虑到尽可能地使解的误差最小，等等而诸如第1 1 节所介绍的修正l a g r a n g e 函 数的形式较简单，而且相应的算法也具有很好的收敛性质鉴于这样一些原因，本文的 研究对象是非线性优化中的一类对偶方法，即。修正l a g r a n g e 函数方法本文取得的结 果如下： 第2 章构造了一类求解不等式约束非线性规划问题的对偶算法在适当的条件下， 论证了这类对偶算法的局部收敛性理论，并给出了原始一对偶序列解的误差上界经过 仔细推证，发现p o l y a k ( 1 9 9 2 ) 的修正障碍函数算法及b e r t s e k a s ( 1 9 8 2 ) 的增广l a g r a n g e 函数算法是这类算法的特例基于p o l y a k ( 1 9 8 8 ) 求解极大极小问题的光滑函数方法，第 2 章还构造了一个求解不等式约束非线性规划问题的对偶算法这个对偶算法的形式比 较简单并且不需要考虑初始点的可行性第2 章对这一对偶算法的收敛性进行了精细证 盔重型王盔堂堡圭堂垡丝窒：韭垡堡垡垡主塑二耋塑苎婆塑望堡受塞 明，对它所基于的势函数的h e s s e 阵的条件数作出了估计而且这一个对偶算法也属于 我们建立的这一类对偶算法 求解无约束极大极小问题的光滑化方法是一类颇受青睐的方法，如 l i ( 1 9 9 2 ，1 9 9 7 ) 1 3 4 】，删建立的凝聚函数法在工程计算中就很有效 z h a n g & t a n g ( 1 9 9 7 ) 例 对l i 的方法进行变形，基于b e r t s e k a s ( 1 9 8 2 ) 的罚函数构造了一个对偶算法它既是一 种光滑化方法，也是一种修正l a g r a n g e 函数方法虽然z h a “g & t a n g ( 1 9 9 7 ) 讨论了这 一方法的性质，但没有给出该方法的收敛性证明，也没有进行有效的数值实验第3 章给 出了这一对偶算法的精细的收敛性结果在j a c o b i 唯一性条件下，证明了罚参数存在一 阀值，当罚参数小于这一闽值时，对偶算法产生的序列局部收敛到问题的k u h n t u c k e r 解，并且给出了参数解的估计公式还分析了含参数的势函数的h e s s e 阵的条件数与罚 参数之间的关系，这有助于我们在进行效值实验时选取适当的罚参数 第2 ，3 章讨论的对偶算法的第2 步都需要精确地求解一无约束极小化同题，这在实 际计算中是很费时并且是很难实现的为此，第4 章建立了不需精确求解势函数的无约 束极小化问题的对偶算法，即，在实际计算中对该步进行修正的对偶算法我们证明了这 些修正的对偶算法仍然具有很好的收敛性质，即同前两章的对偶算法的收敛结果相同 第4 章还进一步构造了求解般约束非线性规划问题的对偶算法给出了这个对偶算法 的局部收敛性结果，并且估计了所构造的修正l a g r a n g e 函数的h e s s e 阵的条件数，表明 它是依赖于罚参数的 前三章建立的对偶算法的收敛性结果在理论上是很完善的。但在实际问题的计算中 它们是否有效，需要数值实验来证实第5 章分别对这些算法进行了大量的数值实验 数值实验表明了这些对偶算法是有效的，同时也验证了取得的某些理论结果是正确的 6 苎! 窒至箜壅塑塞垡些堕塑塑二壅型堡蔓鳖 一 2 不等式约束优化问题的一类对偶算法 这一章首先给出了一类求解不等式约束优化问题的对偶算法的理论框架；在 某些适当的条件下，建立了该类方法的局部收敛性定理然后基于个指数型修正 l a g r a a g e 函数建立了个具体的对偶算法，并目发现它是这类对偶方法的特例进一 步对这一对偶算法的收敛性进行了精细分析，并且又分析了该指数型修正l a g t a n g e 函数的h e s s e 阵的条件数与罚参数之间的关系 2 1 一类构造性对偶算法 在这一节，我们构造了一类求解不等式约束优化问题的对偶算法证明了在适当的条 件下，势函数的罚参数存在一个阀值，当罚参数小于这个阔值时，由这一类方法所产生的 序列局部收敛到问题的k u h n - t u c k e r 解，并且我们也建立了解的依赖于罚参数的误差上 界验证了p o l y a k ( 1 9 9 2 ) 的两种修正障碍函数算法与b e r t s e k a s ( 1 9 8 2 ) 的增广l a g r a n g e 函数算法都是这类算法的特例，同时也验证了第2 2 节将要介绍的对偶算法也是这类算 法的特例 2 1 1 引言 考虑如下的不等式约束优化问题 血“弛! 。、m 1 ) s t z q = $ | 9 ( z ) so ) ， 、7 其中f ：四h 厨，g ：聍1 - 一刀“均是二次连续可微函数求解这一问题的传统数 值方法有很多，如，f i a c c o m c c o r m i c k ( 1 9 6 8 ) 建立的序列无约束极小化方法，h a n ( 1 9 7 6 ，1 9 7 7 ) ) 建立的序列二次规划方法，b e r t s e k a s ( 1 9 8 2 ) 建立的乘子法，等等近年来 对求解这一问题的原始一对偶算法的研究已成为非线性规划领域的新的研究热点，有代 表性的如绪论所述，e 1 - b a k r y , t a p i a ，t s u c h i y a z h a n g ( 1 9 9 6 ) ，y a m a s h i t a ( 1 9 9 2 ，1 9 9 6 ， 1 9 9 z ) ，g a y , o v e r t o n w r i g h t ( 1 9 9 8 ) ，等等 通过对p o l y a k ( 1 9 9 2 ) 建立的修正障碍函数的研究，我们构造如下一类修正l a g r a n g e 函数 m 日( z ，”，t ) = ，( z ) + ：( 或( 嚣) ，让，t ) ，( 2 1 2 ) i = 1 其中t 0 是罚参数，西：皿皿皿 o ) - _ 肥是光滑函数本节将要讨论的对偶 算法的主要特点是它不需寻找问题( 2 1 1 ) 的初始可行点而这一点使得它在实际计算中 7 大连理工大学博士学位论文t 非线性优化中的一类对偶算法的理论研究 比可行方向法及其他需要初始可行点的方法具有更大的吸引力，这主要是因为寻找问题 ( 2 1 1 ) 的初始可行点在后者中往往占有很大的工作量第2 1 2 节给出后面章节中所需的 预备知识在第2 1 3 节中我们建立些适当的条件，并且发现在这些条件下，h ( x ，t ) 具有很好的性质第2 1 。4 节建立一类对偶算法及其相应的的局部收敛性理论第2 1 。5 节验证了p o l y a k ( 1 9 9 2 ) 的修正障碍函数法与b e r t s e l m s ( 1 9 8 2 ) 的增广l a g r a n g e 函数法 都是这类对偶算法的特例，并且发现将在第2 2 节中介绍的求解问题( 2 1 1 ) 的基于指数 型修正l a g r a n g e 函数而建立的对偶算法也是这类对偶算法的个特例， 2 1 2 预备知识 我们主要考虑问题( 2 1 1 ) 的局部极小点令三( z ，牡) = f ( x ) + 兰lu l g i ( x ) 表示这 一问题的l a g r a n g e 函数，b ( z ) = 矧肌( z ) = 0 ，i = 1 ，m ) 表示约柬函数在髫处的紧 指标集，矿= ( 矿，4 ) 表示问题( 2 。1 1 ) 的k u h n t u c k e r 对，并且矿满足如下条件t ( a ) 为方便起见，记日( ) = 1 ，r ( r m ) ； ( b ) k u h n - t u c k e r 条件在矿成立，即t v 。i ( x + ，牡) = 0 ，矿0 ， 让孙( 矿) = 0 ，g i ( x ) 0 ，i = 1 ，m ( c ) 严格互补松弛条件成立，邵： 珏； 0 ，i b ( x ) ； ( d ) v 鲰( 。+ ) l i b ( x + ) ) 是组线性无关的向量； ( e ) 对于任意满足v g ( x 4 ) t y = 0 ，i b ( x + ) 的y 0 ，存在常数a o 0 ，使得 y t v ：l ( x + ，u ) a o ir y l l 2 成立 下面的引理出自b e r t s e k a s ( 1 9 8 2 ) ，该引理在以后耍建立的对偶算法中起着熏要作 用 引理2 1 1 令a 是皿叩上的对称矩阵，q 是四”上的半正定矩阵假如对任意满 足。t 日茁= 0 的。0 ，总有x t a x 0 成立，则存在常数e 0 与p 0 ，使得对任意的 c i ，成立着 户( a + c q ) z 1 i z f l 2 ，v z 四。 下面引入一些以后论述中要用到的符号： v 亘( z ) = ( v 9 ，( 。) ，v 办( 。) ) ，珊( z ) = ( v 褂z ( 。) ，v 孙) 8 第2 章 丕堇壅塑塞垡些坚堕堕二耋型堡苎鳖一 矿 a i ( 口，u ，t ) a ( z ，让，t ) s ( x + ，e ) 四2 盥m + ( ：，：) t 舻，面= ( 钍i ，牡：) r 皿7 ， 蒜( 蹴现待h - j m ，t 0 ( a 1 ( 茹，u ，t ) ，a 。( 。，u ，t ) ) t 况“，u + = d i a g l _ 0 ，t o ； ( a 6 ) l 象( o ，b ，t ) i m ( 其中m 0 是常数) ，b 0 ，t o ； ( a 7 ) 存在t o 0 ，使得对任意的o 0 ，使得当i t l ( 0 ，旬时，v ：日( 矿，t + ，t ) 是严格正定矩阵 证明：计算得 m 7 v ：酢，u 一= v 2 m ) + 善嵩湎川) 铲咖) + + c g g , ( 坐x ) o g 一, ( x ) ( m ( z ) m ，t ) v 玑( 茁) v g , ( z ) t 、，、山，仙l ，。，l 、山，、山， 于是 v ：。日( 卫+ ，u + ，t ) = v ：工( 茹。，牡+ ) + ，7 ( f t l ) v 口( z + ) v g ( x + ) r 根据条件( e ) 与引理2 1 1 ，易知存在 0 ，使得当 t i ( o ，旬时，v ：胃( 矿，u + ，t ) 是严格 正定的口 注2 1 1 由日( z ，u ，t ) 的性质。我们可知当i t 充分小时，。是日( z ，u ，t ) 的