On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
From MaRDI portal
Publication:4286944
DOI10.1287/moor.18.4.964zbMath0810.90091MaRDI QIDQ4286944
Michael J. Todd, Yinyu Ye, Shinji Mizuno
Publication date: 12 April 1994
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/8829
65K05: Numerical mathematical programming methods
90C60: Abstract computational complexity for mathematical programming problems
90C05: Linear programming
90C51: Interior-point methods
Related Items
Implementation of interior point methods for mixed semidefinite and second order cone optimization problems, Perturbed path following predictor-corrector interior point algorithms, Sdpha: a Matlab implementation of homogeneous interior-point algorithms for semidefinite programming, Predictor–corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central path, ON THE PROPERTIES OF ∊-SENSITIVITY ANALYSIS FOR LINEAR PROGRAMMING, On the finite convergence of interior-point algorithms for linear programming, Convergence behavior of interior-point algorithms, Semidefinite programming for discrete optimization and matrix completion problems, A Mizuno-Todd-Ye type predictor-corrector algorithm for sufficient linear complementarity problems, Postponing the choice of the barrier parameter in Mehrotra-type predictor-corrector algorithms, A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms, Adaptive large-neighborhood self-regular predictor-corrector interior-point methods for linear optimization, Enlarging neighborhoods of interior-point algorithms for linear programming via least values of proximity measure functions, Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions, Superlinearly convergent infeasible-interior-point algorithm for degenerate LCP, On the long-step path-following method for semidefinite programming, Superlinear convergence of interior-point algorithms for semidefinite programming, Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming, A modified layered-step interior-point algorithm for linear programming, Primal-dual potential reduction methods for semidefinite programming using affine-scaling directions, Symmetric primal-dual path-following algorithms for semidefinite programming, Interior-point methods with decomposition for solving large-scale linear programs, Degeneracy in interior point methods for linear programming: A survey, A primal-dual infeasible-interior-point algorithm for linear programming, An extension of the potential reduction algorithm for linear complementarity problems with some priority goals, A modified predictor-corrector method for linear programming, 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, Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited, Primal-dual interior point approach for computing \(l_ 1\)-solutions and \(l_ \infty\)-solutions of overdetermined linear systems, Modified predictor-corrector algorithm for locating weighted centers in linear programming, A primal-dual affine-scaling potential-reduction algorithm for linear programming, Local convergence of interior-point algorithms for degenerate monotone LCP, A globally convergent primal-dual interior point algorithm for convex programming, Global convergence in infeasible-interior-point algorithms, Interior-point algorithms for semi-infinite programming, Limiting behavior of weighted central paths in linear programming, Constant potential primal-dual algorithms: A framework, Polynomiality of infeasible-interior-point algorithms for linear programming, A predictor-corrector infeasible-interior-point algorithm for linear programming, Asymptotic convergence in a generalized predictor-corrector method, A primal-dual interior point method whose running time depends only on the constraint matrix, Long-step strategies in interior-point primal-dual methods, Fast convergence of the simplified largest step path following algorithm, Improved complexity using higher-order correctors for primal-dual Dikin affine scaling, The largest step path following algorithm for monotone linear complementarity problems, Superlinear and quadratic convergence of some primal - dual interior point methods for constrained optimization, An extension of predictor-corrector algorithm to a class of convex separable program, Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs, Predictor-corrector method for nonlinear complementarity problems, The Gaussian hare and the Laplacian tortoise: computability of squared-error versus absolute-error estimators. With comments by Ronald A. Thisted and M. R. Osborne and a rejoinder by the authors, An \(\varepsilon\)-sensitivity analysis in the primal-dual interior point method, On self-regular IPMs (with comments and rejoinder), On the convergence of primal-dual interior-point methods with wide neighborhoods, A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points, Two interior-point methods for nonlinear \(P_*(\tau)\)-complementarity problems., The Mizuno-Todd-Ye algorithm in a larger neighborhood of the central path, Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure., On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms, Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence, The curvature integral and the complexity of linear complementarity problems, A quadratically convergent \(\text{O}((\kappa +1)\sqrt n L)\)-iteration algorithm for the \(P_ *(\kappa)\)-matrix linear complementarity problem, A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems, An \(O(nL)\) infeasible-interior-point algorithm for LCP with quadratic convergence, A Mehrotra-type predictor-corrector algorithm with polynomiality and \(Q\)-subquadratic convergence, A simplified homogeneous and self-dual linear programming algorithm and its implementation, Primal-dual target-following algorithms for linear programming, A lower bound on the number of iterations of long-step primal-dual linear programming algorithms, A superquadratic infeasible-interior-point method for linear complementarity problems, An \(O(\sqrt {n} L)\) iteration bound primal-dual cone affine scaling algorithm for linear programming, Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems, A predictor-corrector method for extended linear-quadratic programming, Theoretical convergence of large-step primal-dual interior point algorithms for linear programming, A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming, A path to the Arrow-Debreu competitive market equilibrium, Corrector-predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path, On the probabilistic complexity of finding an approximate solution for linear programming, Improved complexity results on solving real-number linear feasibility problems, A quadratically convergent polynomial long-step algorithm for A class of nonlinear monotone complementarity problems*, An Infeasible Mizuno–Todd–Ye Type Algorithm for Convex Quadratic Programming with Polynomial Complexity, Complexity of the primal–dual path-following algorithms for the weighted determinant maximization problems with linear matrix inequalities in the narrow neighbourhood, Mehrotra-type predictor-corrector algorithm revisited, Solving large-scale linear programs by interior-point methods under the Matlab∗Environment†, Search directions and convergence analysis of some infeasibnle path-following methods for the monoton semi-definite lcp∗, Iteration complexity of an interior-point algorithm for nonlinear p∗-complementarity problems
