（计算数学专业论文）一类严格线性不等式组的解法.pdf

大连理工大学硕士学位论文 摘要 线性不等式组在数学、物理、计算机应用以及管理等多种领域中都有广泛的应用， 很多实际问题都可以应用到或者转化为线性不等式组问题，如 1 中的微分包含关于非 光滑区域生存性的判别问题， 2 ：i 中的移动通信系统中的功率最优控制问题等等。线性 不等式组一般可以看作线性规划问题用单纯形法或者内点法来求解。但对严格线性不等 式组，线性规划方法一般得到的是边界点而不是问题的解。本文考虑严格线性不等式组， rj v 、n 尤其是二次特征值反问题中提出的特殊形式的严格线性不等式组 的数值解法。 【x 0 我们将其转化为三种形式的m i n i m a x 问题，对转化后的三种问题，用凝聚函数法分别将 其目标函数光滑化，并分别用带 m i j o 不精确线搜索的最速下降法、带自适应参数修 正的凝聚函数法以及既约梯度法来求解。最后在m a a b 环境下给出了数值实验，实验 结果表明，将严格线性不等式组问题转化为m i n i m a x 问题来求解，避免了得到边界点解 的情形，得到的结果比较令人满意。： 关键词：严格线性不等式组；线性规划；m i n i m a x 问题；凝聚函数法；数值实验 二耋塑垡壁至篁蒌望盟堡 as o l u t i o nf o rak i n do f l i n e a rs y s t e mo fs t r i c ti n e q u a l i t i e s a b s t r a c t l i n e a rs y s t e mo f i n e q u a l i t i e si sw i d e l yu s e di nm a n yf i e l d ss u c ha sm a t h e m a t i c s ，d h y s i c s c o m p u t e ra p p l i c a t i o na n dm a n a g e m e n ts c i e n c e ；m a n yp r o b l e m si np r a c t i c ec a l lu s eo rb e t r a n s f o r m e dt ol i n e a rs y s t e mo fi n e q u a l i t i e ss u c ha st h ep r o b l e mo f d e t e r m i n i n gt h ev i a b i l i t y f o rac l a s so f n o t l l i n e a rc o n t r o ls y s t e m so dar e g i o nw i t hn o n s m o o t hb o u n d a r yi n 1 a n dt h e p r o b l e mo fo p t i r e a lt r a n s m i t t e rp o w e rc o n t r o li nc e l l u l a rr a d i os y s t e m si n 2 l i n e a rs y s t e m o fi n e q u a l i t i e si su s u a l l ys o l v e da sal i n e a rp r o g r a m m i n gp r o b l e mb ys i m p l e xm e t h o da n d i n t e r i o r - p o i n tm e t h o d ，b u tw h e nr e f e r r i n gt ot h el i n e a rs y s t e mo fs t r i c ti n e q u a l i t i e s ，t h el i n e a r p r o g r a m m i n gm e t h o di sn o tp r o p e r ，a si t sr e s u l ti so f t e nt h eb o u n d a r yp o i n ti n s t e a do ft h e s o l u t i o no ft h ep r o b l e m t 1 1 i sp a p e rc o n s i d e r st h en u m e r i c a ls o l u t i o no fl i n e a rs y s t e mo fs t r i c t r n i n e q o a l i t i e s ，e s p e c i a l l yf o rt h ep r o b l e mf o 衄e da s “7 u ，w h i c hr i s e sf r o mt h eq u a d r a t i c 2 lz 0 i n v e r s e e i g e n v a l u ep r o b l e m w et r a n s f o r r nt h es p e c i a lk i n do fi i n e a rs y g e mo fs t r i c t i n e q u a l i t i e si n t ot h r e ek i n d so fm i i n m a xp r o b l e m s ，a n dt h e ns m o o t ht h eo b j e c tf u n c t i o n sw i t h t h ea g g r e g a t ef u n c t i o nm e t h o d t h e nw es o l v et h et h r e em i n i m a xp r o b i e m sw i t h s t e e p e s t d e s c e n tm e t h o dw i t ha r m i j oi n e x a c tl i n es e a r c hr u l e ，t h ea g g r e g a t ef u n c t i o nm e t h o dw i t h a d a p t i v ep a r a m e t e ra d j u s t m e n ta n dt 1 1 em e t h o do fr e d u c e dg r a d i e n t a t1 a s tt h en u m e r i c a l e x p e r i m e n ti sd o n eu n d e rt h ee n v i r o n m e n to fm a t l a b t h er e s u l ts h o w st h a tt h et r a n s f o r m a t i o n f r o ml i n e a rs y s t e mo fs t r i c ti n e q u a l i t i e st om i n i m a xp r o b l e ma v o i d st h es h o r t a g eo fg e e i n ga b o u n d a r yp o i n ts o l u t i o na n di ss a t i s f 舛n g k e yw o r d s ：l i n e a rs y s t e mo fs t r i c ti n e q u a l i t i e s ；l i n e a rp r o g r a m m i n g ；m i n i m a xp r o b l e m ； t h ea g g r e g a t ef u n c t i o nm e t h o d ；n u m e r i c a le x p e r i m e n t 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 、， 作者签名： z 远 日期： 鲤! 渔 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：主堑坠 导师签名一丕亟二 且年月盟日 大连理工大学硕士学位论文 1绪论 线性不等式组问题在数学、物理、计算机应用以及管理等多种领域中都有广泛的应 用。很多实际问题都可以应用到或者转化为线性不等式组问题，如 1 中的微分包含关 于非光滑区域生存性的判别问题， 2 中的移动通信系统中的功率最优控制问题， 3 中 的钻井布局模型的构造问题， 4 中的医药工作中调配辅料食谱、选方配药、选择医疗 方案等问题，以及 5 中的基于效用最大化的投资组合模型等等。 经过一系列处理，弹簧振动系统的反二次特征值问题 m x a 2 + c x a + k x = 0 ( 1 1 ) 其中，a 、x 为给定的特征值与特征向量，要求的m 、c 、k 分别为质量、阻尼、弹性系 数矩阵( c 0 ) ，可转化为如下线性不等式组( m o o d yc h u ，2 0 0 6 年8 月在大连理工大学 的讲座) ： ( 枷。 m ：， 其中y ，z 为给定的上三角矩阵。不同于一般的线性不等式组问题，( 1 2 ) 要求所有的不等 式均为严格不等式。 解决线性不等式组问题有以下两种思路：是考虑线性不等式组的相容性，即先判 断线性不等式组是否有解，在此基础上再给出适当的算法求解：一是不考虑不等式组的 相容性，直接给出算法求解，由计算结果来判断原不等式组是否有解。基于第一种思路， 关于不等式组相容性的判别已经有了很多结果，如 6 中的a b s s g 算法， 7 中的关于s 矩阵的些结论，等等；但这些方法只是对某些特殊结构的线性不等式组给出了相容性 的充分或必要条件，对结构一般的线性不等式组则没有统一的结果。而基于第二种思路， 比较常用的是将线性不等式组问题看作线性规划问题，用单纯形方法 8 或者内点法 9 求解。 将( 1 2 ) 看作线性规划问题来求解容易得到边界点。鉴于这种情形，我们希望找到 别的方法来避免产生上述情况。我们不针对( 1 2 ) 中的特殊矩阵，而是考虑更一般的情况， 将( 1 2 ) 抽象为一般形式： 问题( p ) ：给定a r m ，求x r ”， s t j 出刈( 1 3 )( ) lx 0 由于( p ) 中的不等式均为严格不等式，故若将其看作线性规划问题用单纯形方法来解 f 将目标函数设为常数，式( 1 3 ) 作为约束条件) ，根据其最优解必在可行域顶点处得到可 知，容易得到边界点，即，使得( p ) 中某些不等式变为等式，故单纯形方法不可行，具体 例子将在第四章给出。因此，我们考虑将其转化为m i n i m a x 问题来求解。 本文的安排如下：下一章我们介绍相关理论，第三章给出解严格线性不等式组问题 口) 的几个解法，最后，第四章我们将给出数值实验。 大连理工大学硕士学位论文 2相关理论 2 1 有限1 1 1 i n i m a x 问题简介 有限m i n i m a x 问题是在实际的工程应用中提出的一类重要的不可微优化问题，并且 成为非线性泛函分析的重要组成部分，特别是在工程设计、电子线路规划、数学经济、 最优化理论、变分不等式、微分方程等诸多领域有广泛的应用。有限m i n i m a x 问题也出 现在以下问题中：厶，k 逼近问题；非线性方程组求解问题；用不可微罚函数法求解 非线性规划问题等等。 有限m i n i m a x 问题的一般形式为： ( d ) 孵妒 其中妒：r ”j r 定义为妒= m 擎厂，而，：r ”斗r ，q = 1 ，q ) 是 光滑函数。 m i n i m a x 方法是一类重要的数学规划方法，它是无约束优化问题与约束优化问题之 间的自然桥梁，而且与非线性方程组、非线性规划、多目标规划等数学问题之间有密切 关系( 文献 1 0 3 ) ，因此如何求解它具有重要的理论价值和实际意义。目前已经提出 了很多解决有限m i n i m a x 问题的方法，很多研究者提出通过解决一系列信赖域类型的无 约束( 见参考文献 1 1 ，【1 2 与 1 3 ) 或约束( 见参考文献 1 4 ， 1 5 ) 子问题来解决该问 题。还有些研究者提出将原问题转化为如下形式来解决( 文献e 1 6 ) ： ( d ) ，婴呜+ 。缸l ，一口0 ，j q j d ip i l l o 等就在 1 7 中对该形式发展了一种可微罚函数方法。此外，也有很多文章 ( 1 8 一 2 8 ) 提出m i n i m a x 问题的光滑化逼近解法，即，将m i n i m a x 问题转化为简单的 光滑无约束问题来求解。但由于m i n i m a x 函数的非光滑性，当逼近精度较高时光滑逼 近问题会变的非常病态，这样算法就会面临数值困难和较慢的收敛速度。因此，本来简 单的光滑化技术应用因为逼近精度与问题病态的两难选择而变得复杂。针对这种问题， 文献 2 9 中给出了一种自适应参数修正准则，该准则保证了当迭代点远离最优解时参数 保持很小，而随着迭代点逼近最优解参数会变大。 一类严格线性不等式组的解法 2 2 凝聚函数法 f 1 8 中给出了根据j a y n e s 的极大熵原理所导出的求解极大极小问题的凝聚函数法。 构造p ) 的l a g r a n g e 函数： l ( x ，a ，a ) = a + a ，m 一a 】 ( 2 1 ) i = l 其中， 为与不等式约束g ) 一as o 相关的l a g r a n g e 乘子，取非负值。 由问题( d ) 关于a 的k k t 条件，得到 a ，- - 1 ( 2 2 ) i - i 将其代入式( 2 1 ) ，消去a ，得到简化形式： l ( x ，a ) = a ，g ) ( 2 3 ) l = i 易知，不等式 g ，z ) - - 九，g ) 妒g ) ( 2 4 ) i - 1 对于集合 a = o ：a ，= i ) ( 2 5 ) 1 = 1 中的任意a 成立。即，函数，的任何凸组合总小于或等于最大值函数妒( 弗。 我们的目的是要找到个函数来逼近9 ( ，因此必须找一个向量a 使得l a g r a n g e 函数取极大值并使得不等式( 2 4 ) 成为等式，即必须求解如下的对偶问题： m o 娶l ( x ，a ) = 丑z ( d ( 2 6 ) 将乘子 解释为相应函数z 关于最大值函数妒的概率，则三g ，a ) 可看作原来 所有函数，的均值。上述问题可解释为求概率分布使三( x ，a ) = 9 的问题。根据j a y n e s 提出的极大熵原理，这个概率分配应使相应的s h a n n o n 熵函数取极大值。把熵函数的极 大化要求作为一个附加准则，构造一个复合的l a g r a n g e 对偶问题： m 枞a x l ，( 、x ，a ) = l ( x ，1 ) + h ( 1 ) i p ( 2 7 ) 其中函数 大连理工大学硕士学位论文 日( a ) = 一 1 1 1 ( 2 8 ) 即为对应这里概率分配的s h a n n o n 熵。问题( 2 7 ) 中的附加项只不过代表在原来对偶问题 ( 2 6 ) 上施加的另一个极大化目标面己，其中正的参数p 用来对两个目标进行平衡。显然， 当p 趋于无穷大时，问题( 2 7 ) 将化为( 2 ，6 ) 。 对问题( 2 7 ) 关于石求导可得其解析解： = e x p 西( 力 艺e x p 彤( 习 i = 1 ，q ( 2 9 ) 将其代入问题( 2 7 ) 的目标函数l p ( x , x ) ，消去a ，得到一个仅为x 的函数，这个函数即 为 驰) 2 ；11 1 1 接唧( 彤) ) ( 2 1 。) 从而得到求解极大极小问题的极大熵方法( 又称凝聚函数法) ，即将问题( d 7 ) 转化为无 约束优化问题： m i n 。阱h p 倭e x 蛔 ( 2 1 1 ) 将lx ) 改写为如下形式： g ) = 9 + 言1 i l 喜e x p 。一妒g 油 ( 2 1 2 ) c 具有如下性质( 18 】) ： 性质10 e ( 0 一妒( ) 0 l n ( q ) l p ( 2 1 3 ) 性质2 巴将随p 的增加单调下降，并且当p 趋于无穷大时以9 ( 0 为极限。 性质3 若：g ) ，i - - 1 ，2 ，q 是凸函数，则c 是凸函数。 性质4r g ) 与，g ) ，i = 1 , 2 ，口中可徼性最低的函数有同样的可微性质。 性质5 设驴g ) 是凸函数，如) 是c 的稳定点，则 如) ) 的任一聚点都是妒的 极小点。进一步，若9 g ) 是严格凸函数，x ( p ) 是c g ) 的稳定点，则如) 寸x ，x 是妒 的唯一极小点。 一类严格线性不等式组的解法 2 3 既约梯度法 既约梯度法( 见【3 0 】) 是1 9 6 3 年由w o 璐提出的改进可行方向的一种方法，用来解 决具有线性约束条件的非线性规划问题。其基本思想是：利用约束条件将所考察问题中 的某些交量用其它的一组独立变量来表示，从而使问题的维数降低，并且利用既约梯度， 直接构造出一个改进的可行方向d ，然后沿此方向进行线搜索，从而得到一个新点，这 样一步步来逼近原问题的最优解。 对于如下形式的线性约束优化问题： r a i n f ( x ) s t 彳x = b( 2 1 4 ) x 0 有定理2 1 ( 见 3 0 ) 定理2 1 设j 是问题( 2 1 4 ) 的一个可行解，使得x 7 = g ；，工：j ， 0 ，其中a = ( b ，n ) ， 而基矩阵b 是肌x 聊可逆矩阵，用i 表示基变量的指标集。令 r 7 = 可r | v 。g ) 7 b 。4 = ，砖) ( 2 1 5 ) d 7 = p ；，) 是按式( 2 1 6 ) 和( 2 1 7 ) 形成的方向，对非基变量，仨，令 巧= 膨雾； 基变量对应的为 d b = 一b n d 。 ( 2 1 7 ) 若d 0 ，则d 是一个改进的可行方向：而乒o 的充要条件是x 为k k t 点。 2 4 线性规划 当最优化问题中的目标函数与约束函数都是变量工r ”的线性函数时称为线性规 划。线性规划是在第二次世界大战期间从军事应用中发展起来的，目前它的应用已经遍 及备行各业。线性规划的标准形式如下( s 】) ： 大连理工大学硕士学位论文 疆n n c 】x 】+ c 2 x 2 十十c n x h s j q 】葺+ 口1 2 恐+ + 口l 。矗= 6 1 a 2 1 + g 2 2 x 2 + + a 2 一x n2b 2 ( 2 1 8 ) 1 五+ 2 而+ + 。x n = 6 卅 毛，屯，0 所有右边常数都是非负的，即鱼0 。 线性规划问题具有如下基本特性： 线性规划问题的可行域如果非空，则是一个凸集凸多面体： 如果线性规划问题有最优解，那么最优解可在可行域的顶点中确定； 如果可行域有界，可行域只有有限个顶点，问题的最优解必存在，并在这有限 个顶点中确定； 最优解可由最优顶点处的有效约束形成的方程组的解确定。 将( 2 1 8 ) 写为矩阵形式，有 r a i n0 x 豇t 4 x = b( 2 1 9 ) x 0 其对偶形式为 m a x z ( y ) 一by ( 2 2 0 ) s t 爿7 y c 则有下列结论( 【8 】) ： 定理2 2 ( 弱对偶定理) 设x 和y 分别是原始问题和对偶问题的可行解，则有 ，( x ) = c o 6 7 y = z ( y ) 弱对偶定理表明，一个极小化线性规划问题在其某一可行点处的函数值，给出了另 一个作为其对偶的极大化线性规划问题的最优值的一个上界；或者说，一个极大化线性 规划问题在其某一可行点处的函数值，给出了另一个作为其对偶的极小化线性规划问题 的最优值的一个下界。由此可得两个推论： 推论2 - 3 如果两个互为对偶的线性规划问题中有一个无有界的最优解，则另一个问 题必定不可行。 推论2 4 如果两个问题各有一个可行解，且相应的目标函数值相同，则这两个可行 解各是相应问题的最优解。 一类严格线性不等式组的解法 定理2 5 ( 强对偶定理) 如果互为对偶的两个线性规划问题中一个有最优解，则另 一个也有最优解，且两者的最优目标函数值相等。 2 4 1 单纯形法 求线性规划问题最优解的单纯形方法是由g b d a n t z i g 在1 9 4 7 年提出的，由于这 一方法的有效性，几十年来一直在几乎所有的领域得到广泛的应用。 单纯形方法是一种迭代法，它根据线性规划问题的特点在问题可行域的顶点中逐步 确定问题的最优解。在每一个是基本可行解的迭代点，如果它不是最优的，单纯形法从 与该顶点相联接的边中确定一个使目标函数值下降的边，沿该边移动可以确定一个与该 顶点相邻，且目标函数又优于该顶点的新顶点( 基本可行解) 。由于可行域的顶点数是 有限的，如果每一次移动都能使目标函数值下降，则经过有限次的移动方法必终止于问 题的一个最优顶点。 2 4 2 原始对偶内点法 1 9 8 4 年印度数学家k a r m a r k a r 对线性规划的求解提出了一个具有多项式时间复杂性 的内点算法。不同于单纯性方法，内点算法从线性规划问题可行域的一个严格内点开始， 产生一个使目标函数值逐步改善的严格内点序列，并最终收敛于问题的最优解( 见文献 【8 】) 。 经过近2 0 年的研究与发展，如今已有大量求解线性规划问题的内点算法，其中原 始对偶内点算法就是一种应曰广泛、效果又比较好的内点算法。该算法通过用牛顿法求 解由原始线性规划及其对偶规划所得到的原始对偶方程组，在可行域的内部产生个收 敛于最优解的严格可行内点序列。 考虑标准线性规划问题( 2 1 9 ) ，其相应的对偶问题可表示为 m a x b r y j t z = c a 7 y ( 2 2 1 ) z 0 其中z 0 为引入的松弛变量。假设原始问题和对偶问题可行域内部均非空，根据原始可 行性与对偶可行性以及强对偶定理，上述问题的可行解x 和( ，：1 应满足下述方程组： 大连理工大学硕士学位论文 i 爿工= 6 ：2 c - a 7 y( 2 2 2 ) 矽工= 6 7 ) ， 【x o ，z 0 由于c r x - b 7 y = c t x 一厂4 x = p a 7 ) ，) 1 工= x 乙，上述方程组可改写为 f a x = b j z 2 c - a ( 2 2 3 ) l x 7 2 = 0 l x 0 ，z 0 记 x l z , = ，( o ) ，i = l ，2 , - - , n ， ( 2 2 4 ) 则t 和z ，均为正，且在p _ o 时，x , z 。- - - 0 ，i = l ，2 ，h ，即x r ：一oa 因此对逐步减小 并收敛于零的正数序列，求方程组 a x = b z = c a r y ( 2 2 5 ) x ，z ，= ，i = 1 ，2 ，” x 0 z 0 的解，就可保持解的严格可行性，并在p j 0 时最终确定原问题的最优解，和对偶问题 的最优解( ，z ) 。 对方程组( 2 2 5 ) 用迭代法求解，设( x ，弘z ) 是方程组( 2 2 5 ) 解的一个近似，要确定 修正量出，砂，d z 以得到( 2 2 5 ) 的解的更好的近似矿= x + d r ，y + = y + a y ，广= z + 出，满足 f a d x = 0 j d z + a 7 d y 。0( 2 2 6 ) l d z , + z ，d x , = p + - - x i z s i z + 出0 ，z + d z 0 给出原始对偶内点法的迭代步骤如下：( 见文献【8 】) 步1 给定参数值y ，s o ，初始严格可行内点1 ) o ，”，：( 1 o ，初始h o ，置 k = 1 5 步2 若( x k ) 2 ，停止迭代，( x k ，少，矿) 即为满足要求的近似最优解； 一类严格线性不等式组的解法 步3 解方程组得解( 出，砂，d z ) ； 步4 计算 a ，= 幽( 去| 如 。 一- 云d z , o 阿( + a d ) “d = 0 ( 2 2 9 ) 这样的线性搜索为精确线搜索。但是，一般精确线搜索需要的计算量很大，而且在实际 上也不必要，特别对某些非光滑函数或者导数表达式复杂的函数不能利用精确搜索，此 外，在计算实践中人们也发现过分追求先行搜索的精度反而会降低整个方法的效率，因 此人们提出了既花费较少的计算量，又能达到足够下降的不精确线搜索方法。 常用的不精确线搜索准则有g o l d s t e i n 准则，w o l f e 准则以及a r m i j o 准则。 o o l d s t e i n 准则为 1 ( x + a d ) - f ( x ) + ( 1 - p ) a 。( g k ) 7d k ( 2 3 1 ) 其中，0 0 。 g 。 0 矿争刈 陀3 4 ) 大连理工大学硕士学位论文 3 解严格线性不等式组的几个方法 3 1 问题( p ) 转化为m in i m a x 问题 本文将问题( p ) 转化为以下三种m i n i m a x 问题： 问题( d m 。a x 。m i n 备，7 k ，7 五一，矗 ( 3 1 ) 其中，口7 为矩阵a 的第i 个行向量，i = 1 ，2 ，q 问题( d 2 ) 其中，a ，为矩阵a 的第i 个行向量，p 为珂维全1 向量，i = 1 ，2 ，q 闯题( d b ) n m x 。粤一+ 。 ( 3 - 3 ) s t b z = 0 其中，b a ，- e ) ，e 为单位矩阵。 下面我们证明，问题( p ) 有解等价于问题( d 1 ) 、( d 2 ) 、( d 3 ) 的目标函数大于零。 定理3 1 问题口) 有解等价于问题( d 1 ) 的目标函数大于零。 证明：必要性：若( p ) 有解，则存在p 0 ，x o r ”，使得a x 0 0 。从而 m i n 0 。7 z 。，7 p ，砰，群 o ， 进而可得 搿疵n 。，一。7 妒，“，j o 。 充分性： m 。a 。x r a i n a ，7 x ，口。t x ，而，x o o ，不妨设i o 满足 m i n a f i ，ar i ，i ，瓦 - m m i n a ，7 矗一吼7 x ，x 1 ，以o ， 从而有a i 0 ，i 0 ，从而i 即为问题( p ) 的解。证毕。 类似的，我们有 弓f 理3 2 若( p ) 有解，则必有n ! 磐，。i 磐。0 ，7 工 0 ；反之，m ：。a x ，。艘。矗7 x 0 ，帅1 z 41 z ，4 则必有解。 证明：必要性：若( p ) 有解，则存在p o ，妒，使得a x o 0 。从而r a i nk 7 x o o ， i o i 2 口 进而可得，n 础咖 a f x m i l l ar x 0 。 x 0 s = 1 0 一q a 1 2 ，4 0 q 司 q x ；“p 穗跳 一 虬 类严格线性不等式组的解法 充分性：若：max。min，。b7寸o，不妨设孑o满足mi11，矗7i)=mdx。rainxo 2j - i2x o2 。矗7 0 o ， i i ，一，口、 。 4 7 ，；i口+ 7 从而口j i 0 对所有的i = l , 2 , - - - , q 都成立，即a i 0 ，从而i 即为问题( 】p ) 的解。证毕。 引理3 3 若x 是问题( p ) 的解，则对任意的常数c o ，“也是问题( 】盼的解。 证明：若x 是问题( p ) 的解，则必有x o , a x o 。由于常数c o ，故有c x o , 4 ( c x ) = c 似工) o ， 即“也是问题( p ) 的解。证毕。 定理3 4 问题r e ) 有解等价于问题( d 2 ) 的目标函数大于零。 证明：由引理3 3 ，设x 是问题( p ) 的解，令c - - = e 7 工，其中e = ( 1 ，l ，矿，显然c 0 ， 则脚是问题( p ) 的解，且y 满足y 0 且e t y = l 。再由引理3 2 ，可得结论。证毕。 定理3 5 问题( p ) 有解等价于问题( d 3 ) 的目标函数大于零。 证明：问题c d a x x 。0 可转化为卜血 - 。，b 。= 0 。，令b = 渔，- e ，z = e ) ，则问题口，等价 于闯题 筹 ( 3 4 ) 由定理3 1 可得，z 0 等价于m a xm i nz ， o ，从而问题( p ) 有解等价于问题( d 3 ) 的目 t 0 1 z 4 标函数大于零，进而问题( p ) 有解等价于问题( d 3 ) 的目标函数大于零。证毕。 一1 4 大连理工大学硕士学位论文 3 2 算法 3 2 1 求解问题( d 1 ) 的算法 将i 司题( d 1 ) 化为标准的m j n 岫a x l 司题，硐 婴m a x q 7 五，一7 工，一而，一h ( 3 5 ) 则有。 9 0 0 = m a x - a 1 7 k ，一a q t x , 。，一矗 ( 3 6 ) 删。古h 甾e 印( - p o l x ) + 喜舛彤珥 ， il ；i，- lf 2 妒+ 万1h 侉x p ( - p 嘶) ) ) + 窆一e x p ( - p g ，嘶) ) ) ) ( 3 7 ) 一主e x p ( - p a , r x b 。一窆e x p ( - x p ( - p a , rx p ( - p 譬，k ，一ex b 。一e，k ， 哪卜 i 丽墓i 丁e x p ( - 彤j x ) + e x p ( _ 鹦) 妻e x p ( _ p g j x + 妒( 力脏+ 窆( - p g ，+ 妒g 龇， 琴 e x p ( - p ( a x + 妒g ) ) ) + 窆e x p ( _ p g ，+ 妒g ) ) ) = 一土l 旦一 ( 3 8 ) 根据凝聚函数的性质，在一定条件下，只要p 充分大，如) 与工的误差可任意小， 我们给出算法如下： 算法3 2 1 删。准则的最速下降法 步o ：给定初始搜索区间 o ，a 孟】，p ( o 遗 ，卢( o ，1 ) 。取定x 。r ”，口。 o ，a 。】， p = ；1 ，令j = o ，口1 = o ，口2 = 口一，t 为逼近误差取为l o ； 步l ：计算妒g ) ，矗g ) ，v e ，g7 ) ( 为避免发生溢出，分别用( 3 7 ) 、( 3 8 ) 计算) 。 若| j 晖g 1 s f ，停止； 否则，计算最速下降方向h p , ( x ) = 一v g 。) ( 3 9 ) 步2 ：用a n 嘣。不精确线搜索准则计算步长口， 二耋兰鳖堡堡至篓茎丝堕! 壁 步3 ：令x = 工+ a h p , ( x ma - i - - i + l ，转步1 3 2 2 求解问题( d 2 ) 的算法 将河题( d 2 ) 转化为标准的m i l l i m a ) 【问题为 m i n m a x - - a 1 t x ，- - c i q t x s t x o ，e r x = 1 ( 3 1 0 ) ( 3 1 1 ) , - o x ( 3 1 2 ) 乃= 1 p k 喜( e 冲卜弘，x ) 】 = 9 + 上p h 喜【e 冲( - p 州堋 ( 3 1 3 ) 【了ij 争。x p p g i ：+ 妒g 妣，ye x p 一p k i x + 妒g ) k ， v 一i i = lx p ( - p ( a r x + q _ 。( x ) ) ) 1 4 e v 2f x ) ：p a 7 日。g n ( 3 1 5 ) 其中， h 。g ) = a g ，p ) 一a g ，p 弘7 g ，p ) a g ，力= 历昭轨。g ，以，；t q ( x ，砌 a g ，) = q ，g ，p ) ，a 。k p ”7 从而得到约束优化问题 m i n 只x ) s t x o e r x = 1 从数值计算方面来说，p 充分大时，瓦g ) 的h e s s e n 阵会产生病态a 是个问题，我们采用文献 2 9 中的自适应参数修正法。 ( 3 1 6 ) ( 3 1 7 ) ( 3 1 8 ) 因此，p 的选取 x口 一 = g 缈 有叵( 大连理工大学硕士学位论文 算法3 2 2 带自适应参数修正的凝聚函数法 ，、 步o ：给定初始搜索区间【o ，a 一】，p fo ，i 1l ，口，1 ) 。取定x o 矗”，x 。 0 ， 二， 口o o ，a 一 ，p 。= l o g 等，y = 1 ，令净o ，k = - o ，a l = 0 ，口2 = a 一，t 为逼 近误差取为1 0 。； 步1 ：计算妒g 。) ，c ，g ，) ，g ) ； 若巴g ) 一缈g ) r ，且l f v 厶g l 2 ，停止； 否则，令最速下降方向 k g ) = 一g ) ( 3 1 9 ) 步2 ：用子程序3 2 2 3 ，计算步长a 1 ； 步3 ：令z h l = 毒+ 口。h p , b ) ； ( 3 2 0 ) 步4 ：进入子程序3 2 2 1 ，运行完后，计算p 7 x 州，令x = x e 7 x ”1 ，转步1 。 子程序3 2 2 1 自适应参数修正【2 9 】 步o ：令s 。= o 0 0 1 ，岛= o 0 2 ，f = o 0 0 0 1 ，令p = 。 步1 ；若睁f ，j g 2 z ，转步2 ； 否则，令p i + l = p ，置f = i + 1 ，停止。 步2 ：若p 量p 且y = 1 ，其中p 满足占。- 声且，= ，令，= m a x 2 ，妻署) ，p 。= y + 2 ) ，k 爿汁，t = 件t ， 停止。 否则，令a + l = r ( 七+ 2 ) ，k = k + 1 ，i = i + l ，停止a 【2 9 】中并未给出具体的确定p 的方法，经过推理及数值实验r 给出程序如下： 子程序3 2 2 2 确定p 满足s 。- a ，转步2 ；否则，令p = o ； 一类严格线性不等式组的解法 步2 ：计算i i 啊g 2 。 若i l v 只g 矿岛，令p 呵，停止； 若l i v 只g 1 1 2 s 。，转步3 ；否则，转步5 步3 ：z m i d = 号子，计算8 v 巴。g 2 ，转步4 ： 步4 ：若屯1 1 w o g 2 - - a l ，则令a = a l ；否则，t ；t = a 2 大连理工大学硕士学位论文 3 2 3 求解问题( d 3 ) 的算法 将问题( d 3 ) 转化为标准的m b i , n a x i 司题为 m m m a x 。h s tb z - - 0 则有 妒g ) _ 。m a x 。h 应用凝聚函数法可得 ( 3 2 4 ) ( 3 2 5 ) 删= ；1t n 偿阱芦1 ) j ) ：妒 + l n 芝【e x p ( _ 比，+ 9 洲 ( 3 2 6 ) pl 百j 从而得到约束优化问题 m i n 只g ) ( 3 2 7 ) s t b z = 0 对问题( 3 2 7 ) ，其中b = ( a , - e ) ，z = ( ：) ，我们有， 定理3 6 设z 是问题( 3 2 7 ) 的一个可行解，使得，= ( z ；，2 二) ，其中b = ( a e ) ，而基 矩阵一e 为口阶负单位矩阵，用i 表示基变量的指标集。令 7 t - - v f ，( z ) 7 一v 一。( z ) 7 ( 一) 一1 b = 1 9 e ( z ) 7 + v 一。( z ) 7 b = ( 巧，：) ( 3 2 8 ) d 7 = ( ，畦) 是按如下方式形成的方向： a ) 对非基变量j 仨i ，令d ，= 一r j b ) 基变量对应的d 一= 一( 一e ) 一a d , i = a d 。 、 若d 0 ，则d 是一个改进的可行方向；而d = 0 的充要条件是z 为k k t 点。 证明： 首先证明d 为可行方向。由( 3 2 7 ) 可知，d 为可行方向等价于b d = 0 。而由庐：( 氏- e ) 可得 一类严格线性不等式组的解法 胁( 妒e ) ( 乏 = 4 办咆一o ， 从而d 为可行方向。 其次证明d 0 为改进的可行方向。 v 。( 暑) 7 d = ( l c ( 力7 ，r r c ( z ) 7 ) ( 乏j = l c ( z ) 以+ r 。c ( z ) 7 t 。 = v 。( z ) 7 + v 一。0 ( z ) 7 a d 。r 丸= o 一= 一，：，2 o 若d 0 ，则办o ，否则，若以= o ，则以。= 彳办= o ，从而j = 0 ，因此可得， v c ( z ) 7 d 0 引入松弛变量：南 0 ，x 4 0 ，则有 f m i n c 5 一而+ x 2 一x 3 = 0 1 4 x a + x 2 一x 4 = 0 【而，x 2 ，x 3 ，x 4 0 取松弛变量，x 。为基变量，可得x ，= 0 ，x = 0 ，代入解得，而= x ：= 0 ，显然不是原 严格不等式组的解，故不可行。 考虑原问题( p ) 有解情形，取逼近误差t 为t 0 。，p o 为初始参数，其中，x f q 题0 d 1 ) ， 成= ；对问题( d 2 ) ，见= l o g q f ；对问题( d 3 ) ，戤= l 。g q + 一n 。为简单起见，a 均取为 q 阶方阵；在m a t l a b 环境下分别对算法3 2 1 、算法3 2 2 及算法3 2 3 做数值实验，所得结 果如下表： 表5 1c p u 时间统计 t a b 5 1s t a t i s t i c st a b l ef o rc p ut i m e q 1 05 01 0 02 0 05 0 01 0 0 02 0 0 0 算 法 0 0 1 8 70 0 9 0 6o 1 6 2 61 2 0 7 98 1 9