（应用数学专业论文）半定规划算法研究.pdf

内容提要 y 7 6 9 i 0 9 本文的主要工作由两部分组成第一部分，首先，定义了一种新的半正定非线性 规划问题半正定乘性规划，并设计了半正定规划的o a e 算法；其次，指出半 正定乘性规划可以看作一种特殊的几何规划，并且给出了对偶规划的具体形式；最 后，定义了分式锥规划，发展丁c h a x n e s 和c o o p e r 的理论，指出在特定情况下分式 锥规划可以转化为线性的锥规划第二部分，首先，指出文章1 1 9 】的不妥之处；然 后，借用x i o n g 等人的方法【w i ，设计了求解凸二次规划和半正定线性规划的微分代 数方法 关键词：半正定规划；乘性规划；几何规戈；分式锥规划；凸二次规划；微分代 数方法；o a e 方法；对偶 a b s t r a c t t h eo r g a n i z a t i o na n dc o n t e n to ft h i st h e s i sc a nb es u m m a r i z e da 8f o l l o w s ：i n c h a p t e r2 ，f i r s t l y ，w ed e f i n ean e w s e m i d e f i n i t en o n l i n e a rp r o g r a m m i n g - - s e m i d e f m i t e r a u l t i p l i c a t i v ep r o g r a m m i n g ，a n dt h e np r e s e n tt h eo a e8 l g o r i t h mf o ri t s e c o n d l y , w e s h o wt h a ti tc a nb es e e na sas p e c i a lg e o m e t r i cp r o g r a m m i n g ，a n dg i v ei t sg e o m e t r i c d u a l i t y a t1 a s t ，w ed e f i n et h ef r a c t i o n a lc o n i cp r o g r a n a m i n g ，a n dd e v e l o pc h a r n e s a n dc o o p e r st h e o r yf o rt h el i n e a rf r a c t i o n a lp r o g r a m m i n g i nc h a p t e r3 to no n e h a n d ，w eg i v ea ne x a m p l et os h o wam i s t a k ei nr e f e r e n c e 【1 9 】，o nt h eo t h e rh a n d ， w eu s et h em e t h o dw h i c hi sp r e s e n t e di n 1 9 】t od e s i g na na l g o r i t h mf o rt h eq u a d r a i c c o n v e xp r o g r a m m i n ga n dt h es e m i d e f i n i t el i n e a rp r o 目：a m m i n g k e y w o r d s ：s e m i d e f i n i t ep r o g r a m m i n g ；s e m i d e f m i t em u l t i p l i c a t i v ep r o g r a m - m i n g ；g e o m e t r i cp r o g r a m m i n g ；c o n i cf r a c t i o n a lp r o g r a m m i n g ；q u a d r a t i cc o n v e xp r o - g r a m m i n g ；d i f f e r e n t i a l a l g e b r a i cm e t h o d ；o a em e t h o d ；d u a l i t y 符号约定 1 妒：实数域上的t i , 维欧氏空间 s n5 ”，扩+ + ：分别表示是实对称矩阵全体，实半正定矩阵全体，实正定矩阵全体 m ，m 。：分别表示m n 矩阵，n 阶方阵全体 0 表示空集 ，表示单位矩阵 e 表示所有分量为1 的向量 龟表示只有第i 个分量是1 ，其它分量是0 的向量 d i a g ( a ) 表示以向量。的分量为对角元，其它元素为0 的对角矩阵 d e t ( a ) ，a 7 ，a 一，分别表示矩阵a 的行列式，转置。逆矩阵 皇表示定义为的意思 v e c ( a ) 垒( 0 1 l ，a m l ，0 1 2 ，0 t ，1 2 ，a l 。，a m n ) 7 ，即矩阵a 按列拉直 s v e c ( a ) 垒( 1 1 ， h 2 1 ，、j d 。i ，0 2 2 ，v 压口3 2 ， j 口m 2 ，n 。) t ，即矩阵a 的下 三角部分按列拉直，非对角元乘以v 侄 ( a ，b ) 皇t r ( 口7 a ) ，称为f r o b e n i u s 内积，押( ) 表示矩阵的对角元素和，向量形式 的( ) 表示欧氏内积 f n lx b 一口l n b a 圆b 皇l l ，其中a 。 a m l b 一口m n b ， a x = ( l ，x ) ，a 。，x ) ) 7 ，其中x ，a 是对称矩阵( i = l ，m ) a t y = y l a x + - - - + a m ，y 冗m a 兰b ( a 卜b ) ，表示a b 是半正定矩阵( 正定矩阵) 4 骅= ( 笔导) 。其中a 朋。，( a ) 是矩阵函数 ! 祭= ，生地d tl 、。，。，其中a ( t ) m 。是矩阵值函数 、f1。x o 【。i x ) 21 0 $ 隹x 6 。( t i x ) = s u p 扛，z + ) l z x ) h r g m i n f ( x ) x x ) 表示，( z ) 在x 上的最小值解集 o ( z ) 垒扛。i 比t o ，( z ) y ( z ) + 矿，z 一$ ) ) ，表示，( 。) 在点次梯度集合 f 垒( ( z ，矿) 0 ，比x ) ，表示x 的共轭锥 ：表示笛卡儿积 n ( a ，e ) 皇( z l l x , j o 巧i 0 i = 1 ，2 p 再定义一个新函数； f 土 1 g ( f ) = i n f 6 ( ( q x ) + d 0 1 。4 x = 6 x 三0 ，v f 雠 o ， 及新规划t 嘶“p ，娶矗副j 。 ( s d m p 4 ) 由假设可知，g ( ) 是有意义的下面的定理告诉我们。求解( s d m p 4 ) 可通过 求解( s d m p 4 ) 得到 定理2 1 1 如果e 是( s d m p 4 ) 的一个最优解。x 是9 ( 。) 的一个置优解 那么x 是( s d m p 4 ) 的一个最优解 证明设g 是( s d m p 4 ) + 的最优值，x o 和，o 分别是( s d m p 4 ) 的最优解和最 优值因为 喜6 cc g ，x ，+ a t ，p ( 1 9 1 6 c c c ：，x ，+ a o d = 1) 5 p ( 垂c t c ；，x ，+ a 。，) ：， 6 ( ( g ，x ) + d t ) ( 6 ( ( g ，x ) ) p i n ( g ，x ) + d 。) ) ， i ，l，佃l 而且上式等号成立当且仅当 所以 f l ( ( g l i x ) + d 1 ) = f 2 ( ( 岛，x ) + d 2 ) = = 岛c t c ；，x ，+ 由，一( 垂c t c 。，x ，+ 喀，) 5 m t n ( ；娄矗cc c ：，x ，+ a 。，) ie 。，垂6 ) = 垂c c g ，x ，+ 也， 下面要证明g 9 ( ) ) = ，0 第二章半正定非线性规划 一方面，由g 的定义知： ( ，) = ( ；静“，) 9 m i n ( ；娄6 c t c ：，x + ，+ 也，) le 。，垂6 ，) = h ( a ，x ) + 畦) ，o 5 另一方面。令e x a ：( n g 。，警0 ) 1 其中铲。：q 鼎，j ：1 ，p 则有 ( 1 ) 9 ( 。，) 一n ( 凄飘，叫卜。) = m 佃 垂c c g ，x 。，+ 咄，( ；喜矗粼) a x = 乱x 芝。) = ，o 所以( ；9 ( + ) ) = ，。，即有里p ( ( 。，x + ) + 也) = ，。) a i t ix 为( s d m p 4 ) 的一个最 优解。而且有下列的关系式成立 甜( ( g 1 ，x + ) + d z ) = g ( 岛，x ) + d 2 ) ；茹c c g ，x 。，+ 由，= ( 垂c t g ，x + ，+ a 。，) 。 由定理2 1 1 知 g =( 丝竺丛 ( ( a ，x + ) + 也) v = 1 ，p 畦 + ， xq ， 1 ，f f 1 ) ，其中 ( ( c ：，x ，) + 呜) 妒磊忑商蕊i 研“2 1 l a 6 =( 咖 鱼t 吣 a t 旧，) ) ； ( g ，x ) + 以 i = 1 ，2 ，一，p 证明为方便书写，只对1 进行证明设 肌蛔；n 垂c c 啪m ，卜呐x 至。) 因为 ( ( a ，x + ) + d i ) ( ( 岛，x 2 ) + 如) ，( ( q x ，) + d p ) ( ( g 1 ，x + ) + d 1 ) ( ( 岛，x + ) + d 2 ) ( ( q ，x + ) + d p ) = ( 垂cc g ，x 。，+ ) ；( 垂cc a ，x ，+ 吨，) 1 - 5 ( 垂cc g ，x ，+ a 。，) ；( m t n 垂c c c 。，x ，+ 也，i ，；， ( 2 1 1 b ) 一旷 f 疗( ( q ，x ) + 反) 1 i g ：土生生上 ” ( a ，x + ) + d 1 ) 兀( ( g ，x ) 十d ) 型l 一 ( ( 州) ( 咖脚州j ) + 旧，p ) ) l 弓 又因为( ( c l ，x ) + d 1 ) ( c l ，x 1 ) + d 1 ) 及 ( 垂cc c ；，x ，+ 也) ；s ( m t n 垂c t c ：舻，+ 吨，j ，= - z 一，一) ) ； 第二章半正定非线性规划 弘群1 盥唆筹掣 现在给出具体的o a m 算法； s t e p 0 ：用半正定线性规划的原始对偶内点法1 2 2 ，求出 7 d m i n l l ， ，+ d i i 以 = d ， 三u ， 的最优解，根据公式( 2 1 1 ) 算出 的上界f 和下界，令z o = 代7 妒喀 o ) ，取 科e a r g m i n 孝洲泓，圳卜“，x 1三。) i x 1 n 爵( a ，x ) + d ) i 且x = 6 ，三o ， li =j 2 e 酗a ，l 似= b , x hox a r g m i n x x ) ， 2 尊( ( a ，+ d ) 似 ， 、i = lj f 卧r g m i n 娄1c 蜘c 卜增姒，蚓i 似咄x t 。卜 并a 。 ( a g + ( 1 一a ) 等) ( ( g ，x ) + d ) i a x = 6 ，x to ， f =j p ( 埘+ ( 1 一a ) f 2 ) ( ( c ；，x 。) + d i ) ；l g ( m 1 - t - ( 1 一a ) f 2 ) ， 所以g 嬉) 是 f k o ) 上的凹函数 垤 0 ，取 占= 血 哦 + + x x g g 等 毋 ， ” 砷 一 一 l 1 + + d d + + x x q g 醵 ， 一一 一 p99 畦+ xg ， ：亘 。 吨 一 础，n ：叵 + 一， 、 柳 r a 0 ，则算法在有限步之内终止；如果= 0 ，则算法产生 的每一个聚点都是最优解 证明( 1 ) 0 的情形假设算法无限的进行下去那么必存在正常数0 0 ，及 子列f f q 岛 o ，l ，2 ，) ，使得1 一n 孛 目，均经过简单的计算可得，超双曲 面鱼在点裔处的切超平耽州泸 则f k 。( 扣) 皇 盎争- p = o , 均 一p = 0 ，所以1 一 枣；0 ，这与假设矛盾 ，= 】 ( 2 ) s = 0 的情形因为z o 是有界闭集，所以必有聚点设为产生点列的一个 聚点，则存在子列( f b 使得恕f h = 由引理2 i 4 知。9 ( ) 是z 0 上的连续函 数，则9 ( 白= l i mg ( 1 ) 9 ( ) 从而f 即为最优解 口 下面给出号孳实例说明上述算拳的可行性算篱先得到( s d m p 4 ) 的最优解p ， 然后求解r a i n 嚣( ( a ，x ) + 吐) l a x = 6 ，x 兰0 第二章半正定非线性规划 3 0 0 、，41 0 1 、 5 31 9 i c 2 = 1 1 0 3 06 l 1 9 6 2 一1 6 1 5 0 0 、，0 0 0 5 、 oo l ，a 2 = l oo 5o i o o o 5 o 一1 。= ( 砂= ( 0 0 1 1 = o o o ，珈= ( ：) ，磊= g ， x ：= 1 0 0 0 0 - 0 5 9 1 0 0 2 2 5 5 f 1 弱：1 0 b 所以，最优解存在用原始对偶内点法求解，它的最优值是0 3 1 0 1 ，最优解是 弼_ f 器篡 2 昌0 1 0 0 = = 渡 e a 1 1 a 子例 、， o 帖 。毗o l l 第二章半正定非线性规划 1 2 由( 2 1 1 ) 得到，0 0 9 9 2 甜s0 4 3 8 0 2 2 8 3 1 g i 0 0 8 3 5 取e = 9 1 0 1 6 ，运 用本文的算法得到，p = ( 0 1 7 5 4 ，5 7 0 1 9 ) 用原始对偶内点法求解 m i n ( ( ；c 1 + g ，x l a x = b ，x 三o ) 得到它的最优值是3 5 0 4 5 ，最优解是 r 1 j d 0 0 0 x + = l - 0 3 9 5 7 o 0 8 5 6 则m i n ( a ，x ) ( q ，x ) i a x = b ，x 兰o ) 的最优值是3 0 7 0 3 ，最优解是 x = 1 0 0 0 0 0 3 9 5 7 0 0 8 5 6 当把半正定乘性规划问题转化为r a i n 9 ( f ) l 兀6 1 ，fs f ，其中g ( f ) 是 连续单调上升的凹函数由于连续的凹函数在紧凸集的极小值可在某个极点上达到。 而且凹函数在紧凸集上具有局部极小点的全局最优的性质，所以要找在紧凸集上的全 局极小点，只要在紧凸集的极点上寻找即可但是 f l f l 6 i ，i s s f 的极点并 不容易寻找。因此我们的策略一般是构造一系列的有界多面体满足z o ) z k ) z k + 1 z n z 0 忙= 1 ，2 ，) ，然后取p a r g m i n 9 ( f ) 睡y ( z k ) ) 以二维的情况作说明取 p v ( z ) ，过超双曲面兀矗= l 上的点_ = 殳1 作切线交砂的边界于两点，产生 “1 ( 鱼砖) 新的有界多面体z 1 ，根据g ( f ) 的连续性，凹性。及单调上升性。可以断言9 ( f ) 在 z 1 上的极小值可以在z 1 的极点处达到，不妨设极小点是f 1 般来说给定 一个具体的取切线的方案，都会有如下的结果t9 ( f 1 ) s9 ( + ) ，嬉k + 1 ) g ( f 1 ) ， 其中f 是最优解。，( f ) 是一个满足i i m ，( e ) = i 的函数已证明- 给定精度e 0 ， 则算法必在有限步终止如果e = 0 ，则算法产生的点列的聚点即为最优解但是遗憾 的是，无法给出算法的时间复杂性，这是一个值得继续研究的课题是否能将o a e fpp1 算法运用到更一般的乘性规划，如m i n 兀凡( z ) i z d 这是一个值得探讨的 l j 2 l 扭1j 问题另外，本文o a e 算法都要求目标函数是可行域上的正值函数，以保证最优解 的良好性质这无疑是一个极强的条件，能否减弱条件尚须研究 怒一 跏螂哪加加 | l l 一 跚| | 享哪加加 ，。一 第二章半正定非线性规划 2 2 半正定线性乘性规划的几何对偶 1 3 2 2 1 几何规划概述 本节将说明形如( s d m p l ) 的半正定线性乘性规划可以转化为特殊的几何规划， 并且给出其具体的几何对偶形式 令z 。= ( 一) t ，= ) ，e j ，记z = ( z o ，一，一) ，其中，和t ，是有限的指标集， 一形。j ，一7 计，j jn = n o + m + ，x 是冗”的一个锥。它 的共轭锥f = 矿f ( z ，) o ，z x g k ：冗”t 一冗是闭真凸函效( c l o s e dp r o p e r c o n v e xf u n c t i o n ) j 2 4 1 ，它的有效域是c k ，它的共轭函数记为虻( 矿) ，正奇次扩张函数 记为鲒( 矿，肌) ，其中 虻( 扩) = s u p ( 扩，z “) 一g k ( x ) ) ，( 2 2 1 ) 9 ( 矿，“k ) = 互为几何对偶的规戈d 是指具有如下形式的规划 斗训h p 恸“，l 第篙 m t n g c z ，a ，= 虻c 护，+ t e l 菇+ c z “，x t ，l 兰善兰。；：歹 z ) ( ，z ) ( ， 肼( ) 兰o ，i j ；菇( 一) so ，j 正 z ，z ) = 0 z “o g o ( = o ) ， a = 0 ，( z 。，z ) = s u p ( e t ，z t ) ，或者 i 0 ，z “e i o g , ( 士) ，t j c e b 心2 0 ，( 一一) = ! u p ( 一，一) ，或者脚 0 ，一脚锄( 一心) ，j 正 d e g 。 凡g i ( z ) = o ， j ；如菇( 一+ ) = o ，j j ( g p ) ( d g p ) ( 2 2 3 8 ) ( 2 2 3 b ) ( 2 2 3 c ) ( 2 2 3 d ) ( 2 2 3 e ) ( 2 2 3 f ) ( 2 2 3 9 ) 0 + 鲰 挑 果果它如如其 一 沁审 泌州慨 ，-f、ll【 第二章半正定非线性规划 1 4 如果c 。：7 p 0 u g ：7 z 0 j ) ，那么( 2 2 3 e ) 和( 2 - 2 3 f ) 可以分别用 ( 2 , 2 3 e ) 和( 2 2 3 0 代替 k 0 ，z “a ，a 甄( 。) ，i ， ( 2 2 - 3 e ) 。 “0 ，一蜥a 野【一脚) ，j j ， ( 2 ，2 3 i ) 性质2 2 1i 群19 ( z ) 是闭凸真函数， g + ( 矿) 是g ( z ) 的共轭函数，则 ( z ，一) 9 l ( 矿) + g ( z ) ， 而且等号成立当且仅当矿0 9 0 ) - 性质2 2 2 如果0 ，i s ) 和( 一， ) 分别是r 6 咧和p a p ) 的可行解则 甜( 0 3 i ，茁如) a ，m ( 一) 十西+ ( 王；，九) ，v i i ，而且等号成立当且仅当( 2 2 3 e ) 成立； 叫( 一，一+ ) 助疗( 舻+ ) 十疗( q ，脚) ，w 而且等号成立当且仅当( 2 - 2 - 3 f ) 成立 证明仅证第i ) 种情形。第i i ) 种情形可以类似证明 当k ；0 时，( 一，$ “) s u p ( z ，$ “) = j i e i ( x ) + g r ( 。 ) ，且等号成立当且 冗” 仅当( 2 2 3 e ) 成立 当九 0 时， k i d ( 一) 4 - 蝣+ ( z “， 。) = 曲( z ) + 。西( ) a i g 。( 一) 4 - 九( ( 一， ) 一仇( 一) ) 一 = ( 一，髫“) 且由性质2 2 1 知，等号成立当且仅当( 2 2 。3 e ) 成立。 口 定理2 2 3 如秉( z ，p ) 和( 矿， ) 分剐是r g 彤和伊g 彤, i 铲r , , f f q i f 一则 0 s g ( z ，p ) + g ( z ， ) ， 且等号成立当且仅当( 2 2 3 c ) 一( 2 2 3 9 ) 成立 第二章半正定非线性规划 1 5 证明 g ( z ，p ) + g ( z ，a ) = 卯( 护) + 疗( 一，脚) + 懿( 一) + 酊+ ( 。”，a 。) j e ji e i 兰9 0 ( z o ) + 酣( z “) + ( 对( 一，如) + 酊( 一) ) + ( 9 ：+ o + ，九) + 凡仇( ) ) j ji e j ( z o ，z “) + ( 一，) + ( ，z “) j ji e ! = ( 最z ) 0 ， 且由性质2 2 1 知，等号成立当且仅当( 2 2 3 c ) 一( 2 2 3 9 ) 被满足 o 几何规划更详尽的知识可参见【2 5 】 2 2 2 半正定乘性规划的几何对偶 假设乘积目标函数中的每一个函数在可行域上都是恒正的凹函数，且峨0 ，通 过等价变换把( s d m p l ) 作变成如下的规划。 口 m i n 一a i l o g8 i + 6 ( 口i ( g ) s t 0 ) + s ：s0 ，t = 1 ，- 一，p 吼一s ：；o ，f = 1 ，p ( s d m p s ) y y = 0 ，t = 1 ，p r y a 0 为了说明( s d m p i ) 是一个特殊的几何规划，我们给出如下的对应关系t ，= f 1 ，2 ，升，j = 以 一h ( y ，8 1 ，卸，o ) ， z 1 一( v 1 ，! ，p ，s j ，) x 一 ( 玑y 1 ，y p ，8 h ，8 p ，s ；，s 玉n ) p 助( z o ) 一一啦l 卵& + 6 ( n g ) ) ， t = 1 g i ( x ) h - i , ( y ) + s ：o ，i = 1 ，n ( 2 2 4 8 ) ( 2 2 4 b ) ( 2 2 4 c ) ( 2 2 4 d ) ( 2 2 4 e ) ( 2 2 4 f ) s 吼仉一 a j i j j 一劣窖 第二章半正定非线性规划 把目标函数视作一妻m l o g5 。+ 6 ( d l 回) + ( o ，) ，即有( 2 2 4 b ) 式的对应关系 现在分步完成( s d m p 5 ) 几何对偶形式： ( 1 ) 求几何对偶的目标函数( 见附录a 1 ) 令也( s ，) = - a il o g ( s ) ，则 忡扣一t 扣t 1 0 9 ( 一嚣) “( s ： ， 仉，o 牡拈归 第二章半正定非线性规划 1 7 综合( 1 ) 和( 2 ) ，给出( s d m p 5 ) 的几何对偶规划 m i n 三( 一。t + n tl o g ( 暑) ) + 三 - ( 一，i r ( - - 。u ) + ( x ，g ) “- a x + 吕矿_ 0 ( s d m p 6 ) a ， 0 ，矿冗m ，i = 1 ，一，p x 0 ( 3 ) 极值条件( 见附录a 3 ) 如果( s d m p 5 ) 和( s d m p 6 ) 的可行解满足以下的条件，则它们是( s d m p 5 ) 和 ( s d m p 6 ) 的最优解 ( c 一a t y ，x ) = 0 ( ) = 善，t = 1 ，p ， 矿a ，a ，( 扩) ，i = 1 ，p 当f , c y ) = d t y + d ；时， c 刊( 等) = ，鬻 ( 以一笔) w ，+ 也) = = 相对应的( s d m p 6 ) 转化为 a 。一 矿= a 。c l r a i n ( d i 凡一啦l o g a t ) + ( 啦l o g a i 啦) + ( x ，g ) ， i - 1 口 2 i 8 “n 蚤凡凸o ( s d m p t )i = j 0 ，i = 1 ，p x 0 它的极值条件为 ( c 一4 7 ，x ) = 0 ， c i t y + 虻是，p 第二章半正定非线性规划 1 8 2 3 分式锥规划 一般的线性分式规划可表示为： m “ 筹卜啦。) “1 万可p 9 跎o j 1 9 6 2 年，c h i m e s 和c o o p e r 得到分式规划的重要定理 2 1 1 在可行域有界的情 形下，它的最优解可以通过求解两个线性规划得到本节对此进行推广定义了一种 新的规划线性分式锥规划，并且也得到了相类似的结论，它的最优解可以通过 求解两个线性锥规划而得到但是不要求可行域有界 定义以下的规划为线性分式锥规划： m t n ( 嚣尚i 出她。e 州， 其中z ，c ，d 秽b 冗“，o t ，卢冗，a 是7 p 到7 0 “的线性映射，是闭凸的点锥 ( 点锥即丘n ( - k ：) = 0 ) 假设协 = b ，z 丘) ，( d ，z ) + 卢0 再定义两个新的线性锥规划问题 m i n ( c ，v ) + t a l 4 y t b = 0 ，( d ，g ) + 口= 1 ，g c ，t o f p ( 2 ) m i n 一( c ，y ) 一a 1 4 ”一t b = 0 ，一( d ，) 一卢= 1 ，”c ，t o f p ( 3 ) 下面的定理将表明在f p ( 2 ) f p ( 3 ) 有最优解的情况下，可以通过求解线性规划 f p ( 2 ) ，f p ( 3 ) 得到分式规划f p ( i ) 的最优解 定理2 3 1 设( 9 2 ，如) ，慨，t a ) 分别是f p ( 2 ) ，f p ( 3 ) 的最优解，则或者譬是 f p ( 1 ) 的最优解，或者警是f p ( 1 ) 的i 优解 证明比。 z l t z = b ，z 研，我们将证明t 如果( d ，矿) 4 - 卢 0 ，那么 ( c ，矿) + 口、( c 等) + q 雨研而 如果( d ，z ) + 卢 ( d ，妒) 十p 。 这样，就能断定( f p l ) 的最优解可以从( f p 2 ) 和( f p 3 ) 的最优解中产生 一p + 一+ 、一、， 盥“一垃b g 一0 第二章半正定非线性规划1 9 显然普，等坛，a 蛩。b ， “t 35b ，从而蛩，蛩是f p ( i ) 的可行解t 设( d ，矿) + 口 0 ，令f = 瓦而1 0 ，雪= b ，易知，( 蟊0 是f p ( 2 ) 的可行 器d 嵩= 器d 篙- ( c 厕恤( ，z + ) + 卢( ，口) + 硇、。7 ；兰甓= 黼：r c ，抛，+ 如。， ( d ，警) + 口 ( 。，珈) + t 印 ”“” 又( y 2 t 2 ) 是f p ( 2 ) 的最优解。所以 ! ! ! 苎：2 ! d ，矿) + p 一 同理可证t 如果( d ，+ ) + 口 ( d ，矿) + 卢一 从而可以断定警，蟹必有一个是f p ( 1 ) 的最优解 口 定理2 3 2 设r 是f p ( 1 ) 的一个最优解，如果( d ，矿) + p 0 ，刖f p ( 2 ) 有最优 解( 南，南) ；如果( d t 矿) + p 0 ，则f p ( 3 ) 有王优并( 一南，一南) 证明不妨设d ，矿) + 卢 0 ，显然，( 如，幻是f p ( 3 ) 的 一个可行解现用反证法证明，假设f p ( 3 ) 有最优解( 驰，0 3 ) ，满足 则下式成立 一( c ，y 3 ) 一t 3 a o ) 0 ，这隐含- 9 = x l a x = b ， o ) 0 ； ( b ) 对于嚣哥，有疋= ( g ，z ) l c + q 茁一= 一a 7 = 0 ，z o ) o ； ( c ) a 是行满秩矩阵； ( d ) ( q p ) 有最优解牙，记孟a r g m i n c t z + ，0 。i 儿= b ，z2o ) 求解( q p ) 的方法较多，本文主要讨论用微分代数方法来求解( q p ) 为此，先引 入障碍函数b ( z ) = 击，考虑 鼬时 + 扣+ 巷引a x = b , x o ) c ， 易知，v o o l a x = b ，茁 o ) ，有 m 扣螂喜 m 尹1q x m i n m ；瑜i a x = b , x _ 0 ) ， 从而口( p ) 是有意义的 定理3 l 1i n 州肛) i 肛 o ) = 。躲= m i n c t x + x t q x l a x = 6 ，。o ) 证明由于口( p ) 是关于p 的单调上升函数并且有下界，所以 i 1 1 f 口( p ) i p o ) = l 蜒口( p ) 第三章半正定线性规划 0 ，v z x l a x = b ，2 o ，有 ，i * t 叭c t z 埽1 孙+ 嘻去， 所以 m t n c ? z + 互1 茁r 日z la x = 。，z 。) st n f 口( p ) i p 。 另一方面，设 苛a r g m i n c t x + i i z t q 。i a 嚣= 6 ，工0 ) ， 则对v e 0 ，由下确界的定义知，必存在意( x i a x = b ，茁0 ) ，使得 ，牙+ 互1 z t + c t 童+ 汐 由假设( a ) ，可取x o s ，由函数连续性知，存在j 0 ，使得 = i + 6 x o x l a x = b ，z o ) ， 且 c t 牙+ ：牙7 q 孟+ s ，岔+ ；7 q 从而 ，牙增1 协+ p 喜扣 ，1 瑚撕喜去刈n 两边同时取极限p 。0 + 得，c + i l z - 7 口牙+ e 。l - + i m 。，o ( p ) 由 0 的任意性知， m i n ，茁+ 扩q x a = b ，$ o ) m l i m + 0 ( # ) 所以 i n 印( 肌 0 ) _ 州l i r a 鼬) = 幽 ，抖j 1 粕刮a x = b , x _ o ) d 下面总是假设托 0 ，( q p 。) 有最优解 若$ 是( q p ) 的最优解，由k t 条件知，必存在y ，z 满足下列方程。 c + 0 z z a t y = 0 ， ( 3 1 1 a ) a x = b ， ( 3 1 _ i b ) x 2 z = 肛， ( 3 , 1 i c ) z 0 ，： 0 ，冗“， ( 3 1 i d ) 其中x = d i a g ( 霉) ，z = d i a g ( z ) 当肛= 0 时，( 3 1 1 ) 的解就是( q p ) 的最优解 第三章半正定线性规划 引理3 1 2 设a r “。“是行满秩矩阵，m s “。“是正定矩阵，那么a m a t 是正定矩阵 证明：首先a 可表示成a = p 1 ( ko ) p 2 ，其中p l 是m 阶可逆矩阵，p 2 是n 阶可逆矩阵，k 是m 阶单位阵 a m a t = p l ( k 。) 岛m 可( 台) b y = v , 尬t 砰 其中p 2 m 呀= ( m n 。舰m 2 2 2 ) 所以，m 是正定矩阵意昧着a m 也是正定短 阵 口 令 f l ，玑；，“) = c + q 一z 一f = 0 ， f 2 扛，v ，= ，p ) = a z b= 0 ，( 3 1 2 ) f 3 0 ，玑z ，p ) = x 2 z p j = 0 下面的定理将表明z ( 且) ，( p ) ，；( _ “) 是关于p 的连续可微函数，进而口( p ) 也是p 的连续可微函数 定理3 1 3 对于给定满足( 3 1 2 ) 的跏墨( 珈，z o ) b 。和 o 0 ，方程组 ( 3 1 2 ) 一定有唯一通过点( z o ，g o ，z o ) 的连续可微的解和( “) ，( p ) ，z 似) ) ，进而 烈钉弩1 缸) t 驯卅p 善壶 是p 的连续可微函数，而且老= 耋壶 证明记了( z o ，y o ，z 0 ) 为方程组( 3 1 1 ) 在点( $ o ，暑f o ，匈) 的j a c o b i 行列式因 是正定矩阵，q 是半正定矩阵，则2 x f l z + q 是正定的，从而1 2 x o z o + 瑶q i o 第三章半正定线性规划 困此 舶m , z o ，= f 。耋“0 7 引0 z o 0 ，( 珈，) = l a l i2 柳i oj rj f = l 以 o o 】 f 砑q + 2 x o z o 五o 7 o f = ( 一) “ 搿q 2 磊一三a ， = c z ，“f2 硒z ：粥口薯 7f 卟矿 2 硒，瑚惝而蔷嘲a 一 2 ( 1 ) “1 2 x o z o 十x o q i i a ( 2 x o z o 十瑶0 ) 1 砑以7 j 从而s ( x o ，珈，铀) 0 由隐函数存在定理知，存在脚的某个邻域方程组( 3 1 1 ) 有 唯过点( 知，y o ，z o ) 关于p 0 的连续可傲解。) ，) ，；( p ) ，即 ( z o ，y o ，翔) = ( $ ( 脚) ，”( 伽) ，。( 脚) ) 鼬) c 垮1 驰+ 嘻嘉 州一7 以卅咖附( 卅卢吾n 焉券t + 娄高 叫叶啦_ 尸一+ 萎嘉 = 几w ( 卅善志 一方面 f y t ( p ) z ( p ) 】：【矿( p ) 翻，：，7 ( “) 6 第三章半正定线性规划 另一方面， 凶t ( p ) a z ( p ) = 掣盯( p ) a 茁( p ) + y t ( p ) 4 2 7 ( p ) = 可盯( p ) 6 + y t ( 1 a ) a x 7 ( p ) ， 所以y t ( p ) a c u ) = 0 ，故( p ) = 三可1 万 口 下面给出例子说明初始点的存在性； 例子3 1 1 对于下列二次规划 r a i n 一鬻z l + z 2 一孚士3 + 。 + 互3 z ；+ ；+ x l x 2 + 2 + z l 3 s t z l + 石2 一$ 3 = 1 2 x l 一互2 = 1 o l 0 ，霉2 0 一( ) 丁一( 器圹珈= ( 罟，一箬) t 一- 是定理3 1 3 要求的初始点 由定理3 1 3 知。只要求得i n f 口( p ) 0 ) 的最优解，就可得到( q p ) 的最优 解为此选取口( p ) 负梯度方向作为搜索方向， 咖d o亡1 d t d p 鲁x i 设( 跚，p o ，加，p o ) 是定理3 1 3 要求的初始点，由定理3 1 3 知，去是关于肛 的连续可微函数，由微分方程解的存在唯性定理知，肛是t 的连续可微函数。因 此z ，y ，；都是关于t 的连续可微函数对( 3 1 1 ) 关于t 求导得到。 由( 3 1 3 ) 知 q 鲁一鲁一害= o a 鲁= o z x z 害+ x 2 塞= 尝e 塑：一婴：一妻当，dt 咖 鲁如 象= 一等( a m ) 4 a m x 。2 e ， 塞= 。l _ d 扩p x 。z - 1 e _ _ ；x 鲁， d z 砒= - 2 z m ( a t d 蹴y 一；象旷1 e ) ( 3 1 3 a ) ( 3 1 3 b ) ( 3 1 3 c ) ( 3 1 4 a ) ( 3 1 4 b )