（运筹学与控制论专业论文）对称锥优化的某些光滑函数及其应用.pdf

摘要 本论文主要研究对称锥优化中的若干光滑函数及其应用，包括对称锥互补问题的 c m 类光滑函数和f i s h e r - b u r m e i s t e r 光滑函数及c m 类中的c h e n h a r k e r - k a n z o w s m a l e ( c h k s ) 光滑函数在求解线性对称锥规划中的应用；包括对称锥互补问题的一类效 益函数及其在求解对称锥互补问题的应用；还包括一个用于求解非凸半定规戈憎9 非线性 l a g r a n g e 函数本论文取得的主要结果可概括如下： 1 第2 章以欧氏j o r d a n 代数为基础将c h e n ，m a n g a s a r i a n ( 1 9 9 8 ) 提出的一类光滑函数 及f i s h e r - b u r m e i s t e r 光滑函数推广用于处理对称锥互补问题特别地，证明了c h k s 光滑函数及f i s h e r - b u r m e i s t e r 光滑函数的连续可微性基于c h k s 光滑函数，提出 了求解线性对称锥规划的一个非内点连续算法，在适当的条件下，证明了该算法是全 局和局部二次收敛的作为一个具体的应用，该算法被用于求解线性二阶锥规划，得 到了类似的收敛结果 2 第3 章基于欧氏j o r d a n 代数的性质，提出了对称锥互补问题的一类效益函数讨论 了在适当的条件下，基于这类效益函数建立了对称锥互补问题解的一个全局误差界 及这类效益函数水平集的有界性，证明了两个具体函数满足所提出的理论作为一个 具体的应用，结合二阶锥的性质，这类函数被用于处理= 阶锥互补问题 3 第4 章给出了非凸半定规划的一个非线性l a g r a n g e 算法的收敛理论在适当条件 下，证明了罚参数存在一个阀值，当罚参数小于这一阀值时，由非线性l a g r a n g e 算 法产生的序列局部收敛到原问题的k a r u s h - k u h n - t u c k e r ( k k t ) 解，并建立了参数解 的误差估计式 关键词：欧氏j o r d a n 代数，对称锥互补问题，半定互补问题，二阶锥互补问题，线性 非线性互补问题，线性对称锥规划，线性半定规划，线性二阶锥规划，非凸半定规划，光 滑函数，效益函数，非内点连续算法，非线性l a g r a n g e 函数，非线性l a g r a n g e 算法 a b s t r a c t t i n sd i s s e r t a t i o ni sd e v o t e dt ot h es t u d yo fs e v e r a ls m o o t h i n gf u n c t i o n so fs y m m e t r i c c o n eo p t i m i z a t i o na n dt h e i ra p p l i c a t i o n s i tc o n s i s t so fs t u d y i n gt h ec l a s so fc a ds m o o t h - i n gf u n c t i o n sa n dt h ef i s h e r b u r m e i s t e rs m o o t h i n g f u n c t i o nf o rs y m m e r i cc o n ec o m p l e - m e n t a r i t yp r o b l e m s ，a n dt h ea p p l i c a t i o no ft h ec h k ss m o o t h i n gf u n c t i o n ，as p e c i f i c f u n c t i o ni nt h ec mc l a s s ，t os o l v i n gl i n e a rs y m m e t r i cc o n ep r o g r a m m i n g a n ds t u d y i n ga c l a s so fm e r i tf u n c t i o n sf o rs y m m e t r i cc o n ec o m p l e m e n t a r i t yp r o b l e m sa n di t sa p p l i c a t i o n t os o l v i n gs y m m e t r i cc o n ec o m p l e m e n t a r i t yp r o b l e m s a sw e l la ss t u d y i n gan o n l i n e a rl a - g r a n g i a nf u n c t i o nf o rn o n c o n v e x s e m i d e f i n i t ep r o g r a m m i n g t h em a i nr e s u l t s ，o b t a i n e d i nt h i sd i s s e r t a t i o n m a yb es u m m a r i z e da sf o l l o w s ： 1 c h a p t e r2 ，b a s e d o nt h et h e o r yo fe u c l i d e a nj o r d a na l g e b r a s ，e x t e n d sac l a s so f s m o o t h i n g f u n c t i o n s p r o p o s e db yc h e n ，m a n g a s a r i a z l ( 1 9 9 8 ) a n dt h ef i s h e r b u r m e i s t e r s m o o t h i n gf u n c t i o nf o rs o l v i n gn o n l i n e a rc o m p l e m e n t a r i t yp r o b l e m s ，t od e a l i n gw i t h s y m m e t r i c c o n ec o m p l e m e n t a r i t yp r o b l e m s i np a r t i c u l a r ，i ts h o w st h a tc h k ss m o o t h - i n gf u n c t i o na n dt h ef i s h e r b u r m e i s t e rs m o o t h i n g f u n c t i o na r ec o n t i n u o u s l yd i f f e r e n t i a b l e b a s e do nc h k s s m o o t h i n gf u n c t i o n ，an o n i n t e r i o rc o n t i n u a t i o na l g o r i t h mi s c o n s t r u c t e df o rl i n e a rs y m m e t r i cc o n ep r o g r a m m i n g ，w i n c hi sp r o v e nt oh a v eg l o b a l a n dl o c a l l yq u a d r a t i cc o n v e r g e n c e su n d e rc e r t a i na s s u m p t i o n s a sas p e c i f i ca p p l i c a - t i o n ，t h ea l g o r i t h mi se m p l o y e dt os o l v el i n e a rs e c o n d - o r d e rc o n ep r o g r a m m i n g ，a n d s i m i l a rc o n v e r g e n c er e s u l t sa r eo b t a j n e d 2 c h a p t e r3 ，b a s e do nt h ep r o p e r t i e so fe u c l i d e a nj o r d a na l g e b r a s ，p r o p o s e sac l a s s o fm e r i tf u n c t i o n sf o rs y m m e t r i cc o n ec o m p l e m e n t a r i t yp r o b l e m s ，a n de s t a b l i s h sa g l o b a le r r o rb o u n df o rt h es o l u t i o nt os y m m e t r i cc o n ec o m p l e m e n t a r i t yp r o b l e m sa s w e i la st h el e v e lb o u n d e d n e s so fe v e r ym e r i tf u n c t i o nu n d e rs o m es u i t a b l ea s s u m p t i o n s m o r e o v e r ，t w os p e c i f i cf u n c t i o n sa r ed e m o n s t r a t e dt os a t i s f yt h ep r o p o s e dt h e o r y a s as p e c i f i ca p p l i c a t i o n ，t h ec l a s so fm e r i tf u n c t i o n si su s e dt od e a lw i t hs e c o n d - o r d e r c o n ec o m p l e m e n t a r i t yp r o b l e m s ，c o m b i n e dw i t ht h ep r o p e r t i e so fs e c o n d o r d e rc o n e 3 c h a p t e r 4i sd e v o t e dt ot h es t u d yo ft h e c o n v e r g e n c et h e o r yo f an o n l i n e a rl a g r a n g ea l g o r i t h m f o rn o n c o n v e xs e m i d e f i n i t ep r o g r a m m i n g u n d e rs o m em i l da s s u m p t i o n s ，i ti s p r o v e dt h a tt h e r ee x i s t sat h r e s h o l do ft h ep e n a l t yp a r a m e t e rs u c ht h a tt h es e q u e n c e s n l g e n e r a t e db yt h e1 2 0 n l l n e a ra l g o r i t h mi o c a t l yc o n v e r g et ot h ek a r u s h - k u h n - t f l c k e r ( k k t ) p o i n t n o n c o n v e xs e m i d e f i a i t ep r o g r a m m i n gw h e nt h ep e n a l t yp a r a m e t e ri s l e s st h a nt h et h r e s h o l d m o r e o v e r ，w ee s t a b l i s ht h ee r r o rb o u n do ft h es o l u t i o n sw i t h t h ep e n a l t yp a r a m e t e r k e yw o r d s ：e u c l i d e a nj o r d a na l g e b r a s ，s y m m e t r i cc o n ec o m p l e m e n t a r i t yp r o b l e m s ， s e m i d e f i n i t ec o m p l e m e n t a r i t yp r o b l e m s ，s e c o n d - o r d e rc o n ec o m p l e m e n t a r i t yp r o b l e m s 、 l i n e a r n o n l i n e a rc o m p l e m e n t a r i t yp r o b l e m s ，l i n e a rs y m m e t r i cc o n ep r o g r a m m i n g ，l i n e a r s e m i d e f i n i t ep r o g r a m m i n g ，l i n e a rs e c o n d o r d e rc o n ep r o g r a m m i n g ，n o n c o n v e xs e m i d e f - i n i t ep r o g r a m m i n g ，s m o o t h i n gf u n c t i o n ，m e r i tf u n c t i o n ，n o n i n t e r i o rc o n t i n u a t i o n a l g o - r i t h m ，n o n l i n e a rl a g r a n g ef u n c t i o n ，n o n l i n e a rl a g r a n g ea l g o r i t h m 符号说明 下面我们给出本论文中常用符号代表的含义 1 了：n 维向量空间， 尼c 了：对称锥， i n t k ：瓦的内部； 2 础( r ；，哞+ ) ：n 维( 非负，正) 实数空间 n ：自然数集； 3 0 “：= r r ”， q ；= z = ( x o ，蜃) q “f 。o i i 孟| | ) ：二阶锥， 0 + ：= q r d - 0 7 4 s n ( 霹，毋+ ) ：n n 实对称( 半正定，正定) 矩阵空间； 5 。”：j o r d a n 乘法， e ：j o r d a n 代数的单位元； 6 比，y j ，( 。，y ) = t r ( 2 ：o ) ：。与y 的内积 忙| 1 = t r ( z 2 ) ：z 的f 一范数； 7 z 三( 万5 可) ：x y 尼( 一尼) ； 8 a ( 一) ：特征值映射； 9 f ：定义在醒上的函数，的一阶导数； 1 0 a ，0 2 ：实值函数，关于。的偏导数； 1 1 v ，：向景值函数，的梯度， v 7 ，：向量值函数，的j a c o b i 矩阵； 1 2 l 。：从，到了的线性映射且k ( z ) = c 。z e 1 ：l 。的逆映射； 1 3 、b 歹，【z + ：= a r g m i n f e k l i z 一毒i i ； 1 4 ，b s ”，a b ：= t r ( a t b ) ， o ：矩阵的k r o n e c k e r 内积； 1 5 a + ：矩阵的m o o r e - p e n r o s e 逆； 1 6 v e c ( ) ：矩阵的拉直运算； 1 7 # = ( z l ，z 2 ) ：= ( 2 ，z ；) t ； 1 8 o ( ) ：l i r as u p t 。oo ( t ) t 0 光滑化函数廿得到参数化的方程组 h ( z ，卢) = 0 ，然后采用n e w t o n 类算法求解该方程组，并通过逐步调整光滑参数p 趋于0 从而得到非线性互补问题的一个近似解类似于内点算法中的路径跟踪算法，随着光滑 参数趋于0 ，光滑方程组的解构成了一条趋于最优解集的路径但是与内点法不同的是， 光滑化方法可以选取任意初始点，并且在算法实施的过程中，不需要内点的限制，因此， 光滑化方法成为求解互补问题的一颇受青睐的方法 c h e n ，h a r k e r ( 1 9 9 3 ) 【2 2 】首先提出了一个非内点连续算法用于求解线性互补问题； k a n z o w ( 1 9 9 6 ) 6 2 】通过修正光滑化函数对该算法进行了改进，他们所使用的光滑函数是 基于如下形式函数 m ) = ；( 。+ 4 7 7 4 ) 2 第一章绪论 的光滑化函数( z ，y ，p ) = z p 州z y ) p ) ，后来，此函数被人们称为c h e n h a r k e r - k a n z o w s m a l e ( c h k s ) 光滑函数此后，光滑化方法得到了迅速的发展。见c h e n ，c h e n ( 1 9 9 9 ) 2 0 ，c h e n ，x i u ( 1 9 9 9 ) 2 3 ，c h e n ，m a n g a s a r i a n ( 1 9 9 8 ) 2 5 ，b u r k e ，x u ( 2 0 0 0 ) 1 8 ， h o t t a ，y o s h i s e ( 1 9 9 9 ) 5 4 ，k a n z o w ，p i e p e r ( 1 9 9 9 ) 6 3 ，t s e n g ( 1 9 9 9 ) 1 0 9 ，x u ( 2 0 0 0 ) n 5 】等 等在讨论光滑化方法的时候，光滑函数的选取从一定意义上来说是光滑化方法的核心 问题，人们提出了不同形式的光滑函数c h e r t ，m a n g a s a x i a n ( 1 9 9 5 ) 2 4 】提出了基于如下 形式神经网络函数 f ( a ) = l o g ( 1 + e o ) 的光滑函数咖( z ，g ，p ) = z p ，( ( z 一) 肛) ，函数p ，( 8 p ) 正是+ = m a x o ，o ) 的凝聚 函数，有关凝聚函数更深入的讨论见l i ( 1 9 9 1 ) 7 3 随后，c h e n ，m a n g a s a r i a n ( 1 9 9 8 ) 2 5 提出了c m 类： 西( z ，y ，卢) = o p ，( ( 。一y ) z ) ， 其中，c m ，c m 是由定义1 4 6 给出的全体函数构成的集合，其中定义，的，是满 足以下三个条件的实值函数： a ，：r r + 是连续可微的凸函数； b ，l i r a 。，( n ) = 0 ，l i m 。( ，( a ) 一d ) = o ； c v 盘r ，0 o ，v g 0 ( y ，z ) = ( 。，) ， ( z ，x 。y ) = 忙。z ，y ) 则称( ，。) 是欧氏j o r d a n 代数 单位元( i d e n t i 七y ) 对于j o r d a n 代数( ，。) ，如果存在e ，使得坛，有e 。z = zoe = 。，则称e 是j o r d a n 代数( 了) 的单位元我们假设所讨论的j o r d a n 代数都存在 单位元 引理1 4 3 设( 了。) 是一欧氏j o r d a n 代数，则= 矿i z j ) 是一对称锥，称之为了 的平方锥反之，每一个对称锥都是某个欧氏j o r d a n 代数的平方锥 由上面的引理，得到 定义k 实对称矩阵空间s 。上的乘法，z o y = ( x y + 。) 2 ，则s 睾= 护f 。s 6 ) 定义k 维向量空间q 。上的乘法，坛= ( 。q ，2 ) ，y = 扫o ，口) 砂，z 。y = ( x t y ，z o 雪+ s 幻孑) ，贝0 q 睾= z 2 。0 ) 、 定义k 维向量空间瞅上的乘法，。oy = ( x z y ”z 。洳) ( 向量的h a r d a r m a r d 乘 法) ，则r j = z 2j z r ) 秩( r a n k ) 妇了，定义z 的秩如下： r a n k ( x ) 兰m i n k o i a o e + a l z + + - + a k 。2 = 0 ，j 九o ) j o r d a n 代数j 的秩r a n k ( 了) ；m a x x jr a n k ( z ) 特征多项式( c h a r a c t e r i s t i cp o l y n o m i a l ) ，特征值( e i g e n v a l u e s ) 若r a n k ( ：7 ) = r ，则比 ，存在实数衄( z ) ，( z ) 使得 。一a l ( z ) z 7 1 + + ( 一1 ) a ，( z ) e = 0 8 第一章绪论 我们称a 7 一n t ( z ) a r - 1 + + ( 一1 ) a ，( z ) 是x 的特征多项式，它的根a 1 ( z ) ，a 2 ( z ) ，砖( z ) 为z 的特征值若z 的所有特征值都是非负实数，则称z 是半定的，记作z 三o ；若z 的 所有特征值都是正实数，则称。是正定的，记作。 - 0 迹( t r a c e ) ，行列式( d e t e r m i n a n t ) v 。了，定义。的迹，行列式分别如下 t r ( x ) ；凡( z ) = a l ( 正) ， = l d e t ( x ) ；i i a t ( z ) = a r ( z ) i = 1 幂等元( i d e m p o t e n t ) ，j o r d a n 标架( j o r d a nf r a m e ) 对于j o r d a n 代数了，若c ，满足 c 2 = c ，则称c 是一个幂等元；若两个幂等元e ，d 满足c o d = 0 ，则称c 与d 正交；如果一个 非零幂等元不能表示成另外两个非零幂等元之和，则称该幂等元为本原幂等元( p r i m i t i v e i d e m p o t e n t ) ；如果 二f ) 是彼此正交的幂等元且满足c i = e ，其中e 是j o r d a n 代数的 单位元，则称 c 1 ) 是一个完全系；如果一个完全系中的元素都是本原幂等元，则称这个 完全系为j o r d a n 标架；如果r a n k ( = r ，则了中的每个j o r d a n 标架恰好含有r 个元 素 当了= s 2 ，驴，酣时，分别有下述结论 了= s 比s ，茁的特征值就是矩阵z 的特征值凡( z ) 0 = 1 ，k ) ，幂等元 c i ( z ) = p i ( 溉( z ) 7 ，i = 1 、，k ，其中p i ( t ) 是对应于特征值k ( ) 的特征向量，构成 了一个j o r d a n 标架； ，= 0 v 。= ( z o ，牙) q ，令 巾) = 调! ；重： 其中w ( x ) 满足i l w ( 2 ：) l i = 1 ，则z 的特征值分别为a 1 ( z ) = 2 ：0 + 恻，a z ( 。) = 一恻j ， 幂等元c 1 ( z ) = ；( 1 ，u ( 。) ) 及q ( z ) = ( 1 ，一“( 。) ) 构成了一个j o r d a n 标架 j = r = ( z 1 ，。k ) 融，则z 的特征值为她，i = 1 ，幂等元q ( $ ) = e t ，i = 1 ，其中q 的第i 个元素是1 ，其余的元素是0 ，构成了一个j o r d a n 标 架 引理1 4 4 ( 谱分解形式1 ) 假设了是一欧氏j o r d a n 代数，则对任意的z 歹，存在唯 一不相同的实数 l 扛) ，k ( z ) 以及唯一的完全系c 1 ( z ) ，c k ( 2 ：) 满足 z = a 1 ( z ) c l ( z ) + + a ( z ) k ( 。) 9 大连理工大学博士学位论文：对称锥优化的某些光滑函数及其应用 引理1 4 5 ( 谱分解形式2 ) 假设了是一欧氏j o r d a n 代数且r a n k ( j ) = r ，则对任意的 万j ，存在一个j o r d a n 标架c 1 ( z ) ，c r ( z ) 以及实数入1 0 ) ，a ，( z ) 满足 z = a l ( z ) c l ( z ) + - + a ，( z ) c r ( z ) ， 其中九， = 1 ，r 是z 的特征值 根据上瑟的引理，我们可以把任意实值连续函数，推广到j o r d a n 代数了上 定义1 4 6 v x j ，由谱分解形式2 ，我们有z = a l ( z ) c l 扛) + + k 扣) 白( 。) ，定义 f ：了一，如下： f ( z ) ；，( a - ( x ) ) c l ( x ) + 十，( a ，扛) ) c r ) 由定义14 6 ，我们得到下列几个重要的函数 x v 2 = 入j 7 2 ( z ) c 1 ( z ) + - + a ：2 ( z ) c r ( z ) ，z 蔓0 ， 2 = a 扛) c l ( 。) + + a ：忙) c r ( z ) ， $ 一1 = a i l ( x ) c l ( x ) + + a i l 0 ) c r ( 。) ，九0 ， i 。i = i a - ( 。) 1c l ( 。) + + l 扛) l c r ( z ) ， 陋1 + = 协，( z ) 】+ c l ( x ) + + i 扣) 】+ c r 扣) ，l 凡扛) 】+ = m a x 0 ，扎扣) ， 【z 1 一= = a l ( z ) 】一c 1 ( z ) + - - + a ，( z ) 一c r ( ) ，p h ( z ) 一= r a i n 0 、a 。( 茁) ) 于是，我们容易得到下述引理 引理1 4 7 v $ 了，t l l t 结论成立 1 z = p 】+ + b 1 2 1 。l = b 】+ 一p 】； 3 ( 雾j 十【。l 一) = o ； 4 妇，( o ，y ) 0 内积( i n n e rp r o d u c t ) ，范数( n o r m ) 由于迹是对称正定二次型且满足，y ，z 了，t r ( z ，y o 。) = t r ( xo 玑。) ，定义j o r d a n 代数，上的内积如下： ( 。，) t r 忸。g ) ；( a ) 1 7 2 = 厕 ；m p 瞰z ) f ， 】0 f k叫旧 知町此由 第一章绪论 均是j 上的范数为了简便，我们用l i 表示”怯 在结束本节之前，我们给出下面的引理，它将会在以后的讨论中用到 定义1 4 8 由于“。”是双线性的，所以v x 了，存在线性映射l 。：了一了使得v y j 有l ( ) = x 。y 引理l _ 4 9 若c _ 0 ，则线性映射l 。存在逆映射e 1 并且l ；1 在( 牙，功了i n t k ：是连 续的 证明：若c 卜0 ，则v x 0 ，( x ，l 。( 。) ) = t r ( c 。护) 0 ，由此可知线性映射三。是严格 单调映射，所以存在逆映射l j l ，即v x ，存在唯一的d = l i l ( o ) 使得c 。d = o 下 面证明引理的后一部分假设co y = z 且( x ，c ) 一( 牙，e ) ，i n t e 若l c o ，则 有c o ( y l l l y l l ) 一0 ，从而6 0 ( y l l y l l ) 一0 由于d 卜0 ，于是有y lj l yj i o ，这与y l l y l l 的 任何聚点非零相矛盾所以i 0 0 不成立，即恻i 有界，于是y 的任何聚点口满足 茚+ 筘= 牙，即口= e 1 ( 峦) ，所以e 1 ( z ) 在( 牙，甸了i n t k ：是连续的证毕l 第二章线性对称锥规划的非内点连续方法 根据欧氏j o r d a n 代数的相关知识，首先给出了对称锥互补问题的光 滑函数，研究了这类光滑函数具有的某些性质，特别讨论了c h k s 光滑 函数及f i s h e r - b u