在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2018, Vol. 35 ›› Issue (4): 367-374.doi: 10.3969/j.issn.1005-3085.2018.04.001

• •    下一篇

求解不定二次约束二次规划问题的全局优化算法

赵营峰1,2,   刘三阳1,   葛   立1,2   

  1. 1- 西安电子科技大学数学与统计学院，西安  710072
    2- 河南科技学院数学科学学院，新乡  453003
  • 收稿日期:2016-07-01 接受日期:2017-03-27 出版日期:2018-08-15 发布日期:2018-10-15
  • 基金资助:
    国家自然科学基金(11301409)；河南省高等学校重点科研项目(15A110023; 16A110030).

A Global Optimization Algorithm for Indefinite Quadratically Constrained Quadratic Programs

ZHAO Ying-feng1,2,   LIU San-yang1,   GE Li1,2   

  1. 1- School of Mathematics and Statistics, Xidian University, Xi'an 710072
    2- School of Mathematical Science, Henan Institute of Science and Technology, Xinxiang 453003
  • Received:2016-07-01 Accepted:2017-03-27 Online:2018-08-15 Published:2018-10-15
  • Supported by:
    The National Natural Science Foundation of China (11301409); the Science and Technology Key Project of Education Department of Henan Province (15A110023; 16A110030).

PDF (PC)

277

摘要： 不定二次约束二次规划问题广泛应用于芯片设计、无线通信网络、财政金融和众多工程实际问题．目前尚没有通用的全局收敛准则，这使得求解该问题的全局最优解面临着极大挑战．本文使用矩阵的初等变换技巧将原问题转化为等价双线性规划问题，基于等价问题的特征和线性化松弛技巧构造了等价问题的松弛线性规划，通过求解一系列松弛规划问题的最优解逐步逼近原问题的全局最优解．证明了算法的全局收敛性，并进行数值对比和随机实验，实验结果表明算法高效可行．

关键词: 非凸二次规划, 全局优化, 分支定界算法, 线性多乘积规划

Abstract: Indefinite quadratically constrained quadratic programs are widely used in fields of chip design, wireless communication network, finance and many practical engineering problems. Up to now, there is still no general global convergence criteria for solving indefinite quadratically constrained quadratic programs, and it brings great challenges. In this paper, the matrix elementary transformation technique is used for transforming the original problem into an equivalent bilinear programming problem. The linear relaxation programming problem is constructed based on the characteristics of the equivalent problem, and by means of the sequential solutions of a series of linear programming problems, the global optimal solution is obtained. The global convergence is proved and some numerical comparison and random experiments are performed, numerical results show that the algorithm is efficient and feasible.

Key words: nonconvex quadratic programming, global optimization, branch and bound, linear multiplicative programming

中图分类号: