计算多项式函数的全局下确界和全局最小值的有效算法

英文引用格式:XiaoSJ,ZengGX.Algorithmsforcomputingtheglobalinmumandminimumofapolynomialfunction(inChinese).SciSinMath,2011,41(9):759{788,doi:10.1360/012010-977中国科学:数学2011年第41卷第9期:759788计算多项式函数的全局下确界和全局最小值的有效算法肖水晶,曾广兴∗南昌大学数学系,南昌330031E-mail:[e-mail],[e-mail]收稿日期:2010-12-07;接受日期:2011-08-01;*通信作者国家自然科学基金(批准号:10761006,11161034)资助项目摘要通过捕获所谓的严格临界点,本文提出了一个计算实多项式函数的全局下确界和全局最小值的有效方法.对于实数域R上一个n元多项式f,该方法可用来判定f在Rn上是否具有有限的全局下确界.在f具有有限的全局下确界的情况下,f的下确界可严格地表示为码(h;a,b),其中h是一个实单元多项式,a和b是使得ab的两个有理数,而(h;a,b)代表h(z)在开区间]a,b[中仅有的实根.此外,当f具有有限下确界时,本文的方法可进一步判定f的下确界能否达到.在我们的算法设计中,著名的吴方法起着重要作用.关键词多项式优化全局下确界全局最小值严格临界点转换原理吴方法有理单元表示MSC(2000)主题分类68W30,12F101引言多项式的全局极小化问题可描述如下:对于一个非零的实多元多项式f∈R[x1,...,xn],计算f的全局下确界inff(Rn),且在inff(Rn)̸=−∞时,判定f的全局下确界能否达到,即判定f是否具有全局最小值.这样一个问题已在许多文献中被研究,例如文献[1–6].在文献[1]中,考察了目标多项式函数的一阶偏导数,并且采用了Gr¨obner基运算.当所有一阶偏导数具有无限多个公共零点时,目标多项式函数的临界点不能简单和清晰地给出.文献[2]对目标多项式函数附加了一些有关条件,以致在应用上不具有普遍性.文献[3]的作者通过半正定规划方法研究了一类多项式的全局极小化问题.然而,半正定规划方法对于其他多项式,比如Motzkin多项式x41x22+x21x42+x63−3x21x22x23,不能产生所期望的结果.在文献[4]中,对于给定的多项式f∈R[x1,...,xn],引进了一个辅助多项式fλ:=f(x1,...,xn)+λ(x2m1+···+x2mn),其中λ是一个任意正数,2m是一个大于f的全次数的固定偶数.与原多项式f相比较,fλ在问题处理上具有如下两个优势:其一,fλ总具有全局最小值;其二,fλ的所有一阶偏导数∂fλ/∂xi(i=1,...,n)组成一个零维系统,且它们对于任意全次数的项序构成一个简化Gr¨obner基.作为文献[4]中一个重要结果,当λ趋向0时,inff(Rn)正是f(xλ)的极限,这里xλ为fλ的任意一个最小值点.根据这一结果,文献[4]得到了一个基于解矩阵特征问题的算法.通过该算法,在确有的情况下能获得f的最小值,且在f没有全局最小值的情况下可计算出inff(Rn).然而,一个判定多项式是否有最小值的直接方法在文献[4]中未给出.此外,当算法所产生的矩阵特征肖水晶等:计算多项式函数的全局下确界和全局最小值的算法值不能写成清晰可比的数据时,难以通过相互比较鉴别出欲求的下确界.在文献[5]中,通过梯度理想上平方和松弛(sumofsquares(SOS)relaxation),提出了一个求多项式的全局最小值的算法.然而,文献[5]中主要算法(Algorithm1)立足于这一前提:输入的多项式被假定能达到下确界,且该算法计算出的最小值往往是近似的.在文献[6]中,通过把原先的优化问题化为半正定规划问题,作者在f有下界的情况下考虑了计算f的全局下确界的问题.由于文献[6]中算法是数值的,所计算出的下确界(或最小值)也大多是近似的.在本文中,我们将提出一个有效地计算实多项式函数的全局下确界和全局最小值的新方法.对于实数域R上一个n元多项式f,本文中的方法可用来判定f在Rn上是否具有有限的(全局)下确界.在f具有有限下确界的情况下,f在Rn上的下确界可严格地表示为码(h;a,b),其中h是一个在端点为有理数的开区间]a,b[中恰有一个根的实单元多项式,而(h;a,b)正代表h(z)在]a,b[中仅有的实根.此外,当f在Rn上具有有限下确界时,可进一步判定f在Rn上的下确界能否达到,即判定f是否具有全局最小值.在我们的算法设计中,著名的吴方法起着重要作用.吴方法是立足于所谓的零点分解定理(见文献[7]中定理5.1).设g是F[Y]中一个非常量多项式,其中F是一个域,且Y:={y1,...,ym}是一个变量集.变量yj(16j6m)被称作g关于通常字典序y1≺···≺ym的首变量,若g∈F[y1,...,yj],但g/∈F[y1,...,yj−1].在下文中,g的首变量将记作lv(g),且g作为F[y1,...,yj−1]上含单变量yj的多项式的首项系数被称作g的初式.由F[Y]中非常量多项式g1,...,gs组成的一个序列C被称作一个(关于通常字典序的)升链,若lv(g1)≺···≺lv(gs).此时,由g1,...,gs的初式所组成的集合称作C的初式集.再设P和Q是F[Y]的两个有限子集,且K是F的任意一个扩张.此时,我们可得到Kn的如下子集:ZeroK(P/Q)={¯α∈¯Kn|对于全部p∈P,p(¯α)=0,但对于全部q∈Q,q(¯α)̸=0}.特别地,当Q={1}时,我们将使用ZeroK(P)来取代ZeroK(P/{1}).为方便起见,现将零点分解定理引述如下:零点分解定理设F是一个可计算域,且P是K[Y]的一个有限子集,则存在一个有效算法,可构造出一组升链C1,...,Cr,使得对于F的任意扩张K,下面等式成立:ZeroK(P)=∪16j6rZeroK(Cj/Ij),其中Ij是Cj的初式集,j=1,...,r.上面定理中所说的有效算法即为熟知的吴方法.应指出,吴方法已编制成一个名为wsolve的计算机通用软件,可用于有理系数多项式来生成升链.由[7]中定义3.12知,一个字典序可诱导出由F[Y]中多项式所组成的全部升列之间的一个偏序≻,使得对于两个升列C1={f1,...,fr}和C2={g1,...,gs},C1≻C2,如果满足下面两个条件之一:(1)存在一个自然数t,使得t6min{r,s},fj和gj同序,16jt,但gt的序低于ft.(2)rs,且fj和gj同序,16jr.正如[7]中定理3.3所指出,偏序≻是良型的(well-founded),即根本不存在由升列构成的如下无限序列:C1≻C2≻···≻Cj≻···.760中国科学:数学第41卷第9期在全文中,除实数域R和有理域Q外,所涉及的域F也都被假定是特征为零的域.对于域F上多项式环F[Y],除非特别指明,有关变量的字典序总默认为通常字典序y1≺···≺ym.本文的剩余部分安排如下.第2节包含一些预备工作.在这一节中,我们将实数域R扩充为一个包含无限大正元素η的实闭域R,并获得了一些涉及域R(η)上单元多项式的有用算法.在第3节中,我们针对半代数子集引进了“严格临界点”这一概念,并提出了一个捕获某类半代数子集的严格临界点的算法.在第4节中,对于实数域R上一个n元多项式f,我们研究了f在仿射空间Rn中闭立方体[−η,η]n上的最小值,由此在理论上建立了一些反映该最小值与f的全局下确界之间紧密关系的结论,其中包括一个有关多元多项式f具有全局最小值的充分必要条件.在此基础上,我们提出了一个算法,该算法既可计算f的全局下确界,又可判定f的全局下确界能否达到,这里f是实数域R上任意一个多元多项式.最后一节给出了几个实例,用来表明我们的算法的有效性.2预备工作在建立主要算法前,我们需要一些预备工作.在此,先需要将实数域R扩充为一个包含无限大元素η的序域.设η是实数域R上一个未定元,R[η]为实数域R上含未定元η的单元多项式环,且R(η)为实数域R上含未定元η的有理函数域,则R(η)={g(η)h(η)|g,h∈R[η],且h(η)̸=0}.由序域理论(参见文献[8]或[9]),实数域R的序6可惟一地拓展为R(η)的一个序,仍记作6,使得对于非零元gh∈R(η),其中g,h∈R[η]\{0},gh0,当且仅当R[η]中单元多项式gh的首项系数为负.显然,对于非零多项式g∈R[η],g0当且仅当g的首项系数为负.从而−η0且a−η0,其中a为任意实数.由此有0η且aη,其中a为任意实数.换言之,η是实数域R上无限大的正元素.记R为序域(R(η),6)的实闭包,且R的惟一序仍记作6.自然有R⊂R.R中一个元素α称作是实数域R上有界元素,若对于某个正数d,−dαd.R中一个元素ϵ称作是实数域R上无限小元素,若对于任意正数δ,−δϵδ.现在,我们构造R的如下两个子集:A:={z∈R|对于某个正数d∈R,−d6z6d},M:={z∈R|对于每个正数d∈R,−δ6z6δ}.因而,A由R中所有在R上有界的元素组成,而M由R中所有在R上无限小的元素组成.容易验证,A是R的一个子环,M是A的一个理想,且A和M在R中关于序6都是凸的.根据序6的结构,显然R⊂A⊂R,且η−1∈M.在下文中,R\A中的元素都称作在R上的无界元素.对于α∈R,构造R的如下子集:Ωα:={r∈R|α6r}.当Ωα̸=∅时,其中α∈R,记π(α)为Ωα的下确界inf(Ωα).此时,π(α)∈R∪{−∞},且π(α)∈R当且仅当α∈A.当Ωα=∅时,我们规定π(α):=∞.这样,我们得到一个R到R∪{∞,−∞}的映射π,使得对于每个α∈R,π(α)恰是α的象.容易验证,映射π满足下面命题中全部条件,该命题的证明留给读者.命题2.1设记号同上,则下面条件都成立:761肖水晶等:计算多项式函数的全局下确界和全局最小值的算法(1)限制映射π|A是环A到环R的一个R-同态,使得M恰为π|A的核.(2)对于ξ∈R\A,π(ξ)=∞若ξ0;否则,π(ξ)=−∞.(3)对于α,β∈R,由α6β可推出π(α)6π(β),这里约定:对于任意实数r,−∞r∞.定义1对于α∈R,π(α)称作α的标准化.由命题2.1中条件(1)知,π(g(η−1))=g(0),其中g∈R[z].特别地,π(η−1)=0.此外,对于任意α∈A,α−π(α)∈M.在下文中,我们将采用如下常用符号:对于a,b∈R,其中ab,]a,b[(或[a,b])表示R中左右端点分别为a和b的开(或闭)区间{r∈R|arb}(或{r∈R|a6r6b}),但]α,β[R(或[α,β]R)表示R中左右端点分别为α和β的开(或闭)区间{γ∈R|αγβ}(或{γ∈R|α6γ6β}),其中a,b∈R且ab.当然,(有限的或无限的)半开(或闭)区间可类似地表示.对于R上一个变量y,R[η][y]中元素既可看作R[y]上含η的单元多项式,又可看作R[η]上含y的单元多项式.对于非零Φ(y)∈R[η][y],用lcoeff(Φ,η)和deg(Φ;η)表示Φ(y)作为R[y]上含η的单元多项式的首项系数和次数.同样,用lcoeff(Φ,y)和deg(Φ;y)表示Φ(y)作为R[η]上含y的单元多项式的首项系数和次数.显然,lcoeff(Φ(y),η)∈R[y],但lcoeff(Φ(y),y)∈R[η].为了精确地表示实多项式函数的全局下确界和全局最小值,我们将采用下面定义所描述的区间表示法(Intervalrepresentation).对于实代数数的区间表示,有关详情可见于[10]中§8.5.定义2设h(y)是R[y]中一个非零多项式,且]a,b[是R中一个开区间.若h(a)