资源描述：
《一类混合整数规划问题的全局最优性条件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、http://www.paper.edu.cn一类混合整数规划问题的全局最优性条件王杉林兰州大学数学与统计学院，甘肃兰州（730000）E-mail:wangshanl05@lzu.cn摘要：本文研究了带箱约束混合二次规划问题的全局最优性条件。利用全局次微分（L-次微分）方法，对一般二次函数的L-次微分进行了全面刻画，最后建立了带箱约束混合二次规划问题一个局部最优解是全局最优性的一个充分条件。关键词：非凸二次规划,L-次微分,全局优化条件中图分类号：O221.2文献标示码：A1.引言考虑下列优化问题：1TT(
2、MQP)min():fx=+xAxxa2s..txui∈∈[,,viM]xuj∈{,,vjN}∈nn,其中ASaaa∈=,(,...,n)∈RMN,,⊂{1,...,n}且M∩∪NM=∅,Nn={1,...},uv,都为整数1且uv<。(MQP)是一类特殊的二次规划问题，同时也是组合优化理论重要的研究对象。它也有很多实际的应用，例如二次分配问题，图论中的极大团问题，背包问题等等。Beck,A.andnTeboulle,M.在文献[1]中研究了当x∈−{}1,1时的全局最优性充要条件，在文[2]中作者又n研究了
3、xuv∈[,]时的一个全局最优性充分条件。本文推广了上述文献中的一些结果，给出ii了(MQP)的一个全局最优性充分条件。2.非凸优化问题的全局最优性条件本小节主要根据文[1]给出了L-次微分的概念，并利用此概念考虑了非凸优化问题的全局优化条件和Lagrange乘子条件之间的关系，建立了对于一般带二次约束二次优化问题的全局最优性条件。nnnn我们将用到下列符号：R是n维欧式空间，R表示R上的非负子空间，S表+n示n阶实对称矩阵；对于xyRxy,,∈≥表示xy≥=,1i,...,n；A;0表示Aii是半正定矩阵；
4、用diag(α,αα,...,)表示对角线上的元素为α,αα,...,，其余元12n12n素都为0的对角矩阵。nn定义2.1设f:,RR→=Ll{
5、l:}RR→,如果f()xfxl≥+−()()(),xlx00n∀∈xR，则称l是f在x处的L-次梯度，f在x处的所有L-次梯度的集合称为f在x处000的L-次微分，记作∂f()x。Lnn注意在上面定义中若L是定义在R上的线性函数的集合，那么对于定义在R上的实-1-http://www.paper.edu.cn值凸函数f，有∂=f()xf∂()x，其中∂f()x是
6、凸分析意义下的次微分。Ln定义2.2(L-正则锥).对一个给定的集合D∈R,D的L-正则锥N是LD,⎧{}lLlylx∈−:()()0,≤∀yD∈如果xD∈指:NLD,:=⎨⎩∅∉,如果xD注意到如果集合L是线性函数所成的集合,则NN=,此处N是指一般凸分析意LD,DD义下的凸集的正则锥。n考虑优化问题（P）min{():fxxSxRgx∈=∈{
7、()≤=0,i1,...,}}n。innn定理2.1设f:,RR→SRxS⊂∈,.令L=→{
8、:llRR},使得对任意lL∈有−∈lL.如果f∈L,那么x是（P）的
9、一个全局极小点的充要条件是−∂fx()∩N()x≠∅。LL,S值得注意的是,对一般函数f，集合S，以及一般的函数集合L，计算∂f()x和LNx()是很困难的。但当f是二次函数，L是由一些二次函数所成的集合时，却有下LS,列结论。设S表示nn×对称矩阵的集合，带二次约束的二次规划问题的一般形式为：n1TT()QQPminxAxax+0021TTs..txAxaxc++≤0,im=1,...,iii2n1TT其中A∈∈∈SaRcR,,,im=1,...,。为行文方便，令f():xx=+Axax，对每个inii00
10、21TTnim=1,...,，g():xx=+Axax+c。SxRgxi=∈{
11、()≤=0,1,...,}m，iiiii2nT1Tn取L=→=+∈∈{:lRRlx
12、()xAxbxASbR,,}，容易看出L是线性空间，于是当n2lL∈时−∈lL。1TTn性质2.1设hx()=+xAxaxcASa+,∈,∈Rc,∈R。n21TT则∂=hx()xAxbxA+
13、=ABbaBxBSB−=,+∈,,;0L{n}2[3]定理2.2对于问题()QQP，设xS∈，如果存在λ≥=0,im1,...,满足：immmm∑∑∑iii=
14、==111λλλiiAA++000;0,(iiAAx)+(iiaa+)=0且∑λiigx()0=，那么x是()QQP的一个全i=1局极小解。此定理的证明见文[2]。定理2.2给出了x是()QQP的一个全局极小解的充分条件。-2-http://www.paper.edu.cn3.带箱约束混合二次规划问题的全局最优性充分条件考虑下列在引言中所给的优化问题1TT(MQP)min():fx=+xAxxa2s
