Abstract
In the adaptive step primal-dual interior point method for linear programming, polynomial algorithms are obtained by computing Newton directions towards targets on the central path, and restricting the iterates to a neighborhood of this central path. In this paper, the adaptive step methodology is extended, by considering targets in a certain central region, which contains the usual central path, and subsequently generating iterates in a neighborhood of this region. The size of the central region can vary from the central path to the whole feasible region by choosing a certain parameter. An 𝒪(√nL) iteration bound is obtained under mild conditions on the choice of the target points. In particular, we leave plenty of room for experimentation with search directions. The practical performance of the new primal-dual interior point method is measured on part of the Netlib test set for various sizes of the central region.
Keywords
Interior point methodIterated functionMathematicsPath (computing)Linear programmingDual (grammatical number)Mathematical optimizationPoint (geometry)Set (abstract data type)AlgorithmComputer scienceGeometry
Affiliated Institutions
Related Publications
On the Implementation of a Primal-Dual Interior Point Method
This paper gives an approach to implementing a second-order primal-dual interior point method. It uses a Taylor polynomial of second order to approximate a primal-dual trajector...
On Finding Primal- and Dual-Optimal Bases
We show that if there exists a strongly polynomial time algorithm that finds a basis which is optimal for both the primal and the dual problems, given an optimal solution for on...
A Globally Convergent Primal-Dual Interior-Point Filter Method for Nonconvex Nonlinear Programming
In this paper, the filter technique of Fletcher and Leyffer (1997) is used to globalize the primal-dual interior-point algorithm for nonlinear programming, avoiding the use of m...
Theory and algorithms for linear optimization : an interior point approach
Partial table of contents: INTRODUCTION: THEORY AND COMPLEXITY. Duality Theory for Linear Optimization. A Polynomial Algorithm for the Skew-Symmetric Model. Solving the Canonica...
An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
We present an O(√nL)-iteration homogeneous and self-dual linear programming (LP) algorithm. The algorithm possesses the following features: • It solves the linear programming pr...
Publication Info
- Year
- 1997
- Type
- article
- Volume
- 22
- Issue
- 2
- Pages
- 408-431
- Citations
- 18
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
18
OpenAlex
Cite This
J.F. Sturm,
Shuzhong Zhang
(1997).
On a Wide Region of Centers and Primal-Dual Interior Point Algorithms for Linear Programming.
Mathematics of Operations Research
, 22
(2)
, 408-431.
https://doi.org/10.1287/moor.22.2.408
Identifiers
- DOI
- 10.1287/moor.22.2.408