Abstract
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 problem without any regularity assumption concerning the existence of optimal, feasible, or interior feasible solutions. • It can start at any positive primal-dual pair, feasible or infeasible, near the central ray of the positive orthant (cone), and it does not use any big M penalty parameter or lower bound. • Each iteration solves a system of linear equations whose dimension is almost the same as that solved in the standard (primal-dual) interior-point algorithms. • If the LP problem has a solution, the algorithm generates a sequence that approaches feasibility and optimality simultaneously; if the problem is infeasible or unbounded, the algorithm will correctly detect infeasibility for at least one of the primal and dual problems.
Keywords
OrthantMathematicsInterior point methodLinear programmingMathematical optimizationSequence (biology)Dimension (graph theory)Dual (grammatical number)Linear-fractional programmingAlgorithmFeasible regionApplied mathematicsCombinatorics
Affiliated Institutions
Related Publications
On a Wide Region of Centers and Primal-Dual Interior Point Algorithms for Linear Programming
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 p...
A globally convergent primal-dual interior point method for constrained optimization
Abstract This paper proposes a primal-dual interior point method for solving general nonlinearly constrained optimization problems. The method is based on solving the Barrier Ka...
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 Primal-Dual Interior-Point Method for Nonlinear Programming with Strong Global and Local Convergence Properties
An exact-penalty-function-based scheme---inspired from an old idea due to Mayne and Polak [Math. Program., 11 (1976), pp.67--80]---is proposed for extending to general smooth co...
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...
Publication Info
- Year
- 1994
- Type
- article
- Volume
- 19
- Issue
- 1
- Pages
- 53-67
- Citations
- 362
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
362
OpenAlex
Cite This
Yinyu Ye,
Michael J. Todd,
Shinji Mizuno
(1994).
An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm.
Mathematics of Operations Research
, 19
(1)
, 53-67.
https://doi.org/10.1287/moor.19.1.53
Identifiers
- DOI
- 10.1287/moor.19.1.53