一类多项式全局优化的差分算法.pdf

《一类多项式全局优化的差分算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第42卷第5期同济大学学报(自然科学版)VO1．42No．52014年5月JOURNALOFTONGJIUNIVERSITY(NATURALSCIENCE)May2Ol4文章编号：0253—374X(2014)05—0804—03一类多项式全局优化的差分算法朱经浩，何似菡(同济大学数学系，上海200092)摘要：引入一类元多项式的倒向微分流以求解全局优化问VP()一(2懈}一，2rnx~'-，⋯，题．沿着倒向微分流，建立一个差分一牛顿混合算法，并证明了2~2m-)+Ax一，由算法所得迭代点的绝对误差受到差分步长的一致界囿．应且其Hesse矩阵

2、为用所建立的算法，给出了一个数值计算的例子．V。尸()=diag(2m(2m—1)z}一，关键词：多项式全局优化；倒向微分方程；差分一牛顿混合算2nr-。2m(2m一1)32，⋯，—法2m(2m～1)z2rr-0)+A中图分类号：0224文献标志码：A此矩阵中除了对角线上为非负项外其他处均为0．可见，对于VxfR"，有VP()≥0．ADifferenceAlgorithmtoFindGlobal这类多项式具有一定的实际意义，在文献[1—2]MinimizersofaPolynomial阐述了下述问题：ZttUJinghao，HESihanra

3、in{P(x)一w(x)+1Ax一}(2)(DepartmentofMathematics，Ton~iUniversity，Shanghai200092，xElJChina)其中Abstract：Thispaperpresentsadifferentialflowconcerningw()===耋k_

4、1(1I[ekxl一EZk)theglobaloptimizationwithpolynomials．Alongtheflow这个问题经常出现在许多复杂系统中，涵盖相变的whichleadstoaglobalminimizerthereispo

5、sedamixed非凸分析、网络设计及通信的离散优化等方面．如果differencealgorithmwithNewtonmethod．AnerroranalysisofthealgorithmisgivenwithanumericalexampletoA≥o，令式(2)中一0，专a===4，p=n，B一(demonstratethemixeddiferencemethod．为只有在第k行与第k列交叉位置的元素为1，其余Keywords：globaloptimizationwithpolynomial；backwarddifferential

6、flow；mixeddifferencealgorithmwithNewton元素都为0的，z阶方阵)，于是得到w()一∑2，method这样问题(2)所涉及的目标函数即为本文所关注的一类多项式．考虑如下多项式全局优化问题(P)：minP()1全局最优化S．t．∈R其中对于一(zl，2，⋯，)r∈R1．1一个球约束优化问题文献[3—4]证明了多项式全局优化问题(P)的所P()一∑z+1xTAx一厂(1)有最优点都含于一个以原点为中心的闭球内部，以z一1这里≥2，A一()z，⋯，是半正定矩阵，而，一下记此闭球为(fl，⋯，)是一个维非零向量．多

7、项式P()的D：={XlxTx≤d。}梯度为这样无约束多项式全局优化问题(P)就等价地转化收稿日期：2013-06—24基金项目：国家自然科学基金(10671145)第一作者：朱经浩(1949一)，男，教授，博士生导师，主要研究方向为最优控制理论与应用．E-mail：jinghaok@online．sh_cn通讯作者：何似菡(199O一)，女，硕士生，主要研究方向为最优控制理论与应用．E-mail：hesihan0804@foxmail．CYI第5期朱经浩，等：一类多项式全局优化的差分算法为以下球约束优化问题：P(ID)是关于lD>fD单调递

8、减的．定理1I5]设(ID)，lD∈(O，+oo)为式(6)，(7)定minP()===∑z2+1xTAx一，，义的微分流，记S．t．lI≤d．(3)量(0+)一lim2(p)显然这里的关键问题是如何得到闭球的半径d，按斗u若(O+)Yc(O+)≤，则(0+)是P()在球D上的照文献[4]给出的计算公式可得到全局最小点．以下说明应用定理1可求解球约束下的全局优—m，T／2n2m-I)t化问题(3)．由引理1和引理2可知，lJit(p)JJ关于p>0单调递减．若存在正实数使得()}1一d，则对其中任意∈D有M—max{I以l，1I)1≤≤，l(

9、5)P()≥P()+号[—d。]≥而J是最优化问题rainJ2,n()一(2)!∑s，inf{P()+号[—d。]}一lJS．t．l一1的最优值．1．2全局最优点P