Near boundary behavior of primal-dual potential reduction algorithms for linear programming
type: Item
instance of: scholarly article
title: Near boundary behavior of primal-dual potential reduction algorithms for linear programming
zbMATH Open document ID: 0780.90066
DOI: 10.1007/BF01581269
author: Yanyan Li
published in: Mathematical Programming. Series A. Series B
publication date: 1993-06-29T00:00:00Z
review text: For a linear program of the form \(\min\{c^ T x;\;Ax=b,\;x\geq 0\}\) and the potential function \(\phi(x,s)=\rho_ P\ln(x^ T s)-\sum^ n_{j=1} \ln(x_ j s_ j)\), where \(s\) are dual slacks, the authors describe ranges (relative to \(\rho_ P\)) on the size of the parameter \(\rho_ s\) used in formulae for generating search directions which guarantee a constant reduction in the potential function.
reviewed by: Jiří Rohn
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90-08
zbMATH DE Number: 221252
zbMATH Keywords: interior point algorithm
zbMATH Keywords: potential function
MaRDI profile type: Publication
cites work: Long steps in an \(O(n^ 3L)\) algorithm for linear programming
cites work: Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
cites work: Q3033554
cites work: An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming
cites work: Q3348711
cites work: A note on a potential reduction algorithm for LP with simultaneous primal-dual updating
cites work: A new polynomial-time algorithm for linear programming
cites work: A unified approach to interior point algorithms for linear complementarity problems: A summary
cites work: An interior point potential reduction algorithm for the linear complementarity problem
cites work: An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
cites work: A polynomial-time algorithm for a class of linear complementarity problems
cites work: Q3491304
cites work: An Implementation of a Primal-Dual Interior Point Method for Linear Programming
cites work: Q4206561
cites work: Interior path following primal-dual algorithms. I: Linear programming
cites work: A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
cites work: A polynomial-time algorithm, based on Newton's method, for linear programming
cites work: A Centered Projective Algorithm for Linear Programming
cites work: An \(O(n^ 3L)\) potential reduction algorithm for linear programming
cites work: On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms
description: scientific article; zbMATH DE number 221252