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

A Global Optimization Algorithm for Indefinite Quadratically Constrained Quadratic Programs

作　　者：赵营峰 刘三阳 葛立 ZHAO Ying-feng;LIU San-yang;GE Li(School of Mathematics and Statistics,Xidian University,Xi'an 710072;School of Mathematical Science,Henan Institute of Science and Technology,Xinxiang 453003)

机构地区：[1]西安电子科技大学数学与统计学院,西安710072 [2]河南科技学院数学科学学院,新乡453003

出　　处：《工程数学学报》2018年第4期367-374,共8页Chinese Journal of Engineering Mathematics

基　　金：国家自然科学基金(11301409);河南省高等学校重点科研项目(15A110023;16A110030)~~

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

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

分 类 号：O221.2[理学—运筹学与控制论]