Enlarging neighborhoods of interior-point algorithms for linear programming via least values of proximity measure functions
type: Item
instance of: scholarly article
title: Enlarging neighborhoods of interior-point algorithms for linear programming via least values of proximity measure functions
zbMATH Open document ID: 1121.65072
author: J. Martínez
published in: Applied Numerical Mathematics
publication date: 2007-07-23T00:00:00Z
review text: The interior-point algorithms working in wider neighborhoods are generally known to perform better than those counterparts using smaller neighborhoods. The author considers predictor-corrector methods based on a 2-norm and an \({\infty}\)-norm neighborhood, and shows how to use the least value of a proximity measure function to enlarge the neighborhood of the central path. The algorithms are proved to retain both the best known iteration complexity and the quadratic convergence of the original algorithms. The methods can be viewed as a new design for interior-point methods.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C51
zbMATH DE Number: 5173639
zbMATH Keywords: linear programming
zbMATH Keywords: interior-point algorithms
zbMATH Keywords: iteration complexity
zbMATH Keywords: neighborhoods
zbMATH Keywords: predictor-corrector methods
zbMATH Keywords: quadratic convergence
MaRDI profile type: Publication
full work available at URL: j.apnum.2006.09.009
OpenAlex ID: W2113292332
cites work: A New Infinity-Norm Path Following Algorithm for Linear Programming
cites work: Karmarkar's linear programming algorithm and Newton's method
cites work: Higher-Order Predictor-Corrector Interior Point Methods with Application to Quadratic Objectives
cites work: Complexity of Predictor-Corrector Algorithms for LCP Based on a Large Neighborhood of the Central Path
cites work: An Asymptotical $O(\sqrt{n} L)$-Iteration Path-Following Linear Programming Algorithm That Uses Wide Neighborhoods
cites work: On the Local Convergence of a Predictor-Corrector Method for Semidefinite Programming
cites work: A unified approach to interior point algorithms for linear complementarity problems: A summary
cites work: On the Implementation of a Primal-Dual Interior Point Method
cites work: On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
cites work: A Predictor-Corrector Algorithm for Linear Optimization Based on a Specific Self-Regular Proximity Function
cites work: A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points
cites work: An Infeasible-Interior-Point Predictor-Corrector Algorithm for Linear Programming
cites work: The Mizuno-Todd-Ye algorithm in a larger neighborhood of the central path
cites work: A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with \(O(\sqrt nL)\)-iteration complexity
cites work: Q4339096
cites work: The complexity of high-order predictor-corrector methods for solving sufficient linear complementarity problems
cites work: Global Linear and Local Quadratic Convergence of a Long-Step Adaptive-Mode Interior Point Method for Some Monotone Variational Inequality Problems
cites work: Q5691079
cites work: Q4382667
cites work: On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP
cites work: Interior Point Algorithms For Linear Complementarity Problems Based On Large Neighborhoods Of The Central Path
cites work: Two interior-point methods for nonlinear \(P_*(\tau)\)-complementarity problems.
DOI: 10.1016/J.APNUM.2006.09.009
description: scientific article; zbMATH DE number 5173639