English

运筹学学报

• 运筹学 • 上一篇    下一篇

求解多项式规划的一个全局最优化算法

田明雨1  杨永建1,*   

  1. 1. 上海大学数学系, 上海 200444
  • 收稿日期:2017-06-09 出版日期:2018-12-15 发布日期:2018-12-15
  • 通讯作者: 杨永建 E-mail: yjyang@shu.edu.cn
  • 基金资助:

    国家自然科学基金(Nos. 60873099, 11161001)

A global optimization algorithm for polynomial programming

TIAN Mingyu1  YANG Yongjian1,*   

  1. 1. Department of Mathematics, Shanghai University, Shanghai 200444, China
  • Received:2017-06-09 Online:2018-12-15 Published:2018-12-15

PDF

168

摘要：

提出一个求解带箱子约束的一般多项式规划问题的全局最优化算法, 该算法包含两个阶段, 在第一个阶段, 利用局部最优化算法找到一个局部最优解. 在第二阶段, 利用一个在单位球上致密的向量序列, 将多元多项式转化为一元多项式, 通过求解一元多项式的根, 找到一个比当前局部最优解更好的点作为初始点, 回到第一个 阶段, 从而得到一个更好的局部最优解, 通过两个阶段的循环最终找到问题的全局最优解, 并给出了算法收敛性分析. 最后, 数值结果表明了算法是有效的.

关键词: 一般多项式, 向量序列, 全局最优化, 收敛性

Abstract:

This paper presents a global optimization algorithm for solving the general polynomial programming with box constraint. The algorithm includes two phases. In the first phase, a local optimal solution is found by a local optimization algorithm. In the second phase, with a density vector sequence on the unit ball, we transform the multivariate polynomial into univariate polynomial, and find a point which is smaller than the current local optimal point by solving the roots of univariate polynomial. We use it as the new initial point, and return to the first phase. Therefore we can get a better local optimal solution. Through repeating the two phases, we can find the global optimal solution of the problem eventually. And the convergence of the algorithm is analyzed. Finally, the numerical results show that the algorithm is effective.

Key words: general polynomial, vector sequence, global optimization, convergence