求解标准二次优化问题的割平面算法

标准的二次优化问题是NP-hard问题,把该问题转化为半不定的线性规划问题,且提出了一个线性规划的割平面算法来求解这个半不定的线性规划问题,并给出了该算法的收敛性证明.     

On Global Optimality Conditions and Cutting Plane Algorithms

We discuss global optimality conditions and cutting plane algorithms for DC optimization. The discussion is motivated by certain incorrect results that have appeared recently in the literature on these topics. Incidentally, we investigate the relation of the Tikhonov reciprocity theorem to the optimality conditions for general nonconvex global optimization problems and show how the outer-approximation scheme developed earlier for DC programming can be used to solve a wider class of problems.     

On the generalization of ECP and OA methods to nonsmooth convex MINLP problems

In this article, generalization of some mixed-integer nonlinear programming algorithms to cover convex nonsmooth problems is studied. In the extended cutting plane method, gradients are replaced by the subgradients of the convex function and the resulting algorithm shall be proved to converge to a global optimum. It is shown through a counterexample that this type of generalization is insufficient with certain versions of the outer approximation algorithm. However, with some modifications to the outer approximation method a special type of nonsmooth functions for which the subdifferential at any point is a convex combination of a finite number of subgradients at the point can be considered. Numerical results with extended cutting plane method are also reported.     

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.     

A Cutting Plane Algorithm for Linear Reverse Convex Programs

In this paper, global optimization of linear programs with an additional reverse convex constraint is considered. This type of problem arises in many applications such as engineering design, communications networks, and many management decision support systems with budget constraints and economies-of-scale. The main difficulty with this type of problem is the presence of the complicated reverse convex constraint, which destroys the convexity and possibly the connectivity of the feasible region, putting the problem in a class of difficult and mathematically intractable problems. We present a cutting plane method within the scope of a branch-and-bound scheme that efficiently partitions the polytope associated with the linear constraints and systematically fathoms these portions through the use of the bounds. An upper bound and a lower bound for the optimal value is found and improved at each iteration. The algorithm terminates when all the generated subdivisions have been fathomed.     

The minimization of lower subdifferentiable functions under nonlinear constraints: An all feasible cutting plane algorithm

Nonlinear, possibly nonsmooth, minimization problems are considered with boundedly lower subdifferentiable objective and constraints. An algorithm of the cutting plane type is developed, which has the property that the objective needs to be considered at feasible points only. It generates automatically a nondecreasing sequence of lower bounds converging to the optimal function value, thus admitting a rational rule for stopping the calculations when sufficient precision in the objective value has been obtained. Details are given concerning the efficient implementation of the algorithm. Computational results are reported concerning the algorithm as applied to continuous location problems with distance constraints. The author thanks the referees for several constructive remarks and for pointing out an error in an earlier version of the proof of Lemma 2.1.     

Cutting Plane/Tabu Search Algorithms for Low Rank Concave Quadratic Programming Problems

In this paper, we will propose an efficient heuristic algorithm for solving concave quadratic programming problems whose rank of the objective function is relatively small. This algorithm is a combination of Tuy's cutting plane to eliminate the feasible region and a kind of tabu-search method to find a good vertex. We first generate a set of V of vertices and select one of these vertices as a starting point at each step, and apply tabu-search and Tuy's cutting plane algorithm where the list of tabu consists of those vertices eliminated by cutting planes and those newly generated vertices by cutting planes. When all vertices of the set V are eliminated, the algorithm is terminated. This algorithm need not converge to a global minimum, but it can work very well when the rank is relatively small (up to seven). The incumbent solutions are in fact globally optimal for all tested problems. We also propose an alternative algorithm by incorporating Rosen's hyperrectangle cut. This algorithm is more efficient than the combination of Tuy's cutting plane and tabu-search.     

Conical Partition Algorithm for Maximizing the Sum of dc Ratios

The following problem is considered in this paper: 0, j = 1,\ldots,m,$$" align="middle" border="0"> are d.c. (difference of convex) functions over a convex compact set D in R^n. Specifically, it is reformulated into the problem of maximizing a linear objective function over a feasible region defined by multiple reverse convex functions. Several favorable properties are developed and a branch-and-bound algorithm based on the conical partition and the outer approximation scheme is presented. Preliminary results of numerical experiments are reported on the efficiency of the proposed algorithm.AMS Subject Classifications: 90C32, 90C30, 65K05.The authors were partially supported by a Grant-in-Aid (Yang Dai: C-13650444; Jianming Shi and Shouyang Wang: C-14550405) of the Ministry of Education, Science, Sports and Culture of Japan.     

A Combined Algorithm for Fractional Programming

In this paper, we present an outer approximation algorithm for solving the following problem: max _xS {f(x)/g(x)}, where f(x)0 and g(x)>0 are d.c. (difference of convex) functions over a convex compact subset S of R ⁿ . Let ()=max _xS (f(x)–g(x)), then the problem is equivalent to finding out a solution of the equation ()=0. Though the monotonicity of () is well known, it is very time-consuming to solve the previous equation, because that maximizing (f(x)–g(x)) is very hard due to that maximizing a convex function over a convex set is NP-hard. To avoid such tactics, we give a transformation under which both the objective and the feasible region turn to be d.c. After discussing some properties, we propose a global optimization approach to find an optimal solution for the encountered problem.     

