基于Lasserre松弛的紧约束多项式优化问题逼近界分析

高雷阜,周 庆

(辽宁工程技术大学优化与决策研究所,辽宁阜新 123000)

1　引言

多项式优化问题(POP)可描述为目标函数和约束条件都用多项式表示的一类优化问题,是全局优化中的一个基本而重要的研究对象,已被广泛应用于信号处理和系统控制等领域.近年来,这类问题吸引了大批学者的关注,产生了丰富的研究成果[1,2].POP的求解是一个颇具挑战性的问题,传统的数值求解方法有最速下降法、牛顿法、拟牛顿法、共轭梯度法、信赖域法等[2−8].但POP一般是非凸的,故用这些方法求出的值不一定是全局最优值,大多情况下只是局部最优值.

POP的数学形式如下

当约束集合是紧集时,其退化为紧约束POP.此类问题是NP难的,不易求解.经典求解采用Lagrange松弛方法,将其松弛成一个凸优化问题.近年来,Lasserre提出了一种求解POP的全局优化算法[2],该方法是基于半定规划(SDP)松弛,能无限逼近问题的全局最优值.目前该方法已广泛应用于多个领域[2−6].此方法被相关学者称为Lasserre松弛方法.

本文主要研究紧约束POP,基于上述松弛思想,结合多项式平方和(SOS),利用Lasserre将原紧约束POP转化为SOS形式及其成立条件,给出其成立条件推导SOS式成立的证明.在进一步转化为求解另一SOS问题的基础上,给出当其矩阵特征值的最小值大于0时,上述条件成立的证明.从而找出其目标函数在约束集合的下界,通过给出的理论,估计出下界与最小值相差的距离,即逼近界.最后,文章将原有的逼近界定理进一步转化,给出了新的逼近界定理.

2　预备知识

引理2.1[3]对于一个阶数为2d的多项式f,存在一个对称矩阵F,有

引理2.2[3−5]f是其中F≥0.

3　问题及主要结果

考虑如下POP

其中S是紧集,f,g1,···,gm的阶数不大于2d(称d为松弛阶数),(3.1)式不易求解,因此

Lasserre将其转化成如下SOS形式去找(3.1)式中fmin的下界[2]

其中deg表示多项式的阶数,fmin(fmax)表示f在S上的最小值(最大值),fsos表示(3.2)式中的最优值.由上述知,对于固定的d,有fsos≤fmin.当g1,···,gm在适当的条件下,存在Q=Q(g1,···,gm)有

为了保证(3.2)式成立,需如下引理.

引理3.1[6]存在一个对称的正定矩阵E 及SOS多项式σ1,···,σm,且deg(σigi)≤2d,i=1,···,m,有

定理3.1若S内部非空,R[x]是实多项式环,R[x]k表示阶数最多是k的多项式的子空间,那么下列叙述等价

(1)引理3.1成立;

(2)对于每个f∈R[x]2d,(3.2)式都可求;

证(1)⇒(2)由引理2.1,有其中F是对称矩阵.由引理3.1知E是正定矩阵,因此存在足够大的λ,且λ＞0,使

(2)⇒(3)显然成立.

因此引理3.1成立.故定理3.1成立.

在引理3.1中,多项式σ1,···,σm和正定矩阵E 可能并不唯一.当λmin(E)越大,获得的逼近界越好.其中X 是对称矩阵,λmax(X)(λmin(X))表示X 的特征值的最大值(最小值),X＞0意味着λmin(X)＞0.因此尽可能找到λmin(E)的最大值,进而解决如下SOS问题

定理3.2假设是(3.4)式的最优解.当且仅当λmin(E∗)＞0,引理3.1才成立.

故结论得证.

引理3.2[9]若S内部非空,对于每个∆∈Ω2d,且0在S内部,则κ2d(S)＞0.

引理3.3[10]如果f∈R[x]2d,那么存在一个对称矩阵W,使得

其中对于任意矩阵A,‖A‖2是标准的二范数,注意 ‖A‖2≤ ‖A‖F.

引理 3.4[11]假设ψ 是包含1的R[x]2d的子空间,χ(ψ,S)＜ ∞,(σ1,···,σm,E)满足引理3.1.令f∈ψ,fmin(fmax)是在S上的最小值(最大值).如果fsos是(3.2)式的最优值,则有

为了得到引理3.4的精确的逼近界,需要估计χ(ψ,S)和λmin(E)的值.

定理3.3假设0在S 的内部,(σ1,···,σm,E)满足引理3.1,令f∈R[x]2d,则有

证因为S内部非空,由引理3.2知如果

对所有的x∈ S 都有|p(x)|≤ 1,则‖p‖L2(S)≤ 1.由有由引理3.4得

故定理得证.

注如果(3.4)式中的最优解用到上式,获得的最优界更好.(3.4)式中的最优值λmin(E∗)的选取依赖于S.已有文献给出但未给收敛性.下面给出具体过程并证明收敛.

在S上非负.若存在SOS多项式s0,s1,···,sm,对每个deg(sigi)≤2d及

因为s0是SOS,有

所以如果(3.6)式成立,则有

如果(3.6)式不成立,但已知R,可以增加(3.1)式的约束条件r(x)≥0.故可以通过来估计.下证其收敛性.

有

4　结论

紧约束POP是NP难的,不易求解,故Lasserre将其转化为SOS形式求目标函数在约束集合的下界.为了使得Lasserre转化的SOS可求,在已知其成立条件前提下,进一步给出证明过程,从而找出所求问题的下界.在已知下界的基础上,通过理论估计出下界与最小值相差的距离,即逼近界.将原有的逼近界定理进行转化,给出另外一个逼近界定理,从而解决原紧约束POP.

[1]陈德俊.多项式优化方法在二次规划问题中的应用[D].北京:清华大学,2011.

[2]Lasserre J B.Global optimization with polynomials and the problem of moments[J].Soc.Indus.Appl.Math.,2001,11(3):796–817.

[3]Prajna S,Papachristodoulou A,Wu F.Nonlinear control synthesis by sum of squares optimization:A Lyapunov-based approach[C].Proc.Asian Contr.Conf.,2004,1:157–165.

[4]Parrilo P A.Semidefinite programming relaxations for semialgebraic problems[J].Math.Prog.,2003,96(2):293–320.

[5]Laurent M.Sum of squares,moment matrices and optimization over polynomials[J].Emer.Appl.Alg.Geom.,2008,149:157–270.

[6]Lasserre J B.Moments,positive polynomials and their applications[M].London:Imperial College Press,2009.

[7]董丽,周金川.无约束优化问题的一个下降方法[J].数学杂志,2015,35(1):173–179.

[8]张新华.等式约束非凸优化问题的修正牛顿算法[J].数学杂志,2015,35(1):1–11.

[9]Barvinok.Eastimating L∞norms by L2knorms for functions on orbits[J].Found.Comp.Math.,2002,2(4):393–412.

[10]Nie J,Demmel J,Sturmfels B.Minimizing polynomials via sum of squares over the gradient ideal[J].Math.Prog.,2005,106(3):587–606.

[11]Reznick B.Some concrete aspects of Hilbert’s 17th problem[J].Contem.Math.,Amer.Math.Soc.,2000,253:251–272.