Polynomial Interior Point Cutting Plane Methods

DOI10.1080/10556780310001607956zbMath1062.90067OpenAlexW2153543949MaRDI QIDQ4653547

John E. Mitchell

Publication date: 7 March 2005

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556780310001607956

zbMATH Keywords

convex optimizationanalytic centervolumetric centercutting plane methods

Mathematics Subject Classification ID

Convex programming (90C25) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Stochastic programming (90C15) Interior-point methods (90C51)

Related Items

Rebalancing an investment portfolio in the presence of convex transaction costs, including market impact costs, Analytic centre stabilization of column generation algorithm for the capacitated vehicle routing problem, A matrix generation approach for eigenvalue optimization, A feasible directions method for nonsmooth convex optimization, Constrained integer fractional programming problem with box constraints, A probabilistic analytic center cutting plane method for feasibility of uncertain LMIs, Using selective orthonormalization to update the analytic center after addition of multiple cuts, Unnamed Item, Research on probabilistic methods for control system design, Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts, A unifying framework for several cutting plane methods for semidefinite programming

Uses Software

• ACCPM

Cites Work

• Unnamed Item
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Solving combinatorial optimization problems using Karmarkar's algorithm
• A build-up variant of the logarithmic barrier method for LP
• Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems
• Complexity analysis of logarithmic barrier decomposition methods for semi-infinite linear programming
• The volumetric barrier for convex quadratic constraints
• A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
• Multiple Cuts in the Analytic Center Cutting Plane Method
• The Volumetric Barrier for Semidefinite Programming
• An outer approximation based branch and cut algorithm for convex 0-1 MINLP problems
• Logarithmic Barrier Decomposition Methods for Semi-infinite Programming
• On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms
• On Finding Primal- and Dual-Optimal Bases
• A Nonlinear Analytic Center Cutting Plane Method for a Class of Convex Programming Problems
• Towards a Practical Volumetric Cutting Plane Method for Convex Programming
• On Vaidya's Volumetric Cutting Plane Method for Convex Programming
• Computational Experience with an Interior Point Cutting Plane Algorithm
• Complexity Analysis of an Interior Cutting Plane Method for Convex Feasibility Problems
• A long-step, cutting plane algorithm for linear and convex programming