On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming

Shinji Mizuno
Shinji Mizuno
Department of Prediction and Control, The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, Tokyo 106, Japan
Search for more papers by this author
,
Michael J. Todd
Michael J. Todd
School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York 14853 USA
Search for more papers by this author
,
Yinyu Ye
Yinyu Ye
Department of Management Sciences, The University of Iowa, Iowa City, Iowa 52242 USA
Search for more papers by this author

Department of Prediction and Control, The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, Tokyo 106, Japan

Search for more papers by this author

Michael J. Todd

School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York 14853 USA

Search for more papers by this author

Yinyu Ye

Department of Management Sciences, The University of Iowa, Iowa City, Iowa 52242 USA

Search for more papers by this author

Published Online:1 Nov 1993https://doi.org/10.1287/moor.18.4.964

Abstract

We describe several adaptive-step primal-dual interior point algorithms for linear programming. All have polynomial time complexity while some allow very long steps in favorable circumstances. We provide heuristic reasoning for expecting that the algorithms will perform much better in practice than guaranteed by the worst-case estimates, based on an analysis using a nonrigorous probabilistic assumption.

Cited by
- EIQP: Execution-Time-Certified and Infeasibility-Detecting QP Solver
  IEEE Transactions on Automatic Control, Vol. 71, No. 5
- An inexact infeasible arc-search interior-point method for linear optimization problems
  20 April 2026 | Numerical Algorithms, Vol. 49
- New Interior-Point Algorithm for Linear Optimization Based on a Universal Tangent Direction
  19 February 2026 | SIAM Journal on Optimization, Vol. 36, No. 1
- Controlled stochastic processes for simulated annealing
  31 March 2026 | ESAIM: Control, Optimisation and Calculus of Variations, Vol. 32
- Interior Point Methods Are Not Worse than Simplex
  3 March 2025 | SIAM Journal on Computing, Vol. 54, No. 5
- Intelligent Roadside Reflection: Efficient Passive Beamforming for IRS Aided mmWave Vehicular Communication
  11 June 2025 | Transactions on Emerging Telecommunications Technologies, Vol. 36, No. 6
- Optimal Diagonal Preconditioning
  Zhaonan Qu; ,
  Wenzhi Gao; ,
  Oliver Hinder; ,
  Yinyu Ye; ,
  Zhengyuan Zhou
  4 March 2024 | Operations Research, Vol. 73, No. 3
- An efficient second-order predictor–corrector infeasible primal–dual IPM algorithm with large iteration path updates for solving well-known SDO problems
  Journal of Computational and Applied Mathematics, Vol. 459
- A new predictor-corrector interior-point algorithm for semidefinite optimization
  30 December 2025 | Demonstratio Mathematica, Vol. 58, No. 1
- A Time-Certified Predictor-Corrector IPM Algorithm for Box-QP
  IEEE Control Systems Letters, Vol. 9
- A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
  29 April 2023 | Mathematical Programming, Vol. 204, No. 1-2
- Doubly autoparallel structure and curvature integrals
  27 July 2023 | Information Geometry, Vol. 7, No. S1
- Strong Convergence of a Two-Step Modified Newton Method for Weighted Complementarity Problems
  28 July 2023 | Axioms, Vol. 12, No. 8
- A step-truncated method in a wide neighborhood interior-point algorithm for linear programming
  13 October 2022 | Optimization Letters, Vol. 17, No. 6
- A Warm-Start Strategy in Interior Point Methods for Shrinking Horizon Model Predictive Control With Variable Discretization Step
  IEEE Transactions on Automatic Control, Vol. 68, No. 6
- Corrector-Predictor Interior-Point Method With New Search Direction for Semidefinite Optimization
  15 February 2023 | Journal of Scientific Computing, Vol. 95, No. 1
- Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation
  EURO Journal on Computational Optimization, Vol. 11
- A new corrector–predictor interior-point method for symmetric cone optimization
  14 January 2022 | Periodica Mathematica Hungarica, Vol. 85, No. 2
- A Mehrotra Type Predictor-Corrector Interior-Point Method for P∗(κ)-HLCP
  21 September 2022 | Numerical Functional Analysis and Optimization, Vol. 43, No. 14
- An efficient arc-search interior-point algorithm for convex quadratic programming with box constraints
  19 March 2022 | Numerical Algorithms, Vol. 91, No. 2
- Interior point methods are not worse than Simplex
- A new wide-neighborhood predictor-corrector interior-point method for semidefinite optimization
  11 June 2021 | Journal of Applied Mathematics and Computing, Vol. 68, No. 2
- Predictor-corrector interior-point algorithm for P*(κ) -linear complementarity problems based on a new type of algebraic equivalent transformation technique
  European Journal of Operational Research, Vol. 298, No. 1
- An Interior Point Parameterized Central Path Following Algorithm for Linearly Constrained Convex Programming
  8 February 2022 | Journal of Scientific Computing, Vol. 90, No. 3
- Introduction
  19 October 2022
