nach oben

Journal of Applied Mathematics and Computing

Erschienen in:

21.09.2016 | Original Research

A superlinearly convergent wide-neighborhood predictor–corrector interior-point algorithm for linear programming

verfasst von: Xiaojue Ma, Hongwei Liu

Erschienen in: Journal of Applied Mathematics and Computing | Ausgabe 1-2/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we propose a new predictor-corrector algorithm with superlinear convergence in a wide neighborhood for linear programming problems. We let the centering parameter in a predictor step is chosen adaptively, which is different from other algorithms in the same wide neighborhood. The choice is a key for the local convergence of the new algorithm. In addition, we use the classical affine scaling direction as a part in a corrector step, not in a predictor step, which contributes to the complexity result. We prove that the new algorithm has a polynomial complexity of \(O(\sqrt{n}L)\), and the duality gap sequence is superlinearly convergent to zero, under the assumption that the iterate points sequence is convergent. Finally, numerical tests indicate its effectiveness.

Vorheriger Artikel Stable manifolds results for planar Hadamard fractional differential equations

Nächster Artikel Residual power series method for solving time-space-fractional Benney-Lin equation arising in falling film 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 "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

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

Wright, S.J.: Primal-dual interior-point methods. SIAM, Philadephia (1997)CrossRefMATH

Ye, Y.: Interior Point Algorithms: Theory and Analysis. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1997)

Potra, F.A., Wright, S.J.: Interior-point methods. J. Comput. Appl. Math. 24, 281–302 (2000)MathSciNetCrossRefMATH

Güler, O., Ye, Y.: Convergence behavior of interior-point algorithms. Math. Progr. 60, 215–228 (1993)MathSciNetCrossRefMATH

Zhang, Y., Tapia, R.A., Dennis, J.E.: On the Superlinear and quadratic convergence of primal-dual interior-point linear programming algorithms. SIAM J. Optim. 2, 304–323 (1992)MathSciNetCrossRefMATH

Zhang, Y., Tapia, R.A.: Superlinear and quadratic convergence of primal-dual interior point algorithms for linear programming revisited. J. Optim. Theory Appl. 73, 229–242 (1992)MathSciNetCrossRefMATH

Zhang, Y., Tapia, R.A.: A superlinearly convergent polynomial primal-dual interior-point algorithm for linear programming. SIAM J. Optim. 3, 118–133 (1993)MathSciNetCrossRefMATH

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

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

10.

Roos, C., Peng, J., Terlaky, T.: Self-Regularity: A New Paradigm for Primal–Dual Interior-Point Algorithms. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2002)

11.

Ai, W., Zhang, S.: An \(O(\sqrt{n}L)\) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SIAM J. Optim. 16, 400–417 (2005)MathSciNetCrossRefMATH

12.

Liu, C., Liu, H., Cong, W.: An \(O(\sqrt{n}L)\) iteration primal-dual second-order corrector algorithm for linear programming. Optim. Lett. 5(4), 729–743 (2011)MathSciNetCrossRefMATH

13.

Liu, C., Liu, H., Liu, X.: Polynomial convergence of second-order Mehrotra-type predictor-corrector algorithms over symmetric cones. J. Optim. Theory Appl. 154, 949–965 (2012)MathSciNetCrossRefMATH

14.

Liu, H., Liu, X., Liu, C.: Mehrotra-type predictor-corrector algorithms for sufficient linear complementarity problem. Appl. Numer. Math. 62, 1685–1700 (2012)MathSciNetCrossRefMATH

15.

Liu, H., Yang, X., Liu, C.: A new wide neighborhood primal-dual infeasible interior-point method for symmetric cone programming. J. Optim. Theory Appl. 158, 796–815 (2013)MathSciNetCrossRefMATH

16.

Feng, Z., Fang, L.: A new \(O(\sqrt{n}L)\)-iteration predictor-corrector algorithm with wide neighborhood for semidefinite programming. J. Comput. Appl. Math. 256, 65–76 (2014)MathSciNetCrossRefMATH

17.

Potra, F.A.: Interior point methods for sufficient horizontal LCP in a wide neighborhood of the central path with best known iteration complexity. SIAM J. Optim. 24, 1–28 (2014)MathSciNetCrossRefMATH

18.

Yang, X., Liu, H., Zhang, Y.: A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighborhood for semi-definite programming. Int. J. Comput. Math. 91, 1082–1096 (2014)MathSciNetCrossRefMATH

19.

Zhang, Y.: Solving large-scale linear programs by interior-point methods under the MATLAB environment. Optim. Methods Softw. 10, 1–31 (1999)MathSciNetCrossRefMATH

20.

Zhu X., Peng J., Terlaky T. and Zhang G.: On implementing self-regular proximity based feasible IPMs. Technical report 2003-02-01. http://www.cas.mcmaster.ca/oplab/publication (2003)

21.

Cartis, C.: On the convergence of a primal–dual second-0rder corrector interior point algorithm for linear programming. Transpl. Proc. 41(8), 2949–2951 (2005)

Titel: A superlinearly convergent wide-neighborhood predictor–corrector interior-point algorithm for linear programming
verfasst von: Xiaojue Ma
Hongwei Liu
Publikationsdatum: 21.09.2016
Verlag: Springer Berlin Heidelberg
Erschienen in: Journal of Applied Mathematics and Computing / Ausgabe 1-2/2017
Print ISSN: 1598-5865
Elektronische ISSN: 1865-2085
DOI: https://doi.org/10.1007/s12190-016-1055-2

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 "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1-2/2017

The Wiener index of unicyclic graphs given number of pendant vertices or cut vertices

Dynamics of an impulsive model of plankton allelopathy with delays

Global asymptotic stability of the higher order equation

Status connectivity indices of graphs and its applications to the boiling point of benzenoid hydrocarbons

An algebraic approach to Wiener number

Oscillation criteria for third order neutral Emden–Fowler delay dynamic equations on time scales