A weighted least squares study of robustness in interior point linear programming

DOI10.1007/BF01299141MaRDI QIDQ1260620zbMATH OpenFDO

Authors Alexander L. Hipolito

Publication date 30 August 1993

Published in Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01299141

zbMATH Keywords

modified Newton centering directionrobustness of interior point linear programming algorithms

Mathematics Subject Classification ID

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

Review text

Although global convergence of the affine scaling algorithm has been proved, it is known that, for a bad choice of the initial interior point, the convergence may become very slow, or even numerical stall may occur. The paper in question studied the robustness of interior point linear programming algorithms, with respect to initial iterates that are close to the boundary (bad initial point). The author computes a modified Newton centering direction and shows that the approach which uses this direction is more robust than both the pure affine scaling approach and one which uses the Newton direction as the centering direction.

Recommendations

• Stabilization of interior-point methods for linear programming
• A Low Complexity Interior-Point Algorithm for Linear Programming
• An interior point method for linear programming
• A Primal-dual affine scaling algorithm with necessary centering as a safeguard
• Weighted-path-following algorithm for linear programming

Cites work

• A modification of Karmarkar's linear programming algorithm
• A new polynomial-time algorithm for linear programming
• A simplified global convergence proof of the affine scaling algorithm
• A survey of search directions in interior point methods for linear programming
• A variation on Karmarkar’s algorithm for solving linear programming problems
• An implementation of Karmarkar's algorithm for linear programming
• Boundary Behavior of Interior Point Algorithms in Linear Programming
• Computational experience with a dual affine variant of Karmarkar's method for linear programming
• Computational experience with a primal-dual interior point method for linear programming
• Computational results of an interior point algorithm for large scale linear programming
• Degeneracy in interior point methods for linear programming: A survey
• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 883145 (Why is no real title available?)
• scientific article; zbMATH DE number 3307153 (Why is no real title available?)
• Search directions for interior linear-programming methods

Cited in

(4)

• Warm start of the primal-dual method applied in the cutting-plane scheme
• Solving nonlinear multicommodity flow problems by the analytic center cutting plane method
• A decomposition-based crash-start for stochastic programming
• A warm-start approach for large-scale stochastic linear programs

This page was built for publication: A weighted least squares study of robustness in interior point linear programming

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