约束不定二次规划的一个快速收敛算法

Fast Convergence Algorithm for Indefinite Quadratic Programming Problems with the General Bound

对不定二次规划,本文提出了一种线性化技术,将其近似地转化为一个线性规划问题;然后,结合后者的线性约束条件,提出了一个缩减子超矩形算法,该算法的主要思想是对于违犯线性约束条件的变量,从箱约束条件中先行删除,再利用分枝算法求最优值点。本文证明了算法的全局收敛性。数值算例表明,对于大规模的二次规划问题,仍能快速求出结果。

A linear transformation method is presented to solve indefinite quadratic programming in this paper. First, the method is to translate indefinite quadratic programming into a relaxed linear programming. Then, according o the linear constraints the reduced sub-super-rectangle algorithm is proposed. The variable which unsatisfied linear constraints is deleted from box constraints by using the algorithm. After that, the results of optimM point are calculated by using the branching algorithm. The global convergence of the algorithm is proved in this paper. In order to verify the validity of the algorithm, a large scale indefinite quadratic programming is increased. The new algorithm is still applicable. The numerical example shows that the algorithm can quickly calculate the results.