Complexity Analysis of an Interior Cutting Plane Method for Convex Feasibility Problems

DOI10.1137/S1052623493258635zbMath0856.90088OpenAlexW1966986674MaRDI QIDQ4895614

Yinyu Ye, Zhi-Quan Luo, Jean-Louis Goffin

Publication date: 14 October 1996

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s1052623493258635

zbMATH Keywords

complexity convergence cutting planes separation oracle convex feasibility problems potential reduction dual column generation algorithm fully polynomial approximation algorithm

Mathematics Subject Classification ID

Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Nonconvex programming, global optimization (90C26)

Related Items

Large-scale optimization with the primal-dual column generation method, Analytic center cutting plane methods for variational inequalities over convex bodies, 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 variational inequalities defined on a domain with infinitely many linear constraints, An analytic center cutting plane method for pseudomonotone variational inequalities, An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix, A cone constrained convex program: structure and algorithms, Distributionally robust portfolio optimization with second-order stochastic dominance based on Wasserstein metric, Learning lyapunov functions for hybrid systems, A proximal analytic center cutting plane algorithm for solving variational inequality problems, A cutting plane method for solving KYP-SDPs, A path-following cutting plane method for some monotone variational inequalities^∗, Large-scale convex optimization methods for air quality policy assessment., Specialized fast algorithms for IQC feasibility and optimization problems., Solving variational inequalities with a quadratic cut method: a primal-dual, Jacobian-free approach, Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017, A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem, Polynomial Interior Point Cutting Plane Methods, Comparison of bundle and classical column generation, A probabilistic analytic center cutting plane method for feasibility of uncertain LMIs, A relaxation method for solving systems with infinitely many linear inequalities, Selective Gram-Schmidt orthonormalization for conic cutting surface algorithms, Interior point method on semi-definite linear complementarity problems using the Nesterov-Todd (NT) search direction: polynomial complexity and local convergence, Self-concordant barriers for convex approximations of structured convex sets, Using selective orthonormalization to update the analytic center after addition of multiple cuts, A generalized projection-based scheme for solving convex constrained optimization problems, An oracle for the discrete-time integral quadratic constraint problem, Rate of convergence of a class of numerical methods solving linear inequality systems, 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, An analytic center cutting plane algorithm for finding equilibrium points, Interior-point methods with decomposition for solving large-scale linear programs, Homogeneous analytic center cutting plane methods with approximate centers, Entropic perturbation method for solving a system of linear inequalities