Linear updates for a single-phase projective method

DOI10.1016/0167-6377(90)90015-WMaRDI QIDQ2276876zbMATH OpenOpenAlexFDO

Authors Chris Fraley

Publication date 1990

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(90)90015-w

zbMATH Keywords

convergencelinear updatessingle-phase projective algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Linear programming (90C05)

Review text

The paper describes an enhancement to the single-phase projective algorithm proposed by \textit{G. de Ghellinck} and \textit{J.-P. Vial} [Algoritmica 1, 425-453 (1986; Zbl 0629.90058)] for the primal linear programming problem. The linear lower-bound update that they give does not ensure convergence with nonfeasible iterates, and is therefore supplemented by a quadratic procedure. In this paper, linear updates are derived that guarantee convergence of the algorithm in a polynomial number of steps.

Recommendations

• Single-projection procedure for linear optimization
• Projected Hessian Updating Algorithms for Nonlinearly Constrained Optimization
• scientific article; zbMATH DE number 21024
• On stable convergence of secant methods with projected updates
• A General Updating Algorithm for Constrained Linear Least Squares Problems
• scientific article; zbMATH DE number 4185389
• A projective simplex method for linear programming
• A rank-one updating approach for solving systems of linear equations in the least squares sense
• Projected gradient methods for linearly constrained problems
• A generalized projection iterative methods for solving non-singular linear systems

Cites work

• A combined phase I-phase II projective algorithm for linear programming
• A polynomial Newton method for linear programming
• A projective algorithm for linear programming with no regularity condition
• An extension of Karmarkar's algorithm for linear programming using dual variables
• An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex
• Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
• On Anstreicher's combined phase I-phase II projective algorithm for linear programming
• Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming

Cited in

(4)

• A combined phase I-phase II scaled potential algorithm for linear programming
• On combined phase 1-phase 2 projective methods for linear programming
• Combining phase I and phase II in a potential reduction algorithm for linear programming
• Single-projection procedure for linear optimization

This page was built for publication: Linear updates for a single-phase projective method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2276876)