（运筹学与控制论专业论文）有界约束整数规划的广义非线性lagrangian方法.pdf

中文摘要 摘要 非线性l a g r a n g i a n 方法是解决有界约束的整数规划问题的有效方法。在 大多数情况下，线性l a g r a n g i a n 松弛方法的强对偶性条件很难满足，从而在 求解此类问题的最优解的过程中会产生对偶间隙。也就是说，传统的线性 l a g r a n g i a n 方法所求的最优解仅仅是原问题的一个下界，而不是原问题的最 优解，从而致使线性l a g r a n g i a n 搜索失效。相比之下，非线性l a g r a n g i a n 方 法针对线性l a g r a n g i a n 这一弱点，能够有效地克服对偶间隙，直接求解到有 界约束整数规划问题的最优解。 目前，已经有一些研究文献针对有界约束的整数规划问题提出了不同形 式的非线性l a g 删1 9 i a n 函数。这些非线性函数都具有近似强对偶性质，从而 保证了该算法通过求解l a g r a n g i a n 对偶问题一定能求解出原问题最优解， 保证了算法的可靠性。 本文基于非线性l a g r a n g i a n 方法的这一优点，在现有的各种l a g r a n g i a n 方法的基础上，研究非线性l a g r a n g i a n 的共同的性质。本文通过构造一族曲 线形成对原问题的最优解对应的点的非线性支撑，根据这类曲线的基本特征 提出了广义的非线性l a g r a n g i a n 方法。通过这一方法，我们可以构造出各种 形式的非线性l a g r a n g i a n i 函数。同时，各种现有的l a g r a n g i a n 函数都是此广 义l a g r a n g i a n 函数的特殊形式。 这些函数都具有上述的非线性l a g r a n g i a n 的近似强对偶性。也就是问题 的l a g r a n g i a n 对偶问题的最优解必定是原问题的最优解。广义l a g r a n g i a n 函 数的另一个重要的性质是，只要参数充分大，不用进行具体的对偶求解，只 需要直接求解松弛问题，就可以得到原问题的最优解。 本文同时为这个广义l a g r a n g i a n 方法提供大量典型算例，证实了该方法 的有效性和可行性。 关键词：非线性整数规划，整数规划，拉格朗日松弛，对偶间隙。 墨奎塑要 a b s t r a c t n o e a r l a g r a n g i a nm e t h o di sa ne f f e c t i v ea l g o r i t h mf o rb o u n d e di n m g e r p r o g r a m m i n g f b rt h es t r o n gl a g r a n g i a nd u a l i t y i s r a r e l yp r e s e n t i n i n t e g e r p r o l z a m m i n g , a n d an o n z e r od u a l i 竹g a po f t t c ne x i s t sw h e nt h el i n e a rl a g r a n g i a n m e t h o di sa d o p t e d t h i sm e a n st h es o l u t i o no fl i n e a rl a g r a n g i a nf u n c t i o ni sn o t t h eo p t i m a ls o l u t i o no ft h eo r i g i n a lp r o b l e m i ti sj u s tal o wb o u n d t h a ti s ， t h el a g r a n g i a nr e s e a r c hm a yf a i lt oi d e n t i f yt h eo p t i m a ls o l u t i o no ft h eo r i g i n a l p r o b l e m s e v e r a ln o n l i n e a rl a g r a n g i a nf o r m u l a t i o n sh a v eb e e nr e c e n t l yp r o p o s e df o r b o u n d e di n t e g e rp r o g r a m m i n g p r o b l e m s w h i l ep o s s e s s i n g 蛆a s y m p t o t i cs t r o n g d u 丑l i t yp r o p e r t y , t h e s ef o r m u l a t i o n so f f e r as i k ：c e s sg u a r a n t e ef o rt h ei d e n t i f i c 撕o n o f a n o p t i m a lp r i m a l s o l u t i o nv i aad u a ls e a r c h i n v e s t i g a t i n g c o m m o nf e a t u r e so fn o n l i n e a r l a g r a n g i a n f o r m u l a t i o n si n c o n s t r u c t i n gan o n l i n e a rs u p p o r tf o rn o n c o m ，e xp i e c e w i s ec o n s t a n tp c r t u r b a l i o n f u n c t i o n ，t h i sp a p e rp r o p o s e sag e n e r a l i z e dn c 咖i n e a rl a g 删蛆f o r m u l a t i o no f w h i c h m a n ye x i s t i n gn o n l i n e a rl a g r a n g i a n f o r m u l a t i o n sb e c o m es p e c i a lc a s e sa n d m a n y c a nb ec o n s t r u c t c da ss p e c i a lc a s e s f o ra l lo ft h e s en o n l i n e a rl a g r a n g i a nf u n c t i o n s ，t h eo r i g i n a lo p t i m a ls o l u t i o n c a nb ei d e n t i f i e dv i at h ed u a lr e s e a r c ho f t h e s en o n l i n e a rl a g r a n g i a nr e s e a r c h o n e o t h e ri m p o r t a n tf e a t u r eo ft h en o n l i n e a rg e n e r a ll a g r a n g i a nf o r m u l a t i o ni st h a tn o a c t u a l d u a ls e a r c h i s n e e d e d w h e n p a r a m e t e r s a r es e t a b o v e c e r t a i n t h r e s h o l d - v a l u e s t h en u m e r i c a lr e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o d i se i 五c i e mi nc o m p u t a t i o ni n s o l v i n g b o u n d e d i n t e g e rp r o g r a m m i n g k e y w o r d s ：n o n l i n e a r i n t e g e rp r o g r a m m i n g ，i n t e g e rp r o g r a m m i n g , l a g r a n g i a n r e l a x a t i o n ，d u a l i t yg a p 一2 主要符号对照表 d ( ”) d p ，( z ) p 9 ( z ) ” l p ( 9 ( z ) ，( z ) ，入) ( a ) 妒( 名1 ) s 矿 x s x 6 主要符号对照表 对偶问题的最优值 对偶问题的最优值，同d ( ”) 目标函数 问题p 的最优解 约束函数 对偶问题的最优解 广义l a g r a n g i a n 函数的通式 对应于a 的松弛问题的值 扰动函数 原问题的可行域 原问题所有的最优解的集合 原问题的不可行域 原问题的定义域 可行集中除去最优解所对应的点之外所有的 点对应的值与最优值的最小差距 第一章引言 第一章引言 1 1 有界约束整数规划问题的描述 1 1 1 整数规划问题 整数规划问题在现代优化理论当中占有重要的地位。在实际生活生产 中，很多问题都要求解答必须是整数的情形。例如，所求解的是机器的台 数，值班的人数，或者装货的车数，背包里边不同物品的件数等等。为了满 足整数解的要求，初看起来，似乎只要把已经得到的分数或者小数舍入化整 就可以了。但这常常是不行的，因为化整后，不见得是可行解，或者虽然可 行，但不一定是最优解。因此，对求解最优化整数解的问题，成为研究领域 中个重大的分支，并且被称为整数规划o n t 唧rp r o g 跚加1 i n g ) ，简称口。整 数规划是最近三十年来发展起来的一个规划论中的重要分支。 整数规划中如果要求所有的变量都为整数，那么就称为，纯整数规 划( n l r ei n t e g e rp r o g r a m m i n g ) 或者称为全整数规划( a l li n t e g e rp r o g r a m m i n g ) ： 如果仅是一部分变量要求为整数，那么称为混合整数规划( m i x e di n t e g e r p r o g r a m m m g ) 。整数规划中还有特殊的形式，如变量只取喊1 ，那么这样的 整数规划称为o - 1 规划。著名的指派问题就是一个典型的0 l 规划问题。 1 1 2 有界约束整数规搀j 问题的模型 如果一个整数规划的定义域是一个有界整数集，并且此整数规划带有约 束条件，那么这样的整数规划称为带约束的有界整数规划问题。本文讨论的 就是此类问题。该类问题可以有如下标准形式： 这里，和吼( z ) ：j p ri = 1 ，m 是连续函数，并且x 是一个有界整数 集，可以看出，闯题p 具有一般性。如果限定，( o ) 和吼( z ) 为线性函数，那 么问题p 就是线性整数规划问题( i l p ) 。如果f ( x ) 和玑( z ) 其中有一者或者 二者都是非线性连续函数，那么问题p 称为非线性整数规划问题。集合x 可 以是一个简单整数集，如，x = o ，1 p ，此时问题p 就是。一1 规划问题。本 文正是针对问题p 这一经典模型，进行研究讨论。 4 d0 m = x嚣 0 1 2 有界约束整数规划问题的应用领域 有界的整数规划问题是优化理论中的经典问题，也是组合优化中的基本 问题。因为，在实际生产生活中，多数优化问题的求解范围都是有一定的限 制的，例如员工人数，车辆数目等。所以，有界性的假设是合理的。同时， 现实生活中多数优化都有一定的限制条件，例如，资源的有限性，完成项目 时间的有限性等。所以，有界约束问题，是实际生产生活中应用非常广泛的 一类问题。由该问题进一步发展衍生出各种闯题在实际生活中都有广泛的应 用。例如资源配置问题【1 4 】，选址问题，非线性背包问题都是有界整数摄划 问题的应用实例。更为广泛的典型应用实例还包括，生产计划【2 5 】，满意采 样 2 】，以及网络的可靠性f 2 0 】等问题。基于此类整数规划的广泛应用，有 界约束整数规划问题的算法可行性和有效性成为研究最优化理论领域中的经 典问题之一。 1 3 有界约束整数规划问题的研究成果 本文针对带约束的有界整数规划问题的算法进行讨论。该问题可以划分 为各种不同类型的问题，例如可分离问题( 背包问题) 等。各类问题针对各自 特点而应运而生了备类算法。在所有的有界约束整数规划的算法中，线性 l a g r a n g i a n ( 拉格朗日) 方法是通用的主流传统算法。此方法的诞生以及发展 可参考 1l 】，【1 9 】， 9 】。线性l a g r a n g i a n 算法的核心思想是将原闯题转化为 i 印a n g i a n 松弛问题，也就是将带约束的问题转化成了一个无约束问题。这 也是最优化理论中常用的方法之一。传统算法对l a g 国n g i a n 对偶问题进行求 解，从而得到的解当作原问题的最优解，或者次优解。 然而传统的l a g r a n g i a n 方法有自身的弱点。这就是，该算法只能保证 第一章引言 为原问题提供下界，并不能保证所得的解就一定是原问题的最优解。当 l a g r a n g i a n 对偶函数的解不是原问题的最优解的时候，产生的两者的差值， 称为对偶间隙。传统的i a g m d 舀蛆方法并不能克服对偶间隙。于是，在最 近几年中相继出现整数规划的各种类型的非线性l a g r a n g i a n 方法【7 】，嘲， 2 u ，【2 3 】， 2 4 j 。这些非线性h g 随喀缸方法推动了l a g r a n g a n 方法的迅 速发展和改善，并进一步洞悉了线性l a g m g i a n 方法的内在特点。 本文针对传统l a g r a n g i a n 方法进行分析，指出线性l a g r a n g i a n 方法存在 的弱点。同时，对现有的各种非线性l a g r a n g i a n 方程进行比较，试图寻找它 们的共同特性，在此基础上，提出一种一般意义上的非线性l a g r 壮g i a n 方 法，称为，广义非线性l a g r a n g i a n 方法。本文将指出该方法的各种特性，并 证明在此方法下l a g m g i a n 对偶间隙将被完全克服，同时指出参数的设定对 于算法求解的简化作用。 1 4 本文结构 本文的结构安排如下。本文在第二章里。分析传统线性l a g r a n g i a n 函 数，阐明研究背景和研究动因。在这一章节里，引入了扰动函数作为辅助 函数，并以实例指出造成线性l a g r a n g i a a 函数失效的原因是扰动函数的非凸 性( n o n c o n v e x ) 。同时对现有的非线性l a g r a n g i = 方法进行比较，从中得到启 发，总结其共性。本文在第三章提出一个广义的非线性l a g r a n g i a n 函数，也 就是本文的中心所在。在这一章里，将会给出对该函数的近似强对偶的性质 的证明，并分析了l a g r a n g i a n 对偶函数的各种特性，之后对它的单峰性给出 了完整的证明。基于前边章节的论证，本文在第四章里给出了充足的算例， 展示了l a g r a n g i a n 函数的单峰性以及本文所提出的广义l a g u a n g m 函数的可 行性合理性。本文在第五章里对全文作了总结。指出广义l a g r a n g i a n 函数的 最主要的两个特性。第一，通过广义l a g r a n g i a n 函数构造出来的l a g r a n g i a l l 函数具有近似强对偶性，郎对偶搜索的最优解必定是原问题的最优解；第 二，由于广义l a g r a n g i a n 特性，只需要设置合适的参数，不需要通过对偶搜 索，直接求解l a g r a n g i a n 松弛问题的最优解，就可以得到原问题的最优解。 一6 一 釜三量焦錾垡丝望壁型坚垡 第二章 传统线性l a g r a n g i a n 方法 2 1 l a g r a n g i a n 方法的诞生和发展 组合优化问题是优化问题当中最重要的分支之一。众多的组合优化问题 都属于整数规划问题凹) 。众所周知，所有的组合最优化问题可以分为两大 类。当中较小的一类是容易求解的问题，这类问题可以在多项式时间内求 解。但组合优化中绝大多数问题都是”难问题”，也被称为n p 问题。这一类问 题在较差的计算情况下，现有的所有算法都需要指数次计算时间才能求解。 然而，在这些”难问题”中，也有一些问题相对容易。例如，背包问题，在一 定的有界约束下，此问题有近似多项式算法。7 0 年代，在算法研究领域中一 个非常重要的优化算法研究思路是将罐问题 通过约束条件的限制而转化为 相对容易求解的问题。 对于有界约束的整数规划问题，线性l a g m g i 柚方法成为实现这一转 化的主要方法。线性l a g m n 廖姐算法的主要思路是通过把约束问题转化成 为无约束的l a g r 趾g i a a 函数，通过求此函数的对偶闯题的最优解而求解原 问题。这样的方法相较求解原问题要容易得多。在算法研究领域中，对偶 l a g r a n g a n l b 题的最优解至少可以在分支定界法在求解原整数规划问题的时 候为该算法提供一个下界，从而改善了分支定界法的求解效率。我们可以看 到，l a g r a n g i a n 方法为线性规划的求解提供了很多重要的改善 9 】。 l a g r a n g i a n 对偶理论在带约束的最优化问题中起着举足轻重的作 用。1 9 7 0 年，l a g r a n g i a n 方法诞生。h e l d 和勋i p 1 2 】用动态规划算法求 解t s p ( t r a v e l i i n g s a l e s m a n p r o b l e m ) 的时候，在求最小生成树的过程中他们提 出了l a 鲋m g 洫方法。这标志着l 唧n g i a i l 方法诞生。h e l d 和h a r p 成功地将 ia g 髓n 百a n 方法应用于用动态规划求解最小生成树的过程。在h c l d 和k a r p 的 启发下，7 0 年代初期，l a g r a n g i a n 方法应用于排队论( f i s h e r , 1 0 1 ) ，后来推 广到般的整数规划问题的求解中( s h a p i r o 【1 8 】) 。l a g m g i a n ：方法为各种组 合优化问题提供了有效的下界，从而改善了各种算法的有效性，有助于符合 实际应用规模的问题的解决。l a g m g i 姐算法的这一优点促使l a g r a n g i a n 方 法在今后的几十年中得到蓬勃发展【9 】。 之后，很多运筹学家( b l a i ra n dj c r o s o w1 9 8 2 ，f i s h e r1 9 8 1 ，o u i g n a r aa n d k i m1 9 9 3 。w i l l i a m s1 9 9 6 ) ，对t a g r a n g i a 耐偶理论在线性整数规划中的运用 都作了深入的研究。同时，l a g r a n g i a n 对偶理论也被引入到非线性整数规划 问题的算法中( m i e h e l o n a n dm a c u l a n1 9 9 1 ，1 9 9 3 ) 。对偶是整数规划中一个非 一1 一 墨三童鲎笙垡丝垒磐蒸坚查鲨 常重要的概念。它把问题的约束条件在l a g m g i a n 乘子的作用下将原问题转 化为无约束的l a g r a n g i a n 松弛问题。之后很多运筹学家针对对偶理论和算法 进行了更加深入的研究，例如， 1 5 】， 3 】，【1 3 】。其中，许多优化算法都与 l a g r a n g i a n 对偶方法有关。l a g r a n g i a n 对偶松弛方法同样也在一些非线性整 数规划中所应用，见【1 7 】， 1 6 】。l a g r a n g i a n 对偶松弛方法被广泛应用于整 数规划当中，( 见，【9 】，【1 2 】，【1 1 ，【1 9 】) 。 至此所提到的l a g r a n g i a 耐偶方法都是在l a g r a n g i a n 乘子的作用下， 将所有约束条件进行线性组合，所以也称之前的l a g r a n g i a n 方法为线性 l a g a n g i a n 方法。 2 2 线性l a g r a n g i a n 方法的描述 在这一节里，我们将给出l a g r a n g i 松弛方法的数学描述。我们首先引 入一个非负的l a g m 9 6 n 变1 ) , 。设r ? = a i 丸o ，t = 1 ，m ) t 我们得到 原问题( 1 1 ) 的对偶松弛问题工： ，拜 ( l ) 爷( ) = ：投l 扛，可) = ，( 茁) + 凡骗扛) ( 2 1 ) 一 扛l 原问题( 1 1 ) 的松弛问题把约束问题转化成为一个无约束的最优化问题。容易 看出，对于任何的a r 譬，问题( l ) 都是原问题( 1 1 ) 的一个下界。 相应的，l a g r a n g i a n 对偶问题定x 如- f , ( d ) 州) 2 。m a 船x 毋( 1 ) ( 2 2 ) 可以看出，对偶问题( d ) 求解原问题的( 1 1 ) 的最大下界。对偶问题d 又称 为对偶搜索。 不失一般性，我们不妨假设m , i n z e x f ( z ) 。 o | 氟毒m 。 h a 曲b n 邮f e 越m 。 q一023 5 i 图1 成功的对偶搜索的图示 图1 针对例l ，将x 上的每一个点对应图像( 9 ( z ) ，( z ) ) 映射到( 丑，z 2 ) 平 面上而得到的。由于x 是一个整数集，所以( 9 ( z ) ，( z ) ) 的图像是一些离散 的点。而直线忽+ ”2 ：1 = d 就是对偶搜索( 2 2 ) 的结果。从图上可以看出， 该问题的对偶搜索恰巧能够搜索到原问题的最优解矿= ( 1 ，2 ) 对应的映射 点p + 。该直线与矿相交，并且在所有( 9 ( z ) ，( 茁) ) ，z x 的点中，矿是z l 负 一9 一 r a i n ，( z ) = o 2 ( 2 ：1 3 ) 2 + 0 1 z ) ) 2 5 ) 2 + 0 1 ( 2 4 ) s ，t 9 0 ) = 茁：一2 5 x l + 1 2 x 2 1 0 霉x = z 【o ，3 】2 i z l ，x 2 ，i n t e g e r 图2 例2 的对偶搜索的图示 图2 的定义方法与图1 相同。其中离散的点同样是区域x 上所有点对 应的( 9 ( ) ，( z ) ) 映射到( = 1 ，砘) 的平面图像。其中直线z 2 + ”z l = n 就是 问题( 2 4 ) 的对偶搜索的结果。而妒( 。1 ) 是扰动函数，其定义为，妒) = m i d f ( = ) ：9 ( 写) s2 l ，z x 。从图上可以看出，扰动函数是一个分 段常数函数。很明显，在这张图上，p = ( 一0 1 ，1 8 ) 是原问题的最优 解矿= ( 1 ，2 ) 对应于这个映射下的点，且最优值是，( 矿) = 1 8 。另一方 面，由于问题d 最优的l a g r a n g i a n 乘子”对应的l a g r a n g i a n 对偶函数的值 是咖( ) = 4 3 3 0 1 4 3 3 0 。 相应地，我们引入一个非负的i a g 陷n 画觚乘子a 0 ，根据传统的线性 i _ a g r a n 西a n 方法所得到的l 姆加咖松弛问题为： 妒( a ) 2 骝l ( z ，a ) 一他) + ( ) ( 3 _ 3 ) 相应地，如下的l a g r a n 删偶问题是一个求解关于a 的最大化问题： 平a 曼【( a ) ( 3 4 ) o 1 3 一 蔓三童墨韭些丝垡g 塑耍磐里墼 在各种研究a n g i 趾方法的文献中给出了不同非线性l 删越松弛问 题。这些松弛问题( 3 3 ) 以非线性函数的形式出现。所以把它们称为非线性 l a g r a a g i a n 方法。 3 1 扰动函数 在这一节里，我们将要给出关于问题( 3 1 ) 的扰动函数的定义，研究扰动 函数的相关性质。通过对扰动函数函数的研究，我们可以从一个新的视角洞 悉非线性l a g r a n g i a n i 蟊数自身的特性。 问题( 3 1 ) 的扰动函数定义为，对于z 1 r ： 妒( 。1 ) = n l m ，( z ) ：g ( x ) z 1 ，z x ) ( 3 5 ) 其中，妒( ) 的定义域为： f = 。l r ：存在。x 满足，9 ( z ) z l ， 由于x 是一个有界整数集，容易得知，函数妒( ) 是一个关于z l 的非增的 分段连续的常数函数，令= = ( 石1 ，勿) ，并在舻中定义一个集合： e = 0 ：砘= 1 ； ( 以) ，2 ：1 f ) ( 3 6 ) 根据( 3 6 ) ，e 定义了一个定义域为f 的函数妒涵) 。其函数图像如图4 所示，见下页。从几何意义上来说，e 是一个在平面( z l ，z 2 ) 上，基于映 射( g ( z ) ，( 。) ) 的关于x 的一个下包络。我们可以明显看到，原始最优解点 的图像矿是e 上的一个点。并且是分段函数中某一段常数函数的左端点。 根据问题( 3 1 ) ，矿所在的这一段常数函数，其很坐标应该包含0 这个点。换 句话说矿的横坐标z 1 ，必定有z l 0 。为了找到这个原问题的最优解所对 应的点矿，我们需要构造一类非线性函数，使得此函数的下凹馥线正好支撑 到e 上的点矿。 1 4 似目舳) ) p ： 一夕” ；一 图4 扰动函数妒( 。1 ) 的图像 以往的研究文献提供了一些非线性l g r a n g i 确数的形式。例如，s u n a n d l i 2 1 】构造了如下的非线性h g r a n g i 蛆函数： c ；( z l , z 2 , ：9 = ；1l n ；( 唧) + e x p 。沁1 ) ) ， ( 3 - 7 ) 其中p 是一个参数，而a 0 是非线性l a g r a n g i a n 函数的l a g r a n g i a n 乘 子。对于任意的以及任意a o ，由曲线诺( z l ，忽，a ) = 口确定的z 1 的定义 域为( 一o o ，( 1 n ( 2 ) p + 口) a ) 。从而，我们可以推出，在曲线噼( z l ，砘，a ) = o t 上的任意一点( 2 l ，z 2 ) 的斜率为： 磊d z 2 = 一蔗a 2e x p ( p ( o , 丽a z l ) 1 ( 3 8 ) 出1 一) 一 、7 进丽，由公式( 3 ，8 ) ，我们可以推出如下的性质： d = z 一2 0 ，z l ( 一。o ，( 1 n ( 2 ) p + 口) a ) ， ( 3 9 ) _ d z 2 。0 ，p o o ，。l ( 一o o ，a a ) ， ( 3 1 0 ) 挈一一o 。，a o o ，z l ( o ，( 1 ( 2 ) 居+ 口) a ) ( 3 1 1 ) 1 5 一 图5 ，非线性【a g 黜昏蛆曲线关于参数p 的变化 而在研究非线性l a g r m 舀趾理论的文献x ua n d l i 【2 4 】中，提出了另一种 非线性l 卿g i a n 函数的形式： 邱( g ( z ) ，。) ，a ) = ，( 石) + ；e 印( a g o ) ) ，a p o 我们将( 9 ( z ) ，( 茹) ) 映射到平面z l ，z 2 ) ，得到另一曲线： 四，炉现+ 号半，入p o ， ( 3 1 2 ) f 3 1 3 ) 其中p 是一个参数，同时a 是此非线性l a g r d a g i a n 函数的乘子对于 任意的以及任意a p 0 ，由曲线四( z l ，忽，入) = a 确定的7 - 1 的定义域 为( 一o o ，警竽) 。从而，我们可以推出，在曲线c ；，砘，a ) = a 上的任意一 点( z 。，沈) 的斜率为： 娶：一e x p ( 概) 出l 1 、“ 1 6 一 ( 3 1 4 ) 图6 曲线将趋近于直角h 公式( 3 1 4 ) 同样具有( 3 8 ) 类似的性质： 璺 o 趣( 一。，娑生) ， a z 1 娑_ 0 ，p _ o 。，。1 ( 一o o ，o ) ， 名1 瓦d z 2 一一o o ，a 一。o ，z - 刊- 州- - t - - ) ( 3 1 5 ) ( 3 1 6 ) ( 3 1 7 ) 从以上两个非线性l a g r a n g i a n t 亨程( 3 7 ) 和( 3 t 3 ) ，我们可以观察到一些 类似的性质。( 3 9 ) 和( 3 1 s ) 中，当a 0 时，砘都是一个在定义域内，关 于以严格递减函数。而且从( 3 1 0 ) 、( 3 “) 、( 3 1 6 ) 和( 3 1 7 ) 可以看出，当z l 喊者盈 0 ，g ( z l ，z 2 ，a ) 关 于。1 和z 2 严格递增。 如果a q ( 。l ，z 2 ，a ) a 砘具有正的下界，j j 吆( 3 1 0 ) 和( 3 1 6 ) 表明，当p o o 的时候，a q ( z l ，z 2 ，a ) o z l 0 。这意味着，当p 取一个足够大的数 的时候，g ( z l ，忽，a ) 将独立于盈。 相应于( 3 1 1 ) 和( 3 1 7 ) ，对于任意z x s ，当a 一十o 。时， 嚣鬃黻一o 。如果a g ( 。- ，砘，a ) a z 2 有严格的正下界，那么，对 于任意茹x s ，当a 一+ o o 对，必有a o ( 礼z 2 ，a ) o z x 一+ o o 。这 表明，对于任意z x s ，当a 一+ 。o 时，必有c ；( z l ，。2 ，a ) 一。o 根据以上我们所期待的非线性支撑函数曲线应该具有的性质，我们自然 地想要构造这样的函数。 一1 8 一 苎三童墨i 璧丝垒壁! ! 唑里墼 3 2 广义l a g r a n g i a n 函数 依照上一节对扰动函数和曲线支撑的分析，以及已有文献中的非线 性l a g r a n g i a n i 函数的启发，我们将在这一节里边提出一种广义的非线性 l a g m g i a a 函数( g e n e r a l i z e dl a s r a n g mf u n c t i o n ) 简记g l f ，并且证明它的近 似强对偶性质。 从上一章的分析当中，广义的l a 乎a n g i a n 函数( g l f ) 应该具有如下性质： 对于任意z x 只当a 趋于无穷时，g l f 也相应地趋于无穷； 对于任意z s ，当p 足够大的时候，g l f 并不依赖于g ( x ) 的取值。 可以看到，只要p 取足够大的值。我们让g l f 收敛于，( o ) ，那么g l f 就 就不依赖于9 ( 岔) 。现在，我们来给出g l f 的定义。 定义1 ：关于参数p 0 ，a 0 的连续函数岛0 ( 苫) ，( 功，a ) 如果满足以下两 个条件，那么称此连续函数为广义l a g r a n g i a n 函数( g l f ) ： ( i ) 对于可行集中任意一点z ，即对任意茁s ，当p o o 时， 有上，( 9 ( z ) ，( ) ，a ) + f ( x ) ( i i ) 对于非可行集中任意一点幽即对于任意的z x s ，当a o o ， 有k ( g ( 。) ，( z ) ，a ) 一+ o o 从定义1 ，我们可以看到，传统的线性l a g r a n g i a n i 蟊数l ( 卫，a ) = ，( 茁) + 幻( 茁) 并不是一个g l f ，因为定义中的条件( i ) 并不满足，例如，对于任 意z s ，l ( x ，a ) 产，( z ) 。现在我们列出一些g l f 的实例。容易看出，以 下的这些例子，都满足定义1 的两个条件。所以，它们是g l f 的实例，都 具有g l f 相应的性质。 例3 ：由s u n a n d l i 2 1 1 定义的，问题( 3 1 ) 的对数一指数l a g r a n g i a n 函数为， 岛( 9 ( 吐m ) ，a ) = ；h 巴( 唧砌+ 唧晒瑚) ， 其中a 0 ，是一个g l f 。 例4 ：f 1 3 x ua n dl i 【2 4 】给出的指数l a g r a n g i a n 函数， l p ( g ( z ) ，( z ) ，a ) = ，( z ) + e x p ( 蛔( z ) ) ，a p 0 ， 蔓三童墨韭垡壁垫竺垂坚里墼 也是一个g l f 。 例5 ：s u na n d l i 在 2 2 】中所提出的对数指数惩罚函数， l p c g ( 。) ，( 石) ，a ) = ，( z ) + 鲁l 【1 + 中( a 9 ( z ) ) ， 也是一个广义l a g r a n g i a n 函数g l f 。 例6 ：以下这个函数，同样也是g l f ： 工p ( 9 ( z ) ，( z ) ，a ) = 矿( 茹) 9 + e 印( p a g ( 。) ) 】； 以上4 个例子都是广义工鸺删】醇m 函数的实例，都满足定义1 。根据定义1 对 g l f 的定义，我们不加证明地给出如下的引理。 引理l ： ( i ) 对于给定的s 和任给一个 0 ( e 为任意小的正数) ，存在一 个p ( 。，s ) 0 使得对于任何p p ( z ，) 有， ，( z ) 一s k ( g ( 霉) ，( z ) ，a ) ，( z ) + g ( 3 1 9 ) ( i i ) 对于给定的z x s 和任给一个m 0 ( m 为任意大的正数) ，存 在a ( 。，m ) 0 使得对任何 入( z ，m ) 有， 工p ( 9 ( 茁) ，( z ) ，a ) 2m ( 3 2 0 ) 关于问题( 3 1 ) 的，基于g l f 的l a g r a n g i a n 松弛问题定义为： 如( a ) ：2 必岛( 9 ( z ) ，m ) ，入) ( 3 2 1 ) 如( a ) 也被称为对偶函数。进而，相应的，关于问题( 3 1 ) 的基于g l f 的l a - g r a n g i 粗对偶问题定义为： d p ：2 妥鬈如( 入) ( 3 2 2 ) 我们将要证明由定义1 ，0 2 1 ) 和( 3 2 2 ) 给出的广义l a g r a n g i a n i 蟊数的近似 强对偶性。即对偶问题的最优值收敛于原问题的最优值。为了说明方便，我 们记 ，+ 2 磐m ) z j 由假设2 ，我们得到f + 0 。 一2 n 一 定理3 1 ：( 近似强对偶性) 设岛( 9 ( z ) ，( z ) ，入) 是一个广义l a g r a n g i a n i 甬数( g l f ) 并且 p 定义 由( 3 2 1 ) ，( 3 2 2 ) 给出，那么 l i r ad 。= f + ， 。o 证明： ( i ) 如果s = x ，那么从( 3 2 1 ) ，( 3 2 2 ) 以及引理l 的第一部分，可以很容易地 得到，u 斗。d p = r n l n z e $ y ( x ) 。 ( i i ) 设x s o ，同样的，通过引理l ，对于任意给定的 0 以及足够大 的p ，我们有， d p 2 i d ，8 。x m 。i x l ll a g ( ? ) ，他) ，a ) s 鼍野m 剃i n ( 9 ( 茹) ，他) ，a ) 兰m 瑚a x m 删i n ( f ( x ) + 6 ) = 厂+ ( 3 2 3 ) 我们称，对于任意p 0 ，存在a 0 便得 x m x i n 8 k ( g ( 茹) ，( z ) ，a ) 磐如( g 扛) ，( z ) ，a ) ( 3 2 4 ) 反证法，假设对于不存在a 0 ，使得( 3 2 4 ) 成立。那么，对于任何 的 0 ，我们有 d p 如( a ) = m i a 州m i n 、。l p ( g ( x ) ，m ) ，a kr a 螂i n 乓( g ( 霉) t 他) ，a ) ) = 蕊驰( z ) ，他) ， ) ( 3 2 5 ) 令m ：广+ 2 e 。从引理1 ，妇x s ，存在天 0 使得 岛( g ( z ) ，( z ) ，天) 广+ 2 e 。令入= 又，由( 3 2 5 ) 我们得到 d p 热o ( g ( z ) ，m ) ，天) ，+ + 瑟( 3 2 6 ) 公式( 3 2 6 ) 与( 3 2 3 ) 矛盾。因此，必定存在” 0 使得( 3 2 4 ) 成立。再根 据引理1 的( 幻以及3 2 4 ，我们得到 一2 l 一 岛 = = 如( r ) 衄 姜鼎k ( g ( z ) ，m ) ，r ) r a 础i n l d g ( 茹) ，m ) ，”) ) m 删i n l p c g ( x ) ，他) ，”) ，+ 一5 ( 3 2 7 ) 综合( 3 2 3 ) 和( 3 2 7 ) 得到，对于任意 0 以及一个充分大的p 0 ， 成立。从而命题得证。 f 一s d p s r + 口 定理3 1 指出，当p 趋于无穷大的时候，l a g r a n 画姐对偶问题的最优值一 定收敛于原问题( 3 1 ) 的最优值。需要注意的是，为了在计算中实现该算法， 我们更加关注是否当p 取一个有限值的时候，对偶搜索能够达到原问题的最 优解。这样，只要参数p 大到某一程度，原问题( 3 1 ) 的最优解就可以由广义 非线性函数的最小化求解而得到。从而避免了对偶搜索的计算复杂性。我们 将在以下的分析中，逐步证明广义l 嘞n 百a n 函数的这一性质。 为了说明方便，我们给出以下两个记号， s + = z s ：，( 。) = ，+ ) ，记为最优解的集合记； 占；m i n ，( z ) ：z s s + ) 一，记6 出去可行集中的最优解外所有的点 对应的值与最优值的最小差距。 引理2 ：存在p + 0 对于任何p 矿，l a g 咖g i 姐松弛问题( 3 2 1 ) 的任一最优 解矿，如果此最优解是原闯题的可行解，即矿s ，那么矿必定是原问 题( 3 1 ) 的一个最优解。 证明：由引理1 的第一部分以及定理3 1 ，取定e = ，存在p + 使得对于任 意p p 有， 于是， f ( x + ) 一岛0 ( z + ) ，f ( x + ) ，a ) ：斛m i n 三p ( 9 0 ) ，m ) ，a ) ，+ + 6 ，( 矿) 一，+ 2 e = 根据6 的定义，矿s + ，命题得证。 口 3 3 对偶函数的单峰性 在这一章里边，我们将继续探索广义l a g m g i 函数l p c g c x ) ，( 。) ，a )