Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2017 | OriginalPaper | Chapter

17. Interior Point Methods

Author : Neculai Andrei

Published in: Continuous Nonlinear Optimization for Engineering Applications in GAMS Technology

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

One of the most powerful methods for solving nonlinear optimization problems known as interior point methods is to be presented in this chapter. They are related to barrier functions. The terms “interior point methods” and “barrier methods” have the same significance and may be used interchangeably. The idea is to keep the current points in the interior of the feasible region. A method for remaining in the interior of the feasible region is to add a component to the objective function, which penalizes close approaches to the boundary. This method was first suggested by Frisch 1955 and developed both in theoretical and computational details by Fiacco and McCormick (1964, 1966, 1968).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Generalized Reduced Gradient with Sequential Linearization: CONOPT
next chapter Filter Methods
Footnotes
1
By homotopy method we understand a continuously tranformation of a mathematical object into another one, in the sense that a simple (easy) problem can be continuously deformed into the given (hard) problem (Henri Poincaré). The solutions to the deformed problems are related and can be tracked as the deformation proceeds. The function describing the deformation is called a homotopy map.
 
Literature
Andrei, N. (1996a). Computational experience with a modified penalty-barrier method for large-scale nonlinear constrained optimization. (Working Paper No. AMOL-96-1, Research Institute for Informatics-ICI, Bucharest, February 6, 1996).
Andrei, N. (1996b). Computational experience with a modified penalty-barrier method for large-scale nonlinear, equality and inequality constrained optimization. (Technical Paper No. AMOL-96-2, Research Institute for Informatics-ICI, Bucharest, February 12, 1996).
Andrei, N. (1996c). Computational experience with “SPENBAR” a sparse variant of a modified penalty-barrier method for large-scale nonlinear, equality and inequality, constrained optimization. (Working Paper No. AMOL-96-3, Research Institute for Informatics-ICI, Bucharest, March 10, 1996).
Andrei, N. (1996d). Computational experience with “SPENBAR” a sparse variant of a modified penalty-barrier method for large-scale nonlinear, equality and inequality, constrained optimization. (Technical Paper No. AMOL-96-4, Research Institute for Informatics-ICI, Bucharest, March 11, 1996).
Andrei, N. (1996e). Numerical examples with “SPENBAR”for large-scale nonlinear, equality and inequality, constrained optimization with zero columns in Jacobian matrices. (Technical Paper No. AMOL-96-5, Research Institute for Informatics-ICI, Bucharest, March 29, 1996).
Andrei, N. (1998c). An interior point algorithm for nonlinear programming. Studies in Informatics and Control, 7(4), 365–395.
Andrei, N. (2009). Critica Raţiunii Algoritmilor de Optimizare fără Restricţii. [Criticism of the Unconstrained Optimization Algorithms Reasoning]. Editura Academiei Române, Bucureşti.
Andrei, N. (2011a) Critica raţiunii algoritmilor de programare liniară. [Criticism of the Linear Programming Algorithms Reasoning]. Editura Academiei Române, Bucureşti.
Andrei, N. (2015). Critica Raţiunii Algoritmilor de Optimizare cu Restricţii. [Criticism of the Constrained Optimization Algorithms Reasoning]. Bucureşti, Balkans: Editura Academiei Române
Bunch J. W., & Kaufman, L. (1977). Indefinite quadratic programming. (Computing Science Technical Report 61, Bell Labs., Murray Hill, NJ).
Bunch, J. R., & Parlett, B. N. (1971). Direct methods for solving symmetric indefinite systems of linear equations. SIAM Journal on Numerical Analysis, 8, 639–655.MathSciNetCrossRefMATH
Byrd, R. H., Hribar, M. E., & Nocedal, J. (1999). An interior point method for large scale nonlinear programming. SIAM Journal on Optimization, 9, 877–900.MathSciNetCrossRefMATH
Cheng, S. H. (1998). Symmetric indefinite matrices: Linear system solvers and modified inertia problems. Ph.D. Thesis. University of Mancester. Faculty of Science and Engineering. January 1998.
Cheng, S. H., & Higham, N. J. (1998). A modified Cholesky algorithm based on a symmetric indefinite factorization. SIAM Journal on Matrix Analysis and Applications, 19, 1097–1110.MathSciNetCrossRefMATH
Conn, A. R., Gould, N. I. M., & Toint, P. L. (2000). Trust-region methods. Philadelphia, PA, USA: MPS-SIAM Series on Optimization, SIAM.CrossRefMATH
Dennis, J. E., Jr., & Schnabel, R. B. (1983). Numerical methods for unconstrained optimization and nonlinear equations. Englewoods Cliffs, NJ, USA: Prentice-Hall.MATH
Dikin, I. I. (1967). Iterative solution of problems of linear and quadratic programming. Soviet Mathematical Doklady, 8, 674–675.MathSciNetMATH
Dikin, I. I. (1974). On the convergence of an iterative process. Upravlyaemye Sistemi, 12, 54–60.MATH
El-Bakry, A. S., Tapia, R. A., Tsuchiya, T., & Zhang, Y. (1996). On the formulation and theory of the Newton interior-point method for nonlinear programming. Journal of Optimization Theory and Applications, 89(3), 507–541.MathSciNetCrossRefMATH
Fiacco, A. V., & McCormick, G. P. (1964). The sequential unconstrained minimization technique for nonlinear programming. A primal-dual method. Management Science, 10, 360–366.
Fiacco, A. V., & McCormick, G. P. (1966). Extensions of SUMT for nonlinear programming: equality constraints and extrapolation. Management Science, 12, 816–828.MathSciNetCrossRefMATH
Fiacco, A. V., & McCormick, G. P. (1968). Nonlinear programming. Sequential unconstrained minimization techniques. John Wiley & Sons, Inc., New York, 1968. [Reprinted as: Volume 4 of SIAM Classics in Applied Mathematics. SIAM Publications, Philadelphia, PA 19104–2688, 1990].
Fletcher, R., & Leyffer, S. (2002). Nonlinear programming without a penalty function. Mathematical Programming, Series A, 91, 239–269.MathSciNetCrossRefMATH
Frisch, K. R. (1955). The logarithmic potential method for convex programming. (Manuscript. Institute of Economics, University of Oslo, Oslo, May 1955.)
Gay, D. M., Overton, M. L., & Wright, M. H. (1997). A primal-dual interior method for nonconvex nonlinear programming. (Technical Report 97–4-08, Bell Lab. Murray Hill, July 29, 1997).
Goldfarb, D., Liu, S., & Wang, S. (1991). A logarithmic barrier function algorithm for quadratically constrained convex quadratic programming. SIAM Journal on Optimization, 1(2), 252–267.MathSciNetCrossRefMATH
Gould, N. I. M., Orban, D., & Toint, P. L. (2005a). Numerical methods for large-scale nonlinear optimization. Acta Numerica, 14, 299–361.MathSciNetCrossRefMATH
Hock, W., & Schittkowski, K. (1981). Test examples for nonlinear programming codes, Lecture notes in economics and mathematical systems (vol. 187). Berlin, Europe: Springer.MATH
Kortanek, K. O., Potra, F. A., & Ye, Y. (1991). On some efficient interior point methods for nonlinear convex programming. Linear Algebra and its Applications, 152, 169–189.MathSciNetCrossRefMATH
Liu, D. C., & Nocedal, J. (1989). On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45, 503–528.MathSciNetCrossRefMATH
Lustig, I. J., Marsten, R. E., & Shanno, D. F. (1990). The primal-dual interior point method on the Cray supercomputer. In T. F. Coleman & Y. Li (Eds.), Large-scale numerical optimization (pp. 70–80). Philadelphia, PA, USA: SIAM.
Lustig, I. J., Marsten, R. E., & Shanno, D. F. (1991). Computational experience with a primal-dual interior point method for linear programming. Linear Algebra and its Applications, 152, 191–222.MathSciNetCrossRefMATH
Lustig, I. J., Marsten, R. E., & Shanno, D. F. (1992). On implementing Mehrotra's predictor-corrector interior-point method for linear programming. SIAM Journal on Optimization, 2(3), 435–449.MathSciNetCrossRefMATH
Lustig, I. J., Marsten, R. E., & Shanno, D. F. (1994). Computational experience with a globally convergent primal-dual predictor-corrector algorithm for linear programming. Mathematical Programming, 66, 123–135.MathSciNetCrossRefMATH
Nocedal, J., & Wright, S. J. (2006). Numerical optimization, Springer series in operations research (2nd ed.). New York, NY, USA: Springer Science+Business Media.MATH
Shanno, D. F. (2012). Who invented the interior-point method? In: Grötschel, M. (Ed.) Optimization stories (pp. 55–64). Documenta Mathematica, Journal der Deutschen Methematiker-Vereinigung, Extra volume, 21st International Symposium on Mathematical Programming, Berlin, August 19–24, 2012.
Shanno, D. F., & Simantiraki, E. M. (1997). Interior-point methods for linear and nonlinear programming. In I. S. Duff & G. A. Watson (Eds.), The state of the art in numerical analysis (pp. 339–362). New York, NY, USA: Oxford University Press.
Shanno, D. F., Breitfeld, M. G., & Simantiraki, E. M. (1996). Implementing barrier methods for nonlinear programming. In T. Terlaky (Ed.), Interior point methods of mathematical programming (pp. 399–414). Dordrecht, Europe: Kluwer Academic Publishers.CrossRef
Sun, W., & Yuan, Y. X. (2006). Optimization theory and methods. Nonlinear programming. New York, NY, USA: Springer Science + Business Media.MATH
Ulbrich, M., Ulbrich, S., & Vicente, L. N. (2004). A globally convergent primal-dual interior-point filter method for nonconvex nonlinear programming. Mathematical Programming, 100, 379–410.MathSciNetCrossRefMATH
Vanderbei, R. J. (1990). ALPO: Another linear program optimizer. (Technical Report AT&T Bell Laboratories).
Vanderbei, R. J. (1994). An interior point code for quadratic programming. (Technical Report SOR 94–15, Princeton University).
Vanderbei, R. J. (1995). LOQO: An interior point code for quadratic programming. (Technical Report SOR 94–15, Princeton University).
Vanderbei, R. J. (2001). Linear programming: Foundations and extensions (2nd ed.). New York, NY, USA: Springer.CrossRefMATH
Vanderbei, R. J., & Shanno, D. F. (1997). An interior-point algorithm for nonconvex nonlinear programming. (Technical Report SOR 97–21, Princeton University).
Wächter, A., & Biegler, L. T. (2005a). Line search filter methods for nonlinear programming: Motivation and global convergence. SIAM Journal on Optimization, 16, 1–31.MathSciNetCrossRefMATH
Wächter, A., & Biegler, L. T. (2005b). Line search filter methods for nonlinear programming: Local convergence. SIAM Journal on Optimization, 16, 32–48.MathSciNetCrossRefMATH
Wächter, A., & Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, 106, 25–57.MathSciNetCrossRefMATH
Metadata
Title
Interior Point Methods
Author
Neculai Andrei
Copyright Year
2017
Book
Continuous Nonlinear Optimization for Engineering Applications in GAMS Technology

Print ISBN: 978-3-319-58355-6

Electronic ISBN: 978-3-319-58356-3

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-58356-3_17