SpringerLink
Log in

Primal-Dual Newton’s Method with Steepest Descent for Linear Programming

  • Conference paper
  • First Online:
Optimization and Applications (OPTIMA 2018)

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 974))

Included in the following conference series:

  • 564 Accesses

Abstract

The primal-dual method for solving linear programming problems is considered. In order to determine the search directions the non-perturbed system of optimality conditions is solved by Newton’s method. If this system is degenerate, then an auxiliary linear complementarity problem is solved for obtained unique directions. Starting points and all consequent points are feasible. The step-lengths are chosen from the steepest descent approach based on minimization of the dual gap. The safety factor is not introduced, and trajectories are allowed to move along the boundaries of the feasible sets. The convergence of the method at a finite number of iterations is proved.

This work was supported by the Russian Foundation for Basic Research (project no. 17-07-00510).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 53.49
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Luenberger, D.: Linear and Nonlinear Programming. Addison-Wesle, London (1984)

    MATH  Google Scholar 

  2. Vanderbei, R.J.: Linear Programming. Foundations and Extensions. Kluwer Academic Publishers, Boston (1997)

    MATH  Google Scholar 

  3. Vasilyev, F.P., Ivanitskiy, A.Y.: In-Depth Analysis of Linear Programming. Springer, Nethelands (2001)

    Book  Google Scholar 

  4. Nesterov, Y.E., Nemirovski, A.: Interior Point Polynomial Algorithms in Convex Programming. SIAM Publications, Philadelphia (1994)

    Book  Google Scholar 

  5. Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997)

    Book  Google Scholar 

  6. Roos, C., Terlaky, T., Vial, J-Ph: Theory and Algorithms for Linear Optimization an Interior Point Approach. Wiley, Chichester (1997)

    MATH  Google Scholar 

  7. Gondzio, J.: Interior point methods 25 years later. Eur. J. Oper. Res. 218, 587–601 (2012)

    Article  MathSciNet  Google Scholar 

  8. Kojima, M., Mizuno, S., Yoshise, A.: A primal-dual interior point method for linear programming. In: Megiddo, N. (ed.) Progress in Mathematical Programming. Interior Point and Related Methods, pp. 29–47. Springer, Berlin (1989). https://doi.org/10.1007/978-1-4613-9617-8_2

    Chapter  Google Scholar 

  9. Kojima, M., Megiddo, N., Mizuno, S.: A primal-dual infeasible-interior point method for linear programming. Math. Program. 61, 263–280 (1993)

    Article  Google Scholar 

  10. Monteiro, R.C., Adler, I.: Interior path-following primal-dual algorithms. Part I: linear programming. Math. Program. 44, 27–41 (1989)

    Article  Google Scholar 

  11. Todd, M.J., Ye, Y.: A centered projective algorithm for linear programming. Math. Oper. Res. 15, 508–529 (1990)

    Article  MathSciNet  Google Scholar 

  12. Ye, Y., Guler, O., Tapia, R., Zhang, Y.: A quadratically convergent \(O(\sqrt{n}L)\)-iteration algorithm for linear programming. Math. Program. 59, 151–162 (1993)

    Article  MathSciNet  Google Scholar 

  13. Gonzaga, C.: Path-following methods for linear programming. SIAM Rev. 34, 167–224 (1992)

    Article  MathSciNet  Google Scholar 

  14. Zhadan, V.G.: Primal-dual Newton method for linear programming problems. Comp. Maths. Math. Phys. 39, 14–28 (1999)

    MathSciNet  MATH  Google Scholar 

  15. McShane, K., Monma, C., Shanno, D.: On implementation of primal-dual interior point method for linear programming. ORSA J. Comput. 1, 70–89 (1989)

    Article  Google Scholar 

  16. Lustig, I.J., Monma, C., Shanno, D.: On implementing Mehrotra’s predictor-corrector interior point method for linear programming. SIAM J. Optim. 2, 435–449 (1992)

    Article  MathSciNet  Google Scholar 

  17. Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic press Inc., Boston (1992)

    MATH  Google Scholar 

  18. El-Bakry, A.S., Tapia, R.A., Zhang, Y.: A study of indicators for identifying zero variables in interior point methods. SIAM Rev. 36, 45–72 (1994)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dorodnicyn Computing Centre, FRC “Computer Science and Control” of RAS, Vaviliva st., 40, 119333, Moscow, Russia

    Vitaly Zhadan

Authors
  1. Vitaly Zhadan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vitaly Zhadan .

Editor information

Editors and Affiliations

  1. FRC CSC RAS, Dorodnitsyn Computing Centre, Moscow, Russia

    Yury Evtushenko

  2. University of Montenegro, Podgorica, Montenegro

    Milojica Jaćimović

  3. Krasovsky Institute of Mathematics and Mechanics, Yekaterinburg, Russia

    Michael Khachay

  4. Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia

    Yury Kochetov

  5. FRC CSC RAS, Dorodnitsyn Computing Centre, Moscow, Russia

    Vlasta Malkova

  6. FRC CSC RAS, Dorodnitsyn Computing Centre, Moscow, Russia

    Mikhail Posypkin

Rights and permissions

Reprints and permissions

Copyright information

© 2019 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Zhadan, V. (2019). Primal-Dual Newton’s Method with Steepest Descent for Linear Programming. In: Evtushenko, Y., Jaćimović, M., Khachay, M., Kochetov, Y., Malkova, V., Posypkin, M. (eds) Optimization and Applications. OPTIMA 2018. Communications in Computer and Information Science, vol 974. Springer, Cham. https://doi.org/10.1007/978-3-030-10934-9_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-10934-9_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-10933-2

  • Online ISBN: 978-3-030-10934-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation