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

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

An exact algorithm for graph partitioning

An exact algorithm is presented for solving edge weighted graph partitioning problems. The algorithm is based on a branch and bound method applied to a continuous quadratic programming formulation of the problem. Lower bounds are obtained by decomposing the objective function into convex and concave parts and replacing the concave part by an affine underestimate. It is shown that the best affine underestimate can be expressed in terms of the center and the radius of the smallest sphere containing the feasible set. The concave term is obtained either by a constant diagonal shift associated with the smallest eigenvalue of the objective function Hessian, or by a diagonal shift obtained by solving a semidefinite programming problem. Numerical results show that the proposed algorithm is competitive with state-of-the-art graph partitioning codes.     

求解非凸区域上凸函数比式和问题的全局优化方法

针对非凸区域上的凸函数比式和问题,给出一种求其全局最优解的确定性方法.该方法基于分支定界框架.首先通过引入变量,将原问题等价转化为d.c.规划问题,然后利用次梯度和凸包络构造松弛线性规划问题,从而将关键的估计下界问题转化为一系列线性规划问题,这些线性规划易于求解而且规模不变,更容易编程实现和应用到实际中;分支采用单纯形对分不但保证其穷举性,而且使得线性规划规模更小.理论分析和数值实验表明所提出的算法可行有效.     

分枝定界算法中的新区间剖分原则

在求解非凸规划的分枝定界法中,剖分区间的选取直接影响到整个算法的收敛速度.本文对现有的LDB区间剖分法进行了改进,给出了一种剖分区间的选取原则,理论分析和数值算例表明采用新的ILDB算法会具有更快的收敛速度.     

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

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

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

A Lagrangian Based Branch-and-Bound Algorithm for Production-transportation Problems

We propose a branch-and-bound algorithm of Falk–Soland's type for solving the minimum cost production-transportation problem with concave production costs. To accelerate the convergence of the algorithm, we reinforce the bounding operation using a Lagrangian relaxation, which is a concave minimization but yields a tighter bound than the usual linear programming relaxation in O(mn log n) additional time. Computational results indicate that the algorithm can solve fairly large scale problems.     

A Branch and Bound Method for Solving Integer Separable Concave Problems

A branch and bound algorithm is proposed for solving integer separable concave problems. The method uses Lagrangian duality to obtain lower and upper bounds. We show that the dual program of a separable concave problem is a linear program. Moreover, we identify an excellent candidate to test on each region of the branch and we show an optimality sufficient condition for this candidate. Preliminary computational results are reported.     

Global optimization algorithm for sum of generalized polynomial ratios problem

In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ?-global optimum.     

Finitely convergent cutting planes for concave minimization

In 1964 Tuy introduced a new type of cutting plane, the concavity cut, in the context of concave minimization. These cutting planes, which are also known as convexity cuts, intersection cuts and Tuy cuts, have found application in several algorithms, e.g., branch and bound algorithm, conical algorithm and cutting plane algorithm, and also in algorithms for other optimization problems, e.g., reverse convex programming, bilinear programming and Lipschitzian optimization. Up to now, however, it has not been possible to either prove or disprove the finite convergence of a pure cutting plane algorithm for concave minimization based solely on these cutting planes. In the present paper a modification of the concavity cut is proposed that yields deeper cutting planes and ensures the finite convergence of a pure cutting plane algorithm based on these cuts.     

一种求解二次约束二次规划问题的自适应全局优化算法

为了更好地解决二次约束二次规划问题(QCQP), 本文基于分支定界算法框架提出了自适应线性松弛技术, 在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分; 通过缩减技术删除不包含全局最优解的部分区域, 以加快算法的收敛速度。最后, 通过数值结果表明提出的算法是有效可行的。     

一种求解二次约束二次规划问题的自适应全局优化算法

为了更好地解决二次约束二次规划问题(QCQP), 本文基于分支定界算法框架提出了自适应线性松弛技术, 在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分; 通过缩减技术删除不包含全局最优解的部分区域, 以加快算法的收敛速度。最后, 通过数值结果表明提出的算法是有效可行的。     

A branch and bound algorithm for globally solving a class of nonconvex programming problems

A branch and bound algorithm is proposed for globally solving a class of nonconvex programming problems (NP). For minimizing the problem, linear lower bounding functions (LLBFs) of objective function and constraint functions are constructed, then a relaxation linear programming is obtained which is solved by the simplex method and which provides the lower bound of the optimal value. The proposed algorithm is convergent to the global minimum through the successive refinement of linear relaxation of the feasible region and the solutions of a series of linear programming problems. And finally the numerical experiment is reported to show the feasibility and effectiveness of the proposed algorithm.     

A Branch and Contract Algorithm for Problems with Concave Univariate, Bilinear and Linear Fractional Terms

A new deterministic branch and bound algorithm is presented in this paper for the global optimization of continuous problems that involve concave univariate, bilinear and linear fractional terms. The proposed algorithm, the branch and contract algorithm, relies on the use of a bounds-contraction subproblem that aims at reducing the size of the search region by eliminating portions of the domain in which the objective function takes only values above a known upper bound. The solution of contraction subproblems at selected branch and bound nodes is performed within a finite contraction operation that helps reducing the total number of nodes in the branch and bound solution tree. The use of the proposed algorithm is illustrated with several numerical examples.     

运筹学中若干离散规划问题的相对差分搜索解法

运筹学中有很多离散规划问题。其中的线性规划通常用分枝定界法或割平面法，还有图上作业法求解。不论哪种方法工作量都不小，而且效率低；至于非线性规划大都是用动态规划法求解，也很麻烦、耗时。对于大规模问题，不论线性或非线性离散规划，现有解法都受到问题规模的限制；还有资源分配和背包问题至今没有见到解决方法。本文就是为了解决这些问题，提出了相对差分搜索算法。通过5个算例和其它文献中的一些算例计算验证了本法简单、快速、有效和精确，尤其不受问题规模的限制是其最大的优点。     

Solving Convex MINLP Optimization Problems Using a Sequential Cutting Plane Algorithm

In this article we look at a new algorithm for solving convex mixed integer nonlinear programming problems. The algorithm uses an integrated approach, where a branch and bound strategy is mixed with solving nonlinear programming problems at each node of the tree. The nonlinear programming problems, at each node, are not solved to optimality, rather one iteration step is taken at each node and then branching is applied. A Sequential Cutting Plane (SCP) algorithm is used for solving the nonlinear programming problems by solving a sequence of linear programming problems. The proposed algorithm generates explicit lower bounds for the nodes in the branch and bound tree, which is a significant improvement over previous algorithms based on QP techniques. Initial numerical results indicate that the described algorithm is a competitive alternative to other existing algorithms for these types of problems.     

AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS

An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs.     

一类带反凸约束的非线性比式和问题的全局优化算法

本文针对一类带有反凸约束的非线性比式和分式规划问题,提出一种求其全局最优解的单纯形分支和对偶定界算法.该算法利用Lagrange对偶理论将其中关键的定界问题转化为一系列易于求解的线性规划问题.收敛性分析和数值算例均表明提出的算法是可行的.     

Global Optimization Versus Integer Programming in Portfolio Optimization under Nonconvex Transaction Costs

This paper is concerned with a portfolio optimization problem under concave and piecewise constant transaction cost. We formulate the problem as nonconcave maximization problem under linear constraints using absolute deviation as a measure of risk and solve it by a branch and bound algorithm developed in the field of global optimization. Also, we compare it with a more standard 0–1 integer programming approach. We will show that a branch and bound method elaborating the special structure of the problem can solve the problem much faster than the state-of-the integer programming code.     

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.