An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints
An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints
复制标题
DOI：
10.1007/s101070050003
复制
发表时间：
2000-05
期刊：
影响因子：
--
通讯作者：
Hoai An Le Thi
中科院分区：
文献类型：
--
作者：
Hoai An Le Thi
在本文中，我们研究了两种方法，以最小化二次型受相交的多个椭球。第一种方法是d.c.（凸函数的差异）优化算法（abbr. DCA），其主要工具是凸极小化中的邻近点算法和/或投影次梯度方法。第二个是一个分支和定界计划使用拉格朗日对偶的边界和椭球平分分支。DCA首先由Pham Dinh于1986年为一般的直流程序引入，后来由我们的各种工作开发，是一种局部方法，但从一个良好的起点出发，它通常提供全局解决方案。这促使我们联合收割机的DCA和我们的分支定界算法，以获得一个良好的初始点的DCA和证明的整体性。在这两种方法中，我们试图使用椭球约束二次规划作为主要的子问题。这个想法是基于这样一个事实，即这些程序可以有效地解决一些可用的（多项式和非多项式时间）算法，其中DCA与重新启动过程最近提出的Pham Dinh和Le Thi已被证明是最强大的和快速的大规模的问题。最后给出了维数为200的几个数值实验，实验结果表明了DCA和DCA-分枝定界组合算法的有效性和鲁棒性。
In this paper we investigate two approaches to minimizing a quadratic form subject to the intersection of finitely many ellipsoids. The first approach is the d.c. (difference of convex functions) optimization algorithm (abbr. DCA) whose main tools are the proximal point algorithm and/or the projection subgradient method in convex minimization. The second is a branch-and-bound scheme using Lagrangian duality for bounding and ellipsoidal bisection in branching. The DCA was first introduced by Pham Dinh in 1986 for a general d.c. program and later developed by our various work is a local method but, from a good starting point, it provides often a global solution. This motivates us to combine the DCA and our branch and bound algorithm in order to obtain a good initial point for the DCA and to prove the globality of the DCA. In both approaches we attempt to use the ellipsoidal constrained quadratic programs as the main subproblems. The idea is based upon the fact that these programs can be efficiently solved by some available (polynomial and nonpolynomial time) algorithms, among them the DCA with restarting procedure recently proposed by Pham Dinh and Le Thi has been shown to be the most robust and fast for large-scale problems. Several numerical experiments with dimension up to 200 are given which show the effectiveness and the robustness of the DCA and the combined DCA-branch-and-bound algorithm.