不定二次规划全局求解的一个新算法

摘要

针对工程设计、设施布局等领域出现的不定二次规划问题的求解,本文给出了一个新的全局优化算法.首先根据二次函数的特点,利用线性松弛化技巧,建立不定二次规划问题的松弛线性规划问题;然后通过一系列松弛线性规划问题的解逐步逼近原问题的最优解.理论上证明了算法的收敛性,数值算例表明算法是有效可行的.%A new global optimization algorithm is presented to solve indefinite quadratic programming problems which have been extensively used in engineering design and facilities layout etc. First, the linear relaxation programming problem of the indefinite quadratic programming problem is derived by utilizing the characteristics of the quadratic function and a linear relaxation technique; then, by means of the sequential solutions of a series of linear programmiug problems, the global optimal solution is obtained. The theoretical analysis and numerical experiment show that the presented algorithm is convergent and efficient.