- An predictor–corrector interior-point algorithm for semidefinite optimization based on a wide neighbourhood
  11 April 2020 | International Journal of Computer Mathematics, Vol. 98, No. 2
- Interior-Point Methods
  20 August 2021
- What Tropical Geometry Tells Us about the Complexity of Linear Programming
  4 February 2021 | SIAM Review, Vol. 63, No. 1
- A Primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils
  Journal of Industrial & Management Optimization, Vol. 17, No. 5
- A quantum interior-point predictor–corrector algorithm for linear programming
  12 October 2020 | Journal of Physics A: Mathematical and Theoretical, Vol. 53, No. 44
- A wide neighborhood predictor-infeasible corrector interior-point algorithm for linear optimization
  4 April 2020 | Optimization Letters, Vol. 14, No. 8
- Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers
- A corrector–predictor interior-point method with new search direction for linear optimization
  15 May 2019 | Central European Journal of Operations Research, Vol. 28, No. 3
- A Full-Newton Step Interior-Point Method for Monotone Weighted Linear Complementarity Problems
  6 August 2020 | Journal of Optimization Theory and Applications, Vol. 186, No. 3
- Fast Quadratic Programming for Mean-Variance Portfolio Optimisation
  15 September 2020 | SN Operations Research Forum, Vol. 1, No. 3
- A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
  22 June 2020
- Primal–Dual Interior-Point Methods for Domain-Driven Formulations
  Mehdi Karimi,
  Levent Tunçel
  4 February 2020 | Mathematics of Operations Research, Vol. 45, No. 2
- The Homogeneous Self-Dual Method
  26 April 2020
- Feasible Corrector-Predictor Interior-Point Algorithm for $P_{*} (\kappa)$-Linear Complementarity Problems Based on a New Search Direction
  28 September 2020 | SIAM Journal on Optimization, Vol. 30, No. 3
- Fast Quadratic Programming for Mean-Variance Portfolio Optimization
  SSRN Electronic Journal, Vol. 10
- A New Search Direction for Full-Newton Step Interior-Point Method in P*(κ)-HLCP
  7 April 2019 | Numerical Functional Analysis and Optimization, Vol. 40, No. 10
- Large-Neighborhood Infeasible Predictor–Corrector Algorithm for Horizontal Linear Complementarity Problems over Cartesian Product of Symmetric Cones
  16 October 2018 | Journal of Optimization Theory and Applications, Vol. 180, No. 3
- The Iteration-Complexity Upper Bound for the Mizuno-Todd-Ye Predictor-Corrector Algorithm is Tight
  15 February 2019
- A Wide-Neighborhood Predictor-Corrector Interior-Point Algorithm for Linear Complementarity Problems
  15 November 2017 | Journal of the Operations Research Society of China, Vol. 6, No. 4
- An efficient computational method of a moment-independent importance measure using quantile regression
  Mechanical Systems and Signal Processing, Vol. 109
- A corrector-predictor arc search interior-point algorithm for symmetric optimization
  Acta Mathematica Scientia, Vol. 38, No. 4
- Polynomial convergence of two higher order interior-point methods for $$P_*(\kappa )$$ P ∗ ( κ ) -LCP in a wide neighborhood of the central path
  5 December 2017 | Periodica Mathematica Hungarica, Vol. 76, No. 2
- An arc-search $${\mathcal {O}}(nL)$$ O ( n L ) infeasible-interior-point algorithm for linear programming
  8 April 2017 | Optimization Letters, Vol. 12, No. 4
- Equilibria and Weighted Complementarity Problems
  1 June 2018
- Log-Barrier Interior Point Methods Are Not Strongly Polynomial
  SIAM Journal on Applied Algebra and Geometry, Vol. 2, No. 1
- Convergence and polynomiality of primal-dual interior-point algorithms for linear programming with selective addition of inequalities
  19 October 2016 | Optimization, Vol. 66, No. 12
- A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for symmetric optimization with the arc-search strategy
  21 November 2017 | Journal of Inequalities and Applications, Vol. 2017, No. 1
- A primal–dual predictor–corrector interior-point method for symmetric cone programming with O(√r log ϵ−1 ) iteration complexity
  31 January 2017 | International Journal of Computer Mathematics, Vol. 94, No. 10
- A superlinearly convergent wide-neighborhood predictor–corrector interior-point algorithm for linear programming
  21 September 2016 | Journal of Applied Mathematics and Computing, Vol. 55, No. 1-2
- Two wide neighborhood interior-point methods for symmetric cone optimization
  9 March 2017 | Computational Optimization and Applications, Vol. 68, No. 1
- An infeasible interior-point algorithm for monotone linear complementarity problem based on a specific kernel function
  31 May 2016 | Journal of Applied Mathematics and Computing, Vol. 54, No. 1-2
- CurveLP-A MATLAB implementation of an infeasible interior-point algorithm for linear programming
  26 July 2016 | Numerical Algorithms, Vol. 74, No. 4
- A Corrector-Predictor Interior-Point Algorithm for P∗ ( κ )-HLCPs Over Cartesian Product of Symmetric Cones
  13 September 2016 | Numerical Functional Analysis and Optimization, Vol. 38, No. 1
- A corrector–predictor path-following method for second-order cone optimization
  23 September 2015 | International Journal of Computer Mathematics, Vol. 93, No. 12
- A New Primal–Dual Predictor–Corrector Interior-Point Method for Linear Programming Based on a Wide Neighbourhood
  30 March 2016 | Journal of Optimization Theory and Applications, Vol. 170, No. 2
- A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones
  7 November 2015 | Numerical Algorithms, Vol. 72, No. 4
- A wide neighborhood infeasible-interior-point method with arc-search for linear programming
  10 June 2015 | Journal of Applied Mathematics and Computing, Vol. 51, No. 1-2
- An $$O(\sqrt{n}L)$$ O ( n L ) iteration Mehrotra-type predictor-corrector algorithm for monotone linear complementarity problem
  11 April 2015 | Optimization Letters, Vol. 10, No. 3
- A Predictor-Corrector Algorithm for P ∗(κ)-Linear Complementarity Problems Based on a Specific Self-Regular Proximity Function
  28 November 2014 | Acta Mathematica Vietnamica, Vol. 41, No. 1
- An infeasible interior-point algorithm with full-Newton steps for $$P_*(\kappa )$$ P ∗ ( κ ) horizontal linear complementarity problems based on a kernel function
  18 December 2014 | Journal of Applied Mathematics and Computing, Vol. 50, No. 1-2
- Basic Properties of Linear Programs
- Duality and Complementarity
- Interior-Point Methods
- A Predictor–Corrector Algorithm for Monotone Linear Complementarity Problems in a Wide Neighborhood
  14 January 2016 | International Journal of Bifurcation and Chaos, Vol. 25, No. 14
- An Adaptive Infeasible Interior-Point Algorithm with Full Nesterov-Todd Step for Semidefinite Optimization
  16 May 2014 | Journal of Mathematical Modelling and Algorithms in Operations Research, Vol. 14, No. 1
- A Class of Path-Following Interior-Point Methods for $$P_*(\kappa )$$ P ∗ ( κ ) -Horizontal Linear Complementarity Problems
  12 February 2015 | Journal of the Operations Research Society of China, Vol. 3, No. 1
- A Corrector–Predictor Path-Following Method for Convex Quadratic Symmetric Cone Optimization
  26 March 2014 | Journal of Optimization Theory and Applications, Vol. 164, No. 1
- Solving the logit-based stochastic user equilibrium problem with elastic demand based on the extended traffic network model
  European Journal of Operational Research, Vol. 239, No. 1
- A New Complexity Analysis for Full-Newton Step Infeasible Interior-Point Algorithm for Horizontal Linear Complementarity Problems
  7 November 2013 | Journal of Optimization Theory and Applications, Vol. 161, No. 3
- A predictor-corrector interior-point algorithm for P ∗ ( κ ) $P_{*}(\kappa )$ -horizontal linear complementarity problem
  11 July 2013 | Numerical Algorithms, Vol. 66, No. 2
- A corrector–predictor path-following algorithm for semidefinite optimization
  25 June 2014 | Asian-European Journal of Mathematics, Vol. 07, No. 02
- An Implementable Predictor-Corrector Method for Solving Semidefinite Programming Problems
  5 September 2014 | Journal of Interdisciplinary Mathematics, Vol. 17, No. 3
- Regression
- Network Flow Problems
- Applications
- Structural Optimization
- The Central Path
- A Path-Following Method
- The Homogeneous Self-Dual Method
- Degeneracy
- Implementation Issues
- Introduction
  10 October 2013
- Integer Linear Programming (ILP)
  10 October 2013
- Pivot Rule
  10 October 2013
- Dual Pivot Rule
  10 October 2013
- Simplex Phase-I Method
  10 October 2013
- Dual Simplex Phase-l Method
  10 October 2013
- Reduced Simplex Method
  10 October 2013
- Improved Reduced Simplex Method
  10 October 2013
- D-Reduced Simplex Method
  10 October 2013
- Criss-Cross Simplex Method
  10 October 2013
- Generalizing Reduced Simplex Method
  10 October 2013
- Geometry of the Feasible Region
  10 October 2013
- Deficient-Basis Method
  10 October 2013
- Dual Deficient-Basis Method
  10 October 2013
- Face Method
  10 October 2013
- Dual Face Method
  10 October 2013
- Pivotal Interior-Point Method
  10 October 2013
- Special Topics
  10 October 2013
- Simplex Method
  10 October 2013
- Duality Principle and Dual Simplex Method
  10 October 2013
- Implementation of the Simplex Method
  10 October 2013
- Sensitivity Analysis and Parametric LP
  10 October 2013
- Variants of the Simplex Method
  10 October 2013
- Decomposition Method
  10 October 2013
- Interior-Point Method
  10 October 2013
- A new O(nL) -iteration predictor–corrector algorithm with wide neighborhood for semidefinite programming
  Journal of Computational and Applied Mathematics, Vol. 256
- Interior Point Methods for Sufficient Horizontal LCP in a Wide Neighborhood of the Central Path with Best Known Iteration Complexity
  SIAM Journal on Optimization, Vol. 24, No. 1
- An Adaptive Infeasible Interior-Point Algorithm for Linear Complementarity Problems
  6 December 2013 | Journal of the Operations Research Society of China, Vol. 1, No. 4
- A Polynomial Arc-Search Interior-Point Algorithm for Linear Programming
  20 February 2013 | Journal of Optimization Theory and Applications, Vol. 158, No. 3
- Polynomial interior-point algorithm for P * ${(\kappa)}$ horizontal linear complementarity problems
  9 August 2012 | Numerical Algorithms, Vol. 63, No. 2
- Trajectory-following methods for large-scale degenerate convex quadratic programming
  16 February 2013 | Mathematical Programming Computation, Vol. 5, No. 2
- Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems
  19 August 2012 | Mathematical Programming Computation, Vol. 5, No. 1
- A Simple Variant of the Mizuno--Todd--Ye Predictor-Corrector Algorithm and Its Objective-Function-Free Complexity
  SIAM Journal on Optimization, Vol. 23, No. 3
- Mehrotra-type predictor–corrector algorithms for sufficient linear complementarity problem
  Applied Numerical Mathematics, Vol. 62, No. 12
- Computational experience with a modified potential reduction algorithm for linear programming
  Optimization Methods and Software, Vol. 27, No. 4-5
- A full-Newton step infeasible interior-point algorithm for monotone LCP based on a locally-kernel function
  12 January 2012 | Numerical Algorithms, Vol. 61, No. 1
- A Predictor-corrector algorithm with multiple corrections for convex quadratic programming
  23 July 2011 | Computational Optimization and Applications, Vol. 52, No. 2
- Weighted Complementarity Problems---A New Paradigm for Computing Equilibria
  SIAM Journal on Optimization, Vol. 22, No. 4
- A polynomial arc-search interior-point algorithm for convex quadratic programming
  European Journal of Operational Research, Vol. 215, No. 1
- Two new predictor-corrector algorithms for second-order cone programming
  6 April 2011 | Applied Mathematics and Mechanics, Vol. 32, No. 4
- Corrector-predictor methods for sufficient linear complementarity problems
  3 June 2009 | Computational Optimization and Applications, Vol. 48, No. 3
- Smoothed analysis of condition numbers and complexity implications for linear programming
  5 May 2009 | Mathematical Programming, Vol. 126, No. 2
- A full-Newton step infeasible-interior-point algorithm for linear complementarity problems
  Nonlinear Analysis: Real World Applications, Vol. 12, No. 1
- An Improved Predictor‐Corrector Interior‐Point Algorithm for Linear Complementarity Problems with O(nL)‐Iteration Complexity
  29 December 2011 | Journal of Applied Mathematics, Vol. 2011, No. 1
- A Class of Infeasible Interior Point Algorithms for Convex Quadratic Programming
  Numerical Functional Analysis and Optimization, Vol. 31, No. 11
- A wide-neighborhood interior-point method for P<inf>*</inf>(κ) complementarity problem
- On the complexity analysis of a Mehrotra-type primal–dual feasible algorithm for semidefinite optimization
  28 November 2008 | Optimization Methods and Software, Vol. 25, No. 3
- Interior-Point Methods for Linear Optimization
  16 June 2010
- Interior Point Methods for LP
  7 November 2009
- On a Class of Superlinearly Convergent Polynomial Time Interior Point Methods for Sufficient LCP
  SIAM Journal on Optimization, Vol. 20, No. 3
- On Interior-Point Warmstarts for Linear and Combinatorial Optimization
  SIAM Journal on Optimization, Vol. 20, No. 4
- A new full-Newton step O(n) infeasible interior-point algorithm for semidefinite optimization
  26 February 2009 | Numerical Algorithms, Vol. 52, No. 2
- Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions
  European Journal of Operational Research, Vol. 194, No. 2
- A Polynomial Predictor-Corrector Trust-Region Algorithm for Linear Programming
  SIAM Journal on Optimization, Vol. 19, No. 4
- Further development of multiple centrality correctors for interior point methods
  31 October 2007 | Computational Optimization and Applications, Vol. 41, No. 3
- A Mehrotra-Type Predictor-Corrector Algorithm for Monotonic Linear Complementarity Problem
- A Wide-Neighborhood Algorithm for Monotone Nonlinear Complementarity Problem
- 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
  16 June 2007 | Mathematical Programming, Vol. 115, No. 1
- An infeasible-interior-point predictor-corrector algorithm for the second-order cone program
  Acta Mathematica Scientia, Vol. 28, No. 3
- Complexity of the primal–dual path-following algorithms for the weighted determinant maximization problems with linear matrix inequalities in the narrow neighbourhood
  Optimization Methods and Software, Vol. 23, No. 3
- On the probabilistic complexity of finding an approximate solution for linear programming
  Journal of Complexity, Vol. 24, No. 2
- Mehrotra-type predictor-corrector algorithm revisited
  Optimization Methods and Software, Vol. 23, No. 2
- The Homogeneous Self-Dual Method
- A Wide Neighborhood Primal-Dual Interior-Point Algorithm for a Class of Convex Programming
- On Mehrotra-Type Predictor-Corrector Algorithms
  SIAM Journal on Optimization, Vol. 18, No. 4
- Primal-Dual Affine Scaling Interior Point Methods for Linear Complementarity Problems
  SIAM Journal on Optimization, Vol. 19, No. 1
- Postponing the choice of the barrier parameter in Mehrotra-type predictor–corrector algorithms
  European Journal of Operational Research, Vol. 182, No. 2
- Enlarging neighborhoods of interior-point algorithms for linear programming via least values of proximity measure functions
  Applied Numerical Mathematics, Vol. 57, No. 9
- A Mizuno–Todd–Ye type predictor–corrector algorithm for sufficient linear complementarity problems
  European Journal of Operational Research, Vol. 181, No. 3
- A path to the Arrow–Debreu competitive market equilibrium
  15 December 2006 | Mathematical Programming, Vol. 111, No. 1-2
- Corrector–predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path
  8 December 2006 | Mathematical Programming, Vol. 111, No. 1-2
- An Infeasible Mizuno–Todd–Ye Type Algorithm for Convex Quadratic Programming with Polynomial Complexity
  Numerical Functional Analysis and Optimization, Vol. 28, No. 3-4
- Adaptive Large-Neighborhood Self-Regular Predictor-Corrector Interior-Point Methods for Linear Optimization
  30 January 2007 | Journal of Optimization Theory and Applications, Vol. 132, No. 1
- Improved complexity results on solving real-number linear feasibility problems
  14 July 2005 | Mathematical Programming, Vol. 106, No. 2
- A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING
  Acta Mathematica Scientia, Vol. 26, No. 2
- Corrector‐Predictor Methods for Sufficient Linear Complementarity Problems in a Wide Neighborhood of the Central Path
  SIAM Journal on Optimization, Vol. 17, No. 3
- A New Complexity Result on Solving the Markov Decision Problem
  Yinyu Ye,
  1 August 2005 | Mathematics of Operations Research, Vol. 30, No. 3
- ON THE PROPERTIES OF ∊-SENSITIVITY ANALYSIS FOR LINEAR PROGRAMMING
  20 November 2011 | Asia-Pacific Journal of Operational Research, Vol. 22, No. 02
- Predictor–corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central path
  Optimization Methods and Software, Vol. 20, No. 1
- Clustered multidimensional data association for limited sensor resolutions
- A Predictor-Corrector Algorithm for Linear Optimization Based on a Specific Self-Regular Proximity Function
  SIAM Journal on Optimization, Vol. 15, No. 4
- An O $(\sqrtn L)$ Iteration Primal-dual Path-following Method, Based on Wide Neighborhoods and Large Updates, for Monotone LCP
  SIAM Journal on Optimization, Vol. 16, No. 2
- A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm
  SIAM Journal on Optimization, Vol. 15, No. 2
- On self-regular IPMs
  Top, Vol. 12, No. 2
- Convergence Analysis of an Inexact Infeasible Interior Point Method for Semidefinite Programming
  Computational Optimization and Applications, Vol. 29, No. 3
- Properties of the Central Points in Linear Programming Problems
  Numerical Algorithms, Vol. 35, No. 2-4
- Probabilistic analysis of a differential equation for linear programming
  Journal of Complexity, Vol. 19, No. 4
- An Interior-Point Approach to Multi-Stage Stochastic Programming
- Fusion of active phased array radars within a quick reaction time using multidimensional data association
- A Variant of the Vavasis--Ye Layered-Step Interior-Point Algorithm for Linear Programming
  SIAM Journal on Optimization, Vol. 13, No. 4
- The Mizuno–Todd–Ye algorithm in a larger neighborhood of the central path
  European Journal of Operational Research, Vol. 143, No. 2
- Semidefinite programming for discrete optimization and matrix completion problems
  Discrete Applied Mathematics, Vol. 123, No. 1-3
- Interior-Point Methods: Worst Case and Average Case Analysis of a Phase-I Algorithm and a Termination Procedure
  Journal of Complexity, Vol. 18, No. 3
- Implementation of interior point methods for mixed semidefinite and second order cone optimization problems
  27 October 2010 | Optimization Methods and Software, Vol. 17, No. 6
- Parallel Interior Point Schemes for Solving Multistage Convex Programming
  Annals of Operations Research, Vol. 108, No. 1-4
- Robust steady‐state target calculation for model predictive control
  16 April 2004 | AIChE Journal, Vol. 46, No. 5
- Central Region Method
- Error Bounds and Superlinear Convergence Analysis of Some Newton-Type Methods in Optimization
- A quadratically convergent polynomial long-step algorithm for A class of nonlinear monotone complementarity problems *
  Optimization, Vol. 48, No. 4
- A Comparison of a Moreau--Yosida-Based Active Set Strategy and Interior Point Methods for Constrained Optimal Control Problems
  SIAM Journal on Optimization, Vol. 11, No. 2
- Two Interior-Point Methods for Nonlinear P *(τ)-Complementarity Problems
  Journal of Optimization Theory and Applications, Vol. 102, No. 3
- An ε-sensitivity analysis in the primal–dual interior point method
  European Journal of Operational Research, Vol. 116, No. 3
- Interior-point methods for reduced Hessian successive quadratic programming
  Computers & Chemical Engineering, Vol. 23, No. 7
- Interior-Point Methods with Decomposition for Solving Large-Scale Linear Programs
  Journal of Optimization Theory and Applications, Vol. 102, No. 1
- On quadratic convergence of the $$O\left( {\sqrt {nL} } \right)$$ -iteration homogeneous and self‐duallinear programming algorithm
  Annals of Operations Research, Vol. 87, No. 0
- An interior point linear programming approach to two-scan data association
  IEEE Transactions on Aerospace and Electronic Systems, Vol. 35, No. 2
- Symmetric primal-dual path-following algorithms for semidefinite programming
  Applied Numerical Mathematics, Vol. 29, No. 3
- Primal-dual potential reduction methods for semidefinite programming using affine-scaling directions
  Applied Numerical Mathematics, Vol. 29, No. 3
- Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming
  Kurt M. Anstreicher,
  Jun Ji,
  Florian A. Potra,
  Yinyu Ye,
  1 February 1999 | Mathematics of Operations Research, Vol. 24, No. 1
- Superlinear Convergence of an Algorithm for Monotone Linear Complementarity Problems, When No Strictly Complementary Solution Exists
  Jos F. Sturm,
  1 February 1999 | Mathematics of Operations Research, Vol. 24, No. 1
- Iteration complexity of an interior-point algorithm for nonlinear p∗-complementarity problems
  International Journal of Computer Mathematics, Vol. 70, No. 4
- Perturbed path following predictor-corrector interior point algorithms
  Optimization Methods and Software, Vol. 11, No. 1-4
- Sdpha: a Matlab implementation of homogeneous interior-point algorithms for semidefinite programming
  Optimization Methods and Software, Vol. 11, No. 1-4
- A Predictor-Corrector Interior-Point Algorithm for the Semidefinite Linear Complementarity Problem Using the Alizadeh--Haeberly--Overton Search Direction
  SIAM Journal on Optimization, Vol. 9, No. 2
- Complexity of Predictor-Corrector Algorithms for LCP Based on a Large Neighborhood of the Central Path
  SIAM Journal on Optimization, Vol. 10, No. 1
- Polynomial Convergence of a New Family of Primal-Dual Algorithms for Semidefinite Programming
  SIAM Journal on Optimization, Vol. 9, No. 3
- High Order Infeasible-Interior-Point Methods for Solving Sufficient Linear Complementarity Problems
  Josef Stoer,
  Martin Wechs,
  Shinji Mizuno,
  1 November 1998 | Mathematics of Operations Research, Vol. 23, No. 4
- A Superlinearly Convergent Primal-Dual Infeasible-Interior-Point Algorithm for Semidefinite Programming
  SIAM Journal on Optimization, Vol. 8, No. 4
- Superlinear Convergence of Interior-Point Algorithms for Semidefinite Programming
  Journal of Optimization Theory and Applications, Vol. 99, No. 1
- Primal-Dual Symmetry and Scale Invariance of Interior-Point Algorithms for Convex Optimization
  Levent Tunçel,
  1 August 1998 | Mathematics of Operations Research, Vol. 23, No. 3
- A modified layered-step interior-point algorithm for linear programming
  Mathematical Programming, Vol. 82, No. 3
- Polynomial Convergence of Primal-Dual Algorithms for Semidefinite Programming Based on the Monteiro and Zhang Family of Directions
  SIAM Journal on Optimization, Vol. 8, No. 3
- On the long-step path-following method for semidefinite programming
  Operations Research Letters, Vol. 22, No. 4-5
- Superlinearly Convergent Infeasible-Interior-Point Algorithm for Degenerate LCP
  Journal of Optimization Theory and Applications, Vol. 97, No. 2
- Interior Point Algorithms For Linear Complementarity Problems Based On Large Neighborhoods Of The Central Path
  SIAM Journal on Optimization, Vol. 8, No. 2
- Primal-Dual Interior-Point Methods for Self-Scaled Cones
  SIAM Journal on Optimization, Vol. 8, No. 2
- On Extending Some Primal--Dual Interior-Point Algorithms From Linear Programming to Semidefinite Programming
  SIAM Journal on Optimization, Vol. 8, No. 2
- Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming
  Mathematical Programming, Vol. 81, No. 1
- Interior point techniques for the constrained simulation problem
  Computers & Chemical Engineering, Vol. 22
- An Interior-Point Method for Approximate Positive Semidefinite Completions
  Computational Optimization and Applications, Vol. 9, No. 2
- On Effectively Computing the Analytic Center of the Solution Set by Primal-Dual Interior-Point Methods
  SIAM Journal on Optimization, Vol. 8, No. 1
- Superlinear Convergence of a Symmetric Primal-Dual Path Following Algorithm for Semidefinite Programming
  SIAM Journal on Optimization, Vol. 8, No. 1
- Global Linear and Local Quadratic Convergence of a Long-Step Adaptive-Mode Interior Point Method for Some Monotone Variational Inequality Problems
  SIAM Journal on Optimization, Vol. 8, No. 1
- Superlinear Convergence of a Symmetric Primal-Dual Path Following Algorithm for SDP
- Computer Solution of Linear Programs: Non-simplex Algorithms
- On Primal—Dual Path—Following Algorithms for Semidefinite Programming
- An Upper Bound for the Average Number of Iterations Required in Phase II of an Interior-Point-Method
- Local convergence of predictor—corrector infeasible-interior-point algorithms for SDPs and SDLCPs
  Mathematical Programming, Vol. 80, No. 2
- Search directions and convergence analysis of some infeasibnle path-following methods for the monoton semi-definite lcp ∗
  29 March 2007 | Optimization Methods and Software, Vol. 9, No. 4
- Solving large-scale linear programs by interior-point methods under the Matlab ∗ Environment †
  Optimization Methods and Software, Vol. 10, No. 1
- The Gaussian hare and the Laplacian tortoise: computability of squared-error versus absolute-error estimators
  Statistical Science, Vol. 12, No. 4
- Bibliography
  14 October 2011
- Predictor-corrector method for nonlinear complementarity problem
  Acta Mathematicae Applicatae Sinica, Vol. 13, No. 3
- On the Interplay among Entropy, Variable Metrics and Potential Functions in Interior-Point Algorithms
  Computational Optimization and Applications, Vol. 8, No. 1
- A Quadratically Convergent Infeasible-Interior-Point Algorithm for LCP with Polynomial Complexity
  SIAM Journal on Optimization, Vol. 7, No. 2
- A Predictor-Corrector Algorithm for a Class of Nonlinear Saddle Point Problems
  SIAM Journal on Control and Optimization, Vol. 35, No. 2
- The largest step path following algorithm for monotone linear complementarity problems
  Mathematical Programming, Vol. 76, No. 2
- On the Convergence of the Mizuno--Todd--Ye Algorithm to the Analytic Center of the Solution Set
  SIAM Journal on Optimization, Vol. 7, No. 1
- On the Quadratic Convergence of the Simplified Mizuno--Todd--Ye Algorithm for Linear Programming
  SIAM Journal on Optimization, Vol. 7, No. 1
- Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices
  SIAM Journal on Optimization, Vol. 7, No. 1
- Long-step strategies in interior-point primal-dual methods
  Mathematical Programming, Vol. 76, No. 1
- Fast convergence of the simplified largest step path following algorithm
  Mathematical Programming, Vol. 76, No. 1
- Improved complexity using higher-order correctors for primal-dual Dikin affine scaling
  Mathematical Programming, Vol. 76, No. 1
- Bounded error parameter estimation: a sequential analytic center approach
- Stability of Augmented System Factorizations in Interior-Point Methods
  SIAM Journal on Matrix Analysis and Applications, Vol. 18, No. 1
- AnO(nL) infeasible-interior-point algorithm for LCP with quadratic convergence
  Annals of Operations Research, Vol. 62, No. 1
- A Mehrotra-type predictor-corrector algorithm with polynomiality andQ-subquadratic convergence
  Annals of Operations Research, Vol. 62, No. 1
- A simplified homogeneous and self-dual linear programming algorithm and its implementation
  Annals of Operations Research, Vol. 62, No. 1
- Primal-dual target-following algorithms for linear programming
  Annals of Operations Research, Vol. 62, No. 1
- A lower bound on the number of iterations of long-step primal-dual linear programming algorithms
  Annals of Operations Research, Vol. 62, No. 1
- Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization
  Mathematical Programming, Vol. 75, No. 3
- A predictor-corrector method for extended linear-quadratic programming
  Computers & Operations Research, Vol. 23, No. 8
- Two Infeasible Interior-Point Predictor-Corrector Algorithms for Linear Programming
  SIAM Journal on Optimization, Vol. 6, No. 3
- An Asymptotical $O(\sqrt{n} L)$-Iteration Path-Following Linear Programming Algorithm That Uses Wide Neighborhoods
  SIAM Journal on Optimization, Vol. 6, No. 3
- Asymptotic convergence in a generalized predictor-corrector method
  Mathematical Programming, Vol. 74, No. 1
