nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

5. Interior-Point Methods

verfasst von : David G. Luenberger, Yinyu Ye

Erschienen in: Linear and Nonlinear Programming

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Linear programs can be viewed in two somewhat complementary ways. They are, in one view, a class of continuous optimization problems each with continuous variables defined on a convex feasible region and with a continuous objective function. They are, therefore, a special case of the general form of problem considered in this text. However, linearity implies a certain degree of degeneracy, since for example the derivatives of all functions are constants and hence the differential methods of general optimization theory cannot be directly used. From an alternative view, linear programs can be considered as a class of combinatorial problems because it is known that solutions can be found by restricting attention to the vertices of the convex polyhedron defined by the constraints. Indeed, this view is natural when considering network problems such as those of early chapters. However, the number of vertices may be large, up to \(n!/m!(n - m)\) !, making direct search impossible for even modest size problems.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Duality and Complementarity

Nächstes Kapitel Conic Linear Programming

We will be more precise about complexity notions such as “polynomial algorithm” in Sect. 5.1 below.

The (topological) interior of any set Ω is the set of points in Ω which are the centers of some balls contained in Ω.

Assumption (A2) is sometimes too strong. It has been shown, however, that when the data consists of integers, it is possible to perturb the problem so that (A2) is satisfied and if the perturbed problem has a feasible solution, so does the original Ω.

The symbol \(\emptyset\) denotes the empty set.

[A5]

E.D. Andersen, Y. Ye, On a homogeneous algorithm for the monotone complementarity problem. Math. Prog. 84, 375–400 (1999)CrossRef

[B3]

D.A., Bayer, J.C. Lagarias, The nonlinear geometry of linear programming, part i: affine and projective scaling trajectories. Trans. Am. Math. Soc 314(2), 499–526 (1989)

[B4]

D.A. Bayer, J.C. Lagarias, The nonlinear geometry of linear programming, part ii: legendre transform coordinates. Trans. Am. Math. Soc. 314(2), 527–581 (1989)

[B6]

M.S. Bazaraa, J.J. Jarvis, H.F. Sherali, Karmarkar’s projective algorithm (Chap. 8.4), pp. 380–394; Analysis of Karmarkar’s algorithm (Chap. 8.5), pp. 394–418, in Linear Programming and Network Flows, 2nd edn. (Wiley New York, 1990)

[B12]

D.P. Bertsekas, Nonlinear Programming (Athena Scientific, Belmont, 1995)

[B13]

D.M. Bertsimas, J.N. Tsitsiklis, Linear Optimization (Athena Scientific, Belmont, 1997)

[B18]

R.E. Bixby, Progress in linear programming. ORSA J. Comput. 6(1), 15–22 (1994)CrossRef

[B20]

R.G. Bland, D. Goldfarb, M.J. Todd, The ellipsoidal method: a survey. Oper. Res. 29, 1039–1091 (1981)CrossRef

[B21]

L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation (Springer, New York, 1996)

[C5]

S.A. Cook, The complexity of theorem-proving procedures, in Proceedings of 3rd ACM Symposium on the Theory of Computing, 1971, pp. 151–158

[C6]

R.W. Cottle, Linear Programming. Lecture Notes for MS& E 310 (Stanford University, Stanford, 2002)

[C7]

R. Cottle, J.S. Pang, R.E. Stone, Interior-Point Methods (Chap. 5.9), in The Linear Complementarity Problem (Academic, Boston, 1992), pp. 461–475

[D9]

G.B. Dantzig, M.N. Thapa, Linear Programming 1: Introduction (Springer, New York, 1997)

[D10]

G.B. Dantzig, M.N. Thapa, Linear Programming 2: Theory and Extensions (Springer, New York, 2003)

[F2]

S.C. Fang, S. Puthenpura, Linear Optimization and Extensions (Prentice-Hall, Englewood Cliffs, NJ, 1994)

[F18]

R.M. Freund, Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function. Math. Program. 51, 203–222 (1991)CrossRef

[F19]

K.R. Frisch, The logarithmic potential method for convex programming. Unpublished Manuscript, Institute of Economics, University of Oslo, Oslo (1955)

[G5]

P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin, M.H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method. Math. Program. 36, 183–209 (1986)CrossRef

[G11]

D. Goldfarb, D. Xiao, A primal projective interior point method for linear programming. Math. Program. 51, 17–43 (1991)CrossRef

[G13]

C.C. Gonzaga, An algorithm for solving linear programming problems in O(n ³ L) operations, in Progress in Mathematical Programming: Interior Point and Related Methods, ed. by N. Megiddo (Springer, New York, 1989), pp. 1–28CrossRef

[G14]

C.C. Gonzaga, M.J. Todd, An \(O(\sqrt{n}L)\)-iteration large-step primal-dual affine algorithm for linear programming. SIAM J. Optim. 2, 349–359 (1992)CrossRef

[H5]

J. Hartmanis, R.E. Stearns, On the computational complexity of algorithms. Trans. Am. Math. Soc. 117, 285–306 (1965)CrossRef

[H6]

D. den Hertog, Interior point approach to linear, quadratic and convex programming, algorithms and complexity, Ph.D. thesis, Faculty of Mathematics and Informatics, TU Delft, BL Delft, 1992

[H12]

P. Huard, Resolution of mathematical programming with nonlinear constraints by the method of centers, in Nonlinear Programming, ed. by J. Abadie (North Holland, Amsterdam, 1967), pp. 207–219

[K2]

N.K. Karmarkar, A new polynomial-time algorithm for linear programming. Combinatorica 4, 373–395 (1984)CrossRef

[K4]

