Abstract

Besides the simplex algorithm, linear programs can also be solved via interior point methods. The theoretical background of such algorithms is the classical log-barrier problem. The aim of this note is to study and generalize the barrier problem using the standard tools of Convex Analysis.

Author information

Contact details are reproduced from the original publication and may be historical.

Keywords

  • Log-barrier problem
  • Lagrange multipliers
  • complementary slackness
  • recessional cone

Mathematics Subject Classification

90C51; 52A41, 90C05, 90C25

References

  1. D. Bayer, J. Lagarias: The nonlinear geometry of linear programming: affine and projective scaling trajectories, Trans. Amer. Math. Soc. 314 (1989) 499–525.https://doi.org/10.2307/2001396Google Scholar
  2. D. Bayer, J. Lagarias: The nonlinear geometry of linear programming: Legendre transform coordinates and central trajectories, Trans. Amer. Math. Soc. 314 (1989) 527–581.https://doi.org/10.2307/2001397Google Scholar
  3. F. Bernstein, G. Doetsch: Zur Theorie der konvexen Funktionen, Math. Ann. 76/4 (1915) 514–526.https://doi.org/10.1007/BF01458222Google Scholar
  4. J. M. Borwein, A. S. Lewis: Convex Analysis and Nonlinear Optimization – Theory and Examples, CMS Books in Mathematics, vol. 3, 2nd ed., Springer, New York (2006).https://doi.org/10.1007/978-0-387-31256-9Google Scholar
  5. G. B. Dantzig: Application of the simplex method to a transportation problem, in: Activity Analysis of Production and Allocation, Cowles Commission Monograph No. 13 (1951) 359–373.Google Scholar
  6. G. B. Dantzig: Linear Programming and Extensions, Princeton University Press, Princeton (1963).https://doi.org/10.1515/9781400884179Google Scholar
  7. A. V. Fiacco, G. P. McCormick: Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York (1968).Google Scholar
  8. P. Huard: Resolution of mathematical programming with nonlinear constraints by the method of centers, in: it Nonlinear Programming, J. Abadie (ed.), North-Holland, Amsterdam (1967) 209–219.Google Scholar
  9. N. Karmarkar: A new polynomial time algorithm for linear programming, Combinatorica 4 (1984) 373–395.https://doi.org/10.1007/BF02579150Google Scholar
  10. L. G. Khachiyan: A polynomial algorithm in linear programming, Dokl. Akad. Nauk SSSR 244/5 (1979) 1093–1096.Google Scholar
  11. V. Klee, G. J. Minty: How good is the simplex algorithm?, in: Inequalities III, Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles 1969, Academic Press, New York (1972) 159–175.Google Scholar
  12. N. Megiddo: Pathways to the optimal set in linear programming, in: Progress in Mathematical Programming, Springer, New York (1989) 131–158.https://doi.org/10.1007/978-1-4613-9617-8_8Google Scholar
  13. R. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  14. C. Roos, T. Terlaky, J. P. Vial: Interior Point Methods for Linear Optimization, Springer, New York (2006).Google Scholar
  15. R. J. Vanderbei: Linear Programming – Foundations and Extensions, International Series in Operations Research and Management Science, vol. 196, 4th ed., Springer, New York (2014).https://doi.org/10.1007/978-1-4614-7630-6Google Scholar
  16. S. J. Wright: Primal-Dual Interior-Point Methods, Society for Industrial and Applied Mathematics, Philadelphia (1997).https://doi.org/10.1137/1.9781611971453Google Scholar

Suggested citation

M. Bessenyei, N. Tóth. “A Convex Analysis View of the Barrier Problem.” Journal of Convex Analysis 29 (2022), No. 3, 827–836. https://doi.org/10.68381/jca29048

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2022. Rights now held by Banach Press LLC.