- A primal-dual interior point method whose running time depends only on the constraint matrix
  Mathematical Programming, Vol. 74, No. 1
- A superquadratic infeasible-interior-point method for linear complementarity problems
  Mathematical Programming, Vol. 73, No. 3
- A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems
  Applied Mathematics & Optimization, Vol. 33, No. 3
- Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems
  Mathematical Programming, Vol. 72, No. 3
- Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem
  29 April 2008 | Statistica Neerlandica, Vol. 50, No. 1
- An $$O(\sqrt n L)$$ iteration bound primal-dual cone affine scaling algorithm for linear programmingiteration bound primal-dual cone affine scaling algorithm for linear programming
  Mathematical Programming, Vol. 72, No. 2
- An Infeasible-Interior-Point Predictor-Corrector Algorithm for Linear Programming
  SIAM Journal on Optimization, Vol. 6, No. 1
- On the Relationship Between the Curvature Integral and the Complexity of Path-Following Methods in Linear Programming
  SIAM Journal on Optimization, Vol. 6, No. 1
- Target-Following Methods for Linear Programming
- Infeasible-Interior-Point Algorithms
- Validation of measurement data using an interior point SQP
  Computers & Chemical Engineering, Vol. 20
- The curvature integral and the complexity of linear complementarity problems
  Mathematical Programming, Vol. 70, No. 1-3
- Superlinear primal-dual affine scaling algorithms for LCP
  Mathematical Programming, Vol. 69, No. 1-3
- A quadratically convergent $$O((\kappa + 1)\sqrt n L)$$ -iteration algorithm for theP *(κ)-matrix linear complementarity problem
  Mathematical Programming, Vol. 69, No. 1-3
- A New Infinity-Norm Path Following Algorithm for Linear Programming
  SIAM Journal on Optimization, Vol. 5, No. 2
- On the convergence of primal-dual interior-point methods with wide neighborhoods
  Computational Optimization and Applications, Vol. 4, No. 2
- Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence
  Journal of Optimization Theory and Applications, Vol. 85, No. 1
- Infeasible-Interior-Point Primal-Dual Potential-Reduction Algorithms for Linear Programming
  SIAM Journal on Optimization, Vol. 5, No. 1
- On polynomiality of the Mehrotra-type predictor—corrector interior-point algorithms
  Mathematical Programming, Vol. 68, No. 1-3
- A predictor-corrector method for solving the P * ( k )-matrix lcp from infeasible starting points
  Optimization Methods and Software, Vol. 6, No. 2
- Polynomiality of infeasible-interior-point algorithms for linear programming
  Mathematical Programming, Vol. 67, No. 1-3
- A quadratically convergent predictor—corrector method for solving linear programs from infeasible starting points
  Mathematical Programming, Vol. 67, No. 1-3
- Constant potential primal—dual algorithms: A framework
  Mathematical Programming, Vol. 66, No. 1-3
- Monotonicity of Primal and Dual Objective Values in Primal-dual Interior-point Algorithms
  SIAM Journal on Optimization, Vol. 4, No. 3
- Local convergence of interior-point algorithms for degenerate monotone LCP
  Computational Optimization and Applications, Vol. 3, No. 2
- Superlinearly Convergent $O ( \sqrt{n} L )$-Iteration Interior-Point Algorithms for Linear Programming and the Monotone Linear Complementarity Problem
  SIAM Journal on Optimization, Vol. 4, No. 2
- Predictor-corrector Methods for a Class of Linear Complementarity Problems
  SIAM Journal on Optimization, Vol. 4, No. 2
- A globally convergent primal—dual interior point algorithm for convex programming
  Mathematical Programming, Vol. 64, No. 1-3
- A Study of Indicators for Identifying Zero Variables in Interior-Point Methods
  SIAM Review, Vol. 36, No. 1
- Global convergence in infeasible-interior-point algorithms
  Mathematical Programming, Vol. 65, No. 1-3
- Interior-point algorithms for semi-infinite programming
  Mathematical Programming, Vol. 65, No. 1-3
- Limiting behavior of weighted central paths in linear programming
  Mathematical Programming, Vol. 65, No. 1-3
- Large-Step Interior Point Algorithms for Linear Complementarity Problems
  SIAM Journal on Optimization, Vol. 3, No. 2
- On the Superlinear Convergence of Interior-Point Algorithms for a General Class of Problems
  SIAM Journal on Optimization, Vol. 3, No. 2
- On the finite convergence of interior-point algorithms for linear programming
  Mathematical Programming, Vol. 57, No. 1-3

cover image Mathematics of Operations Research

Volume 18, Issue 4

November 1993

Pages 767-1019

Article Information

Metrics

Information

Published Online:November 01, 1993

Cite as

Shinji Mizuno, Michael J. Todd, Yinyu Ye, (1993) On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming. Mathematics of Operations Research 18(4):964-981.

https://doi.org/10.1287/moor.18.4.964

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming

Abstract

Volume 18, Issue 4

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News