（应用数学专业论文）广义最小信息熵问题与其对偶理论及其求解方法.pdf

摘要 非线性规划是运筹学数学理论中特别重要而又活跃的一个分支，可认为它是有限维 最优化经典理论的再创造，其特征主要在于：所研究的最优化问题允许复杂的约束，对 最优性、对偶性诸方面进行深入的分析，并强调进行理论概括和提出可行的算法。随着 现代计算机技术的日趋发展，非线性规划正越来越多地运用于最优设计、管理科学、系 统识别、数学物理变分问题等方面，并由此推动非线性规划的进一步发展。 线性规划中优美的对偶性理论，鼓励很多学者把对偶性概念推广到非线性规划问题。 在初期，他们发现可以将某些非线性规划表述为一个相应的对偶规划，且有少量相似于 线性规划的结果，但如果希望得到有意义的结果，只能考虑凸规划。六十年代后期，凸规 划更完全的对偶理论出现了，其中一种方式是基于f e n c h e l 引进的共轭函数概念，这些 后来在r o c k a f e l l a x 的一系列著作中得以发展完善。 在文 6 】中，r o c k a f e l l a r 导出了f e n c h e l 对偶定理，然而有许多凸规划问题直接使 用f e n c h e l 对偶定理很难用显式表示其对偶，有的问题甚至不能直接使用f e n c h e l 对偶定 理。朱德通在文f 8 j 中导出广义的f e n c h e l 对偶定理，并将此定理成功地应用于带约束的 最小区别信息量问题( 简称m d i 问题) 本文讨论比m d i 问题更普遍的带有二次约束和 熵密度约束的广义熵密度规划问题，这两类问题在信息论、统计力学、对策论和保险业 中有着广泛的应用。基于凸规划知识和广义的f e n c h e l 定理，作者推导出这两类问题的 凸对偶规划。同时，发现由非线性规划中l a g r a n g e 对偶可以获得这两类问题的l a g r a n g e 对偶规划，且推导过程中没有涉及很深的数学知识，使得应用更为广泛 通常，我们求出规划问题的对偶形式是希望将不易求解的原问题转化为易于求解的 对偶问题，在分别得到这两类问题的对偶形式后，发现其形式简单，只带有非负约束和线 性约束。本文针对更为一般的带线性不等式约束的优化问题提出弧线路径信赖域算法。 信赖域方法是近年来日益受到关注的一种新的保证算法整体收敛性的逼近方法，信赖域 方法的基本步骤是首先指定一个信赖域半径，然后用带约束的二次模型来确定搜索方向 与步长大小。朱德通在文f 9 1 中将最优路径和修正梯度路径与非单调信赖域方法相结合 讨论无约束优化问题，且文【3 中用信赖域方法解无约束优化问题取f 2 范数形成了形式 简单的近似信赖域路径，此类思想启发作者用弧线路径来解决约束优化问题。考虑到在 一般的信赖域方法中，当目标函数沿该搜索方向的实际下降量和预计下降量拟合得比较 好时，则由该搜索方向得到新的迭代点并调整信赖域半径。否则，缩小信赖域半径并重 新求解搜索方向，因此为求得一被接受的搜索方向往往需要多次求解信赖域子问题使得 计算量相当大。本文在求解线性不等式约束优化问题时，将近似信赖域路径与非单调信 赖域方法相结合，即在信赖域半径内沿近似信赖域路径得到一极小化二次模型的搜索方 向后采用回代法避免重复求解信赖域子问题，在此算法中当搜索方向不被接受时，就用 非单调线搜索技术得到接受步长，定义新的迭代点。这样大大提高了计算速度，而且为 了有更广泛的运用，在本文的实际算法中并不要求目标函数为凸函数。 本文共分为五章。第一章简述了非线性规划和对偶规划的一些基本概念以及一般非 线性规划问题的求解方法，作为研究的基础。第二章中基于广义的f e n c h e l 对偶定理以 及相应的k u h n t u c k e r 条件，导出带有二次约束和熵密度约束的广义熵密度问题的凸对 偶规划，强对偶定理以及相应的k u h n t u c k e r 条件。第三章在第二章的基础上，应用l a g r a n g e 对偶规翅的定义以及非线性规划的基础知识导出了这两类问题的l a g r u n g e 对偶 规划和完整的理论分析。第四章以这两类问题为背景，对更为普遍的线性不等式约束优 化问题提出了弧线路径信赖域算法，并给出计算结果。最后，第五章对本文的工作进行 了总结，提出了进一步的研究方向。 关键词：广义f e n c h e l 对偶定理；l a g r a n g e 对偶规划；熵密度问题； k u h u t u c k e r 条 件；信赖域方法；非单调技术；收敛性。 分类号：0 2 2 1 2 d u a lt h e o r ya n ds o l u t i o no f t h eg e n e r a l i z e dm i n i m u mi n f o r m a t i o ne n t r o p yp r o b l e m a b s t r a c t n o n l i n e a rp r o g r a m m i n gw h i c hi sc o n s i d e r e dt ob er e c r e a t i o no ft h ef i n i t ed i m e n s i o no d t i m i z a t i o nc l a s s i c a lt h e o r yi sav e r yi m p o r t a n ta n da c t i v eb r a n c ho fo p s e a r c h c h a r a c t e r i s t i co f n o n l i n e a rp r o g r a m m i n gl i e si n ：a l l o w a n c eo f c o m p l e xc o n s t r a i n t so i lt h eo p t i m i z a t i o ni ts t u d i e s d e e pa n a l y s i so fo p t i m a l i t ya n dd u a l i t y ，e m p h a s i so i ls u m m a r i z i n gt h e o r e ma n de s t a b l i s h m e n t o ff e a s i b l ea l g o r i t h mw i t ht h ed e v e l o p m e n to fn e wi n f o r m a t i c st e c h n o l o g y ，n o n l i n e a rp r o g r a m - m i n gi s m o r ea n dm o r ew i d e l yu s e di nt h er e s e a r c ho fo p t i m a ld e s i g n ，s c i e n t i f i c m a n a g e m e n t l s y s t e m a t i ci d e n t i f i c a t i o n ，p h v r m e a la n dm a t h e m a t i c a lv a r i a t i o n ，e t cw h i c hp r o m o t ei t s d e v e l o p m e n t e l e g a n td u a lt h e o r yi nl i n e a rp r o g r a m m i n gh a se n c o u r a g e dm a n yr e s e a r c h e r sa p p l y i n gd u a l c o n c e p ti ns o l v i n gn o n l i n e a rp r o g r a m m i n gp r o b l e m a tt h eb e g i n n i n go ft h e i rr e s e a r c h ，t h e y c o u l dt r a n s f o r ms o m en o n l i n e a r p r o g r a m m i n g i n t or e l e v a n td u a l ，s u c ht r a n s f o r m a t i o nm a d es o m e o u t c o m ea l m o s ts i m i l a rt ol i n e a rp r o g r a m m i n g b u ti ft h e yw a n t e d m e a n i n g f u lr e s u l t s ，t h e yh a d t oc o n s i d e rc o n v e xp r o g r a m m i n g i nt h el a t e6 0 s i n t e g r a t e dt h e o r yc a m eu p ，o n eo fi t sw a y s w a sb a s e do n c o n j u g a t e f u n c t i o nt h e o r yi n t r o d u c e db y f e n c h e l ，w h i c hr o c h a f e l l a rh a dd e v e l o p e d a n di m p r o v e di nas e r i e so fh i sb o o k s i n 【6 ，r o c k a f e l l a rh a dd e d u c e dt h ef e n c h e lt h e o r y ，b u ts o m en o n l i n e a rp r o g r a m m i n gc o u l d n o tg e tt h ed u a lb yf e n c h e lt h e o r yd i r e c t l ya n dd u a l t h e o r yc o u l dn o tb ea p p l i e di ns o l v i n gs o m e p r o b l e m ，z h uh a dd e d u c e dg e n e r a l i z e df e n c h e l sd u a l i t yt h e o r e mi n 【s l ，a n df u r t h e ra p p l i e di t t om i n i m u md i s c r i m i n a t i o ni n f o r m a t i o n ( m d i ) p r o b l e m m o r eg e n e r a lq u a d r a t i cc o n s t r a i n t s a n d e n t r o p yc o n s t r a i n so ft h ed e n s i t yp r o g r a m m i n gw i l lb ed e a l tw i t hi nt h i sa r t i c l e t h et w o p r o b l e m s a r ew i d e l ya p p l i e di ni n f o r m a t i o nt h e o r y , s t a t i s t i c a lm e c h a n i c s ，i n s u r a n c eb u s i n e s sa n d g a m et h e o r y i nt h ep r o g r e s so fd e d u c i n gt h ed u a lo ft h e s et w op r o b l e m su s i n gt h ek n o w l e d g e o fc o n v e xp r o g r a m m i n ga n dg e n e r a l i z e df e n c h e lt h e o r y ，y o uc a nf i n dl a 口a n g ed u a lo ft h et w o p r o g r a m m i n gb yl a g r a n g ed u a l i nn o n l i n e a rp r o g r a m m i n gi nt h i sa r t i c l e a sn o tm u c h p r o f o u n d m a t h e m a t i c a lt h e o r yh a si n v o l v e d ，i tc o u l db em u c hw i d e l ya p p l i e d ， n o r m a l l y , w et r yt og e tt h ed u a lf o r mo fm a t h e m a t i c a lp r o g r a m m i n gt oc h a n g ep r i m a r y p r o g r a m m i n g ，w h i c hi s d i f f i c u l tt ob es o l v e di n t oi t sd u a lp r o g r a m m i n g ，w h i c hi se a s i l yt ob e s o l v e d a f t e rw eh a dg o tt h ed u a lf o r mo ft w op r o g r a m m i n g ，w ef o u n dt h e i rf o r mw e r ev e r y s i m p l yb e c a u s et h e yh a do n l yn o n n e g a t i v ea n dl i n e a rc o n s t r a i n t s ，a i m i n ga t m o r eg e n e r a l n o n l i n e a ro p t i m i z a t i o n ss u b j e c tt ol i n e a ri n e q u a l i t yc o n s t r a i n t s ，t h i sa r t i c l ep r o p o s e sc u r v i l i n e a r p a t ht r u s tr e g i o na l g o r i t h m s t r u s tr e g i o nm e t h o d sh a sd r a w no u ra t t e n t i o ni n c r e a s i n g l ya 8o n e a p p r o x i m a t i n g m e t h o dg u a r a n t e e s g e n e r a lc o n v e r g e n c e i t sb a s i cs t e pi sa sf e l l o w s ：f i r s t ，w es e t t r u s t r e g i o nr a d i u s ，a n dt h e nw eg e ta t r i a ls t e pp r o d u c e db yc o n s t r a i n tq u a d r a t i c a lm o d e lz h u h a ss t u d i e du n c o n s t r a i n e do p t i m a lp r o b l e mb yc o m b i n i n go p t i m a lp a t ha n dm o d i f i e dp a t hw i t h n o n m o n o t o n i ct r u s tr e g i o nm e t h o d si n 【9 】) a n dt h eu s eo f1 2n o r mb yt r u s tr e g i o nm e t h o di n 1 i ns e e k i n gt h es o l u t i o no fu n c o n s t r a i n e do p t i m i z a t i o nh a sf o r m e ds i m p l ea p p r o x i m a t et r u s t r e g i o np a t h ，w h i c he n l i g h t e n su st os o l v en o n l i n e a rp r o g r a m m i n gp r o b l e mb yc u r v i l i n e a rp a t h i ng e n e r a lt r u s tr e g i o nm e t h o d ，at r i a lp o i n ti s a c c e p t e da san e wi t e r a t ea n dt h ep r o c e d u r ei s r e p e a t e di ft h et r u er e d u c t i o na c h i e v e db yt h eo b j e c t i v ef u n c t i o na tt h i sp o i n ti sc o m p a r a b l e w i t ht h er e d u c t i o np r e d i c t e db yt h eq u a d r a t i cm o d e l o t h e r w i s e ，t h et r u s tr e g i o nr a d i u si s r e d u c e da n dan e wt r i a lp o i n ti ss e l e c t e d i ti sp o s s i b l et h a tt h er e g i o ns u b p r o b l e mn e e dt ob e r e s o l v e dm a n yt i m e sb e f o r eo b t a i n i n ga na c c e p t a b l es t e p a n dh e n c et h et o t a lc o m p u t a t i o nf o r c o m p l e t i n go n ei t e r a t i o nm i g h tb ee x p e n s i v e t h i sa r t i c l ec o m b i n e sa p p r o x i m a t et r u s tr e g i o n p a t ha n dn o n m o n o t o n i cb a c k t r a c k i n gs t r a t e g yt os o l v en o n l i n e a ro p t i m i z a t i o ns u b j e c tt ol i n e a r i n e q u a l i t yc o n s t r a i n t s ，t h a ti s ，w eu s ea p p r o x i m a t et r u s tr e g i o np a t ht og e tt h er e s e a r c hd i r e c t i o n b ym i n i m u m i n gq u a d r a t i c a lm o d e l i nt h et r u s tr e g i o nb ye m p l o y i n g b a c k t r a c k i n gs t e p st oa v o i d c a l c u l a t i n gt r u s tr e g i o ns u b p r o b l e mr e p e a t e d ly o nt h ec o n d i t i o nt h a tt h er e s e a r c hd i r e c t i o n i s u n a c c e p t a b l e ，w eg o ta c c e p t e ds t e pb yn o n m o n o t o n i cl i n er e s e a r c hm e t h o dt od e f i n en e w i t e r a t i v ep o i n t ，w h i c hi m p r o v e dc a l c u l a t i n gs p e e d g r e a t l y f o rm o r ew i d e l ya p p l i a n c e ，o b j e c t i v e f u n c t i o ni sn o tl i m i t e dt oc o n v e xf u n c t i o ni nt h ep r o p o s e da l g o r i t h m ， t h et h e s i sc o n s i s t so ff i v ep a r t s c h a p t e rip r o v i d e su 8s o m eb a s i cc o n c e p to fn o n l i n e a rp r o - g r a m m i n g a n dd u a lp r o g r a m m i n ga 8w e l la st h eb a s i cm e t h o df 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 g p r o b l e m ，a st h eb a s i sm a t e r i a lf o rt h ef u r t h e rs t u d y b a s e do ng e n e r a lf e n c h e ld u a lt h e o r e m a n dr e l e v a n tk u h n - t u c k e rc o n d i t i o n mc a nd e d u c et h ed u a lp r o g r a m m i n go fg e n e r a le n t r o p y o ft h ed e n s i t yp r o b l e m s ，s t r o n gd u a l i t yt h e o r e ma n dr e l e v a n tk u h n - t u c k e rc o n d i t i o ni nc h a p t e r i i u s i n gl a g r a n g ed u a lp r o g r a m m i n g d e f i n i t i o na n db a s i ct h e o r e mo fn o n l i n e a rp r o g r a m m i n g ， c h a p t e ri i ip r o v i d e su st h e i rl a g r a n g ed u a lp r o g r a m m i n g sa n d t h e i rc o m p l e t et h e o r e t i c a la n a l y s i s b a s e do nt h e s et w ot y p e s o fp r o b l e m ，c h a p t e ri vp r o v i d e su sn o n m o n o t o n i cb a c k t r a c k i n g t r u s tr e g i o ns t r a t e g ya l g o r i t h mv i ac u r v i l i n s a rp a t hf o rm o r eg e n e r a ln o n l i n e a ro p t i m i z a t i o n s s u b j e c tt ol i n e a ri n e q u l i t yc o n s t r a i n t s ，a n dg i v e si t sn u m e r i c a lr e s u l t s c h a p t e rv s u m m a r i z e s t h i sa r t i c l ea n dp o i n t so u tt h ew a yf o rt h ef u r t h e rs t u d y k e y w o r d s ：g e n e r a l i z e df e n c h e l sd u a l i t yt h e o r e m ；l a g r a n g ed u a l i t yp r o g r a m m i n g ；d e n s i t y e n t r o p yp r o b l e m ；k u h n - t u c k e rc o n d i t i o n ；t r u s tr e g i o nm e t h o d ；n o n m o n o t o n i ct e c h n i q u e ；c o n v e r g e n c e a m s1 9 9 1s u b j e c tc l a s s i f i c a t i o n ：0 2 2 1 2 致谢 本文是在导师朱德通教授的精心指导下完成的，在论文选题及研 究的各个阶段，自始至终得到朱老师的热心关怀和指导，并提供了许 多宝贵的资料和极有价值的建议。 光阴似箭，我即将结束在师大的研究生学习生活。在这三年里， 朱老师对学问的执着追求和严谨求实的治学态度激励我努力钻研专 业知识，朱老师对学生细致入微的关怀和无私的帮助使我获益良多， 朱老师的言传身教是我将永远铭记于心的。在此篇论文即将完成之 际，谨向朱老师表示最诚挚的感谢和最崇高的敬意，并以此文来答谢 我的老师。 衷心感谢上海师范大学数理信息学院和研究生院为我在硕士研 究生学习期间提供了良好的学习和科研环境。感谢数理信息学院副院 长张寄洲教授、曾六川教授、王国荣教授、施永兵教授、王立联老师 以及三年来所有曾经关心过和帮助过我的老师。 特别感谢师兄顾益明、师姐赖海英在三年的学习生活中所给予的 帮助和关怀，感谢师妹郭佩华、王云娟在完成论文期间的支持和鼓励。 我还要衷心感谢我的父亲和母亲，是他们的无私奉献使我能安心 地完成学业，我的每一点进步都凝聚了他们无私的爱。 为了避免符号混淆 虢“ 豌”“m ”忆”l l ， ” 1 1 ” x z | c ( z ) q z 4 ( z ) 9 ( z ) h ( x ) = v 2 ，( z ) a ( x ) t t _ l ( z ，u ，p ) a 琏s r i s d o m f ，+ ( z + ) ! k 吼( d ) k 符号说明 我们对本文中的符号做以下说明。 n 维实向量空间 n m 维实矩阵 e u c l i d 范数 1 范数 o 。一范数 佗维决策变量 目标函数的局部极小值点 目标函数 约束函数 可行集 等式约束指标集 不等式约束指标集 p r e d ( d k ) a r e d ( d k ) c ( z o ) = z 瓣“ 1 ( 5 ) ，( 。o ) ) 6 ( ) ( g 。，v 2 ，h k ，c k ，a k ，k ，z k 不一一详述了。) 约束优化问题可行点x 处的起作用集 ，在z 处的梯度，b p v l ( z ) ，在。处的h e s s e 阵 c 在z 处的j a c o b i a n l a g r a n g e 乘子 等式约束优化问题的l a g r a n g e 函数 包台- s ( c 舻) 最小仿射集 s ( c 瓣“1 的相对内点 ，的有效域 ，( 茁) 的共轭函数 ，在当前迭代点。t 处的函数值 目标函数在处的局部二次近似 信赖域半径 信赖域子问题的预计下降量 信赖域子问题的实际下降量 水平集 近似信赖域路径 k ，w 名等表示相应的函数在x k 处的值，这里我们就 第一章引言 1 1 非线性规划的基本概念 最优化是在复杂的实际环境中遇到的许多可行决策中挑选最好决策的科学，为了对 各类问题作出决策，有条理的做法通常包括三个紧密相关的阶段。第一阶段的目标是建 立一个体现所考察决策问题的数学模型，决策者建立模型时首先确定变量；然后收集有 关数据；列出有待最优化( 极大化或极小化) 的目标函数；把变量和数据安排到一组称为 约束的数学关系式( 例如方程和不等式) 中去。第二阶段继续上一过程，对数学模型进行 分析，并选择一个适当的求最优解的数值方法。如果模型的一个或几个约束，或目标函 数是非线性的，这个最优化问题是个非线性规划。非线性规划的分析，对于问题的结 构提供了有价值的观察，并回答了关于能行决策和最优决策的存在性与特征性质问题。 由于其数值解法依赖于目标函数和约束的性质以及最优化问题的结构，决策者必须在分 析的基础上对现有的数值解法确定哪一种( 如果有的话) 能够求得最优解，第三阶段是利 用计算机或者其他工具来求出最优解随着电子计算机的日趋发展，以及工程技术、系 统识别、管理科学等方面研究的不断深入，非线性规划的应用越来越广泛。虽然单纯行 法的发展和高速计算机的出现使得线性规赳成为许多领域中解决问题的一个重要工具， 但是许多实际问题，由于目标函数为非线性或者其中一些约束函数为非线性，所以是不 可能表示为一个线性规划的。人们为了有效地求勰非线性规划问题在过去的几十年中付 出了艰巨的劳动，使之得到了迅速地发展 本文中我们将非线性规划问题表述如下： r a i n ，( 茁) s t q ( z ) = 0 ，i ，( 1 11 ) c l ) 0 ， i z 其中z 舻是决策变量，( z ) 称为目标函数，和工为有限指标集。q ( 口) ( z ) 为 等式约束，岛( 。) 0 刁为不等式约束。如果，( z ) 和g ( z ) ( i 占u 刁中至少有个是 非线性函数时，则称该问题为非线性规划。定义可行集n 为 q = z lc i ( z ) = 0 ，i ；岛0 ) 20 ，i z ) ( 1 1 1 ) 可表示为等价形式 m 锄i n ， 定义j j ，设z + q ，如果在x 。的某一邻域内有 ，( 茁) ，( z 。) ，v z 厂n q ， 1 1 i 1 q 0 n 则称z + 是r j j j 的一个局部极小点。如果对一切z nq 且z 茁+ 有 ，( z ) f ( x + ) ， ( 1 1 5 ) 则称z + 是一个局部严格极小点。 为讨论z + 为约束优化问题局部极小点的最优性条件，我们引入约束优化问题的l a g r a n g e 函数 n ( x ，) = ，( z )v i c | f ( x ) l e e 讹q ( z ) i 6 i 可行点x 的起作用集4 ( 茁) 定义为 a ( x ) = u i i ic 。( z ) = o ) ( 1 1 6 ) ( 1 1 7 ) 定义2 设z ，n ，a ( x + ) 为由仁卅定义的起作用集，如果 v q ( z 。) ，i 4 ( z + ) ) 线性无关，则称其具有线性无关陋i c 驯约束品性。 在此约荣品性的基础上，文【1 2 】中定理1 2 1 给出非线性规划( 1 1 1 ) 的一阶最优性 条件。 定理j j 设。+ 是问题以j 圳的局部极小点，如果l i c q 约束品性在x + 点成立，则存 在拉格朗日乘子矿， + ，其分量为口；( i e ) ，u ；( i 刁，使得 v 。l ( x + ，u + ，矿) q ( z 。) q 扛+ ) 钍i u ：q ( z + ) = 0 、 = 0 i 0 i z 0 i 工 = 0 i 工 ( 1 1 8 ) ( 1 1 9 ) ( 1 1 1 0 ) ( 1 1 1 1 ) ( 1 1 1 2 ) 定理( 1 11 ) 通常称为k a r u s h k u h n t u c k e r ( k k t ) 定理。满足( 1 18 ) 一( 1 1 1 2 ) 的z + 称为 ( 11 1 ) 的k k t 点。对于问题( 1 1 1 ) 可能存在多个拉格朗日乘子“+ ，u + 使( l 1 8 ) 一( 1 1 1 2 ) 成立，但如果l i c q 约束品性成立，则“+ ，v 4 是唯一的。 问题( 1 11 ) 的最简单形式是无约束情况，即u z = d ，则无约束最优化问题表示 为 r a i n ，( 茁) ，。瓣” 类似的，可以定义无约束最优化问题的局部( 严格) 极小点。 定义j j 0 设z ，舻，如果在z + 的某邻域有 ( 1 11 3 ) f ( x ) f ( x + ) ，v z ， ( 1 11 4 ) 2 则称z + 是一鲫的一个局部极小点。如果对3 7 。且x x + 有 ( 11 1 5 ) 则称2 7 。是n 1 1 3 ) 的一个局部严格极小点。 无约束最优化问题的一阶最优性条件比较简单。在文f 1 4 ) 中定理1 43 给出了如下 结论。 定理j ，j 2 设z + 是，jj i s ) 的局部极小点，且，在。的一开邻域内连续可微，则 ( 11 1 6 ) 当目标函数为凸函数时，文 1 4 定理1 4 6 还给出了整体极小点的充分必要条件，它说 明了目标函数为凸函数时，局部极小点即为整体极小点 定理j 3 设，：舻- - 4 脏1 是凸函数，且，c 1 ，则z + 是整体极小点的充分必要条件 是v ( x ，) = 0 。 1 2 对偶规划、最优性条件与最小区别信息量问题 本文对两类广义熵密度问题求出其对偶形式，这里有必要介绍对偶规划，最优性条 件的相关知识。考虑非线性规划问题p r a i n ，( z ) s t q ( z ) = 0 ， i c = f ( 。) 0 ， i z x z ( 1 2 1 ) ( 1 2 2 ) ( 1 2 3 ) ( 1 , 2 4 ) 其中，c ，( i u z ) ：咿_ 精1 ，并且疋是舻中一非空开集。 文【1 3 】中给出k u h n t u c k e r 最优性必要条件：如果牙是问题p 的局部最优解，并 且在适当的约束品性假设下，存在向量( u ，。) 使得 v ，( 雪) + 铫vc i ( 童) + 乱。v q ( 互) = 0 l z 越q 忙) = 0 ， ie z “：20 ，i z ( 12 5 ) ( 12 6 ) ( 1 2 7 ) 而和啦分别是相应于约束q ( z ) = 0 ( i 翻和c ，( z ) 0 ( i 刁的l a g r a n g e 乘子。 而且，u i c i ( 孟) = o ( i 工) 称为互补松弛性条件。在适当的凸性假设下，k u h n t u c k e r 条件也是最优性的充分条件。特别，假定i 是问题p 的一个可行解以及k u h n t u c k e r 条 件成立。 3 与优化问题密切相关的是它的对偶问题。在各种各样的对偶公式中，l a g r a n g e 对偶 公式也许是最具有吸引力的。对于求解大型线性问题，以及凸的和非凸的非线性问题， 它都能导出一些算法，最近，证明了它在全部或者部分变量限制为整数的离散最优化中 是很有用的。同样考虑上面的非线性规划问题p ，将其称为原问题，其l a g r a n g e 对偶问 题d 表述如下： l a g r a n g e 对偶问题d m a x p ( u ， ) stu 0 ( 1 2 8 ) ( 1 2 9 ) 其中o ( u ，u ) = i n f f ( x ) + v i c i ( x ) + u 而( 茁) ：z z ) 。在这里，u 的第i 个分量u i t t e 工 称为对偶变量或相应于约束c i ( z ) 0 ( i z ) 的l a g r a n g e 乘子，而v 的第i 个分量v i 称为对偶变量或相应与约束c t ( z ) = 0 ( i ) 的l a g r a n g e 乘子。可以注意到，即是关于 ，c i ( i u z ) ，没有任何凸性或凹性假设之下，0 仍然是凹函数。注意l a g r a n g e 对偶 函数0 ，对某些向量( u ，口) 可以取一。o 的值，在口( u ， ) 表示式中，约束c i ( z ) 0 ( i 工) 和q ( 。) = 0 ( i ) ，由于利用l a g r a n g 乘子v i ( i ) 和u ；( t 工) 已经合并到目标函 数中。还要注意与不等式约束c i ( z ) 0 ( i z ) 相应的乘子u i 是非负的，而与等式约束 c t ( z ) = 0 ( i 纠相应的乘子地不受符号的限制。 由于对偶问题是将函数f ( x ) + 啦c l ( z ) + v # c 4 ( x ) ：xe2 2 的下确界( 最大下界) t 工 极大化，因此，有时也称为极大一极小对偶问题。 本文中所要讨论的广义熵密度问题是基于下述的带约束的最小区别信息量( m i n i m u md i s c r i m i n a t i o ni n f o r m a t i o n ) 问题，简称m d i 问题： n 。 m i n 妒( z ) = q i n 兰p r l = 1 ， s t 九= 去z t d t 。+ b z + c i 0 ， i = 1 ，一，r z z 0 其中的向量d = ( d - ，d n ) t 0 ，d ，是半正定矩阵( i = 1 ，r ) ；e 表示自然对数的 基。这类问题在物理学、生物学、保险业以及社会科学的统计问题中经常会遇到。 在文【1 3 中给出了一系列关于非线性规划的结论，其中弱对偶定理说明对偶问题的 任何可行解的目标值都是原问题任何可行解的目标值的一个下界。 定理2 j 傅对偶性定理j 设爿是问题p 的可行解，即，。2 2 ，c i ( x ) 0 ( i z ) 和 q ( z ) = 0 ( i 翻还设( u ， ) 是问题d 的可行解，即u 0 ，则s ( x ) 口( u ，v ) 。 定理j 2 2 如果s u p 0 ( u ，u ) ：u o ) = 0 0 ，则不存在点z 爿使得q ( z ) o ( i 工) 和 c i ( x ) = 0 ( i ) ，因此原问题是不可行的。 定理23 如果i n f f ( x ) ：岛( 。) o ( i 工) ，c ；( z ) = 0 ( i ) ，茁爿) = 一。，则对每个 ( “，u ) 且u 0 有p ( u ， ) = 一。 4 定理2 4 如果存在原f - i 题的可行解x 和对偶问题的可行解( u ，口) 使得f ( x ) = 日( u ， ) ， 则3 7 是问题p 的最优解，( “：u ) 是问题d 的最优解。而且，互补松弛性条件u c 。f z ) = 0 ，( i z ) 成立。 原问题的最优目标值大于或等于对偶问题的最优e t 标值。如果严格不等式成立，则 说明存在有对偶性间隙。 下面的强对偶性定理，指出在适当的凸性假设下和约束品性假设下，原问题和对偶 问题的最优目标函数值是相等的。 定理2 5 佛对偶性定理，设z 是乳“中一非空凸集，设，：舻- - + 豌1 和c ( z ) ( i z ) ： 乳“_ 虢“是凹的，并设c i ( x ) = 0 ( i s ) ：孵“- - + 孵是仿射的；即龟( z ) ( i ) 有形式 q ( z ) = a x b 其中a 是矩阵，b 是向量。原问题p 和对偶问题d 两者的最优目标值 相等，印 i n f f ( x ) ：。爿，q ( z ) 0 ( i 工) ，q ( z ) = 0 ( i ) ) = s u p 0 ( u ，v ) ：u o ) 而且，如果下确界有限，则上确界在( 面，o ) ，百0 达到如果下确界在z 达到，则i c ( 牙) = 0 ，i z 。 1 3 求解非线性规划的基本方法 求解非线性规划闻题的基本方法是构造迭代算法，其基本思想是：给定一个初始点 x o 舻，按照某一迭代规则产生一个点列 ，使得当 o k ) 是有限点列时，其最后 一个点是非线性规划问题的最优解；当 是无穷点列时，它有极限点，并且其极限点 是非线性规划问题的最优解。算法的这一特征称为算法的收敛性，它对于求解非线性规 划问题是至关重要的。一个同样重要的问题是算法收敛的速度问题，下面我们给出一些 关于收敛速度的定义。设算法产生的迭代点列 z k ) 在某种范数意义下收敛，即 1 i ml i x , 一x 。1 | = o ( 1 3 1 ) e 。 若存在实数 0 及一个与迭代次数无关的常数q 0 ，使得 1 i m 毕删：q( 1 3 2 ) 。o 。z k 一2 7 , i f “ 则称算法产生的迭代点列 z k ) 具有q o 阶收敛速度( 商收敛速度) 。特别地， ( 1 )