（应用数学专业论文）不定二次规划的最优解集与求解算法.pdf

福建师范大学林惠玲硕士学位论文 记号与约定 z ：全体整数 z + ：全体正整数 r “：实数域上的n 维欧氏空间 r + + ：全体正实数 + o 。，o 。：正无穷大 一o 。：负无穷大 t lo ：a t _ a 三：恒等于 i o i ：o 的绝对值 ”| j ：欧氏范数 ( ，) ：欧氏内积 0 ：空集 i n t s ，r i s ，o s ：分别是集合s 的内部，相对内部和边界 l 1 ：子空间l 的正交补 k e r ( a ) ：a 的零空间 a + ：矩阵a 的m o o r e p e n r o s e 广义逆 a t ：矩阵a 的转置 a 1 ：矩阵a 的逆矩阵 厶，：n 阶单位矩阵 0 。：n 阶零矩阵 d i a g ( a l ，。) ：对角元为a 一，a 。的 1 2 阶对角矩阵 r a n k ( a ) ：矩阵a 的秩 d o m g ：函数g 的有效域 犯m = 三，：；妻：集合x 的指示函数 a r gm i n f ( z ) ：茁x ) ：，( z ) 在x 上的最小值解集 v ，( z ) ：y ( z ) 在点。的梯度 o y ( z ) = 矿：v z r n ，f ( z ) y ( z ) + ( 2 7 + ，z z ) ) ：，( z ) 在点z 的次梯度集合 ：定理或命题证毕，例子求解完毕 v i 摘要 本文探讨不定二次规划问题和它的求解算法，主要由三个部分组成第一部分， 受信赖域子问题的启发，考虑特殊的d c 集( 介于两个同心球之问的点集) 约束的极 小化不定二次规划问题我们首先证明了关于该问题的l a g r a n g i a n 对偶的稳定性， 即不存在对偶间隙；接着利用该性质得到问题的全局最优性条件和最优解集，它可以 像凸规划那样，借助它的对偶问题的解集精确地描述出来最后，通过一个例子来说 明这些结论，同时它也提供了原问题的一种求解方法第二部分，研究第一部分所提 问题的另一种求解算法根据第一部分中得到的问题最优解集精确表示的结论，当 目标函数的二次型矩阵的最小特征值非零时，问题可以转化为两个信赖域子问题，并 根据问题的特殊结构设计了基于目标函数的d c 分解的d c 算法，该算法只要进 行矩阵一向量的乘积运算，且具有很好的全局收敛性最后在m a t l a b 6 5 上进 行例子的数值模拟第三部分，探讨锥约束的不定二次规划问题的最优解集首先， 考虑目标函数的二次型矩阵为块对角阵，同时约束函数的二次型矩阵可逆时，运用 l a g r a n g e 乘子法得到：当目标值允许取负无穷大时，原始问题和对偶问题不存在对 偶间隙，同时还得到对偶问题的最优解集，并借助它把原问题的最优解集详细的描述 出来接着，把这些结论推广到目标函数和约束函数的二次型矩阵均为一般对称矩阵 的情形 关键调：dc 规划不定= 次规划 a g r a n g i a n 对偶性全局最优性条件 最优解集 塑塞堡堇奎兰苎塞丝丝兰堡丝苎 a b s t r a c t i nt h i sa r t i c l e ，w ed i s s c u s st h eo p t i m a ls o l u t i o n sa n ds o l v i n ga l g o r i t h m sf o rt h e i n d e f i n i t eq u a d r a t i cp r o g r a m s t h i sp a p e rm a i n l yc o n s i s t so ft h r e es e c t i o n s i nt h e f i r s ts e c t i o n ，m o t i v a t e db yt h et r u s tr e g i o ns u b p r o b l e m ，w ec o n s i d e rt h ei n d e f i n i t e q u a d r a t i cm i n i m i z a t i o no v e rap a r t i c u l a rd c s e t ，w h o s ep o i n t sa r eb e t w e e nt w ob a l l s p o s s e s s i n gt h es a m ec o r e w ee s t a b l i s hf i r s tt h es t a b i l i t yo ft h el a g r a n g i a nd u a l i t y r e l a t i v et ot h ep r o b l e m ，n a m e l y , t h e r ei sn od u a l i t yg a p t h i se l e m e n t a r yp r o p e r t yi s t h e nu s e dt od e r i v eb o t hg l o b a lo p t i m a l i t yc o n d i t i o n si nt h ep r o b l e ma n dt h es o l u t i o n s e t s ，w h i c hc a nb ed e s c r i b e dw i t ht h eh e l po fi t sd u a ls o l u t i o n se x a c t l ya si nc o n v e x p r o g r a m m i n g a ne x a m p l ei sg i v e nt oi l l u s t r a t et h en a t u r eo ft h er e s u l t s m e a n w h i l e ， i tp r o v i d e sas o l v i n gm e t h o df o rt h ep r i m a lp r o b l e m ， i nt h es e c o n ds e c t i o n ，w ep r o p o s ea n o t h e rs o l v i n ga l g o r i t h mf o rt h ep r o b l e m a d v a n c e di nt h ef i r s ts e c t i o n t h a n k st ot h ed e t a i l e dd e s c r i p t i o n so ft h es t r u c t u r e o ft h es o l u t i o ns e t si nt h ef i r s ts e c t i o n ，i nt h ec a s ew h e nt h es m a l l e s te i g e n v a l u eo f t h eq u a d r a t i co b j e c t i v ef u n c t i o ni sn o n z e r o ，w eo b s e r v et h a tt h ep r o b l e mc a nb ec a s t a st w ot r u s tr e g i o ns u b p r o b l e m s d u et ot h ep a r t i c u l a rs t r u c t u r eo ft h ep r o b l e m w ed e v i s ead c a l g o r i t h mt os o l v ei t ，w h i c hi sb a s eo nt h ed c d e c o m p o s i t i o no f t h eo b j e c t i v ef u n c t i o n i ti sq u i t es i m p l ea n dr e q u i r e sm a t r i x v e c t o rp r o d u c t so n l y m o r e o v e ri tc a nc o n v e r g et ot h eg l o b a ls o l u t i o no ft h et r u s t r e g i o np r o b l e m f i n a l l y ， w em a k et h em a t l a bc o d ef o re x p e r i m e n t i nt h et h i r ds e c t i o n ，c h a r a c t e r i z a t i o no ft h eo p t i m a ls o l u t i o n so fc o n e - c o n s t r a i n e d i n d e f i n i t eq u a d r a t i cm i n i m i z a t i o ni sp r e s e n t e d w h e nt h em a t r i xo ft h eq u a d r a t i c o b j e c t i v ef u n c t i o ni sb l o c kd i a g o n a la n dt h eo n eo ft h ec o n s t r a i n e df u n c t i o ni sn o n - s i n g u l a r ，t h el a g r a n g e sm e t h o do fm u l t i p l i e r si su s e dt oo b t a i nt h ep r o p e r t yt h a t t h e r ei sn od u a l i t yg a pb e t w e e nt h eo p t i m a lv a l u eo fp r i m a lp r o g r a ma n dt h eo n eo f t h ed u a lp r o g r a mi fac o m m o nv a l u eo fn e g a t i v ei n f i n i t yi sp e r m i t t e d w i t ht h ea i do f t h es o l u t i o ns e t so ft h ed u a lp r o g r a m ，t h eo n e so ft h ep r i m a lp r o g r a ma r ed e s c r i b e d e x a c t l y f i n a l l y , t h er e s u l t sa b o v ea r ee x t e n d e dt ot h eg e n e r a ls y m m e t r i cm a t r i c e so f t h eo b j e c t i v ef u n c t i o na n dt h ec o n s t r a i n e df u n c t i o n k e y w o r d s ：d c p r o g r a m m i n g ，i n d e f i n i t eq u a d r a t i cm i n i m i z a t i o n ，l a g r a n g i a n d u a l i t y ，g l o b a lo p t i m a l i t yc o n d i t i o n ，o p t i m a ls o l u t i o n i i 福建师范大学林惠玲硕士学位论文 中文文摘 本文主要探讨两类特殊的不定二次规划问题的最优解集和求解算法，研究的理 论依据主要是非线性规划的对偶理论文章的结构安排如下 第一章概括了目前国内外关于凸的和非凸的二次规划问题的研究情况和主要成 果，指出非凸二次规划的数学模型有着广泛的实际应用背景和重要的理论意义 第二章研究一类特殊的不定二次规划问题，该问题的研究是受信赖域子问题的 启发，它的约束集是个特殊的d c 集，即介于两个同心的欧氏球之间的点集，目标 函数是不定的二次函数，所以它也是个d c 规划，于是就有基于目标函数的d c 分 解( 两个凸函数的差) 的d c 算法，第三章将讨论这样的算法第一节。根据对偶理 论，我们先定义原问题的对偶规划，接着研究对偶规划的目标函数的有效域和显式表 达式等基本性质，通过等价变换，利用l a g a r a n g e 乘子法得到了对偶规划的最优解只 能在边界上达到这一重要结论进一步，我们发现了对偶问题的目标函数在其有效域 的边界上存在唯一最小点的性质，从而得到对偶规划的最优解集最后由鞍点定理得 出原问题的最优性条件，结论是文中的定理2 1 1 3 第二节，利用第一节的最优性条件以及对偶问题的最优解集推导出原问题最优 解集的详细刻画，是本章最重要的结论，即命题2 2 1 该结论主要描述的是原问题的 最优解集具有下列性质： 对于原问题的最优解z ，有 若a 1 0 ，| | a 一1 6 l | r 2 或a l 0 ，l i a 一1 6 【| sr 2 ，贝0i | z | i = r 1 这个结论在下一章的算法设计中起了关键性作用这一节还举例说明这个结论， 同时这个例子也提供了求解原问题的一种方法，它需要先解非线性方程获得对偶问 题的最优解，再求解线性方程组而得到原问题的最优解，这种求解方法需要求出目标 函数的二次型矩阵的因子分解，因此它对大规模问题是不适用的 第三章研究第二章所提问题的另一种求解算法第一节简要的介绍了一般的d c 规划的d c 算法。也就是文中的简化d c 算法，本章的算法就是根据该算法的思 想设计的 第二节，利用第二章命题2 2 1 的结论，我们得到：当目标函数的二次型矩阵的 最小特征值不为零时，原问题可以等价于求解两个有相同目标函数的信赖域子问题 i i i 福建师范大学林惠玲硕士学位论文 因此，我们对p h a md i n ht a o 等人提出的求解信赖域子问题的d c 算法进行适当 的修改，得到求解原问题的d c 算法，即本节中的算法3 2 2 ： 第1 步利用i r l m 计算a 的最小特征值a l 和最大特征值a n ； 第2 步按照选取原则1 确定7 ，令b = a + 7 1 ； 第3 步利用i r l m 计算b 的最小特征值6 l 及对应的特征向量卢，利用i r l m 计算b 的最大特征值矗，按照选取原则2 确定“ 第4 步如果a 1 0 ，i i a - 1 b l l r 2 或a 1 o ，令r = r 2 ；如果a 1 0 ，l i a - 1 b l i r 2 ，令r = r l ； 第5 步任取虿r “( 如取i = 0 ) ，s t o p ：= f a l s e ； 第6 步当s t o p = f a l s e 时执行 ( 1 ) 初始点取矿= 虿，运用算法3 2 1 得到； ( 2 ) 如果由式( 3 5 ) 给出的矿- s x ，则s t o p = t r u e ，z + 是问题( p ) 的全局最 优解；否则，按照选取原则3 确定i ，转( 1 ) 这个算法修改的地方在于：1 要根据本节的选取原则1 确定一个实数使得目标函数 的二次型矩阵是非半正定的，即算法的第2 步；2 要根据本节的选取原则2 确定一 个实数，使得新目标函数的d c 分解的两个分量均为凸函数，即算法的第3 步3 要判断出原问题所等价的信赖域子问题，也就是算法的第4 步算法3 2 2 同样只要 进行矩阵向量的乘积运算，且具有很好的全局收敛性，最关键的是它对大规模 的问题也是适用的最后在m a t l a b 6 5 上进行第二章中的例2 2 2 的数值模拟，对 得到的结果与第二章的进行比较得出算法3 2 2 具有更好的鲁棒性 第四章探讨另一类特殊的不定二次规划问题的最优解集，它的可行域是锥，而且 二阶锥是它的一个特例第一节讨论目标函数的二次型矩阵a 为块对角阵，即 a = ( 乞1 羔) ， 且约束集函数的二次型矩阵c 可逆的情形用到的方法和第一章的相似，利用l a - g r a n g e 乘子法，先是定义了原问题的对偶规划，它实际上等价于一个单变量的凸极 小化问题于是，根据凸规划的最优性条件。我们按照a 1 和a 2 的最小特征值的取 值情况分别讨论对偶问题目标函数的性质，从而得到对偶问题的最优解。进一步借助 它把原问题的最优解详细地刻画出来本节的主要结论是定理4 1 6 ，定理4 1 7 和定 理4 1 1 0 ，它们精确地描述了原问题的所有最优解，以及原问题的最优值o t 和对偶问 i v 堡壅堡堇奎兰苎塞丝堡圭兰堡垒苎 # = = = = = ；= = = = = = = = = = = = = = ；= = = = = = = = = = = = = = = = = = = = ；= = ；一一。一 题的最优值p 之间的关系，即在允许目标函数值取负无穷大时，它们之间不存在对 偶间隙归结起来就是，当q = p = 一时，原问题和对偶问题的解集均为空集； 当o ：p 为有限实数时。对于原问题的最优解z = ( 矿t ，z 玎) r ，存在对偶问题的最 优解r ，使得 t + ( 1 1 y | | 一i i z | 1 ) = 0 ，i l y + i i 忖m 第二节是第一节的推广工作，在a 和c 可交换的前提下，利用矩阵论的相关知 识，把第一节的结论推广到a 和c 均为一般对称阵的情形，得到了与第一节的结论 相类似的结果 v 第l 章引言 第1 章引言 1 1 历史文献介绍 二次规划的研究始于二十世纪五十年代，它是非线性规划中的一种特殊情形标 准的二次规划是指目标函数为二次函数、约束条件是线性等式或线性不等式的规划 问题。其数学模型如下 m i n ，( 。) ：= x t q z + c t x s t o z = b i , i ，( d q p ) o b i ，i 屯， 其中，a i ，c r n ，b i r ，q 为对称矩阵，1 = 1 ，2 ，m 。 ，如= m 。+ 1 ，m 。+ 2 ，一，m ) ，m e z + ( d q p ) 是线性规划向非线性规划的自然过渡，它是非线性规划中最简单且研究 得最成熟的一类问题，也是可以通过有限次迭代求得精确解的一类问题( d q p ) 不 仅本身具有相当广泛的实际应用背景，如在证券组合投资，结构优化问题，系统优化 控制等领域而且在求解其他类型的线性约束优化问题时，常常需要求解一系列做为 子问题出现的( d q p ) 因此，探讨求解问题( d q p ) 的有效方法是十分重要的 若m 。= m ，则( d q p ) 为等式约束二次规划，最简单又最直接的求解方法是直 接消去法，它的思想简单明了使用方便，不足之处是基矩阵可能接近一个奇异矩阵， 从而引起最优解的数值不稳定而常用的求解等式约束二次规划的方法是l a n g r a n g e 乘子法，利用问题的特殊性，可以同时确定其最优解与相应乘子，它的详细分析参看 文n 若q 为半定矩阵，m 。m ，则( d q p ) 称为凸二次规划，它的求解有几个途 径可行方向法是一种，此类方法可看作无约束下降算法的自然推广，其基本思想是 从可行点出发。沿可行下降方向进行搜索，求出使目标函数下降的新的可行点，整个 算法包括选择搜索方向和确定搜索步长两个主要方面基于这种方法的如b e a l e 方法 【2 ，引，它本质上是广义的凸单纯形法另一个一直使用的是起作用集方法，见b o o t 4 1 ， t h e i l 和v a nd ep a n n e f s j 它是在每次迭代中，都以已知的可行点为起点，把在该点 起作用的约束作为等式约束，而把在该点不起作用的约束暂时去掉不考虑，在新的约 柬条件下极小化目标函数，求得新的比较好的可行点之后，再重复以上步骤这样， 就把问题转化为有限个仅带等式约束的凸二次规划来求解文f 6 l 给出了求解等式约 束的凸二次规划的几种算法，它们是严格可行内点算法，不可行内点算法以及把原 福建师范大学林惠玲硕士学位论文 问题转化为线性互补问题的中心路径算法此外，还有由h o u t h a k e r 7 1 提出的解加上 一个形如戤卢的约束问题，并且每次迭代过程中逐步增加p 以及由k e u u 刚， c h e n e y 和g o l d s t e i n 9 1 分别独立提出的割平面法，也称k c g 法，是将凸规划的可行 解集合用有限个半空间来近似，并求解一系列不断改进的线性规划，它们的最优解收 敛于原凸规划问题的最优解 解( d q p ) 的一个通俗方法是解k u h n - t u c k e r 系统，这一想法是由b a r a n k i n 和 d o r f m a n 1 0 】及m a r k o w i t z 【1 1 j 提出的求解k u h n - t u c k e r 系统有一些方法如w o l f e 【1 2 l 提出了一个稍加修改的单纯形法，在那里。对偶可行性被放宽了同时，求解线性互 补问题的互补主元算法也可用来求解该系统这种算法是通过引入人工变量，在邻近 的准互补基本可行解之间移动，得到的结果或是获得一个互补基本可行解，或是找到 一个方向指出由线性互补问题所定义的区域的无界性基于这一思想的有解二次凸 规划的l e m k e 方法【1 3 1 在那里，原来的可行性和对偶可行性都被放宽了，是把线性 规划中的单纯形法加以适当修改，再用来求不等式约束的凸二次规划的k t 点还 有求解k u h n - t u c k e r 系统的择一方法，更详细的研究见c o t t e 和d a n t z i g 1 4 l ，f r a n k 和w o l f e l l 5 l 以及s h e t l y 1 6 】等的著作对于更一般的凸二次规划问题( d q p ) 的求解 算法，可参见文【1 7 】 若q 不是半正定的，则目标函数( x ) 是非凸的，它可能有多个局部极小点 在这种情况下，( d q p ) 是一个非凸规划 非凸的( d q p ) 问题从数学和应用的观点看都具有重要作用例如经济平衡问 题，组合最优化( 如排序问题，甚大规模电路的布局问题) ，弹塑性分析问题，数值偏 微分方程和一般的非线性规划等都源于非凸二次规划 非凸规划问题的求解是很困难的，传统的局部优化方法求得的解无法保证其全 局最优性，参见文【1 8 1 s a h n i 1 9 】首先指出，若q 是负定矩阵，则( d q p ) 是个n p 一 难问题，这个结论同时也被v a v a s i s 2 0 】和p a r d a l o s 2 1 l 所证实近十几年来，有几个 学者指出了对于一般的二次规划问题，研究其解的全局最优性是个n p - 难问题。参 见p a r d a l o s 和v a v a s i s 2 0 l ，h o r s t 2 “他们指明，即使q 只有一个负特征根，( d q p ) 也是n p 一难的为解决这一难题，近十几年来做了很大的努力，同时也得到了一定 成果，参见由f l o u d a s 和v i s w e s w a r a n 1 a l 的综述性文章下面介绍几类常见的不定 二次规划 2 第l 章引言 关于箱约束( b o xc o n s t r a i n t s ) 的二次规划 r a i n ，( z ) ：= ，+ 一z s t 一o o “s 轧t 上i 一o o j ， 若入l t 1 + t 2 0 ，则t d o m 虿，且 孙，：；妻若亳一扣寥 。， 9 福建师范大学林惠玲硕士学位论文 此时，g 在t 0 ，a 1 一t l + t 2 0 上可徽，且 v 荆= ( 嚣i x ( 2 1 j ：r ) i i 毒) 一引。十芎 ( i i ) 若6 f k e r ( a a l j ) 】上，则d o i i 】否= 0 r 2 ：t o ，a l t 1 + t 2 o ) ，t b 时， 孙) = i 茎篮a l e r t + t 2 - 耕喇，嚣 【2 岛 2 q1 。“广“ ( i i i ) 若b 隹 k e r ( a a 1 ，) 】上，a 1 jd o m e = b r 2 ：t o ，a 1 一t 1 + t 2 o ) ，此 时，歹( t ) 由式( 2 2 ) 确定 证明由命题2 1 1 容易得到( i ) 和( i i i ) 下面证明( i i ) 关于d o r 崎的特征由命题2 1 1 即得 若b k e r ( a a 1 驯1 ，则对任意j j ，有b t u j = o ；于是，若b = 0 ，由命题 2 1 1 的( i i ) 知， - y ( t ) = 一l b t x - - r ；+ i t 2 r ；= 一r ：+ i 1 ；2 r ； 若b 0 ，当a l t x + t 2 = 0 时，z = 一( a t z ，+ t 2 i ) + b ，则 孙，= ；若羔一争参 当a l t l + t 2 0 时，由( i ) 得， ( ) = ；喜黑一扣i t 2 嵋 ；若蔫+ ；蒜一和和 ；若黑专 审 对于信赖域子问题 有下面两个结论 m i n ；以z + 矿z ：扣1 2 互1 r ；) i ( q ) 第2 章d c 集约束的不定二次规划最优解集 定理2 1 3 f 5 6 jz 是( q ) 的最优解当且仅当存在唯一的a + 0 ，使得 ( i ) a + a * i 是半正定的； ( i i ) ( a + ”j ) z + = - 6 ； ( i i i ) a + ( | i 矿l l t 2 ) = 0 ，l i i i t 2 记旧) 的解集为q ，且 l f ( a 十a ，) + 6 l f = r 2 ( 2 3 ) 命题2 1 4 1 5 5 j 若b 0 ，则 ( i ) 当a l 0 时，如果i i a 1 圳sr 2 ，则q = 一a “6 ) ；如果i i a - 1 6 r 2 ，则 q = 一( a + a ，) 一1 6 ) ， 其中” 0 是方程( 2 3 ) 的唯一解； ( i i ) 当a l = 0 时， n 果i i a + 6 | i r 2 且b f k e r ( a ) 上，a 1 q = z = z + + u ：u k e r ( a ) ，s t f f z f l 2 = f f z + | f 2 + f f | 2 r ；) ， 其中z + = - a + 6 ；壬。果b 隹 k e r ( a ) 1 或6 e r ( a ) 】1 ，f i a + 6 i f r 2 ，贝1 i q = 一( a + a + ，) 一1 6 ) ， 其中a + 0 是方程( 2 3 ) 的唯一解 因此，由定理2 1 3 和命题2 1 4 知，在以下两种情况下： ( 1 ) a x 0 ，i i a