（计算数学专业论文）求解dc规划的全局收敛性算法和近似点算法.pdf

南京航空航天大学硕士学位论文 摘要 d c 规划是一类重要的非线性规划，具有特殊的结构( 可表为两个凸函数的 差) ，在经济和工程等领域有着广泛应用，我们所熟知的不定二次规划及广义几 何规划就属于d c 规划。本文主要研究d c 规划的理论和算法。第二章利用t a o 提出的d c a 算法并结合分枝定界技巧提出了种解d c 规划的全局收敛性算法， 对于此算法的收敛性文中给出了理论性证明，并且数值试验也表明此算法是叫 行的。作为应用新算法应用于解决不定二次规划以及广义几何规划，从而u 三为 这两类重要的非线性规划的求解提供了新的途径。第三章针对非光滑时的情形， 在s u n 给出的近似点算法的基础上运用b r e g m a n 函数提出一类修正的近似点算 法，并且证明了这类算法的下降性及收敛性。这类算法不仅能够用来解决无约 束d c 规划问题，而且当所给出的b r e g m a n 函数为边界强制的情况下，这种傅法 能用来解决带凸约束的d c 规划问题，当所给出的初始点为约束集合的内点时， 则由算法所得到的点列均为约束集合的内点，则此算法实际为一内点算法。最 后对一类求解凸舰划的修f 近似点算法进行了一些技术上的改进，并给出了收 敛性和收敛率的l l e 叫。 关键词：全局最优化d c 函数， d c 舰划，算法。 求解d c 规划的全局收敛性算法和近似点算法 a b s t r a c t i ti sw e l lk n o w nt h a td c p r o g r a m m i n gi s a ni m p o r t a n tn o n l i n e a rp r o g r a m m i n g n o wm o l ea n dm o r ea t t e n t i o nh a v eb e e n p a i d o ni tb e c a u s eo fi t sb r o a d i m p l i c a t i o ni n e c o n o m ya n de n g i n e e r i n g i nt h ec h 印t e rt w oo ft h ep a p e rw ec o m b i n e dd c aw i t h b r a n c ha n db o u n d a l g o r i t h m ，o n en e wa l g o r i t h mw a sg i v e n a n db o t hi nt h e o r ya n d n u m e r i c a le x a m p l et h en e w a l g o r i t h mh a sb e e np r o v e dt ob er i g h ta n de f f i c i e n t a s t h e i m p l i c a t i o nt h en e wa l g o r i t h mc a nb eu s e dt os o l v et h eu n d e f i n i t e dq u a d r a t i c p r o g r a m m i n ga n dt h eg e n e r a l i z e dg e o m e t r yp r o g r a m m i n g o nt h eo t h e rh a n d ，t h e r e a s o n w h y t h ed c p r o g r a n u n i n g i s p a i d s om u c h a t t e n t i o ni s b e c a u s eo fi t sn o n s m o o t h i nt h ec h a r p t e rt h r e eo f t h ep a p e r , o n em o d i f i e dp r o x i m a l p o i n ta l g o r i t h m u s i n gb l e g m a nf u n c t i o nf o rs o l v i n gd c p r o g r a m m i n g ，t h a ti sb a s e d o nt h eo n e p r o p o s e db ys u n t h ea l g o r i t h mi s p r o v e d t ob eb o t hd e s c e n t a n d c o n v e r g e n t f u r t h e r m o r et h ea l g o r i t h mc a r ln o t o n l y b e a p p l i e d t os o l v et 1 1 e u n c o n s t r a i n e dd c p r o g r a m m i n g ，b u tt h ec o n v e xc o n s t r a i n e do n ew h e nt h eb r e g m a n f u n c t i o ni sb o u n d a r yc o e r c i v e w h e nt h ei n i t i a lp o i n tc h o s e nl i e d i nt h ei n t e r i o r0 1 t h ec o n s t r a i n e ds e t i tc a r lb ep r o v e dt h a tt h es e q u e n c eg o tf r o mt h ea l g o r i t h mt o t a l l y b e l o n gt ot h ec o n s t r a i n e ds e t s ot h ea l g o r i t h mc a na l s ob es a i dt ob eo n ei n t e “o r p o i n ta l g o r i t h m i nt h el a s t ，o n em o d i f i e dp r o x i m a la l g o r i t h mf o r s o l v i n gc o n v e x p r o g r a m m i n g i sm o d i f i e di nt e c h n i q u ea n dt h ec o n v e r g e n c ea n d c o n v e r g e n ts p e e do f t h en e w a l g o r i t h mi sp r o v i d e d ， 、 k e y w o r d s ：t h eg l o b a lp r o g r a m m i n g ，d cf u n c t i o n ，d c p r o g r a m m i n g ，a l g o r i t h m 承诺书 本人郑重声明：所里交的学位论文，是本人在导师指导下，独立 进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容 外，本学位论文的研究成果不包含任何他人享有著作权的内容。对本 论文所涉及的研究工作做出贡献的其他个人和集体，均己在文中以明 确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：星丝遣 日期： 赵：圣。珏 南京航空航大人学硕士学位论文 第一章绪论 d c 规划是一类重要的非线性规划，在经济、工程等领域有着广泛的应用。 下面将分别就d c 规划的引入，求解d c 规划的算法和本文主要工作进行讨论。 1 1d c 规划 设r 0 ( r “) 表示定义在r ”上的凸函数的全体，如果存在g ，h r 0 ( 月) ，使 函数，：r ”一月可表为 f ( x ) = g ( x ) 一 ( x ) ，x r “ 则称函数，为d c 函数，称g ，h 为厂的d c 分解。最优化问题 m i n 厂( z ) 称为无约束d c 舰划。 “设函数，：r ”_ r ( f = l ，优) 均为d c 函数，称最优化问题 f m i n厂( x ) 5 1 厶，( x ) i ， l研= l ，m 为约束d c 规划。 无约束d c 舰划和约束d c 规划统称为d c 规划。 d c 规划是一类重要的非线性规划，其目标函数和约束函数具有特殊的结构。 因而在经济，工程等领域受到人们的广泛重视。实际上我们所熟知的许多最优 化问题都是d c 舰划的一种特殊形式。 考虑广义几何规划 i r a i n疗o ( x ) ( s g p ) 旺片。，( z ) 1 ， lm = l ，m 其中 7 一 ， 。( 工) = 正。c 。+ 兀咿， 棚= o ，l ，m ， p 。i，i 占= + l 或一1 ，”= l ，一，m ，k = 1 ，一，r 。： c 。为正常数，。，为任意实常数，瓦，为任意正整数。 广义几何规划问题( s g p ) 在很多领域例如在风险管理和不同化学工程设 求解d c 规划的全局收敛性算法和近似点算法 中有着广泛的应用( 见 1 - 7 ) 。尽管几何规划己提出多年，但有效的算法并不 多见，特别是全局解的算法远没有得到解决。几何规划的理论和算法依然吸引 着众多学者的关注。 运用指数变换 x = e x p ( y t ) ，七= 1 ，一，h ， 则( s g p ) 问题等价于下面的d c 规划， i m i nk ( y ) ( p 1 ) “t甲。( y ) 1 ， lm = l ，一，m 其中 甲。( y ) = 皖。c 。e x p ( ，。“y ) m = o ，1 肼 令 巴i _ 恤：占，“= 1 1 k 疋 ，n 。| ：恤：瓯“= 一1 ，1 女l ) m = o ，1 ，m 甲。( y ) ：= 甲：( j ，) 一甲：( y ) ， 其中 甲枷) = c 。e x p ( y r 。，) ，吆( y ) ：= e x p ( 芝，y ，) ，e 0 1 z i ，e 。 ，= i 因为函数e x p 0 ) 为凸函数，c 。均为于数，则甲：与甲：，朋= o ，1 ，m 均为凸函 数，因此问题( p 1 ) 实际为d c 规划。 考虑不定二次规划 ( o p ) m i n 鳊( 趴= 三 一g ( x ) ：x r ” ( ) = s u p 一 ( x ) ：x 尺“ 下面给出d c a 算法： d c a 算法 s 1 设s 0 为取定的任意小的正数，取初始点x o r ”，y o a h ( x 0 1 ： s 2 求解x “1 与y “，其中x “1 与y “分别为凸规划问题( p 。) 与( d 。) 的解， 其中 ( p )m i n g ( x ) 一 h ( x ) + 】：x r ”】 ( d )m i n h ( y ) 一【g + ( y ) + ：y r ” s 3 如果忙“一x 0 s 或者g ( “) 一矗o “) g ( x ) 一 ( x 。) 一则停e 迭 代，x “即为所求近似最优解：否则令k ：= k + 1 ，转s 2 。 注：当凸函数疗为可微时，o h ( x ) = v 0 ) ，d c a 算法的迭代点x “。可通过 求解d c 规划的全局收敛性算法和近似点算法 求解下面的最优化问题得到( 见 1 8 2 1 ) ， m i n g ( x ) 一 h ( x ) + 】：x r ” 记p ( g ) 是强凸函数g 的强凸因子，当g 为一般凸函数时规定p ( g ) = 0 。对 于d c a 算法的性质，有下面的定理 定理一8 。2 1 ( i ) 序列k o 。) - h ( x ) 与协( y ) 一g + ( y ) 均为递减的，且 ( 1 ) g ( x “4 ) 一h ( x “1 ) = g ( x ) 一h ( x ) 充要条件是 y o g o “) n o h ( x “。) 和【p ( g ) + p ( ) x “。一x “l f = 0 ( 2 ) h ( y “) 一g ( y “1 ) = h ( y 。) 一g ( _ y ) 充要条件是 x “o h ( y “1 ) n g ( y “1 ) 和 p ( g ) + p ( 矗+ ) j ，“一y l = 0 。 ( i i ) 序列扛。 ( 涉 ) 的每个聚点x ( j ，+ ) 为g h ( h + 一g 。) 的关键点。 ( i i i ) 如果 p ( g ) + p ( h ) 0 ( p ( g ) + p ( h ) 0 ) ， 那么序列肛“1 一x ( 眇“一j ，咖收敛。 ( i v ) 如果目标函数在d c a 聚点的邻域内为凸有限的，而且其第二个d c 元 在这一点处为可微的，则此点为原规划问题的局部最优点。 ( v ) 当，。= g h 为凸函数时d c a 算法收敛到原规划问题的全局最优解。 这些年d c a 算法无论从理论还是数值试验方面都已经得到逐步的完善( 见 2 2 2 3 ，2 5 ) 。对于一般的d c 最优化问题，数值试验显示d c a 算法具有f 列 特点： ( 1 ) 算法经常会收敛到原问题的全局解： ( 2 ) 算法能够在较短的时间内解决大型问题； ( 3 ) 算法能用于解决非光滑问题( 见 2 7 ，2 8 ) 。 由此知d c a 算法是一个很好的算法。 近似点算法主要是用来求解凸规划问题 m l n m 舻烈x ) 其中g ( x ) r 。( r ”) ，g 不一定可微。 经典近似点迭代为 r ，、 x f * l = a r g m i n x e r i s ( 小i x - x k 阱 l 。k j 或表为 x ( i + “a g ) “坼 南京航空航大人学硕士学位论文 其中i 为单位映射，融( x ) 表示函数g 在点x 处的次微分。容易证明当以+ = 屯时， 有o o g ( x 。) ，从而得到原规划的最优点吒。r o c k a f e l l a r 3 0 1 详尽讨论丁经典 近似点算法的收敛性。 1 9 7 6 年，l m b r e g m a n 引吲入了b r e g m a n 函数的概念，在此基础上c e n s o r 和l e n t 堪1 定义了b r e g m a n 距离。利用b r e g m a n 距离，b u r a c h i k 和s c h e i m h e r g 给出了下面的修诉近似点迭代 以+ i = a r g r a i n 凡( j ) + 口( t 屯) 或 0 a g ( x ) + 五( v l ( x ) 一v l ( x k ) ) i 。 其中d ，( x ，y ) 表示x ，y 间的b r e g m a n 距离，f ：彤啼r 为b r e g m a n 函数， 0 为 常数。当，( x ) = ：时，则此修币的近似点算法就是经典的近似点算法。从而 得到原规划的最优点x “。r s b u r a e h i k 和a n u s e m 对修讵的近似点算法进 行了细致研究。 1 3 本文主要工作 本文主要研究【) c 觇划的理论和算法。 目f j f 求解d c 觇划的局部优化方法有多种陋。7 】，而对d c 规划的全局优化力 法却很少，已有的全局优化方法都是针对d c 规划的特殊形式进行讨论的，例如 二次规划，广义) l f a l 】j l 划等【1 2 1 】。这些方法大多采用不同的定界技术，但f 1 9 2 1 中的定界技术难以处理一般d c 规划问题。基于以上考虑，本文将研究d c 觇划 的全局优化方法。本文将给出一个新的定界技术，对d c 规划问题提出了一个全 局优化算法。利用d c 函数的固有性质，对目标函数和约束函数进行下界估计， 建立d c 规划的子问题。通过对子问题可行域的细分以及一系列子问题的求解过 程，证明了在最优解存在的条件下，算法能收敛到d c 规划的全局最优解。与f 1 9 - 2 l i 的算法相比，本文提出的方法不但能解决二次规划和广义几何问题还能用求 求解一般d c 规划问题，而 1 9 2 1 】中讨论的问题只是本文的特殊形式。数值试验 表明方法是可行的。 另外，本文还将列s u n 2 6 1 所提出的算法用b r e g m a n 距离进行修正，与f 2 6 】 的算法相比新方法不仅能够用来求解无约束d c 规划问题，而且町用来求解带j j ，l 约束d c 规划问题，而 2 6 】的算法只是新算法的一种特殊形式。 求解d c 规划的全局收敛性算法和近似点算法 最后本文对求解凸规划的修f 近似点算法进行了一些技术上的改进，并给 出了改进后算法的收敛性和收敛率。 本文是按如下顺序安排的：第一章是绪论部分，首先介绍d c 函数和d c 规 划的定义，接着介绍了要用到的两个主要算法，最后介绍了本文的主要工作。 第二章和第三章是本文的重点。求解d c 规划的全局优化方法在第二章给出，首 先讨论了应用d c a 算法求解带凸约束的d c 规划问题，接着给出了求解带箱约 束d c 规划的全局收敛性算法，最后提出求解带一般约束d c 规划的全局优化方 法，并证明了当d c 规划存在最优解时，算法收敛到d c 规划的全局最优解。第 三章给出了求解d c 规划的修正近似点算法，先介绍了与求解d c 规划有关的一 些定义及相关的定理和推论，接着提出了求解d c 规划的修f 近似点算法，最后 将此算法分别应用于求解无约束和带凸约束d c 规划问题。第四章讨论了求解凸 规划的修正近似点算法。第五章是数值试验，通过数值试验进一步说明了算法 的收敛性。第六章是全文总结，并对研究工作作出展望。 南京航空航大大学硕士学位论文 第二章求解d c 规划的全局收敛性算法 本章利用d c a 算法及分枝定界策略提出一种求解d c 舰划的全局收敛性算 法并且证明了算法的收敛性。 d c a 算法在本章发挥着不可替代的作用：它被用于 ( 1 ) 局部求解( d c e ) 的子问题： ( 2 ) 结合分枝定界法全局求解( d c p ) 问题。 先研究带凸约束的d c 规划问题： ( c d c p ) r a i n g n ( x ) s 1 g ，。( z ) t 。撤= 1 ，膨 x z 。= 酽，x 。】cr ” 其中二次连续可微叫函数g 。( x ) 分解为 g ( 1 ( x ) ：= g ( ：( r ) 一g j ( z ) ， ( 1 ) ，。为任意实数，一= ( 兰? ，) 7 ，0 = ( ；? ，；：) 7 ，兰，0 ，；：( 待1 ，。) 均为干 限实数g 。( x ) f 。，( ) ，m = 0 , 1 ，m ，且均为二次连续可微的。 在本章中设( c i ) c p ) 问题的可行域为， c ：= 扛x ”：g 。( x ) t 。， = i ，肼： 2 1 用d c a 算法局部求解( c d c p ) 问题 对于d c a 算法，不同的d c 分解及不同的初始点均会极大的影响算法的收 敛性质及收敛效率。出于d c 函数有无数个d c 分解，因此对于不同的d ，c 分 解应用d c a 算法会得到不同的迭代序列。下面本文将给出目标函数的三种d 。 分解，最终第三种分解策略将被采用。 由于函数g 。在箱约束x o 上均为二次连续可微的，由矩阵代数的知识：二次 连续可微函数g 。的海色阵v 2 g 。( x ) 的特征值知( z ) 为关于x 的连续函数，因此 知( x ) 在箱约束x “上存在最大值和最小值。不妨令 则取 从而 f o ：2m a x 。“nf n ( x ) ，o ：= m i n 。；r 。知( 工) ，7 ：。f o + 0 1 ，y ：= m a x ( 0 1 ，一f o + o 1 ) 求解d c 规划的全局收敛性算法平l j 近似点算法 吾叩i x | j2 一g o ( 石) ，寻y i 艽j j 2 + g 。( x ) ，v x ex 。， 均为凸的。由此可以得到( c d c p ) 问题目标函数g 。三种形式的d c 分解，z 。为 定义在集合c 上的指示函数，按如下方式定义； 如果x c ，则z c ( x ) = 0 ：否则z c ( z ) = + 。 g ( x ) ：= g j ( 工) + z 。( x ) ； 或者 g ( x ) ：= z ，( x ) + ，x 02 + g o ( x ) 或者 h ( x ) 四( 工) ( 2 ) ( z ) ：= 昙，i i x i i 2 g ( x ) ：= z ，( x ) + 委1 7 8 x t l 2 ； ( z ) ：= ，7 f l x r j 2 一g o ( x ) ( 4 ) 相对于分解( 2 ) d c a 算法可描述为： 算法d c a p l s o 令x o 为r “中给定的一点，取s 0 为任意小的f 数，令k ：0 ： s 1 解 m i n g - ( 5 ) 【s t z c 得到点茁“。 s 2 如果妒“- - x k i | s s 或者( g 一 ) ( x i t * ) ( g 一 ) ) # ，则终止；否则令 k - k + 1 ，转s l 。 如果把s 1 的最优化问题换为 i m i n 扫邮+ g 0 ( 矿 y x ( c 一 忙i x x 叩 ：一2 南京航空航天大学硕士学位论文 得到此问题的最优解“i ，即 x “1 = p r o j c ( ，厶) ， 其中v g 。，p r o 。分别表示g 。的微分算子，c 上的投影算予： s 2 如果“一j 。l f s 或者( g 一 ) ( x “1 ) ( g 一 ) ( x ) 一占则终止：否则令 k ：= k 十1 ，转s 1 。 注1 虽然从理论上来说r 和，是明显存在的，但目前还没有有效的算法能够 解决此问题。对于定义在低于四维空间的d c 函数，l et h j l 2 4j 提出了一种有效尊： 法能够得到r 和，可对高于四维的情况却无能为力了。但利用下面的算法可初 步判断y 是否满足( ：j ) 式。叩是否满足( 4 ) 式，如不满足可以利用下面的算法 对，和r 进行调整。对于每次迭代得到海色阵v 2 g 0 0 ) ，我们需要判断选取的，7 。 和y + 是否使得， i 一甲! g 0 0 ) 和ni + v 2 g 。0 ) 为f 定，其中i 为单位阵。我们 知道c h o l e s k y 分解不但能够分解对称正定矩阵，而且可判断一个对称矩阵足否 正定 4 2 | 。由此可蹬汁算法如下， 算法c p z s 1 令r o ：= 0 1 ，- - 0 1 ，：= 0 ； s 2 分对叩，i v 二g o ( ) 和y ，i + v2 g o ( x ) 进行c h o l e s k y 分解判定是否为j 1 定的，若是令讯：= 坪，以车y ，否则转下一步： s 3 令r ，+ l ：= 4 ，7 ，+ i ：= 4 y ，：= j + l ，转s 2 。 由于约束集的紧性和g 。的二次连续可微性知，r 。和，。可以在有限步得剑川 为有限的。 注2 对于二次函数来 兑，因为v 2 g 0 为常数，即为二次函数所对应的矩阵， 因此叩和，是容易确定的。只需要求得此矩阵的最大特征值叩。和最小特征值， 再令刁：- r o + o 1 ，：= m a x ( 0 1 ，一，o + 0 1 ) 即可。当然也可利用算法c p z 来求得7 7 。 注3 数值试验显示相应于分解( 4 ) 的d c a p 3 算法更有效率一些。 本章下面将就箱约束d c 规划和一般约束d c 规划两种情况进行讨论。 2 2 全局求解箱约束d c 规划 本节主要讨论当约束集合为箱约束的情况，即 c 两， m i ng 。：! 。：。墨。，；。，cr 。 求解d c 规划的全局收敛性算法和近似点算法 2 ，2 1d c a 算法局部解( 两) 问题 应用d c a p 3 算法局部解上面的最优化问题( p 1 ) ，取目标函数的d c 分解如 下， g l ( x ) ：= z r ( 砂 去玎嘶i i ；( x ) ：= 玎俐2 一g 。( x ) ( 8 ) ( 其中7 7 为使得函数去即z 4 2 一瓯，( x ) 在x 。上为凸函数的证数) ，由此我们可把 ( 两) 写为如下的d c 规划问题， ( 两铮：j 商n g r ( d c p ) ( z ) ( x ) ( 9 ) ”铮 ：伍工：苫” j j ，工l 把d c a p 3 算法应用于( 西西) 问题得到两个点列扛+ 和b ， y = ( 砰i v g 。) ( x ) ；x k + l = p r 吼( y 么) ( t o ) 算法d c a b p 3 a s 1 令z o 为r 扣的点，s 为一充分小的正数，令k ：= 0 ： s 2 计算y = 班一v g o ( j ) ： s 3 令：生，当i ：l ，、n ，7 如果x ：歹：；j ，令x = y ： 如果歹；：，令x = ；? ： 否贝0 令x ? ”= ；： s 4 如果肛“i x 。ss ，则停止迭代：否则令女芹k + l ，转s 2 。 下面考虑( 两) 的一种特殊形式：g 。为震”上的凹函数，即( 两) 为一箱约束凹 最小化问题。我们提出另一种d c 分解 gj ( x ) ：= z f ( 工) ；h i ( x ) ：= - g o ( 工) ( 1 1 ) 相应于上面的分解，将d c a 算法应用于洒) 得到下列两个点列k 和 ， y = - v g o ( z ) ； z “1 a r g m i n ：工c ( 1 2 ) m 于m i n ：工c = 二m i n l - w ? ：点，o 置s - 。，因此有， 算法d c a b p 3 b s 1 令并。为r ”中的点，g 为一充分小的正数，令女：= 0 ： s 2 计算y = 一v g 。f x ) ： s 3 当i = i 、n 时 南京航空航天大学硕士学位论文 空口果y ? 0 ，令x ? ”= x ? ： 否则，令x “= ；? ； s 4 如果“_ x k 忙，则停止迭代；否则令t _ k + l ，转s 2 。 注4 算法d c a b p 3 a 和算法d c a b p 3 b 仅仅需要向量的乘积因此他们都可用 于解决大型问题。数值试验表明算法d c a b p 3 a 和算法d c a b p 3 b 能很快的收敛于 ( p 1 ) 的局部极小点，而且当我们所选择的初始点z o 离全局最优点充分近的时候， 这两种算法均收敛于( p 1 ) 的全局极小点。 2 2 2 分枝定界法 本部分对( p 1 ) 的目标函数g 。进行下界估计。不妨记( p 1 ) 的箱约束集合为 b 譬k ：墨? 一z ：b 1 ，n ，下面将计算g 。在b 上t y j y # 。 定下界当目标函数能容易分解成( 3 ) 式，则取g 0 的d c 分解为， g o ( z ) = g ( x ) 一h ( x ) g ( r ) 以( z ) + y 1 1 + g o ( 工) ； ( z ) ：= ，2 其中y 0 使得g 为凸函数。 令 姒) ：= 芝，( 一) ：窆冬瞄+ z ) t 一墨譬 一 事实上 z ；一( 墨? + x - - ，0 ) z ，+ 苎o ，z - - ? = ( x ，一兰? ) ( x ，一- - x ，0 ) 0 ，f ：l ，2 ，一，n 则 l ( x ) h ( x ) 构造函数 g ( z ) ：= ( 鲁删2 + g o ( x ) ) 一窆( t ) ( 1 ：3 ) o ，= l 则g ( x ) 为凸函数且满足g ( x ) s g o ( x ) ，v x b 。在目标函数为二次函数或者y 比 较容易求出的情况下可以采用此种定界策略，尽管在理论上说y 是明显存存的， 但对于目标函数为一般函数的情况下求出y 是相当困难的。因此我们必须寻找 个更一般求解目标函数下界的方法。 由于d c 规划的c 1 c ，分解有无穷多个，下面看其分解( 2 ) 求解d c 规划的全局收敛性算法和近似点算法 g 0 ( 工) = g ( x ) 一h ( x ) 其中 g ( x ) ：= g ：( x ) + z 。( 工) ；h ( x ) ：= g j ( x ) q ( x ) ，g ：( x ) 均为二次连续可微的凸函数，则对于给定的y r ”有 g j ( x ) g ：( y ) + vx r ” ( 1 4 ) 因此当迭代进行了k 步得到当前点为x ，则对于k + l 步我们对目标函数g 。可以 采用下面的凹下界估计， g ( x ) ：= g ：( x ) + 一0 3 ( x ) vz r ” ( 1 5 ) 事实上此函数的f i 两部分为线性的，第三部分为凹的，因此函数为凹的。 g o 在b 上的下界风可通过解下面的带箱约束凹规划得到 风：= r a i n g ( x ) ：x b ( 1 6 ) 有很多方法可以解此最优化问题例如，可对g ( x ) 作下面的d c 分解， g ( x ) = g ( x ) 一 ( x )( 1 7 ) 其中 譬( t ) z 。( x ) + 詈j ! ；h ( x ) 丢刁忙i i 2 一g ( x ) ( 1 8 ) 叩是f 常数。然后使用d c a b p 3 b 算法来求解子问题( 1 6 ) ，可得到( 两) 的下界风。 注5 在下面的算法中总是采用( 1 5 ) 式对原规划进行下界估计，并用蛑裂、 d c a b p 3 b 来求解相应的子问题( 1 6 ) 。 定上界在每一步迭代中可以通过计算( 1 6 ) 的最优解x 8 而得到( 两) 最优值的一 个上界g 0 ( 工8 ) 。 一 注6 当目标函数为二次函数或者，和即比较容易求出的情况下，以x8 为初始点 应用算法d c a p 3 来解( p 1 ) 可得一更好的上界，这是因为算法d c a 产生的序列 x 。 使得 g 。o ) = g ( z ) 一 ( 工) 为递减的 2 3 3 2 1 。 分枝本文采取长方体分枝策略。这种策略能够充分保证算法的收敛性，这是因 为：此方法能够保证分枝定界中的每一无穷步分枝中的最大区间趋向于零。下 面描述此种策略：令b 譬【x i , y 1 b 为需要分枝的长方体。选择一f 整数p 并使 得 p = a r g m a x x ：一y ：k = l ，h j ( 1 9 ) 下面划分b ：将区间 x ：，y p 】二分为下面的两区间 【x ：，( x ；+ y ：) 2 】和【( x ；+ y ：) 2 ，y ： 。 南京航空航天大学硕士学位论文 2 2 3 全局求解( 两) 的算法b b d c a 算法 本节给出求解( 两) 全局最优解的一个新算法，新算法的基本思想是：将d c a 算法和分枝定界法结合起来，在每一步判断所得到的上界和下界的差是否满足 给定的终止条件如满足则停止迭代，得到近似最优解：否则进行分枝，重新 迭代直到得到最优解。 算法b b d c a s o 初始化 0 1 令b 。：= b 解下面的最优化问题 岛= = r a i n g ( x ) ：x e b o j 得最优解x 8 及原规划最优值的一个下界。一 o 2 令i ：= g 【】( x 8 ) x o ；x 8 ”。 如果盹屈。+ s ，则迭代停止，x o 为近似最优解。 否则，令- 玩 ，k 卜0 。 8 1 选择b k 。，使得反# 风、= m i n h ：b 婀t 。将bk 二分为下丽得两 部分b k i = 1 2 。 s 2 解下面的最优化问题( c p k ；) ( j = 1 , 2 ) ( c p k )玩。r a i n g ( x ) ：x b k 。 得最优值风和最优解x “。 如果g o ( z m ) 0 ，使得 y 7 v 2 g 。( x ) y s 刮坩，v x b ，r ”( 2 1 ) 此性质对其d c 分解试( 工) ，g ：( x ) 也成立t 即分别存在厶 0 ，l ： 0 使得下 面两式成立， y 7 v 3 g ：( z ) y 上l t l y l l 2 ，v x b ，、吵r ”， 岁7 可：g ：c x ) y s 上： 少旷，v x b ，b 9 r ”。 南京航空航天人学硕十学位论文 因此有下面的关系： 0 g o ( z ) g ( x ) = ( 6 j ( x ) 一g ；( x ) ) 一( g ：( x 。) + - a 3 ( x ) ) = g j ( x ) 一g j ( z 7 ) 一 = ( x x7 ) 7 v2 g ：( x ( 日) ) ( x x7 ) 0 。 求斛d c 规划的全局收敛性算法和近似点算法 2 3 1 分枝定界法 定下界在上一部分中已经给出了目标函数的下界估计，下面再给出约束函数 g ，= 1 , 2 ，m ，的下界估计。 当g ，能容易分解成( 3 ) 式，取其d ，c 分解为， g 肛) ：= 妻，川x i i ：+ g 肛) ；h j ( x ) ：= 丢y 川x i l 2 ，= l ，2 ，m ( 2 ： ) 则有， ，廖) 一- 窆协，) ：窆冬瞄帆- o ) 一一量0 圳- - 0 廖) ，= 1 2 吖 ( 2 4 ) t l忙j 定义， 石，( 工) ：= 去，川x i l 2 + g 肛) 一，( x ) ，= l ，2 ，m ( 2 5 ) 其中y ，为使去，1 2 + g ，( x ) ，v x 。为凸函数的f 数，则在( 2 5 ) 中定义的函 数g ，( x ) ，j = 1 , 2 m 均为凸的，且满足 o ( x ) g ，( x ) ，j = 1 , 2 ，吖 但对于般的d c 函数y 并不是容易求的，因此可设约束函数g ，y = 1 , 2 ，m ， 的d c 分解为 g ，( x ) ：= g ，( x ) 一h ，( x ) g ，( x ) ：= g ；( x ) ；h ，( 工) ：= g ；( x ) = 1 2 ，膨 ( 2 6 ) 因此当迭代进行了k 步得到当前点为机，则对于k + t 步我们对约束函数g ， ，= 1 , 2 ，m ，可以采用下面的下界估计。令 g ，( x ) ：= g ：( x ) + 一g ；( x ) v 上r ”，= 1 , 2 ，吖( 2 7 ) 则g ，( x ) 为约束函数g ，= 1 , 2 ，m ，的下界估计。 因此通过解下面的凸优化问题可得( d c p ) 问题的一个下界： l r a i no ( x ) ( p c ) s t g 。0 ) s ，。，搠= 1 ，m 【x e 。：心，；。】c 为方便起见令i ：= k 尺_ 否。( x ) f 。，x 。= k 。，- o l ，则刁为紧集，且( p c ) 问题可重新写为： ( p c ) r a i n ，。ig ( x ) 6 南京航空航天犬学硕士学位论文 设拆为定义在( 上的指示函数，n i 0 ) 为指示函数拆在x 点的次微分a 取 ( p c ) 中目标函数g 的d c 分解为， g ( x ) = g ( x ) 一h ( x ) 其中 g ( x 1 ：= z i ( x ) + - ；q l x r ； ( x ) ：= 去碍i j x l | 2 一g ( x ) f 2 8 ) 其中口 0 ，基f 本分解可以应用d c a 算法来求解( p c ) 问题。由此可以得到原 规划( d c p ) 问题最优值的一个下界： 卢i ：= m i n g ( x ) ：x c ( 2 9 ) 当( d c p ) 问题的最优解为有限，从而( p c ) 问题的解也有限，且( p c ) 问 题的拉格朗f 1 乘子 = ( ， 。，) 0 容易求出的情况下，文献 3 4 指出问题 ( 2 9 ) 等价于下丽的箱约束凸规划问题， ，、f m i n g o ) + t t m p兄，( 卜石心) ) c 1() 、l 。、“ kx x o = 睦。，；。】cr ” 显然此问题可用i ) c a b p 3 a 来求解，但遗憾的是拉格朗同乘子并不容易求得。 一般情况下可以采用罚函数法，约束变尺度法以及可行方向法等等 3 5 3 6 1 求解 子问题( 2 9 ) 。 定上界在每步通过计算g ( x 。) 得到( d c p ) 问题最优值的一个e 界，其中x i 为 问题( p c ) 的最优解目为( d c p ) 问题的可行解：否则去掉此点进行下一步逖代 分枝策略本部分中的分枝策略与上一部分中的相同。 2 3 2 算法b b d c a j s 0 初始化 o 1 令b 0 = = ，r 。：k ：苎? t j ? ：f _ 1 ， 化问题： ，0 取上界d = 。解下面的蠼优 o - m i n g ( x ) ：x c 得最优解x 矗，设可行点集合f ：0 。 0 2 如果x “为( d c p ) 问题的可行解，即满足 g 。( x 。) f 。( m = 1 ，m ) ， 则令盘：= g i ，( r ”) t f - 扛“ 。如果口s 反+ s ，则停止迭代x “为得到的迈 似最优解，其中# 0 为允许误差。 令卜 玩 ，寿- 0 。 求解d c 规划的全局收敛性算法和近似点算法 s l 取b 。的中点x ，如果x 为d c p 的可行解，则f f u 扛”j 。定义上界 口竽m i n g j ) ( x ) ；如果f o ，已最优可行点为x “= a r g m i n g o ( x ) 。 8 2 将b 。分支得到新的子长方体集合，记为s 。 2 1 对于每一x s ，计算g ，( x ) ，j = 0 ，l ，2 ，m 在长方体上的下界 e ( x ，x ) 和石，( x ：) ，= 1 , 2 ，m 。如果存在一- ，( j = 1 , 2 ，m ) 使得其中一 个下界满足下列条件： g ( x 。v ) 口或者g ，( x ；