Generalized affine scaling algorithms for linear programming problems

DOI10.1016/J.COR.2019.104807MaRDI QIDQ2337378zbMATH OpenOpenAlexWikidataFDO

Authors Md Sarowar Morshed, Md. Noor-E-Alam

Publication date 19 November 2019

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.07373

zbMATH Keywords

affine scalingDikin processinterior point methodsNesterov accelerationShanks series transformation

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) Interior-point methods (90C51)

Abstract: Interior Point Methods are widely used to solve Linear Programming problems. In this work, we present two primal affine scaling algorithms to achieve faster convergence in solving Linear Programming problems. In the first algorithm, we integrate Nesterov's restarting strategy in the primal affine scaling method with an extra parameter, which in turn generalizes the original primal affine scaling method. We provide the proof of convergence for the proposed generalized algorithm considering long step size. We also provide the proof of convergence for the primal and dual sequence without the degeneracy assumption. This convergence result generalizes the original convergence result for the affine scaling methods and it gives us hints about the existence of a new family of methods. Then, we introduce a second algorithm to accelerate the convergence rate of the generalized algorithm by integrating a non-linear series transformation technique. Our numerical results show that the proposed algorithms outperform the original primal affine scaling method.

Recommendations

• A primal-dual affine-scaling potential-reduction algorithm for linear programming
• scientific article; zbMATH DE number 1226308
• Implementing an affine scaling algorithm for linear programming
• A class of primal affine scaling algorithms
• scientific article; zbMATH DE number 1785846

Cites work

• A class of primal affine scaling algorithms
• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• A modification of Karmarkar's linear programming algorithm
• A new polynomial-time algorithm for linear programming
• A Polynomial Primal-Dual Dikin-Type Algorithm for Linear Programming
• A simple proof of a primal affine scaling method
• A simplified global convergence proof of the affine scaling algorithm
• A THREE STEP QUADRATICALLY CONVERGENT VERSION OF PRIMAL AFFINE SCALING METHOD
• A variation on Karmarkar’s algorithm for solving linear programming problems
• An affine scaling optimal path method with interior backtracking curvilinear technique for linear constrained optimization
• An Affine-Scaling Interior-Point Method for Continuous Knapsack Constraints with Application to Support Vector Machines
• An interior affine scaling cubic regularization algorithm for derivative-free optimization subject to bound constraints
• Approximation accuracy, gradient methods, and error bound for structured convex optimization
• Chaotic behavior of the affine scaling algorithm for linear programming
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Global Convergence of a Long-Step Affine Scaling Algorithm for Degenerate Linear Programming Problems
• Global convergence of the affine scaling methods for degenerate linear programming problems
• Global Convergence Property of the Affine Scaling Methods for Primal Degenerate Linear Programming Problems
• Gradient methods for minimizing composite functions
• scientific article; zbMATH DE number 3114505 (Why is no real title available?)
• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• scientific article; zbMATH DE number 4202017 (Why is no real title available?)
• scientific article; zbMATH DE number 1131479 (Why is no real title available?)
• scientific article; zbMATH DE number 3301975 (Why is no real title available?)
• scientific article; zbMATH DE number 964349 (Why is no real title available?)
• Limiting behavior of the affine scaling continuous trajectories for linear programming problems
• Linear programming. Foundations and extensions
• On the chaotic behavior of the primal-dual affine-scaling algorithm for linear optimization
• Primal-dual affine-scaling algorithms fail for semidefinite programming
• Projected affine-scaling interior-point Newton's method with line search filter for box constrained optimization
• Random walks on polytopes and an affine interior point method for linear programming
• Smooth minimization of non-smooth functions
• Superlinear convergence of the affine scaling algorithm
• Two-thirds is sharp for affine scaling

Cited in

(11)

• On affine scaling and semi-infinite programming
• Superlinear primal-dual affine scaling algorithms for LCP
• Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
• Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
• Chaotic behavior of the affine scaling algorithm for linear programming
• A modified scaling algorithm for LP
• Numerical experiments with the symmetric affine scaling algorithm on degenerate linear programming problema
• scientific article; zbMATH DE number 1226308 (Why is no real title available?)
• scientific article; zbMATH DE number 2153272 (Why is no real title available?)
• An infeasible interior-point arc-search method with Nesterov's restarting strategy for linear programming problems
• The affine-scaling direction for linear programming is a limit of projective-scaling directions

Describes a project that uses

Uses Software

• CPLEX

This page was built for publication: Generalized affine scaling algorithms for linear programming problems

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