D．C．集（凸集的差）约束的非凸二次规
划的最优解集学生知识现状分析
第24卷第5期工程数学V o1.24No.5
2007年10月CHINESEJOURNALOFENGINEERINGMA THEMA TICSOct.2007 文章编~:1005—3085(2007)05—0801—12
D.C.集(凸集的差)约束的非凸二次规划的最优解集木 林惠玲，张圣贵
(福建师范大学数学与计算机科学学院，福州350007)
摘要：本文研究D.C.集f凸集的差1上极小化非凸二次规划问题的最优解.我们首先证明了该问题 的Lagrange对偶的稳定性，即不存在对偶间隙：接着利用该性质得到问题的全局最优性条件和 最优解集，它可以像凸规划那样，借助它的对偶问题的解集精确地描述出来.最后，通过一个例
子来说明这些结论.
关键词:D.C.规划：非凸二次规划:Lagrange对偶性；全局最优性条件
分类号:AMS(2000)49M29;90C46中图分类号:O221.2文献标识码:A
1引言与记号
本文中，我们考虑如下的非凸二次规划问题
=min{,()=丢Ax+6:r≤llIIr;)(P)
其中A∈Rn×n,A=A,b∈Rn,r1,r2∈R++,r1<r2.
问题(P)是一个D.C.规划问题.对于D.C.规划，文【1]中给出求解典范D.C.规划(定义见
文【1])的多种算法；文【2]中给出在欧氏空间R"上极小化两个闭凸函数之差的规划的全局最优
性条件与D.C.算法.若记E={:1r}1lIxllj122),E1={:~jjxll112),E2=
{:1lIxll122)，并引入指示函数
有机纤维,,f0,x∈E,
x蛆
则5E(X)=5E()+5E.()，于是可以把(P)转化为在欧氏空间R"上极小化两个凸函数之差
的规划.但注意到问题(P)的特殊结构，本文采用Langrange对偶理论来刻画问题(P)的最优
性条件.
同时，问题(P)又是…个在多个二次约束上极小化不定二次函数的问题，记为(F) XTQ0一2
XTQ{一26+C{0(P)
其中QT=Q∈R",b∈R",i=0,1,…,m.关于问题(F)，文【3]主要利用矩阵束的技巧
得到解的存在性定理及最优性条件；文【4]运用半定规划松弛的方法得到这类问题的多项式时
澳洲网上唐人街
收稿日期:2005-12-16.作者简介：林惠玲(t98t年9月生)，女，硕士.研究方向：最优化理论与算法.
基金项目：福建省自然科学~(S06500082006J0202)；福建省教育厅资助项目(JA050210)；福建省教育厅资助
项目fJB06095).
802工程数学第24卷
美国国务卿职责间可解条件，同时给出单一等式约束的非线性规划的多项式时间算法.但它们都没有给出问
题(P)的最优解集的具体描述.
本文研究D.C.集上的极小化非凸二次规划问题.在接下来的一节中，我们利用La- grange对偶理论，得到问题(P)的Lagrange对偶的稳定性，即不存在对偶间隙，而且问
题(P)的解集可以像凸规划那样，借助它的对偶问题的解集精确地描述出来.这些结论对探索
问题(P)的求解方法起到关键性作用.
在本文中，运用如下记号:
R++：全体正实数;t厂:t厂的梯度;intS,riS,OS：分别是集合S的内部，相对内部
和边界:
A+:A的Moore-penrose广义逆;AT:A的转置;l1.11：欧氏范数:
L上：子空间L的正交补;ker(A):A的零空间;domg：函数口的有效域.
2全局最优性条件
定义(P)的Lagrange函数
L(,￡):{1TA+6T+(r}～IIx11)+(1111一r22),tl,t0,I一
∞,t=(tl,t2)0.
首先考虑线性方程组
(A—tlI+t2I)x=一b(1)
的解.
设A的特征值为A1A2…≤A，对应的n个标准正交特征向量为u1,u2,…,u.
若A1～t1+t2>0，则(1)的唯一解是x(t)=一(A—tlI+t2)一b.由于A=AT，故存在, 使得A=Udiag(A1,A2,…,)T，其中U=[Ul,U2,…,】，于是
川=
i=11,.—.
若A1一t1+t2=0,b∈[ker(A—AII)]上，则当b=0时,x(t)=一(A—tlI+t2)+b=0;
当b≠0时，记J={1in:Ai=A1)，则{1,…，礼)\J≠O,+(￡)是(1)的解，满足
+(t)ll=∑
tJ
注下文中，如果没有特别说明，则有卓越网
(bTu)
(九一￡1+￡2)
x(t)=x(tl,t2)=-(A—tlI+t2I)一6,+(￡)=+(tl,t2)=-(A一￡1+t2I)+b.
对任意的t0,t∈R，定义
)=inf{T(A啦++t2lr2一和:∈R"),
则-9(￡)是t0上的凹函数.
定义(P)的对偶问题为
=sup{g(t):t0}.
(Pt)
(D)
第5期!玲，张圣贵:D.C.集(凸集的差)约束的非凸二次规划的最优解集803
命题1(domg:R.:￡0,1一tl+20,b∈[ker(一tiI+t~SK};
(g(t)bT+夸r}一等r;=一6T(A-t1+2)+6+每r}一圭22"22,V∈,￡∈dom9
证明()doing:{0：夕()>；一∞)，若1一t1+2<0，则对于v∈ker(～】,),
有AX=1，贝U
lI
1
.
i
.
ra
(一
1
一
T(A-t~I+t2I)x+bTx+≥r}一.t2r;)
=
lI()11~112+bTx+一t2r22)------00
_f(一.O.若t0,1一tl+t20，则(P)是一个凸规划，由可微无约束问题的最优性条件[5]知
,
∈Pt营(1)有解，即b∈[ker(A—1+2删上.
(i)由()证得，当∈Pt,t0时,(一1+2)=一b.故
9(t)=三bTx+tlr}一t2_r22=～T(一￡1+￡2)+6+tl}一t2_22.
令
(t)=～9(t)=16T(—
t+t.)+6一≥r}+t2r;,
则是凸的，且dom=domg.
命题2(i)若t0,A1～t1+t2>0，则t∈dom，目
=
三一t2
此时，在t>0,A1～t1+t2>0上可微，且
(扰)
当b=0
()若b[ker(A一
许佑嘉时,(t)re(e)式确定.
c,=
(1.:._+)
贝Udom
当b≠0
∈R.:t0
,1一t1+t20)，此时,
=
三～
A1驯上，则d.崎={t∈R.:t0,1一t1+t2>0)，此
证明由题1容易得到()和().下面证明().
关于doI的特征由命题1即得.
若6∈[ker(A—1驯上，则vj∈bT=0：于是，若b:0，由命题1的()知, (t)=～16T一
≥r}+t2r;=一tl2+t2r;.
若b≠0，当A1一tl+t2=0时,：一(—t1+t2)+6，则
=
三～
=时
上，幢譬
+
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议