Complexity analysis of the analytic center cutting plane method that uses multiple cuts

We analyze the complexity of the analytic center cutting plane or column generation algorithm for solving general convex problems defined by a separation oracle. The oracle is called at the analytic center of a polytope, which contains a solution set and is given by the intersection of the linear inequalities previously generated from the oracle. If the center is not in the solution set, separating hyperplanes will be placed through the center to shrink the containing polytope. While the complexity result has been recently established for the algorithm when one cutting plane is placed in each iteration, the result remains open when multiple cuts are added. Moreover, adding multiple cuts actually is a key to practical effectiveness in solving many problems and it presents theoretical difficulties in analyzing cutting plane methods. In this paper, we show that the analytic center cutting plane algorithm, with multiple cuts added in each iteration, still is a fully polynomial approximation algorithm. The research of the author is supported by NSF grant DDM-9207347, an Iowa Business School Summer Grant, and a University of Iowa Obermann Fellowship.     

An analytic center quadratic cut method for the convex quadratic feasibility problem

 We consider a quadratic cut method based on analytic centers for two cases of convex quadratic feasibility problems. In the first case, the convex set is defined by a finite yet large number, N, of convex quadratic inequalities. We extend quadratic cut algorithm of Luo and Sun [3] for solving such problems by placing or translating the quadratic cuts directly through the current approximate center. We show that, in terms of total number of addition and translation of cuts, our algorithm has the same polynomial worst case complexity as theirs [3]. However, the total number of steps, where steps consist of (damped) Newton steps, function evaluations and arithmetic operations, required to update from one approximate center to another is , where ε is the radius of the largest ball contained in the feasible set. In the second case, the convex set is defined by an infinite number of certain strongly convex quadratic inequalities. We adapt the same quadratic cut method for the first case to the second one. We show that in this case the quadratic cut algorithm is a fully polynomial approximation scheme. Furthermore, we show that, at each iteration, k, the total number steps (as described above) required to update from one approximate center to another is at most , with ε as defined above. Received: April 2000 / Accepted: June 2002 Published online: September 5, 2002 Key words. convex quadratic feasibility problem – interior-point methods – analytic center – quadratic cuts – potential function     

On Improvements to the Analytic Center Cutting Plane Method

In this paper, we explore a weakness of a specific implementation of the analytic center cutting plane method applied to convex optimization problems, which may lead to weaker results than Kelley's cutting plane method. Improvements to the analytic center cutting plane method are suggested, and tested on some example problems.     

Starlike approximations of analytic functions

When an analytic function is not univalent, it is often of interest to approximate it by univalent functions. In this paper we introduce a measure of the non-univalency of a function and we derive a method for constructing the best starlike univalent approximations of analytic functions with respect to it, suitable for both practical problems and numerical implementation.     

A second-order cone cutting surface method: complexity and application

We present an analytic center cutting surface algorithm that uses mixed linear and multiple second-order cone cuts. Theoretical issues and applications of this technique are discussed. From the theoretical viewpoint, we derive two complexity results. We show that an approximate analytic center can be recovered after simultaneously adding p second-order cone cuts in O(plog (p+1)) Newton steps, and that the overall algorithm is polynomial. From the application viewpoint, we implement our algorithm on mixed linear-quadratic-semidefinite programming problems with bounded feasible region and report some computational results on randomly generated fully dense problems. We compare our CPU time with that of SDPLR, SDPT3, and SeDuMi and show that our algorithm outperforms these software packages on problems with fully dense coefficient matrices. We also show the performance of our algorithm on semidefinite relaxations of the maxcut and Lovasz theta problems. M.R. Oskoorouchi’s work has been completed with the support of the partial research grant from the College of Business Administration, California State University San Marcos, and the University Professional Development Grant. J.E. Mitchell’s material is based upon work supported by the National Science Foundation under Grant No. 0317323. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.     

A numerical algorithm for the solution of Signorini problems

In this paper we propose a new iterative algorithm for the solution of a certain class of Signorini problems. Such problems arise in the modelling of a variety of physical phenomena and usually involve the determination of an unknown free boundary. Here we describe a way of locating the free boundary directly and provide a proof that the algorithm converges when used with analytic methods. The advantage of this algorithm is that it can be used in conjunction with any numerical method with minimal development of extra code. We demonstrate its application with the boundary element method to some physical problems in both two and three dimensions.     

A Center Cutting Plane Algorithm for a Likelihood Estimate Problem

We describe a method for solving the maximum likelihood estimate problem of a mixing distribution, based on an interior cutting plane algorithm with cuts through analytic centers. From increasingly refined discretized statistical problem models we construct a sequence of inner non-linear problems and solve them approximately applying a primal-dual algorithm to the dual formulation. Refining the statistical problem is equivalent to adding cuts to the inner problems.     

(Robust) Edge-based semidefinite programming relaxation of sensor network localization

