求解带二次约束的非凸二次规划的一种分支定界算法

本文提出了一种求解带二次约束和线性约束的二次规划的分支定界算法.在算法中,我们运用Lipschitz条件来确定目标函数和约束函数的在每个n矩形上的上下界,对于n矩形的分割,我们采用选择n矩形最长边的二分法,同时我们采用了一些矩形删除技术,在不大幅增加计算量的前提下,起到了加速算法收敛的效果.从理论上我们证明了算法的收敛性,同时数值实验表明该算法是有效的.     

Greedy and Local Search Heuristics for Unconstrained Binary Quadratic Programming

In this paper, a greedy heuristic and two local search algorithms, 1-opt local search and k-opt local search, are proposed for the unconstrained binary quadratic programming problem (BQP). These heuristics are well suited for the incorporation into meta-heuristics such as evolutionary algorithms. Their performance is compared for 115 problem instances. All methods are capable of producing high quality solutions in short time. In particular, the greedy heuristic is able to find near optimum solutions a few percent below the best-known solutions, and the local search procedures are sufficient to find the best-known solutions of all problem instances with n 100. The k-opt local searches even find the best-known solutions for all problems of size n 250 and for 11 out of 15 instances of size n = 500 in all runs. For larger problems (n = 500, 1000, 2500), the heuristics appear to be capable of finding near optimum solutions quickly. Therefore, the proposed heuristics—especially the k-opt local search—offer a great potential for the incorporation in more sophisticated meta-heuristics.     

二次比式和问题的加速分枝定界算法

本文给出非凸二次约束上二次比式和问题(P)的一个新的加速分枝定界算法.该算法利用线性化技术建立了问题(P)的松弛线性规划问题(RLP),通过对其可行域的细分和求解一系列线性规划问题,不断更新(P)的全局最优值的上下界.为了提高收敛速度,从最优性和可行性两方面,提出了新的删除技术,理论上证明该算法是收敛的,数值试验表明了算法的有效性和可行性.     

非凸二次规划的粒子群算法

给出了粒子群算法中惯性权值和学习因子的一种简单改进,并将其应用到非凸二次规划的求解中,通过数值试验与现有的求解非凸二次规划问题的分支定界法进行了比较,得到了较好的结果.     

Global Optimization Techniques for Solving the General Quadratic Integer Programming Problem

We consider the problem of minimizing a general quadratic function over a polytope in the n-dimensional space with integrality restrictions on all of the variables. (This class of problems contains, e.g., the quadratic 0-1 program as a special case.) A finite branch and bound algorithm is established, in which the branching procedure is the so-called integral rectangular partition, and the bound estimation is performed by solving a concave programming problem with a special structure. Three methods for solving this special concave program are proposed.     

A Non-Interior Path Following Method for Convex Quadratic Programming Problems with Bound Constraints

We propose a non-interior path following algorithm for convex quadratic programming problems with bound constraints based on Chen-Harker-Kanzow-Smale smoothing technique. Conditions are given under which the algorithm is globally convergent or globally linearly convergent. Preliminary numerical experiments indicate that the method is promising.     

Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints

The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported.     

A New Semidefinite Programming Bound for Indefinite Quadratic Forms Over a Simplex

The paper describes a method for computing a lower bound of the global minimum of an indefinite quadratic form over a simplex. The bound is derived by computing an underestimator of the convex envelope by solving a semidefinite program (SDP). This results in a convex quadratic program (QP). It is shown that the optimal value of the QP is a lower bound of the optimal value of the original problem. Since there exist fast (polynomial time) algorithms for solving SDP's and QP's the bound can be computed in reasonable time. Numerical experiments indicate that the relative error of the bound is about 10 percent for problems up to 20 variables, which is much better than a known SDP bound.     

不等式约束二次规划的一新算法

文献[1]提出了一般等式约束非线性规划问题一种求解途径．文献[2]应用这一途径给出了等式约束二次规划问题的一种算法，本文在文献[1]和[2]的基础上对不等式约束二次规划问题提出了一种新算法．     

一种新的可分凸二次规划的不可行内点算法

本文对可分凸二次规划提出了一个新的不可行内点算法 ,证明了该算法是一个多项式时间算法 ,并将迭代复杂性界降至O(nL) .     

An Algorithm for Global Minimization of Linearly Constrained Quadratic Functions*

A branch and bound algorithm is proposed for finding an approximate global optimum of quadratic functions over a bounded polyhedral set. The algorithm uses Lagrangian duality to obtain lower bounds. Preliminary computational results are reported.     

Interior-Point Solver for Large-Scale Quadratic Programming Problems with Bound Constraints

