标题 - PDF Free Download

2015 年 11 月 Nov.2015 重庆师范大学学报(自然科学版) 第 32 卷第 6 期 J ou r n o fchongq ngno rm Un ve r s N u r Sc enc e) y( Vo.32 No.6 DOI: 10. 11721/c 20150617 qnu j 运筹学与控制论非凸半定规划的鞍点存在性研究 * 李永玲,罗洪林,向彦宁 (重庆师范大学数学学院,重庆 401331) 摘要:主要利用矩阵分析的谱分解 Fr oben us内积及其相关性质,凸分析的凸集分离定理来研究非凸半定规划问题的鞍点的存在性,通过 3 种不同的方式给出并证明了鞍点存在的一些充分必要以及充分必要条件首先,利用一个不等式系统给出了与文献[ 1]中的对偶定理等价的一个鞍点存在的充分必要条件然后,给出了广义的 KKT 条件,并在不变凸性的假设下,证明了广义 KKT 条件是鞍点存在的一个充分条件;若 x n C,则广义 KKT 条件是鞍点存在的一个必要条件最后,定义了一个扰动函数ν,并在非凸半定规划问题的最优解存在的假设下,利用此扰动函数给出了鞍点存在的一个充分必要条件:若非凸半定规划问题的最优解存在,则对偶可达且无对偶间隙等价于扰动函数ν 的上图在点 ( 0, ν( 0)) 处存在支撑超平面关键词:非凸半定规划;鞍点;广义 KKT 条件;不变凸中图分类号: O224 文献标志码: A 文章编号: 1672 6693( 2015) 06 0009 06 文中用 Rm, Sn, Sn+ 分别表示 m 维向量空间, n 阶对称矩阵空间及n 阶半定矩阵锥考虑如下形式的非凸半定规划问题: m n f( x) s.. g( x) 0, G( x) 0, x C Rm 其中函数 f: Rm R, Rm Rk, G: Rm Sn 均不要求是凸的,且 G( x) 0 当且仅当 -G( x) Sn+ g: ( 1) 鞍点在优化问题的对偶理论以及最优性条件的讨论中扮演着重要的角色鞍点可以把原问题与对偶问题的最优解以及其最优值紧密联系起来,因此鞍点存在性的研究对于优化问题是很重要的文献[ 1]中给出了对偶定理,事实上即为鞍点存在的一个充分必要条件此文献在 S e r条件成立,以及类凸(预不变凸)性的假设下,证明了鞍点存在的一个充分条件文献中还研究了问题 ( 1)的一种特殊情况,即把 x) 0 退化为等式约束即 x)=0,此时则不满足 S e r条件,文献中也给出了对应的鞍点存在的充分必 g( g( 要条件文献[ 2]中证明了鞍点存在的一个充分必要条件,并在凸性和 S e r条件的假设下给出了鞍点存在的 [,] 一个充分条件事实上,文献[ 2]中的非线性半定规划问题是问题( 1)的特殊情况 1 3,因此本文给出的部分结论比文献[ 2]中的结论更一般,所以文献[ 2]中的部分结论是本文结论的特殊情况在一般的非线性规划问题中,无论是在最优性条件还是鞍点存在性的研究, K rus r条件(简称 -Kuhn -Tucke [] KKT 条件)都起着重要的作用 4 在非线性半定规划一个局部最优解处满足 Rob ns on 约束品性的前提下,文献[ 5]中证明了以下条件是等价的:强二阶充分条件和约束非退; KKT 系统的 C rke sj c ob n 非奇异;KKT 点满足强正则性文献[ 6]中也给出了在不同的假设条件下 KKT 点是广义方程的强正则解此外,从计算的角度来看,由于 KKT 系统的求解易在计算机上实现,因此本文给出了所谓的广义 K rus r条件( 6)式, -Kuhn -Tucke 简称广义 KKT 条件本文讨论了鞍点存在性与广义 KKT 条件的关系,证明了在不变凸性的假设下,广义 KKT 条件是鞍点存在的充分条件还给出了与文献[ 1]中的对偶定理等价的一个定理即鞍点存在的另一个充分必要 * 收稿日期: 2014 11 24 修回日期: 2015 04 07 资助项目:国家自然科学基金( No. 11431004) 网络出版时间: 2015 9 28 12: 02 作者简介:李永玲,女,研究方向为最优化理论与算法,半定规划,E-m : 1152280286@qq. c om;通信作者:罗洪林,副教授,E-m : 1071025013@f udn. edu. cn //www. /kcms /de /50. 网络出版地址: h cnk. ne 1165. n. 20150928. 1202. 022. h m p:

10 重庆师范大学学报 ( 自然科学版 ) hp://www.cqnuj.cn 第 32 卷条件, 这一充分必要条件由方程组的形式给出易在计算机上求解引入扰动函数, 并利用扰动函数来刻画鞍点存在的一个充分必要条件本文在第 1 节中给出了一些记号与定义, 在第 2 节中讨论了非凸半定规划问题 (1) 的鞍点存在的一些充分必要以及充分必要条件第 3 节为总结部分 1 预备知识与记号 n n 这一节将介绍一些定义性质与符号在对称矩阵空间 S n 中可定义内积为 A B= AjBj =r(ab), =1 j=1 A C1q æa C11 A,B S n A C21 A C2q, 其中 r 表示矩阵的迹基于此可以定义 A C=........., 其中 A S n,c= A C p1 A C pq C p1 C1q æc11 C21 C2q.........,Cj S n,a Cj 为对称矩阵空间 S n 中定义的内积 C pq 用 Z 表示 R (S j 或 R S j ) 时, 其中,j 可以为任意的正整数, 当且仅当 Z 表示 R (S j 或 R S j ) 时, 用 Z+ 表示 R + (S j + 或 R + S j + ) 在此基础上可定义如下的偏序关系 : A B A-B Z+,A>B A-B nz+, A,B Z 若 A 0,B 0, 则有 A B 0 事实上, 因为 A 0,B 0 则存在 n 阶矩阵 P,H 使得 A=PP T,B=H T H, 因此有 A B=r(PP T H T H)=r(P T H T HP)=r((HP) T HP) 0 称 G:R m S n 是可微的, 若 G(x) 作为 x R m 的多元函数是可微的, 令 æ G(x) x1 æg1(x) G(x) dg(x) dx = G2(x) x2 =...,... Gm(x ) G(x) x m 其中 G(x)= G (x) 为 n n(=1,,m) 偏导数矩阵, 则称 dg(x) 为 G(x) 对 x 的导数用 DG(x) 表示 G( ) 在 x dx m x 的微分映射, 即 DG(x) 为从 R m 到 S n 的线性映射, 定义为 DG(x)y= yg(x), 且记 dg(x) =1 dx : =DG(x) 定义 1 [1] 设集合 C R m, 如果存在一个向量值函数 η : R m R m R m 使得 x,y C,λ [0,1], 有 y+λη ( x,y) C, 则称 C 是关于函数 η 的不变凸集定义 2 [1] 设集合 C R m 是函数 η : R m R m R m 的不变凸集,T:C Z, 若对 x,y C,λ [0,1], 有则称 T 是关于函数 η 的预不变凸函数 T(y+λη ( x,y)) λt(x)+(1-λ)t(y), (2) 类似于 R m R 上的不变凸函数的定义 [7], 可定义 R m S n 上的不变凸函数, 即有如下定义定义 3 设集合 C R m,g:c S n 可微, 如果存在一个向量值函数 η : R m R m R m 使得则称 G 是关于函数 η 的不变凸函数 G(x)-G(y) DG(y) η (x,y), x,y C, [8] 事实上, 若 T:C Z Fréche 可微且是关于向量值函数 η 的预不变凸函数, 则 T 为不变凸函数这是因为

第 6 期李永玲, 等 : 非凸半定规划的鞍点存在性研究 11 T Fréche 可微且对 x,y C,λ [0,1],T 满足 (2) 式, 则 (2) 式可改写为 λ(t(x)-t(y)) T(y+λη ( x,y))- T(y), 两边同时除以 λ, 令 λ 0+ 有 T(x)-T(y) DT(y) η (x,y), 因此 T 为不变凸函数, 反之不然 2 鞍点存在性的研究本节讨论非凸半定规划问题 (1) 的鞍点存在的充分必要条件充分条件及必要条件用 Ω 表示问题 (1) 的可行集, 即 Ω:= { x C g(x) 0,G(x) 0 } 定义问题 (1) 的 Lgrnge 函数如下 :L(x, μ,u)=f(x)+μ T g(x)+u G(x), 且称 θ( μ,u)=mn L(x, x C μ,u) 为 L(x, μ,u)( 其中 ( μ,u) 0) 的对偶目标函数, 则问题 (1) 的对偶问题可以写成 mx θ( ( μ,u) 0 μ,u) (3) (x, μ,u) 称为 Lgrnge 函数 L(x, μ,u) 的一个鞍点, 如果 x C,( μ,u) 0, 且满足 L(x, μ,u) L(x, μ,u) L(x, μ,u), x C, ( μ,u) 0 (4) (4) 式的解与问题 (1) 和对偶问题 (3) 的关系由以下定理给出在文献 [1] 的定理 3.3 证明了若 Ω 非空, 则 (x, μ,u) 为 L(x, μ,u) 的鞍点且 x Ω 当且仅当 x,( μ,u) 分别为原始问题 (1) 与对偶问题 (3) 的最优解, 且无对偶间隙即 f(x)=θ( μ,u) 本文将给出鞍点存在性的另一个充分必要条件如下定理 1 (x, μ,u) 为 Lgrnge 函数 L(x, μ,u)=f(x)+μ T g(x)+u G(x),x C,( μ,u) 0 的鞍点的充分 ì :L(x, μ,u)=mn{l(x, μ,u):x C}, 必要条件是 íb:g(x) 0,G(x) 0, îc: μ T g(x)=0,u G(x)=0 证明假设 (x, μ,u) 为 L(x, μ,u) 的鞍点, 由鞍点的定义可知成立 ; 由 (4) 式知 f(x)+μ T g(x)+u G(x) f(x)+μ T g(x)+u G(x), ( μ,u) 0, (5) 从而 g(x) 0,G(x) 0, 否则假设 g(x) 0,G(x) 0 不成立, 则 g(x) 0 不成立或者 G(x) 0 不成立对于第 1 种情况, 设 g(x)=(g1(x),g2(x),,gk(x)) T, 则存在 {1,,k} 使得 g(x)>0, 让 μ 充分大, μj =0(j ),U=U, 则 (5) 式中左边充分大, 与 (5) 式矛盾, 从而 g(x) 0 对于第 2 种情况, 设 G(x) 的特征值为 λ2, 由 G(x) 0 不成立有 >0, 则存在正交矩阵 P 使得 æ G(x)=P æ P T, 取 μ=μ, 0 U=P æ 0 U G(x)=r(P æ P T P 0 让充分大, 则 (5) 式中左边充分大, 与 (5) 式矛盾, 从而 G(x) 0,b 成立 P T 0(>0), 则 0 P T )=, (5) 式中令 μ=0,u =U, 有 μ T g(x) 0, 又由 μ T g(x) 0, 得到 μ T g(x)=0 (5) 式中令 μ=μ, U =0, 有 U G(x) 0, 又由 U G(x) 0, 得到 U G(x)=0,c 成立假设,b,c 成立, 由可得 L(x, μ,u) L(x, μ,u), x C 由 b,c 可得 L(x, μ,u)=f(x)+μ T g(x)+u G(x) f(x)+μ T g(x)+u G(x)=L(x, μ,u)( ( μ,u) 0), 所以 (x, μ,u) 为 L(x, μ,u) 的鞍点注 1 事实上 x,( μ,u) 分别为原始问题 (1) 与对偶问题 (3) 的最优解, 且无对偶间隙即 f(x)=θ( μ,u) 与定理 1 中的,b,c 等价, 由定理 1 中的 b 可以看出 (x, μ,u) 为鞍点蕴含着 x 可行, 因此文献 [1] 中的定理 3.3 可以改写为若 Ω 非空, 则 (x, μ,u) 为 L(x, μ,u) 的鞍点当且仅当 x,( μ,u) 分别为原始问题 (1) 与对偶问题 (3) 的最优证毕

12 重庆师范大学学报 ( 自然科学版 ) hp://www.cqnuj.cn 第 32 卷解, 且无对偶间隙即 f(x)=θ( μ,u), 所以定理 1 与文献 [1] 中的定理 3.3 等价相对于文献 [1] 中的定理 3.3, 本文的定理 1 中的,b,c 所构成的系统的解容易在计算机上实现为了讨论鞍点存在性的必要充分条件, 本文仿照一般的非线性规划问题中由 Lgrnge 函数产生的 KrusẖKuhṉTucker 条件, 本文也给出了所谓的广义 KrusẖKuhṉTucker 条件, 简称广义 KKT 条件 : 其中 x Ω,( μ,u) 0 ì Ñf(x)+μ T Ñg(x)+U DG(x)=0, íμ T g(x)=0, îu G(x)=0 如下定理讨论了鞍点存在性与广义 KKT 条件的关系定理 2 考虑问题 (1)x Ω, 假设存在 ( μ,u) 0 满足 (6) 式, 设 g(x)= (g1(x),g2(x),,gk(x)) T,I= { :g(x)=0,=1,, k }, 假设 f,g( I),G 是关于相同的 η : R m R m R m 的不变凸函数, 则 (x, μ,u) 为 L(x, μ,u) 的鞍点 ; 反之, 假设 (x, μ,u) 为 L(x, μ,u) 的鞍点,x nc,( μ,u) 0, 则 x 为问题 (1) 的可行点, 且 (x, μ,u) 满足 (6) 式证明假设 (x, μ,u),x Ω,( μ,u) 0, 使得 (6) 式成立, x C, 由不变凸性有 (8) 式乘 μ,(9) 式与 U 作内积, 与 (7) 式相加可得 (6) f(x)-f(x) Ñf(x) T η ( x,x), (7) g(x)-g(x) Ñg(x) T η ( x,x), I, (8) G(x)-G(x) DG(x) η (x,x), (9) f(x)+ I μg(x)+u G(x)- (f(x)+ I μg(x)+u G(x)) 由 (6) 式中 μ T g(x)=0, 可得 μ=0 ( I),(10) 式可转化为 (Ñf(x)+ I μ Ñg(x)+U DG(x)) T η ( x,x), (10) f(x)+μ T g(x)+u G(x)-(f(x)+μ T g(x)+u G(x)) (Ñf(x)+μ T Ñg(x)+U DG(x)) T η ( x,x)=0, 即对 x C 都有 L(x, μ,u) L(x, μ,u), 由 g(x) 0,G(x) 0, μ T g(x)=u G(x)=0, 可得 f(x)+μ T g(x)+u G(x) f(x)=f(x)+μ T g(x)+u G(x)( ( μ,u) 0), 即对 ( μ,u) 0 都有 L(x, μ,u) L(x, μ,u), 故 (x, μ,u) 为 L(x, μ,u) 的鞍点假设 (x, μ,u) 为 L(x, μ,u) 的鞍点, 则由定理 1 可得 g(x) 0,G(x) 0, μ T g(x)=u G(x)=0,L(x, μ,u) L(x, μ,u), ( μ,u) 0, 又由 x nc, 由费马定理可得 Ñ xl(x, μ,u)=0 即 Ñf(x)+μ T Ñg(x)+U DG(x)=0 故 (x, μ,u) 满足 (6) 式注 2 定理 2 说明了在不变凸性的假设下, 广义 KKT 条件是鞍点存在的一个充分条件注 3 在定理 2 中把条件 f,g( I),G 是关于相同的 η : R m R m R m 的不变凸函数改为 C 是关于 η : R m R m R m 的不变凸集,f,g( I),G 是 Fréche 可微的且是关于向量值函数 η 的预不变凸函数则定理仍成立考虑问题 (1), 定义扰动函数 ν:r k S n R, 定理 3 证明 ν(y)=mn{f(x):g(x) y1(y1=(y (1) 1,,y (k) 1 ) T ),G(x) y2,y2 S n,y=(y1,y2),x C} (11) 假设问题 (1) 的最优解 x 存在, 则 (x, μ,u) 为 L(x, μ,u) 的鞍点的充分必要条件是证毕 ν(y) ν(0)-μ T y1-u y2, y R k S n (12) 假设 (x, μ,u) 为 L(x, μ,u) 的鞍点, 由文献 [1] 中的定理 3.3 知 f(x)=θ( μ,u) 因为 ν(0)=nfp= f(x), 则对 y R k S n 有 ν(0)=θ( μ,u)=mn{f(x)+μ T g(x)+u G(x):x C}= μ T y1+u y2+mn{f(x)+μ T (g(x)-y1)+u (G(x)-y2):x C}

第 6 期李永玲, 等 : 非凸半定规划的鞍点存在性研究 13 对扰动问题 (11) 应用弱对偶定理有 ν(0) μ T y1+u y2+ν(y)( y R k S n ), 故 (12) 式成立反之, 若 (12) 式成立,x 为问题 (1) 的最优解, 有 x C,g(x) 0,G(x) 0, 下证 ( μ,u) 0 假设 ( μ,u) 0 不成立, 则 μ 0 不成立或者 U 0 不成立对于第 1 种情况即 μ 0 不成立, 则存在 μ<0 ( {1,,k}),(12) 式中令 y () 1 >0,y ( j) 1 =0,j,y2=0, 则有 ν(0) ν(y) ν(0)-μy () 1 μy () 1 0, 与 μy () 1 < 0 矛盾, 因此有 μ 0 对于第 2 种情况, 设 U 的特征值为 λ2, 由 U 0 不成立, 必有 <0, 则存在正 æ 交矩阵 P 使得 U=P y2 U y2 0, 与矛盾, 因此有 U 0, 故 ( μ,u) 0 æ0 P T,(12) 式中令 y1=0,y2=p æ æ U y2=rp æ0 P T P P T 0, 则 ν(0) ν(y) ν(0)-u 0 1 P T =<0, 0 1 (12) 式中令 y=y=(g(x),g(x)) 0, 则 ν(y) ν(0)=f(x) 因为 x 为 y=y 时扰动问题 (11) 的可行点, 所以 ν(0)=f(x) ν(y), 从而可得 ν(0)=ν(y) 由 (12) 式有 μ T g(x)+u G(x) 0 又由 ( μ,u) 0, (g(x),g(x)) 0 有 μ T g(x)+u G(x) 0, 可得 μ T g(x)+u G(x)=0, 从而有 μ T g(x)=u G(x)=0 最后由 (12) 式有 L(x, μ,u)=f(x)+μ T g(x)+u G(x)=f(x)=ν(0) ν(y)+μ T y1+u y2, y R k S n 对 ^x C, 令 ^y= (g(^x),g(^x)), 则 ^x 为 y=^y 时扰动问题 (11) 的可行点, 可得 f(^x) ν(^y) 由 (12) 式有 f(x)=ν(0) ν(^y)+μ T g(^x)+u G(^x) f(^x)+μ T g(^x)+u G(^x)=L(^x, μ,u), ^x C 由前面的证明知 μ T g(x)=u G(x)=0, 则 L(x, μ,u)=f(x)+μ T g(x)+u G(x)=f(x) L(^x, μ,u), ^x C 即 L(x, μ,u) L(x, μ,u), x C 由 (g(x),g(x)) 0, 可得 L(x, μ,u)=f(x)+μ T g(x)+u G(x) f(x)=f(x)+μ T g(x)+u G(x)=L(x, μ,u), ( μ,u) 0 故 (x, μ,u) 为 L(x, μ,u) 的鞍点注 4 定理 3 说明了若 x 为问题 (1) 的最优解,(x, μ,u) 为 L(x, μ,u) 的鞍点的充分必要条件是超平面 H= {(y,z):<( μ,u,1),(y,z)>=ν(0),(y,z) R k S n R} 是扰动函数 ν 的上图 epν={(y,z):z ν(y),y R k S n } 在点 (y,z)=(0,ν(0)) 处的支撑超平面, 其中 y=(y1,y2),<( μ,u,1),(y,z)>=μ T y1+u y2+z 换言之, 若问题 (1) 的最优解存在, 则对偶可达且无对偶间隙等价于扰动函数 ν 的上图在点 (0,ν(0)) 处的支撑超平面存在 3 结论文中对非凸半定规划问题 (1) 的鞍点存在性进行了讨论定理 1 给出了一个鞍点存在的充分必要条件, 且与文献 [1] 中的定理 3.3 是等价的定理 2 在不变凸性的假设下证明了广义 KKT 条件是鞍点存在和全局最优性的充分条件定理 3 则是引入扰动函数来刻画鞍点存在的一个充分必要条件证毕参考文献 : [1]Sun W,LC,Smpo RJB.Onduyheoryfornoṉ convexsemdefneprogrmmng[j].annsofoperons Reserch,2011,186(1):331-343. [2]FnJ.Duyheoresnnonnersemdefneprogrmmng[J].Apped mhemcseers,2005,18(9):1068-1073. [3] 李成进, 孙文瑜. 非凸半定规划的广义 Fkrs 引理及最优性条件 [J]. 高等学校计算数学学报,2008,30(2):184-192.

14 JournofChongqngNormUnversy(NurScence) hp://www.cqnuj.cn Vo.32No.6 LCJ,Sun W Y.GenerzedFkrsemmndopm condonsfornonconvexsemdefneprogrmmngproḇ ems[j].numercmhemcsjournofchneseunverses,2008,30(2):184-192. [4]BzrM S,SherH D,SheyC M.Nonnerprogrmmng:heoryndgorhms[M].NewYork:JohnWey& Sons,2013. [5]Sun D.Thesrongseconḏordersufcencondonnd consrn nondegenercy n nonner semdefne progrmmngndhermpcons[j].mhemcsofopeṟ onsreserch,2006,31(4):761-776. OperonsReserchndCybernecs TheSudyofheExsenceofSddePonforNonconvex SemdefneProgrmmngProbems [6] 张立卫. 非线性半定规划若干进展 [J]. 运筹学学报,2014, 18(1):93-112. ZhngL W.Nonnersemdefneprogrmmngsomedeveopmen[J].Journof OperonReserch,2014,18 (1):93-112. [7]WerT,JeykumrV.Acssofnonconvexfunconsnd mhemcprogrmmng[j].buenofhe Ausrn MhemcSocey,1988,38(2):177-189. [8] 张立卫. 锥约束优化 [M]. 北京 : 科学出版社,2010. ZhngL W.Coneconsrnsopmzon[M].Bejng:ScencePress,2010. LIYongng,LUO Hongn,XIANG Ynnng (CoegeofMhemcsScences,ChongqngNormUnversy,Chongqng401331,Chn) Absrc:Inhspper,wedevoeosudyheexsenceofhesddeponofnonconvexsemdefneprogrmmngprobemsby mensofspecrdecomposon,innerproducndcorreveproperesofmrxanyssndsepronheoremofconvexse ofconvexanyss.inhscse,somenecessrynd/orsufcencondonsforexsenceforhesddeponredervedndproved nhreedferenwys.frs,wepresensufcenndnecessrycondonwhchsequvenoduheoremnref.[1]byuzngnnequysysem.then,wegvegenerzedkrusẖkuhṉtuckercondonndprovehscondonssufcencondonsforexsenceofhesddeponundernvexconvexyssumpon.inddon,fx nc,hssufcencondonsso necessrycondon.fny,wedefneperurbonfunconwhchsusedodeducesufcenndnecessrycondonforexsṯ enceofhesddepon:dunmenndhebsenceofduygpsequvenoheexsenceofsuppornghyperpnefor heepgrphofνhepon(0,ν(0)). Keywords:nonconvexsemdefneprogrmmng;sddepon;generzedKKTcondon;nvex ( 责任编辑黄颖 )