一类不定二次规划问题的分枝定界法

A branch and bound algorithm for a kind of indefinite quadratic programming

研究一类特殊的不定二次规划问题的全局最优解.首先利用广义Cholesky分解对该类不定二次规划问题进行预处理,然后进行凹凸分离并用常见的分枝定界法进行求解.利用典型算例进行数值试验,并在试验过程中对分枝定界法采用新的剖分原则进行线性逼近,结果表明该算法是有效的并且运行时间和迭代次数都较少.

The global optimal solution of a kind of indefinite quadratic programming was studied.Firstly,the indefinite quadratic programming was preconditioned by generalized Cholesky factorization,then concave-convex separation was carried out and the branch and bound algorithm was used to solve the last problem.The numerical test was performed with the typical samples and new region subdivision and linear approximation were adopted in the test.The validity of the algorithm was verified with the little running time and few iterations.