Recently Wang, Zheng, Boyd, and Ye (SIAM J Optim 19:655–673, 2008) proposed a further relaxation of the semidefinite programming (SDP) relaxation of the sensor network localization problem, named edge-based SDP (ESDP). In simulation, the ESDP is solved much faster by interior-point method than SDP relaxation, and the solutions found are comparable or better in approximation accuracy. We study some key properties of the ESDP relaxation, showing that, when distances are exact, zero individual trace is not only sufficient, but also necessary for a sensor to be correctly positioned by an interior solution. We also show via an example that, when distances are inexact, zero individual trace is insufficient for a sensor to be accurately positioned by an interior solution. We then propose a noise-aware robust version of ESDP relaxation for which small individual trace is necessary and sufficient for a sensor to be accurately positioned by a certain analytic center solution, assuming the noise level is sufficiently small. For this analytic center solution, the position error for each sensor is shown to be in the order of the square root of its trace. Lastly, we propose a log-barrier penalty coordinate gradient descent method to find such an analytic center solution. In simulation, this method is much faster than interior-point method for solving ESDP, and the solutions found are comparable in approximation accuracy. Moreover, the method can distribute its computation over the sensors via local communication, making it practical for positioning and tracking in real time.     

A note on some analytic center cutting plane methods for convex feasibility and minimization problems

Recently Goffin, Luo and Ye have analyzed the complexity of an analytic center algorithm for convex feasibility problems defined by a separation oracle. The oracle is called at the (possibly approximate) analytic center of the set given by the linear inequalities which are the previous answers of the oracle. We discuss oracles for the problem of minimizing a convex (possibly nondifferentiable) function subject to box constraints, and give corresponding complexity estimates.The research of the first author is supported by the Polish Academy of Sciences; the research of the second author is supported by the State Committee for Scientific Research under Grant 8S50502206.     

A new approach to center conditions for simple analytic monodromic singularities

In this paper we present an alternative algorithm for computing Poincaré-Lyapunov constants of simple monodromic singularities of planar analytic vector fields based on the concept of inverse integrating factor. Simple monodromic singular points are those for which after performing the first (generalized) polar blow-up, there appear no singular points. In other words, the associated Poincaré return map is analytic. An improvement of the method determines a priori the minimum number of Poincaré-Lyapunov constants which must cancel to ensure that the monodromic singularity is in fact a center when the explicit Laurent series of an inverse integrating factor is known in (generalized) polar coordinates. Several examples show the usefulness of the method.     

精确解析法的子结构算法

文[1]提出精确解析法,用以求解任意变系数常微分方程,并利用初参数算法给出一个解的解析表达式.但利用初参数算法,对某一类问题,如长柱壳弯曲和振动等,它们的解将难以在计算机上得到.本文通过非均匀轴对称长圆柱壳弯曲问题,给出精确解析法的子结构算法,它能够计算初参数算法在计算机上不能解决的问题.问题最后和初参数算法一样能归结为求解一个低阶代数方程组.文末给出算例,表明本文算法的正确性,并和初参数算法作了比较.     

A Polynomial Cutting Surfaces Algorithm for the Convex Feasibility Problem Defined by Self-Concordant Inequalities

Consider a nonempty convex set in ^m which is defined by a finite number of smooth convex inequalities and which admits a self-concordant logarithmic barrier. We study the analytic center based column generation algorithm for the problem of finding a feasible point in this set. At each iteration the algorithm computes an approximate analytic center of the set defined by the inequalities generated in the previous iterations. If this approximate analytic center is a solution, then the algorithm terminates; otherwise either an existing inequality is shifted or a new inequality is added into the system. As the number of iterations increases, the set defined by the generated inequalities shrinks and the algorithm eventually finds a solution of the problem. The algorithm can be thought of as an extension of the classical cutting plane method. The difference is that we use analytic centers and convex cuts instead of arbitrary infeasible points and linear cuts. In contrast to the cutting plane method, the algorithm has a polynomial worst case complexity of O(Nlog 1/) on the total number of cuts to be used, where N is the number of convex inequalities in the original problem and is the maximum common slack of the original inequality system.     

Stochastic design optimization of asynchronous flexible assembly systems

This paper presents the application of the stochastic quasigradient method (SQG) of Ermoliev and Gaivaronski to the performance optimization of asynchronous flexible assembly systems (AFAS). These systems are subject to blocking and starvation effects that make complete analytic performance modeling difficult. A hybrid algorithm is presented in this paper which uses a queueing network model to set the number of pallets in the system and then an SQG algorithm is used to set the buffer spacings to obtain optimal system throughput. Different forms of the SQG algorithm are examined and the specification of optimal buffer sizes and pallet numbers for a variety of assembly systems with ten stations are discussed. The combined Network-SQG method appears to perform well in obtaining a near optimal solution in this discrete optimization example, even though the SQG method was primarily designed for application to differentiable performance functionals. While a number of both theoretical and practical problems remain to be resolved, a heuristic version of the SQG method appears to be a reasonable technique for analyzing optimization problems for certain complex manufacturing systems.     

A matrix generation approach for eigenvalue optimization

