一类全局优化问题的线性化方法

本文对带有不定二次约束且目标函数为非凸二次函数的最优化问题提出了一类新的确定型全局优化算法,通过对目标函数和约束函数的线性下界估计,建立了原规划的松弛线性规划,通过对松弛线性规划可行域的细分以及一系列松弛线性规划的求解过程,得到原问题的全局最优解.我们从理论上证明了算法能收敛到原问题的全局最优解.

A Global Optimization Algorithm Using Linear Relaxation

The paper considers the global minimum of (QP) that arise in various practice problems.By utilizing the inherent property of the quadratic function an approximations a linear relaxation of (QP) is then obtained.Thus initial (QP) is reduced to a sequence of linear programming problems through the successive refinement of a linear relaxation of feasible region of the objective function.The proposed algorithm is convergent to the global minimum of (QP) by means of the subsequent solutions of a series of linear programming problems.Test results indicate that the proposed algorithm is extremely robust and can be used successfully to solve the global minimum of (QP) on a microcomputer.