In this paper, we present an interior-point algorithm for large and sparse convex quadratic programming problems with bound constraints. The algorithm is based on the potential reduction method and the use of iterative techniques to solve the linear system arising at each iteration. The global convergence properties of the potential reduction method are reassessed in order to take into account the inexact solution of the inner system. We describe the iterative solver, based on the conjugate gradient method with a limited-memory incomplete Cholesky factorization as preconditioner. Furthermore, we discuss some adaptive strategies for the fill-in and accuracy requirements that we use in solving the linear systems in order to avoid unnecessary inner iterations when the iterates are far from the solution. Finally, we present the results of numerical experiments carried out to verify the effectiveness of the proposed strategies. We consider randomly generated sparse problems without a special structure. Also, we compare the proposed algorithm with the MOSEK solver. Research partially supported by the MIUR FIRB Project RBNE01WBBB “Large-Scale Nonlinear Optimization.”     

解带有二次约束非凸二次规划问题的一个分枝缩减方法

在这篇论文里,有机地把外逼近方法与分枝定界技术结合起来,提出了解带有二次约束非凸二次规划问题的一个分枝缩减方法;给出了原问题的一个新的线性规划松弛,以便确定它在超矩形上全局最优值的一个下界;利用超矩形的一个深度二级剖分方法,以及超矩形的缩减和删除技术,提高算法的收敛速度;证明了在知道原问题可行点的条件下,该算法在有限步里就可以获得原问题的一个全局最优化解,并且用一个例子说明了该算法是有效的.     

Distributed versus Centralized Storage and Control for Parallel Branch and Bound: Mixed Integer Programming on the CM-5

This paper describes parallel, non-shared-memoryimplementation of the classical general mixed integer branch and boundalgorithm, with experiments on the CM-5 family of parallel processors. Themain issue in such an implementation is whether task scheduling and certaindata-storage functions should be handled by a single processor, orspread among multiple processors. The centralized approach riskscreating processing bottlenecks, while the more decentralizedimplementations differ more from the fundamental serial algorithm.Extensive computational tests on standard MIPLIB problems comparecentralized, clustered, and fully decentralized task scheduling methods, using a novel combination of random work scattering and rendezvous-basedglobal load balancing, along with a distributed control by tokentechnique. Further experiments compare centralized and distributedschemes for storing heuristic pseudo-cost branching data. The distributed storage method is based on continual asynchronous reductionalong a tree of redundant storage sites. On average, decentralized taskscheduling appears at least as effective as central control, butpseudo-cost storage should be kept as centralized as possible.     

一种基于LVI求解二次规划问题的数值算法

给出并研究了一种数值算法(简称94LVI算法),用于求解带等式和双端约束的二次规划问题. 这类带约束的二次规划问题首先被转换为线性变分不等式问题,该问题等价于分段线性投影等式.接着使用94LVI算法求解上述分段线性投影等式,从而得到QP问题的最优解. 进一步给出了94LVI算法的全局收敛性证明. 94LVI算法与经典有效集算法的对比实验结果证实了给出的94LVI算法在求解二次规划问题上的高效性与优越性.     

Using a Hybrid Genetic-Algorithm/Branch and Bound Approach to Solve Feasibility and Optimization Integer Programming Problems

The satisfiability problem in forms such as maximum satisfiability (MAX-SAT) remains a hard problem. The most successful approaches for solving such problems use a form of systematic tree search. This paper describes the use of a hybrid algorithm, combining genetic algorithms and integer programming branch and bound approaches, to solve MAX-SAT problems. Such problems are formulated as integer programs and solved by a hybrid algorithm implemented within standard mathematical programming software. Computational testing of the algorithm, which mixes heuristic and exact approaches, is described.     

一个求解箱约束二次规划的非内点预估校正算法

利用Chen-Harker-Kanzow-Smale光滑技术,给出了一个求解箱约束二次规划的预估校正的算法,它是Xu‘s方程的进一步研究,它的思想是将问题的K-T条件转化成一组光滑的等式,再用预估校正方法求解.同现存的算法相比,该算法具有较快的收敛速度,且所需的条件相对较弱.本文改进了该领域内的一些最新结果.     

一种非增值型凸二次双层规划的有效算法

主要研究了非增值型凸二次双层规划的一种有效求解算法。首先利用数学规划的对偶理论,将所求双层规划转化为一个下层只有一个无约束凸二次子规划的双层规划问题.然后根据两个双层规划的最优解和最优目标值之间的关系,提出一种简单有效的算法来解决非增值型凸二次双层规划问题.并通过数值算例的计算结果说明了该算法的可行性和有效性。     

A Semidefinite Programming Heuristic for Quadratic Programming Problems with Complementarity Constraints

The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822.     

A Branch and Bound Algorithm for Separable Concave Programming

In this paper, we propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into sub-rectangles when one problem is branched into two subproblems. It is proved that the LDB method is a normal rectangle subdivision(NRS). Numerical tests on problems with dimensions from 100 to 10000 show that the proposed branch and bound algorithm is efficient for solving large scale separable concave programming problems, and convergence rate is faster than ω-subdivision method.