A polynomial-time algorithm for a class of linear complementarity problems

From MaRDI portal

Revision as of 03:02, 31 January 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Publication:1123139

Jump to:navigation, search

DOI10.1007/BF01587074zbMath0676.90087OpenAlexW2030674458MaRDI QIDQ1123139

Shinji Mizuno, Akiko Yoshise, Kojima, Masakazu

Publication date: 1989

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

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

zbMATH Keywords

polynomial-time algorithm Karmarkar's algorithm path of centers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items (only showing first 100 items - show all)

New variants of the criss-cross method for linearly constrained convex quadratic programming ⋮ A globally convergent primal-dual interior point algorithm for convex programming ⋮ An \(O(\sqrt{n}L)\) iteration Mehrotra-type predictor-corrector algorithm for monotone linear complementarity problem ⋮ Global convergence in infeasible-interior-point algorithms ⋮ Interior-point algorithms for semi-infinite programming ⋮ Extensions of the potential reduction algorithm for linear programming ⋮ Primal-dual algorithms for linear programming based on the logarithmic barrier method ⋮ Limiting behavior of weighted central paths in linear programming ⋮ Interior-point algorithms for monotone affine variational inequalities ⋮ A new method for a class of linear variational inequalities ⋮ Polynomiality of infeasible-interior-point algorithms for linear programming ⋮ Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence ⋮ Asymptotic convergence in a generalized predictor-corrector method ⋮ A primal-dual interior point method whose running time depends only on the constraint matrix ⋮ Status determination by interior-point methods for convex optimization problems in domain-driven form ⋮ Fast convergence of the simplified largest step path following algorithm ⋮ Improved complexity using higher-order correctors for primal-dual Dikin affine scaling ⋮ The curvature integral and the complexity of linear complementarity problems ⋮ A generalized homogeneous and self-dual algorithm for linear programming ⋮ On a quadratic programming problem involving distances in trees ⋮ A new large-update interior point algorithm for \(P_{*}(\kappa)\) LCPs based on kernel functions ⋮ An arc-search \({\mathcal {O}}(nL)\) infeasible-interior-point algorithm for linear programming ⋮ The largest step path following algorithm for monotone linear complementarity problems ⋮ A quadratically convergent \(\text{O}((\kappa +1)\sqrt n L)\)-iteration algorithm for the \(P_ *(\kappa)\)-matrix linear complementarity problem ⋮ A continuation method for monotone variational inequalities ⋮ Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems ⋮ 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 ⋮ A lower bound on the number of iterations of long-step primal-dual linear programming algorithms ⋮ A fully polynomial epsilon approximation cutting plane algorithm for solving combinatorial linear programs containing a sufficiently large ball ⋮ Interior-point methods for nonlinear complementarity problems ⋮ A new continuation method for complementarity problems with uniform P- functions ⋮ A predictor-corrector method for extended linear-quadratic programming ⋮ Interior path following primal-dual algorithms. II: Convex quadratic programming ⋮ A Mizuno-Todd-Ye type predictor-corrector algorithm for sufficient linear complementarity problems ⋮ Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs ⋮ A polynomial arc-search interior-point algorithm for linear programming ⋮ On solving a non-convex quadratic programming problem involving resistance distances in graphs ⋮ Smoothing methods for convex inequalities and linear complementarity problems ⋮ An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities ⋮ An infeasible interior-point algorithm for monotone linear complementarity problem based on a specific kernel function ⋮ Complexity analysis of a full-{N}ewton step interior-point method for linear optimization ⋮ On the complexity of computing the handicap of a sufficient matrix ⋮ A full-Newton step infeasible interior-point algorithm for monotone LCP based on a locally-kernel function ⋮ A class of linear complementarity problems solvable in polynomial time ⋮ On some efficient interior point methods for nonlinear convex programming ⋮ An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems ⋮ A FPTAS for computing a symmetric leontief competitive economy equilibrium ⋮ A unified approach to interior point algorithms for linear complementarity problems: A summary ⋮ An \(O(n^ 3L)\) adaptive path following algorithm for a linear complementarity problem ⋮ Enumeration of PLCP-orientations of the 4-cube ⋮ Unified complexity analysis for Newton LP methods ⋮ Complexity analysis of a linear complementarity algorithm based on a Lyapunov function ⋮ A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programming ⋮ Generalizations of the hidden Minkowski property ⋮ Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming ⋮ On affine scaling algorithms for nonconvex quadratic programming ⋮ On the convergence of the affine-scaling algorithm ⋮ An interior point potential reduction algorithm for the linear complementarity problem ⋮ Crashing a maximum-weight complementary basis ⋮ A polynomial method of approximate centers for linear programming ⋮ A little theorem of the big \({\mathcal M}\) in interior point algorithms ⋮ Exterior point algorithms for nearest points and convex quadratic programs ⋮ On the finite convergence of interior-point algorithms for linear programming ⋮ A long-step barrier method for convex quadratic programming ⋮ Convergence behavior of interior-point algorithms ⋮ On partial updating in a potential reduction linear programming algorithm of Kojima, Mizuno, and Yoshise ⋮ A new polynomial time method for a linear complementarity problem ⋮ On combined phase 1-phase 2 projective methods for linear programming ⋮ A polynomial path-following interior point algorithm for general linear complementarity problems ⋮ A continuation algorithm for a class of linear complementarity problems using an extrapolation technique ⋮ Near boundary behavior of primal-dual potential reduction algorithms for linear programming ⋮ On the convergence of primal-dual interior-point methods with wide neighborhoods ⋮ The linear complementarity problem, sufficient matrices, and the criss- cross method ⋮ Two interior-point methods for nonlinear \(P_*(\tau)\)-complementarity problems. ⋮ On well definedness of the central path ⋮ Containing and shrinking ellipsoids in the path-following algorithm ⋮ A class of smoothing functions for nonlinear and mixed complementarity problems ⋮ Computational complexity of norm-maximization ⋮ A sublinear parallel algorithm for stable matching ⋮ An interior point method, based on rank-1 updates, for linear programming ⋮ A modified layered-step interior-point algorithm for linear programming ⋮ Symmetric primal-dual path-following algorithms for semidefinite programming ⋮ Strict feasibility conditions in nonlinear complementarity problems ⋮ Degeneracy in interior point methods for linear programming: A survey ⋮ The relation between the path of centers and Smale's regularization of the linear programming problem ⋮ Interior-point algorithms for global optimization ⋮ O(n\({}^ pL)\)-iteration and \(O(n^ 3L)\)-operation potential reduction algorithms for linear programming ⋮ A primal-dual infeasible-interior-point algorithm for linear programming ⋮ Algorithms for the solution of quadratic knapsack problems ⋮ An extension of the potential reduction algorithm for linear complementarity problems with some priority goals ⋮ Finding an interior point in the optimal face of linear programs ⋮ On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP ⋮ An \(O(n^ 3L)\) potential reduction algorithm for linear programming ⋮ An interior point parameterized central path following algorithm for linearly constrained convex programming ⋮ Global linear convergence of a path-following algorithm for some monotone variational inequality problems ⋮ On solution-containing ellipsoids in linear programming ⋮ A primal-dual affine-scaling potential-reduction algorithm for linear programming ⋮ A block principal pivoting algorithm for large-scale strictly monotone linear complementarity problems

Cites Work

This page was built for publication: A polynomial-time algorithm for a class of linear complementarity problems

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1123139&oldid=13171337"