带交易费用的投资组合模型的割平面解法

本文讨论了带交易费用的投资组合模型，因对这一类带二次约束的线性优化问题没有特殊的处理方法，我们利用割平面法使这一非线性优化间题可通过解一系列线性规划问题来求解．     

Constraint decomposition algorithms in global optimization

Many global optimization problems can be formulated in the form min{c(x, y): x X, y Y, (x, y) Z, y G} where X, Y are polytopes in ^p , ⁿ , respectively, Z is a closed convex set in ^p+n, while G is the complement of an open convex set in ⁿ . The function c: ^p+n is assumed to be linear. Using the fact that the nonconvex constraints depend only upon they-variables, we modify and combine basic global optimization techniques such that some new decomposition methods result which involve global optimization procedures only in ⁿ . Computational experiments show that the resulting algorithms work well for problems with smalln.     

一种求解线性二层规划的割平面方法

以下层问题的K-T最优性条件代替下层问题,将线性二层规划转化为相应的单层规划问题,通过分析单层规划可行解集合的结构特征,设计了一种求解线性二层规划全局最优解的割平面算法.数值结果表明所设计的割平面算法是可行、有效的.     

A Long-Step, Cutting Plane Algorithm for Linear and Convex Programming

A cutting plane method for linear programming is described. This method is an extension of Atkinson and Vaidya's algorithm, and uses the central trajectory. The logarithmic barrier function is used explicitly, motivated partly by the successful implementation of such algorithms. This makes it possible to maintain primal and dual iterates, thus allowing termination at will, instead of having to solve to completion. This algorithm has the same complexity (O(nL ²) iterations) as Atkinson and Vaidya's algorithm, but improves upon it in that it is a long-step version, while theirs is a short-step one in some sense. For this reason, this algorithm is computationally much more promising as well. This algorithm can be of use in solving combinatorial optimization problems with large numbers of constraints, such as the Traveling Salesman Problem.     

混合遗传算法收敛性分析

针对遗传算法爬山能力弱但合局搜索能力强的特点 ,本文将遗传算法嵌入到基入传统优化的拟下降算法中 ,并对算法的拟下降步骤做了一定的改进 ,使得整个算法具有全局收敛性 .本文采用马尔可夫的观点进一步证明了算法的全局收敛性 ,并用极难优化的测试函数给出了数值算例 ,证明了本文算法为一种可行的全局优化算法 .     

New variable-metric algorithms for nondifferentiable optimization problems

This paper deals with new variable-metric algorithms for nonsmooth optimization problems, the so-called adaptive algorithms. The essence of these algorithms is that there are two simultaneously working gradient algorithms: the first is in the main space and the second is in the space of the matrices that modify the main variables. The convergence of these algorithms is proved for different cases. The results of numerical experiments are also given.     

整数规划中割平面法的研究

割平面法是求解整数规划问题常用方法之一.用割平面法求解整数规划的基本思路是:先用单纯形表格方法去求解不考虑整数约束条件的松弛问题的最优解,如果获得的最优解的值都是整数,即为所求,运算停止.如果所得最优解不完全是整数,即松弛问题最优解中存在某个基变量为非整数值时,就从最优表中提取出关于这个基变量的约束等式,再从这个约束式出发构造一个割平面方程加入最优表中,再求出新的最优解,这样不断重复的构造割平面方程,直到找到整数解为止.主要研究以下四个关键点:一是研究从最优表中提取出的、关于基变量的约束等式出发,通过将式中的系数进行整数和非负真分数的分解,从而得到一个小于等于0的另外一个不等式的推导过程;二是总结出从小于等于0的那个约束不等式出发构造割平面方程的四种方法;三是分析构造割平面方程的这四种方法相互之间的区别和联系;四是探讨割平面法的几何意义.通过对这四个方面的分析和研究,对割平面法进行透彻的剖析,使读者能够全面把握割平面法.     

一种约束非光滑优化问题的信赖域算法

提出了一种易实施的求解带线性约束的非光滑优化问题的信赖域算法，并在一定的条件下证明了该算法所产生的迭代序列的任何聚点都是原问题的稳定点．有限的数值例子表明，该方法是行之有效的．     

An active set method for solving linearly constrained nonsmooth optimization problems

An algorithm for solving linearly constrained optimization problems is proposed. The search direction is computed by a bundle principle and the constraints are treated through an active set strategy. Difficulties that arise when the objective function is nonsmooth, require a clever choice of a constraint to relax. A certain nondegeneracy assumption is necessary to obtain convergence. Most of this research was performed when the author was with I.N.R.I.A. (Domaine de Voluceau-Rocquencourt, B.P. 105, 78153 Le Chesnay Cédex, France). This research was supported in part by the National Science Foundation, Grants No. DMC-84-51515 and OIR-85-00108.     

A New Nonmonotone Linesearch SQP Algorithm for Unconstrained Minimax Problem

In this article, unconstrained minimax problems are discussed, and a sequential quadratic programming (SQP) algorithm with a new nonmonotone linesearch is presented. At each iteration, a search direction of descent is obtained by solving a quadratic programming (QP). To circumvent the Maratos effect, a high-order correction direction is achieved by solving another QP and a new nonmonotone linesearch is performed. Under reasonable conditions, the global convergence and the rate of superlinear convergence are established. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.