Near boundary behavior of primal-dual potential reduction algorithms for linear programming
From MaRDI portal
Publication:1803608
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.
Recommendations
- scientific article; zbMATH DE number 4197744
- An \(O(n^ 3L)\) potential reduction algorithm for linear programming
- Infeasible-Interior-Point Primal-Dual Potential-Reduction Algorithms for Linear Programming
- A potential-reduction variant of Renegar's short-step path-following method for linear programming
- scientific article; zbMATH DE number 1047677
Cites work
- A Centered Projective Algorithm for Linear Programming
- A new polynomial-time algorithm for linear programming
- A note on a potential reduction algorithm for LP with simultaneous primal-dual updating
- A polynomial-time algorithm for a class of linear complementarity problems
- A polynomial-time algorithm, based on Newton's method, for linear programming
- A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
- A unified approach to interior point algorithms for linear complementarity problems: A summary
- An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming
- An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
- An \(O(n^ 3L)\) potential reduction algorithm for linear programming
- An Implementation of a Primal-Dual Interior Point Method for Linear Programming
- An interior point potential reduction algorithm for the linear complementarity problem
- scientific article; zbMATH DE number 4131946 (Why is no real title available?)
- scientific article; zbMATH DE number 4199975 (Why is no real title available?)
- scientific article; zbMATH DE number 4164543 (Why is no real title available?)
- scientific article; zbMATH DE number 4126998 (Why is no real title available?)
- Interior path following primal-dual algorithms. I: Linear programming
- Long steps in an \(O(n^ 3L)\) algorithm for linear programming
- On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms
- Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
Cited in
(11)- On lower bound updates in primal potential reduction methods for linear programming
- A primal-dual affine-scaling potential-reduction algorithm for linear programming
- Potential-reduction methods in mathematical programming
- Deriving potential functions via a symmetry principle for nonlinear equations
- A boundary-point LP solution method and its application to dense linear programs
- Theoretical convergence of large-step primal-dual interior point algorithms for linear programming
- Asymptotic Behavior of Continuous Trajectories for Primal-Dual Potential-Reduction Methods
- Les effets de l'exposant de la fonction barrière multiplicative dans les méthodes de points intérieurs
- On the length of primal-dual projection of potential reduction algorithm
- On the finite convergence of interior-point algorithms for linear programming
- Convergence behavior of interior-point algorithms
This page was built for publication: Near boundary behavior of primal-dual potential reduction algorithms for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1803608)
