（运筹学与控制论专业论文）求解非线性优化问题非线性lagrange方法探讨.pdf

大连理工大学硕士学位论文 摘要 非线性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 第l 章介绍了惩罚函数法的基础知识惩罚函数法根据对惩罚对象的不同要求分 为外罚函数法和内罚函数法，我们通过简单的例子阐明了两种罚函数的基本思想由于 内罚函数法不能处理等式约束问题，因此，我们在推广f r i s h 函数的时候，对等式约束 部分，采用的是外罚函数法 2 第2 章介绍了乘子法的基本思想严格来说，乘子法是惩罚函数法的一个分支虽 然不能通过求解所构造的无约束问题的最优解而直接得到原来约束问题的最优解，但是 当惩罚参数f 小到一定量后，调节参数“和元使之分别趋于 和彳，就能得到约束问题 的最优解我们推广的f r i s h 函数，正是基于这一理论对等式约束部分进行的处理 3 第3 章建立了推广f f i s h 函数的理论框架首先给出了若干假设条件以保证该非线 性l a g r a n g e 算法的收敛性，这些条件对发展其相应的对偶理论是必要的收敛定理表 明：当惩罚参数小于某一阈值时，基于该函数的对偶算法具有局部收敛性质然后，基 于该函数，建立了相应的对偶算法 关键词：非线性l a g r a n g e 函数；惩罚函数法；乘子法；对偶算法 求解非线性优化问题非线性l a g r a n g e 方法探讨 t h ed i s c u s s i o no fn o n l i n e a rl a g r a n g em e t h o d sf o rs o l v i n g n 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 a b s t r a c t n o n l i n e a rl a g r a n g ef u n c t i o n sa r ev a r i e so fc l a s s i c a ll a g r a n g i a n s ，i nw h i c ht h em u l t i p l i e r v e c t o r so rc o n s t r a i n tf u n c t i o n sa r ei n v o l v e di nn o n l i n e a rw a y s t h ed u a lm e t h o d sa r e d e v e l o p e df o rs o l v i n go p t i m i z a t i o np r o b l e m sb a s e do nn o n l i n e a rl a g r a n g i a n s ，w h i c hi sc a l l e d n o n l i n e a rl a g r a n g em e t h o d s n o n l i n e a rl a g r a n g em e t h o d sp l a ya l li m p o r t a n tr o l ei ns o l v i n g 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 a st h en o n l i n e a rl a g r a n g i a n sc a l lb eu s e dt od e v e l o pd u a l a l g o r i t h m sf o rn o n l i n e a rp r o g r a m m i n g , w h i c hr e q u i r en or e s t r i c t i o n so nt h ef e a s i b i l i t yo f p r i m a lv a r i a b l e s t h i sd i s s e r t a t i o ni sd e v o t e dt ot h ed i s c u s s i o no fak i n do fl a g r a n g ef u n c t i o n f o rs o l v i n gn o n l i n e a rp r o g r a m m i n gw i t hb o t hi n e q u a l i t yc o n s t r a i n t sa n de q u a l i t yc o n s t r a i n t s b a s e do ni t , d u a la l g o r i t h mi sd e v e l o p e d n em a i nc o n t e n t si n t h i sd i s s e r t a t i o nm a yb e s u m m a r i z e da sf o l l o w s ： 1 c h a p t e r li n t r o d u c e st h eb a s i ck n o w l e d g eo fp e n a l t yf u n c t i o nm e t h o d s p e n a l t y f u n c t i o nm e t h o d si n c l u d e o u t s i d ep e n a l t yf u n c t i o nm e t h o d sa n di n s i d ep e n a l t yf u n c t i o n m e t h o d s ，d e p e n d i n go nt h ed i f f e r e n tr e q u i r e m e n tf o rt h ep e n a l t yo b j e c t s w ec h o o s et h e o u t s i d ep e n a l t yf u n c t i o nm e t h o d sf o rt h ee q u a l i t yc o n s t r a i n t sw h e nw eg e n e r a l i z et h ef r i s h f u n c t i o n ，b e c a u s et h ei n s i d ep e n a l t yf u n c t i o nm e t h o d sc a l l td e a lw i t hi t 2 c h a p t e r2i n t r o d u c e st h eb a s i ct h o u g h t so fm u l t i p l i e rv e c t o r sm e t h o d s s t r i c t l y s p e a k i n g ，t h em u l t i p l i e rv e c t o r sm e t h o d si sa ne m b r a n c h m e n to fp e n a l t yf u n c t i o nm e t h o d s a l t h o u g hw ec a l l tg e tt h eo p t i m a ls o l u t i o no ft h ep r i m a r yc o n s t r a i n t sp r o b l e mb ys o l v i n gt h e n oc o n s t r a i n t sf u n c t i o nw ec o n s t r u c t ，b u tw h e nt h ep e n a l t yp a r a m e t e r c ri ss m a l le n o u g h ， a d j u s tt h ep a r a m e t e r s 以 a n d 五 s ot h a tt h e yc a nc l o s et o ”a n d r e s p e c t i v e l y ，t h e nw e c a ng e tt h eo p t i m a ls o l u t i o no ft h ec o n s t r a i n t sp r o b l e m t h ef r i s hf u n c t i o nw eg e n e r a l i z ei s b a s e do nt h i st h e o r yt od e a lw i t ht h ee q u a l i t yc o n s t r a i n t s 3 c h a p t e r3e s t a b l i s h e sat h e o r yf r a m e w o r kf o rt h eg e n e r a l i z e df r i s hf u n c t i o n f i r s t l y ，a s e to fa s s u m p t i o n sa r ep r o p o s e dt og u a r a n t e et h ec o n v e r g e n c eo ft h en o n l i n e a rl a g r a n g i a n a l g o r i t h m sa sw e l la st od e v e l o pt h ed u a la p p r o a c h e s t h ec o n v e r g e n c et h e o r e ms h o w st h a t t h ed u a la l g o r i t h mb a s e do nt h el a g r a n g i a ni sl o c a l l yc o n v e r g e n tw h e nt h ep e n a l t yp a r a m e t e r i ss m a l l e rt h a nat h r e s h o l d t h e n ，t h ed u a la l g o r i t h ma s s o c i a t e dw i t ht h i sk i n do fn o n l i n e a r l a g r a n g i a ni sd e v e l o p e d 一i i 大连理工大学硕士学位论文 k e yw o r d s ：n o n l i n e a rl a g r a n g i a n s ；t h ep e n a l t yf u n c t i o nm e t h o d s ；t h em u l t i p l i e rv e c t o r s m e t h o d s ；d u a la l g o r i t h m s 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：二茁l 瞳缉上k 鲍盈上也翅垃拉血么够毖勺善三靴 作者签名： 司拖肄 日期：二年上月二么日 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：j 拦璺型巫篷止西匕凼荡氇蚯望垃丝够纽雩丝立翌扯 作者签名：址超圣日期：叁监年丝月幺日 导师签名： ! 妊彳盈 日期： 2 笾左年生月上否日 大连理工大学硕士研究生学位论文 引言 考虑非线性优化问题 m i ni m i z e f o ( x ) ， s u b j e c tt oz ( z ) 0 ，i i = l ，”) ， ( o 1 ) 啊( x ) = 0 ，f e = 所+ 1 ，d ， 其中石r “，z ( z ) ：r ”哼r ，= 0 9 0 m 0 9 m ，啊( 功：r ”_ r l , f = m + l ，是实值函数问题 ( 0 1 ) 经典的( 线性) l a g r a n g e 函数定义为 j ， l ( x ，材) = f o ( x ) - 扰，f a x ) - 甜，囊( 工) ， l f f i li f f i m + l 它在描述( o 1 ) 最优性条件及设计求解算法中起着重要作用对于凸规划，根据经典 l a g r a n g e 函数可以建立鞍点理论，也可以发展基于对于某一 求解m i n l ( x ，甜。) 的对偶 算法对于非凸非线性规划，l ( x , u ) 通常是非凸的，即使当u 5 趋于u 及x 在工的邻域 内，其中( 石，“) 是( 0 1 ) 的k u h n - t u c k e r 点，因而在数值实验上面临着一些困难 无论在线性规划还是非线性规划中，惩罚函数【h 1 和障碍函数对算法的研究均起着 重要作用众所周知，内点法跟对数障碍函数密切相关，见y e ( 1 9 9 8 ) 5 1 对于凸规划，障 碍函数在发展内点算法中扮演中心的角色，见n e s t e r o v & n e m i r o v s k i i ( t 9 9 4 ) t 6 1 国内外学 者对障碍函数都作了大量的研究，给出了有效的算法并取得了许多收敛性结果 惩罚函数和障碍函数法旨在将约束优化问题转化为序列无约束优化问题，该方法的 研究可追溯到c o u r a n t ( 1 9 4 3 ) 1 7 1 ，f r i s h ( 1 9 9 5 ) 引，c a r r o l l ( 1 9 6 1 ) t 9 1 等学者的工作关于研究惩 罚函数和障碍函数法的代表性工作可参阅 f i a e c o 和m c c o r m i c k ( 1 9 6 8 ) t l o 】， m c c o r m i c k ( 1 9 7 1 ) 1 l l 】等人的工作然而，早期的惩罚函数法或障碍函数法，要求惩罚参数 趋于无穷大或零，这在数值计算中面临着诸多困难为克服上述方法的不 足，h e s t e n e s ( 1 9 6 9 ) t 1 2 1 与p o w e l l ( 1 9 6 9 ) t 1 3 1 分别各自独立地提出了近似增广l a g r a n g e 函数 ，( z ，五) = f 0 ( x ) + 五7 办( x ) + 等0 办 ) 1 1 2 ( c o ) 和 ， p ( x ，五，乡) = 兀o ) + 【乃( x ) + 嘭】2 盲l 来求解具有等式约束的非线性优化问题 求解非线性优化问题非线性t a g r a l i g e 方法的探讨 最初的乘子法是基于二次增广l a g r a n g e 函数( 形式最简单的修正l a g r a n g e 函数) 建立的，这一方法的优点在于，它克服了早期惩罚函数的病态问题以及收敛速度较慢等 弱点h a a r h o f f & b u y s ( 1 9 7 0 ) t m l 进一步研究了求解一般的非线性规划问题的二次乘子法关 于应用增广l a g r a n g e 函数研究l a g r a n g e 乘子迭代的一些有意义的早期工作，可参见 m i e l e 等人的工作然而，这几位学者并没有分析近似增广l a g r a n g e 法的收敛 性p o l 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 r 把h e s t e n s ，p o w e l l 和 h a r d o f f & b u y s 的思想又进一步推广，应用于不等式约束优化问题，得到一般约束优化问 题的近似增广l a g r a n g e 法的理论b e r t s e k a s ( 1 9 7 5 ) 讨论了二次乘子法收敛速率，并建立 了二次乘子法优于标准的二次惩罚函数法r u p p 提出了乘子法的收敛条件而不必考虑 初始乘子的选择b e r t s e k a s 1 5 】针对凸规划问题，提出了惩罚函数法产生一个最优l a g r a n g e 乘子的必要且充分条性条件关于近似增广l a g r a n g e 法的详细研究工作可参阅 b e r t s e k a s 1 6 a 7 及b e t t s 1 s , 1 9 d i p i l l o 和g r i p p o ( 1 9 7 9 ) 引入了一类求解具有等式约束的优化问题的增广l a g r a n g e 函数 f o ，c ) = 石( z ) + r c l l h 0 ) ， 其中e 是经典l a g r a n g e 函数关于x 的梯度，并给出了矩阵m ( x ) 的几个选择，于1 9 8 2 年 的论文中，通过引入松弛变量及对矩阵m ( x ) 的特殊选择，将其应用于求解具有不等式 约束的优化问题1 9 8 7 年，c a r o t e n u t o 和r a i c o n u 将该方法用于求解极小化具有双线性约 束的二次函数，并用较弱的假设条件证得了相似的结果 g l a d ( 1 9 7 9 ) 研究了在l a g r a n g e 函数 p ( ，万，c ) = 石( x ) + 7 办( x ) + 导办( _ x ) 7 办o ) + 9 - 篆 m a x o ，一饼( x ) + 4 ) ) 2 一寺万7 万 o ) 二 -j-i二。 对l a g r a n g e 乘子的不同更新的收敛性质 在1 9 8 0 年，b o g g s & t o l l e 引入了一类新的乘子法，发展了对偶理论，构造了一类新的 惩罚函数并建立了精确罚和乘子法的联系这一类乘子法与d i p i l l o ( 1 9 7 9 ) 提出的相关 由于非线性l a g r a n g e 函数可用于发展求解非线性规划问题的对偶算法，该算法对原 始变量的可行性没有限制，最近几年，许多学者对这一课题的研究做出了重要的贡献 随着人们对修正l a g r a n g e 函数方法的深入研究，该方法的优越性逐渐显示出来，尤其是 函数的形式也由复杂趋向于简单 大连理工大学硕士研究生学位论文 对于凸规划，p o l y a k & t e b o u l l e ( 1 9 9 7 ) 讨论了一类具有如下形式的l a g r a n g e 函数 g ( x ，”，) = 厶( x ) 一u , v ( - , f , ( x ) ) ， ( o 2 ) 其中a 0 是惩罚参数，是二次连续可微函数他们发展了n o n l i n e a rr e s c a l i n g ( n r ) 算 法在适当的假设条件下，证明了由n r 算法产生的对偶解序列全局收敛到最优乘子，而 相应的原始解序列在e r g o d i c 意义下收敛到近似原始最优解此外，a u s l e n d e r ，c o m i n e t t i 和h a d d o u ( 1 9 9 7 ) ，以及b e n t a l 和z i b u l e v s k y ( 1 9 9 7 ) 研究了一类l a g r a n g e 函数并获 得了许多收敛性结果基于l o g - s i g m o i d 函数，p o l y a k ( 2 0 0 2 ) 发展了n r 算法并建立了 收敛速度特别地，在标准的二阶最优性条件下，n r 算法具有q 一线性收敛速度 进一步地，对于具有不等式约束的凸规划问题，p o l y a k & g r i v a ( 2 0 0 4 ) 提出了原始一 对偶n o n l i n e a rr e s c a l i n g ( p d n r ) 算法，证明了p d n r 算法具有全局收敛性，并估计了原始解 序列和对偶解序列的误差界特别地，在标准的二阶最优性条件下，误差界线性收敛到 0 g r i v a & p o l y a k ( 2 0 0 5 ) 发展了具有动态s c a l i n g 参数更新的原始一对偶n o n l i n e a rr e s e a l i n g 算法基于函数( o 1 ) ，证明了该算法的全局收敛性，并且在标准的二阶最优性条件及 h e s s e 阵v 2 z ( x ) ，f = o ，朋满足l i p s c h i t z 条件下，具有1 5 q 一超线性收敛速率除了 r a p o l y a k 同其合作者的工作外，a u s l e n d e r ，c o m i n e t t i 和h a d d o u ( 1 9 9 7 ) 以及b e n t a l 和z i b u l e v s k y ( 1 9 9 7 ) 研究了其他的非线性l a g r a n g e 函数并获得了有意义的收敛性结果 对于非凸规划，m a n g a s a r i a n 引入了一类非线性l a g r a n g e 函数来求解具有不等式约 束的优化问题，导致了无约束鞍点问题c h a r a l a m b o u s ( 1 9 9 7 ) 给出了极小p 一函数 b e r t s e k a s ( 1 9 8 2 ) 提出了幂l a g r a n g e 函数： ，( x ，七) = 五( x ) 一鸬【1 一p 一引】， p o l y a k ( 1 9 9 2 ) 1 2 0 1 给出了两个修正的障碍函数，即修正的f r i s h 函数 r朋1 即心f ) - 烈功叫善刈n ( 沙) + 1 n 幽位， 【4 - 0 0 ， x 舞i n t q ， 和修正的c a r r o l l 函数 r朋1 刚：j 胁) - 善蚶( 手他) + 1 ) 一】艇m m ， 【+ 0 0 ， z i n t f 2 。， 其中t 0 是惩罚参数，q ，= ( x i1 + ，( x ) o ，i = 1 ，1 ) ， 求解非线性优化问题非线性l a g r a n g e 方法的探讨 l i ( 1 9 9 5 ) 构造了p 一幂l a g r a n g e 函数 l 一 三p ( x ，“) = 【兀( x ) 】p 一甜， 【z ( x ) 】p 一 ) ， j 覃i 和部分p 一幂l a g r a n g e 函数 l l p ( 工，甜) = f o ( x ) 一甜， l f ( x ) 】，一”) ， i - ! 其中p 0 是惩罚参数，假定z ( x ) = ，( z ) 一6 f 及z ( x ) ( f = 1 ，m ) 取正值且 色 o ( i = 1 ，册) l i ( 1 9 9 5 ) 证明了，当p 足够大时，所构造等价问题的扰动函数在b 附 近是局部凸的，且当应用原始一对偶方法时，能够保证对偶间隙为0 后来，x u ( 1 9 9 7 ) 对部分p 幂l a g r a n g e 函数得到相似的结果，也就是，进一步地，p 一幂l a g r a n g e 函数 可用于保证整数规划问题成功的对偶研究 针对具有等式约束和不等式约束的优化问题，g o l d f a r be ta 1 ( 1 9 9 9 ) 提出了一个修 正的障碍一增广l a g r a n g e 函数法 p o l y a k ( 2 0 0 1 ) 又构造了l o g s i g m o i d 函数 f ( x ，材，七) = 厶( 工) 一u i 2 l n 2 2 1 n ( 1 仃舭) 】， i - - i 来求解具有不等式约束的优化问题 贺素香( 2 0 0 4 ) 等给出了一个势函数 f，一上 f ( x , u , t ) ： ( 工) + i ，i 善堋一z ( 工) ) i , i l 】，x i n t s ， 【+ o o ， 9x芒ints， 其中f 0 为惩罚参数，s = x l l 一，( z ) o ，i = l ，m ) 此外，在通常的二阶充分性条件下，j e a n p i e r r ed u s s a u l t ( 2 0 0 4 ) 分析了形如( 0 2 ) 的非线性l a g r a n g e 函数类的渐近性，并获得了超线性收敛结果( 阶4 3 ) 那些抽象的 惩罚函数包含了由r p o l y a k 引入的所谓的修正障碍函数及c o m i n e t t ia n dd u s s a u l t ( 1 9 9 4 ) 等学者提出的指数惩罚函数 对于无约束极小一极大优化问题 m ，i nm i s ，a 5 。xf , ( x )工 i s ，s j h c h a r a l a m b o u s ( 1 9 7 9 ) 提出了p 一阶函数，该函数具有一些好的性质，基于该函数的算法 具有有效的收敛性但是，p 一阶函数的表达式较复杂，不利于计算p o l y a k ( 1 9 9 8 ) 建立了 大连理工大学硕士研究生学位论文 一个形式简单的光滑函数 e p ( 础) = 亡叩州”， ，i = 1 其中p 0 是惩罚参数，并证明了基于该函数的算法具有很好的收敛性质 最近，r p o l y a k 提出了n r 法来求解离散的极小一极大问题，利用函数l i f ，将原始的极小 一极大问题转化为一个等价问题，该变换用一个正的s e a l i n g 参数或由正的s c a l i n g 参数向 量来衡量对于等价问题，经典的l a g r a n g e 函数是n r 法的主要工具所提出的非线性 l a g r a n g e 函数如下： l ( x ，z ，) = y ( 一z ( z ) ) ， i s l im 其中旯s 。= 五尺：，l 乃= 1 ) 它避免了病态，与此同时也改善了收敛速率特别地，此 l i = 1 在标准的二阶最优性条件下，当s c a l i n g 参数固定且足够小时，n r 法具有q - 线性收敛速 率 由于非线性l a g r a n g e 函数可用于发展求解非线性规划问题的对偶算法，该算法对原 始变量的可行性没有限制基于非线性l a g r a n g e 函数f ( x ，甜，f ) 的对偶算法可叙述如下： d 一算法 s t e p1 给定t o 0 ，u o 0 ，置k = 0 ； s t e p 2 求解( 近似) m i nf b ，材k , t ) ，得到它的( 近似) 解x ； s t e p3 如果x 满足原问题的终止准则，停止；否则，转s t e p4 1 s t e p4 更新l a g r a n g e 乘子2 及参数f 甜“1 = “x , k 砧， ) ，t k + t 满足f m f ； s t e p5 置k = k - i - l ，返回s t e p2 在上述的概念性算法中，需选择终止准则甜胛是由函数f ( x ，u ，t ) 决定的映射且具有 下述性质： 材川= u m w ( x k , “k ，t ) 0 如果甜0 ， ( o 3 ) 这保证了由d 算法产生的迭代点的对偶可行性 求解非线性优化问题非线性l a g r a l l g e 方法的探讨 本文主要考虑既有不等式约束又有等式约束的优化问题 m i n i m i z e f o ( x ) s u b j e c tt oz ( x ) 0 ，i i = 1 ，删) ，( n l p ) ，( x ) = 0 ，f e = 朋+ 1 ，) 其中x r ”，z ( 石) ：r ”一r 1 ，f = o ，是实值函数 ，订， j 己l ( x ，“，名) = f o ( x ) - 材，z ( x ) 一以z ( 石) 为问题( n l p ) 的经典l a g r a n g e 函数及 i-!l=m+l i ( x ) = 4 z ( z ) = o ，f = l ，m ) 为起作用的约束指标集 本文讨论的非线性l a g r a n g e 函数满足下述三条特性： ( 1 ) 当z ( i = o ，) 是二次可微函数时，非线性l a g r a n g e 函数是二次可微的； ( 2 ) 存在一阈值，始得当惩罚参数小于( 或大于) 该阈值且”趋于”，五趋于刀时， 非线性l a g r a n g e 函数在x 附近是局部凸的； ( 3 ) 性质( o 3 ) 成立 本文所取得的主要结果可概括如下：将解决只含有不等式约束优化问题的修正的 f r i s h 函数结合乘子法，推广至解决既含有不等式约束又含有等式约束的优化问题，并 且推广后的函数关于乘子是线性的分析了推广后的函数性质，证明了该算法的收敛性 收敛定理表明：当惩罚参数小于某一阈值时，推广后的f r i s h 函数的对偶算法具有局部 收敛性质 我们给出一些预备知识以方便本文的研究 首先，我们列出如下的假设条件，这些条件在后续的讨论中会用到 ( a ) ，( x ) ，( 江o ，) 二次连续可微； ( b ) 为方便叙述，假设i ( x ) = i ：，( x ) = 0 ，i = l ，m ) = l ，r ) ； ( c ) 设( x ，”。，力) r “x r ”x r 卜”满足k u h n t u c k e r 条件： v ，三( x ，“，z ) = 0 ；u ? o ，f = 1 , 2 ，聊；z ( x ) “? = o ，i = 1 , 2 ，脚； ( d ) 严格互补松弛条件成立，即甜0 ，i i ( x ) ； ( e ) o ) i f i ( x ) ue ) 是线性无关的向量集； ( f ) ( v ：三( x 。，u * 9 z ) y ，y ) ( 少，y ) ，v y 0 ：v f , ( x ) 7 y = 0 ； 其中 0 是一常数，i i ( x ) ue 其次，我们给出本文所用到的一些基本定理及命题 大连理工大学硕士研究生学位论文 定理0 1 ( 第二隐函数定理) 蚴令s5r ”+ ”是一开集，叉er ”是一紧致集，h ：s 专r ”是 定义在s 上的函数且满足对于某一p 0 ，h c p 假设v 。h ( x ，y ) 存在且在s 上是连续的 设向量y r ”满足( x ，y ) s ，厅( x ，y ) = 0 ，且对所有的x x ，矩阵v ，h ( x ，y ) 是非奇异的， 则存在g o ，万 0 ，以及函数矽：s ( x ；占) 一s ( y ；万) 满足在s ( x ；s ) 上c ，对任意 x x ，y = ( x ) ，以及对任意工s ( x ；c ) ，b i g ，声( x ) 】= 0 函数在下述意义下是唯一的： 女口果x s ( x ；s ) ，y s ( y ；万) ，且h ( x ，y ) = 0 ，贝u y = 矽( x ) 进一步地，如果p l ，对于任意工s ( x ；f ) ， v 妒( 工) = - v ，h x ，矿( x ) 】【v ，h x ，矽( x ) 】一1 定理0 2 ( f i n s l e r 定理) 【1 2 1 令b ，c r “且c 0 ，则对于满足x7 c x = 0 的0 x r “使 得z r b x 0 当且仅当存在满足对于任意，b + 心是正定的 定理0 3 ( i ) e b r e u 定理) 【1 2 1 令a r ”“与b r ，则对于满足a x = 0 的0 z r ”使得 x 7 出 0 当且仅当存在使得对任意，b + 7 彳是正定的 下述命题是d e b r e u 定理的一种修正形式 命题o 1 【1 6 1 令么是”刀对称阵，b 是一，玎矩阵且u = d i a g ( u r 7 哼r 7 满足 ”= ( 甜l ，“，) o rb y = 0j a ，名 0 则存在足够小的t o 0 及正常数( o ，旯) ，使得当f ( 0 ，t o ) 时， ，坛r ” 最后，我们引入下列符号： f ( x ) = u ( x ) ，z ( x ) ) 7 ， 工，( x ) = ( 石( x ) ，( x ) ) 1 ， 五，- ，) ( x ) = ( ，+ 。( 工) ，厶( x ) ) r ，正，一，) ( x ) = ( 厶+ 。( x ) ，z ( x ) ) r ， 夥( x ) = ( w ( x ) ，w ( 功) ，瓢，) ( z ) = ( w ( x ) ，( z ) ) ， w ) ( x ) = ( w + ，( x ) ，既( x ”，瓢砌) ( 工) = ( 既+ 。( x ) ，( z ) ) ， z ，= ( 掰j ，：) 7 r ”，z = ( 乞+ i ，) 7 r 卜”， ”0 ) = ( “：，卅：) r r 7 ，甜乙，) ( 甜- l ，甜：) 7 r ”， s ( x ，s ) = x r ”x m x 1 0 s ) ，s ( 甜，占) = ( 甜r m u w 2 d * 05 占) ， s ( z ，s ) = 旯r 卜m 一删ss ) ，删= 。= 嘶阶x j 求解非线性优化问题非线性l a g r a n g e 方法的探讨 s ( z ，占) = s ( 工，) s ( 甜，s ) s ( z ，占) ，z = ( 工，甜，z ) ， q = ( 卅z ( z ) o ，= 1 ，所) ， 8 q ，= 工i l + 詈z ( 工) 。，f = l ，所) 大连理工大学硕士研究生学位论文 1 惩罚函数法 为了方便我们理解和推广f r i s h 函数，我们先将推广该函数的依据做一介绍，主要 是惩罚函数法和乘子法我们先来介绍一下惩罚函数法的基本内容 1 1 外惩罚函数法 最早的罚函数( p e n a l t yf u n c t i o n ) 法是由c o u r a n t 在1 9 4 3 年提出来的，其基本思想 是：对不满足约束条件的点进行惩罚，通过求解多个罚函数的极小得到约束问题的最优 解 先给一个简单的例子来阐明罚函数法的基本思想考虑一个变量，仅有一个不等式 约束的问题： m i n f o ( x ) = x 2 ， ( 1 1 1 ) s j z ( 工) = 一x 一1 0 ， 其可行域为( 埘 - l 】，最优解为x = 一1 现将问题( 1 1 1 ) 转化为无约束问题，也就是说，希望构造相应的无约束问题，而 该无约束问题的解恰好是约束问题的最优解从直观上看，要做到这一点就必须增大在 非可行域处的目标函数值，即对非可行域处的目标函数加以惩罚 现构造惩罚函数，一种较为简单而又能保证函数具有连续的偏导数的方法为： f f o ( x ) ，z ( x ) o ，f x 2 , - - x l 0 ， 烈五2 汹吲1 删2 胎f 1 ) 0 时，有x ( ，) _ x ，比较( 1 2 8 ) 式和( 1 2 1 0 ) 式，显然由( 1 2 1 0 ) 式得到的 x ( ，) 专工的速度比( 1 2 8 ) 由式得到的x ( r ) 专x 速度快这个结论对于一般情况也成立， 因此常常选用( 1 2 1 0 ) 式作为障碍函数 下面给出具体的算法： 算法1 2 1 ( 障碍函数法) s t e p1 选择序列以) ， 递减趋于0 ，取初始点x o d o ， 这里 d o = 州z ( z ) 0 , i i ) ， 置精度要求占，置k = 1 s t e p2 以x ( 卜1 为初始点，求解无约束问题 m i n p ( x ，r k ) = f o ( 工) + r k b ( x ) ， 其中 即) 2 荟志私( 功一i f f i = | h 【胁) 】， 得到最优解x ( s t e p 3 r k b ( x ( k ) ) 占，则停止计算，否则，置k = k + l ，转s t e p 2 使用算法1 2 1 求解约束问题时，应注意以下几个问题： ( 1 ) d o 非空，即可行域的内部非空； ( 2 ) 在算法第二步求解无约束问题时作一维搜索过程中，要保证得到的点不出约束的边 界这是因为由( 1 2 3 ) 式确定的b ( x ) 在z ( 力= 0 处函数无定义，而由( 1 2 4 ) 式 确定的b ( x ) 在，( x ) 0 处无定义； ( 3 ) 由于无约束问题的最优解x ”在可行域的内部，因此在求解无约束问题中，其终止准 则可采用通常的终止准则 内罚函数虽然克服了外罚函数的缺点，但其缺点是不能处理等式约束问题 求解非线性优化问题非线性l a g r a n g e 方法的探讨 2 乘子法 严格来说乘子法是属于罚函数方法的一个分支，惩罚函数法的优点在于将约束问 题转化为无约束问题，可用求解无约束问题的算法来求解约束问题的最优解但罚函数 的主要缺点在于需要惩罚因子充分小，才能得到约束问题的极小点，这会使罚函数的 h e s s e 矩阵变的病态，给无约束问题的求解带来了困难，h e s t e n e s 和p o w e l l 于1 9 6 4 年各 自独立地提出了乘子法本节主要介绍乘子法的基本内容，为我们下一步推广f r i s h 函数 做准备 2 1改进惩罚函数法的设想 考虑一个简单的等式约束问题 m i n 五( x ) = f o ( x , ，屯) ， ( 2 1 1 ) s t z ( x ) = f l ( x l ，屯) = 0 ， 其罚函数问题为 1 m i n p ( x ，t y ) = 厶( x ) + 圭石2 ( x ) ， ( 2 1 2 ) z d 设x 。是( 2 1 1 ) 的全局解，考察x 是否为无约束问题( 2 1 2 ) 的全局解( 局部解) p ( x ，盯) 在z 的梯度为 v ，p ( x ，仃) = 可( 工) + 二z ( x ) 弓z ( x )