二次规划问题的一种线性化算法

A Linearization Algorithm for Globally Solving Quadratic Programs

提出了一种全局求解二次约束二次规划问题的有效算法,这类优化问题广泛应用于工程优化、工程设计等实际问题中.通过采用一种新的线性化技术,建立了具有二次约束的二次规划问题的线性规划松驰问题.为了提高算法的计算速度,还提出了区间缩减规则.通过对初始矩形的分割和对一系列线性规划松弛问题的求解,实现并且证明了算法收敛于初始问题的最优解.

In this paper,an effective algorithm for globally solving quadratic programs with quadratic constraints were presented,which was widely used in practical problems such as engineering optimization and engineering design.By utilizing new linearization technique,a linear programming relaxation problem for quadratic programming problems with quadratic constraints was established.To improve the computational speed of the proposed algorithm,some interval reduction operations were used to compress the investigated interval.By subsequently partitioning the initial rectangular and solving a sequence of linear programming relaxation problems,the proposed algorithm was convergent to the global optimal solution of the initial problem.