A little theorem of the big \({\mathcal M}\) in interior point algorithms

DOI10.1007/BF01581253zbMath0793.90083OpenAlexW2113273909MaRDI QIDQ687037

Akiko Yoshise, Shinji Mizuno, Kojima, Masakazu

Publication date: 16 August 1994

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

Full work available at URL: https://doi.org/10.1007/bf01581253

zbMATH Keywords

interior point algorithmsartificial self-dual linear programbig \(\mathcal M\)polynomial-time potential reduction algorithmpositive semi-definite linear complementarity

Mathematics Subject Classification ID

Convex programming (90C25) Linear programming (90C05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items (8)

Global convergence in infeasible-interior-point algorithms ⋮ Status determination by interior-point methods for convex optimization problems in domain-driven form ⋮ A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems ⋮ Basic lemmas in polynomial-time infeasible-interior-point methods for linear programs ⋮ An infeasible-interior-point algorithm using projections onto a convex set ⋮ An interior point method for general large-scale quadratic programming problems ⋮ A primal-dual infeasible-interior-point algorithm for linear programming ⋮ On the big \({\mathcal M}\) in the affine scaling algorithm

Cites Work

• Unnamed Item
• Feasibility issues in a primal-dual interior-point method for linear programming
• Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
• Computational experience with a primal-dual interior point method for linear programming
• A polynomial Newton method for linear programming
• A combined phase I-phase II projective algorithm for linear programming
• Interior path following primal-dual algorithms. I: Linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
• A unified approach to interior point algorithms for linear complementarity problems: A summary
• An interior point potential reduction algorithm for the linear complementarity problem
• A new polynomial time method for a linear complementarity problem
• Symmetric indefinite systems for interior point methods
• Theoretical convergence of large-step primal-dual interior point algorithms for linear programming
• Combining phase I and phase II in a potential reduction algorithm for linear programming
• The nonlinear complementarity problem, with applications. I
• Simple bounds for solutions of monotone complementarity problems and convex programs
• An Implementation of a Primal-Dual Interior Point Method for Linear Programming
• Classes of functions and feasibility conditions in nonlinear complementarity problems
• A monotone complementarity problem with feasible solutions but no complementary solutions
• A General Framework of Continuation Methods for Complementarity Problems

This page was built for publication: A little theorem of the big \({\mathcal M}\) in interior point algorithms