Infeasible-Interior-Point Primal-Dual Potential-Reduction Algorithms for Linear Programming | Zendy

Shinji Mizuno | Zendy; Masakazu Kojima | Zendy; Michael J. Todd | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Infeasible-Interior-Point Primal-Dual Potential-Reduction Algorithms for Linear Programming

Author(s) -

Shinji Mizuno,

Masakazu Kojima,

Michael J. Todd

Publication year - 1995

Publication title -

siam journal on optimization

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 2.066

H-Index - 136

eISSN - 1095-7189

pISSN - 1052-6234

DOI - 10.1137/0805003

Subject(s) - interior point method , mathematics , monotone polygon , reduction (mathematics) , linear programming , algorithm , constant (computer programming) , mathematical optimization , bounded function , function (biology) , duality (order theory) , duality gap , polynomial , optimization problem , discrete mathematics , computer science , mathematical analysis , geometry , evolutionary biology , biology , programming language

. In this paper, we propose primal-dual potential-reduction algorithms which canstart from an infeasible interior point. We first describe two such algorithms and show that bothare polynomial-time bounded. One of the algorithms decreases the Tanabe-Todd-Ye primal-dualpotential function by a constant at each iteration under the condition that the duality gap decreasesby at most the same ratio as the infeasibility. The other reduces a new potential function, whichhas one more term in the...

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research