We study the extension of a column generation technique to nonpolyhedral models. In particular, we study the problem of minimizing the maximum eigenvalue of an affine combination of symmetric matrices. At each step of the algorithm a restricted master problem in the primal space, corresponding to the relaxed dual (original) problem, is formed. A query point is obtained as an approximate analytic center of a bounded set that contains the optimal solution of the dual problem. The original objective function is evaluated at the query point, and depending on its differentiability a column or a matrix is added to the restricted master problem. We discuss the issues of recovering feasibility after the restricted master problem is updated by a column or a matrix. The computational experience of implementing the algorithm on randomly generated problems are reported and the cpu time of the matrix generation algorithm is compared with that of the primal-dual interior point methods on dense and sparse problems using the software SDPT3. Our numerical results illustrate that the matrix generation algorithm outperforms primal-dual interior point methods on dense problems with no structure and also on a class of sparse problems. This work has been completed with the partial support of a summer grant from the College of Business Administration, California State University San Marcos, and the University Professional Development/Research and Creative Activity Grant     

An interior-point Benders based branch-and-cut algorithm for mixed integer programs

We present an interior-point branch-and-cut algorithm for structured integer programs based on Benders decomposition and the analytic center cutting plane method (ACCPM). We show that the ACCPM based Benders cuts are both pareto-optimal and valid for any node of the branch-and-bound tree. The valid cuts are added to a pool of cuts that is used to warm-start the solution of the nodes after branching. The algorithm is tested on two classes of problems: the capacitated facility location problem and the multicommodity capacitated fixed charge network design problem. For the capacitated facility location problem, the proposed approach was on average 2.5 times faster than Benders-branch-and-cut and 11 times faster than classical Benders decomposition. For the multicommodity capacitated fixed charge network design problem, the proposed approach was 4 times faster than Benders-branch-and-cut while classical Benders decomposition failed to solve the majority of the tested instances.     

An innovative flower pollination algorithm for continuous optimization problem

The flower pollination algorithm (FPA) is a relatively new swarm optimization algorithm that inspired by the pollination phenomenon of natural phanerogam. Since its proposed, it has received widespread attention and been applied in various engineering fields. However, the FPA still has certain drawbacks, such as inadequate optimization precision and poor convergence. In this paper, an innovative flower pollination algorithm based on cloud mutation is proposed (CMFPA), which adds information of all dimensions in the global optimization stage and uses the designed cloud mutation method to redistribute the population center. To verify the performance of the CMFPA in solving continuous optimization problems, we test twenty-four well-known functions, composition functions of CEC2013 and all benchmark functions of CEC2017. The results demonstrate that the CMFPA has better performance compared with other state-of-the-art algorithms. In addition, the CMFPA is implemented for five constrained optimization problems in practical engineering, and the performance is compared with state-of-the-art algorithms to further prove the effectiveness and efficiency of the CMFPA.     

ACCPM with a nonlinear constraint and an active set strategy to solve nonlinear multicommodity flow problems

This paper proposes an implementation of a constrained analytic center cutting plane method to solve nonlinear multicommodity flow problems. The new approach exploits the property that the objective of the Lagrangian dual problem has a smooth component with second order derivatives readily available in closed form. The cutting planes issued from the nonsmooth component and the epigraph set of the smooth component form a localization set that is endowed with a self-concordant augmented barrier. Our implementation uses an approximate analytic center associated with that barrier to query the oracle of the nonsmooth component. The paper also proposes an approximation scheme for the original objective. An active set strategy can be applied to the transformed problem: it reduces the dimension of the dual space and accelerates computations. The new approach solves huge instances with high accuracy. The method is compared to alternative approaches proposed in the literature. An erratum to this article can be found at     

Approximating the zeros of analytic functions by the exclusion algorithm

We give a practical version of the exclusion algorithm for localizing the zeros of an analytic function and in particular of a polynomial in a compact of . We extend the real exclusion algorithm to a Jordan curve and give a method which excludes discs without any zero. The result of this algorithm is a set of discs arbitrarily small which contains the zeros of the analytic function.     

Quadratic convergence of the Iri-Imai algorithm for degenerate linear programming problems

A local analysis of the Iri-Imai algorithm for linear programming is given to demonstrate quadratic convergence under degeneracy. Specifically, we show that the algorithm with an exact line search either terminates after a finite number of iterations yielding a point on the set of optimal solutions or converges quadratically to one of the relative analytic centers of the faces of the set of optimal solutions including vertices. Mostly, the sequence generated falls into one of the optimal vertices, and it is rare that the sequence converges to the relative analytic center of a face whose dimension is greater than or equal to one.This paper is based on Ref. 1.The author thanks Professor Kunio Tanabe of the Institute of Statistical Mathematics for valuable comments as well as stimulating discussions.     

On the center-focus problem for systems with a degenerate singular point

For an analytic system with nonzero cubic part and with a degenerate monodromic singular point, we indicate an algorithm for constructing the asymptotic expansion of the Poincaré map. We present closed-form expressions for the first four focus quantities and find two necessary conditions for a center.