资源描述:
《基于契比雪夫多项式和半正定规划求解一维全局最优化的e-全局最优值》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、http://www.paper.edu.cnFindingǫ-globalMinimumofOne-dimensionalFunctioninAnIntervalBasedOnChebyshevPolynomialAndSemi-definiteProgrammingSunChuren∗InstituteofEconomicsandTrade,201600ShanghaiInstituteofForeignTrade,Songjiang,Shanghai,ChinaE-mail:sunchuren@sohu.comH
2、uangLei†DepartmentofTechnology,BridgeMillofHami,Xinjiang,ChinaE-mail:valleyh@sohu.comAbstractWeconsiderfindingtheǫ-globaloptimalvalueofaone-dimensionalfunctionf(x)insomeinterval[a,b]forsomegivenaccuracyǫ>0.Ourapproachisbasedoninterpolationandsemi-definiteprogramm
3、ing.Wefirstfindanwonderfulinter-polationpolynomialPn(x)whoseinterpolationbasisconsistsofthebinarypairs(xi,f(xi)),i=1,···,n+1,wherexi,i=1,···,n+1aren+1zerosoftheCheby-shevpolynomialT(x).Aswillbeshowninthearticle,ifnislargerthanlnMforn+1ǫsomenumberM>0forthegivenacc
4、uracyǫ>0,thereholds
5、f(x)−Pn(x)
6、≤ǫ.Wethenreplacingfindingtheǫ-globaloptimalvalueoff(x)in[a,b]byfindingtheglobaloptimalvalueofPn(x)in[a,b].Weshowthatsuchaproblemcanbecon-vertedintoasemi-definiteprogrammingproblem,hencecanbesolvedinpolynomialtime.Toprocesstheconversi
7、on,wefirstconsidertheglobalnonnegativityproblemofaone-dimensionalpolynomialinR.Weshowthatsuchproblemcanbesolvedviasemi-definiteprogramming.Thenweconsidertheglobalnonnegativityproblemofapolynomialin[a,b]andalsoshowthattheproblemcanbesolvedviasemi-definiteprogrammin
8、g.Thustheglobaloptimalvalueofapolynomialisabletobefound.Toillustrateourapproachposedinthisarticle,wegiveanexampleanddetailedcomputationprocessisshown.Keywords.One-dimensionalglobaloptimization;Chebyshevpolynomial;Interpolation;Polynomialnon-negativity;Semi-defin
9、iteprogrammingAMSsubjectclassification.90C46∗SunChuren,Ph.DcandidateofCUHK;Postaddress:TheInstituteofEconomicsandTrade,TheInstituteofForeignTradeofShanghai,Songjiang,Shanghai,201600;Email:sunchuren@sohu.com.†HuangLei,Female,DepartmentofTechnology,BridgeMillofHam
10、i,Xinjiang;Email:val-leyh@sohu.com.1http://www.paper.edu.cn1IntroductionWeconsiderthefollowingone-dimensionalglobaloptimizationprobleminthispaper.minf(x)(1.1)s.t.x∈[a,b]⊆Rwh