A cutting plane algorithm for convex programming that uses analytic centers

DOI10.1007/BF01585551zbMath0855.90094MaRDI QIDQ1922689

Pravin M. Vaidya, David S. Atkinson

Publication date: 3 February 1997

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

cutting planesoracleanalytic center of a polytope

Mathematics Subject Classification ID

Convex programming (90C25)

Related Items (32)

A second-order cone cutting surface method: Complexity and application ⋮ Complexity of some cutting plane methods that use analytic centers ⋮ Utility function programs and optimization over the efficient set in multiple-objective decision making ⋮ Solving nonlinear multicommodity flow problems by the analytic center cutting plane method ⋮ A variable metric method for nonsmooth convex constrained optimization ⋮ A simple method for convex optimization in the oracle model ⋮ Solving real-world linear ordering problems using a primal-dual interior point cutting plane method ⋮ An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix ⋮ Optimization under uncertainty with applications to design of truss structures ⋮ A cutting plane method from analytic centers for stochastic programming ⋮ Complexity estimates of some cutting plane methods based on the analytic barrier ⋮ Convex analysis in groups and semigroups: a sampler ⋮ A \(J\)-symmetric quasi-Newton method for minimax problems ⋮ Learning lyapunov functions for hybrid systems ⋮ Unnamed Item ⋮ A cutting-plane method to nonsmooth multiobjective optimization problems ⋮ Specialized fast algorithms for IQC feasibility and optimization problems. ⋮ A utility theory based interactive approach to robustness in linear optimization ⋮ On complexity of the translational-cut algorithm for convex minimax problems ⋮ A probabilistic analytic center cutting plane method for feasibility of uncertain LMIs ⋮ On the volumetric path ⋮ Solving the discrete \(l_p\)-approximation problem by a method of centers ⋮ Self-concordant barriers for convex approximations of structured convex sets ⋮ Research on probabilistic methods for control system design ⋮ Predicting abnormal returns from news using text classification ⋮ A copositive framework for analysis of hybrid Ising-classical algorithms ⋮ An oracle for the discrete-time integral quadratic constraint problem ⋮ A filter-variable-metric method for nonsmooth convex constrained optimization ⋮ A note on some analytic center cutting plane methods for convex feasibility and minimization problems ⋮ Primal-dual-infeasible Newton approach for the analytic center deep-cutting plane method ⋮ Complexity analysis of logarithmic barrier decomposition methods for semi-infinite linear programming ⋮ Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition

Uses Software

• ACCPM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A scaling technique for finding the weighted analytic center of a polytope
• A new polynomial-time algorithm for linear programming
• A potential-reduction variant of Renegar's short-step path-following method for linear programming
• Matrix multiplication via arithmetic progressions
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Cutting planes and column generation techniques with the projective algorithm
• Interior-point methods for convex programming
• Geometric algorithms and combinatorial optimization
• On the complexity of approximating the maximal inscribed ellipsoid for a polytope
• Experimental behavior of an interior point cutting plane algorithm for convex programming: An application to geometric programming
• A logarithmic barrier cutting plane method for convex programming
• On the convergence of the method of analytic centers when applied to convex quadratic programs
• A Method for the Parametric Center Problem, with a Strictly Monotone Polynomial-Time Algorithm for Linear Programming
• A Potential Reduction Algorithm Allowing Column Generation

This page was built for publication: A cutting plane algorithm for convex programming that uses analytic centers