L.G. Khachiyan, A polynomial algorithm for linear programming. Doklady Akad. Nauk USSR 244, 1093–1096 (1979). Translated in Soviet Math. Doklady 20, 191–194 (1979)

[K5]

V. Klee, G.J. Minty, How good is the simplex method, in Inequalities III, ed. by O. Shisha (Academic, New York, 1972)

[K6]

M. Kojima, S. Mizuno, A. Yoshise, A polynomial-time algorithm for a class of linear complementarity problems. Math. Program. 44, 1–26 (1989)CrossRef

[K7]

M. Kojima, S. Mizuno, A. Yoshise, An \(O(\sqrt{n}L)\) iteration potential reduction algorithm for linear complementarity problems. Math. Program. 50, 331–342 (1991)CrossRef

[L18]

Z.Q. Luo, J. Sturm, S. Zhang, Conic convex programming and self-dual embedding. Optim. Methods Softw. 14, 169–218 (2000)CrossRef

[L19]

I.J. Lustig, R.E. Marsten, D.F. Shanno, On implementing mehrotra’s predictor-corrector interior point method for linear programming. SIAM J. Optim. 2, 435–449 (1992)CrossRef

[M3]

L. McLinden, The analogue of Moreau’s proximation theorem, with applications to the nonlinear complementarity problem. Pac. J. Math. 88, 101–161 (1980)CrossRef

[M4]

N. Megiddo, Pathways to the optimal set in linear programming, in Progress in Mathematical Programming: Interior Point and Related Methods, ed. by N. Megiddo (Springer, New York, 1989), pp. 131–158CrossRef

[M5]

S. Mehrotra, On the implementation of a primal-dual interior point method. SIAM J. Optim. 2(4), 575–601 (1992)CrossRef

[M6]

S. Mizuno, M.J. Todd, Y. Ye, On adaptive step primal-dual interior point algorithms for linear programming. Math. Oper. Res. 18, 964–981 (1993)CrossRef

[M7]

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

[M12]

K.G. Murty, The Karmarkar’s algorithm for linear programming (Chap. 11.4.1), in Linear Complementarity, Linear and Nonlinear Programming. Sigma Series in Applied Mathematics, vol. 3 (Heldermann Verlag, Berlin, 1988), pp. 469–494

[N1]

S.G., Nash, A. Sofer Linear and Nonlinear Programming (McGraw-Hill Companies, New York, 1996)

[N2]

Y. Nesterov, A. Nemirovskii, Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms (SIAM Publications, Philadelphia, 1994)CrossRef

[P2]

C. Papadimitriou, K. Steiglitz, Combinatorial Optimization Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, NJ, 1982)

[R1]

J. Renegar, A polynomial-time algorithm, based on Newton’s method, for linear programming. Math. Program. 40, 59–93 (1988)CrossRef

[R2]

J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization (Society for Industrial and Applied Mathematics, Philadelphia, 2001)CrossRef

[R4]

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

[S1]

R. Saigal, Linear Programming: Modern Integrated Analysis (Kluwer Academic Publisher, Boston, 1995)CrossRef

[S8]

G. Sonnevend, An ‘analytic center’ for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, in System Modelling and Optimization: Proceedings of the 12th IFIP-Conference held in Budapest, Hungary, September 1985, ed. by A. Prekopa, J. Szelezsan, B. Strazicky. Lecture Notes in Control and Information Sciences, vol. 84 (Springer, Berlin, 1986), pp. 866–876

[S11]

J.F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11&12, 625–633 (1999)

[T2]

K. Tanabe, Complementarity-enforced centered Newton method for mathematical programming, in New Methods for Linear Programming, ed. by K. Tone (The Institute of Statistical Mathematics, Tokyo, 1987), pp. 118–144

[T4]

M.J. Todd, A low complexity interior point algorithm for linear programming. SIAM J. Optim. 2, 198–209 (1992)CrossRef

[T5]

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

[T10]

L. Tunçel, Constant potential primal-dual algorithms: a framework. Math. Prog. 66, 145–159 (1994)CrossRef

[T11]

R. Tutuncu, An infeasible-interior-point potential-reduction algorithm for linear programming, Ph.D. thesis, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1995

[V1]

P.M. Vaidya, An algorithm for linear programming which requires \(O((m + n)n^{2} + (m + n)^{1.5}nL)\) arithmetic operations. Math. Prog. 47, 175–201 (1990). Condensed version in: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 29–38

[V3]

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

[V4]

S.A. Vavasis, Nonlinear Optimization: Complexity Issues (Oxford Science, New York, NY, 1991)

[W8]

S.J. Wright, Primal-Dual Interior-Point Methods (SIAM, Philadelphia, 1996)

[Y1]

Y. Ye, An O(n ³ L) potential reduction algorithm for linear programming. Math. Program. 50, 239–258 (1991)CrossRef

[Y2]

Y. Ye, M.J. Todd, S. Mizuno, An \(O(\sqrt{n}L)\)-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19, 53–67 (1994)CrossRef

[Y3]

Y. Ye, Interior Point Algorithms (Wiley, New York, 1997)CrossRef

[269]

Y. Ye, A new complexity result on solving the markov decision problem. Math. Oper. Res. 30, 733–749 (2005)CrossRef

[Z3]

Y. Zhang, D. Zhang, On polynomiality of the mehrotra-type predictor-corrector interior-point algorithms. Math. Program. 68, 303–317 (1995)CrossRef

Titel: Interior-Point Methods
verfasst von: David G. Luenberger
Yinyu Ye
Verlag: Springer International Publishing
Buch: Linear and Nonlinear Programming
Print ISBN: 978-3-319-18841-6

Electronic ISBN: 978-3-319-18842-3

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-18842-3_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"