Top

Journal of Applied Mathematics and Computing

Published in:

21-09-2016 | Original Research

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

Published in: Journal of Applied Mathematics and Computing | Issue 1-2/2017

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

search-config

AI-assisted search

Off

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.

previous article Stable manifolds results for planar Hadamard fractional differential equations

next article Residual power series method for solving time-space-fractional Benney-Lin equation arising in falling film problems

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

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

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)

Title: A superlinearly convergent wide-neighborhood predictor–corrector interior-point algorithm for linear programming
Publication date: 21-09-2016
Published in: Journal of Applied Mathematics and Computing / Issue 1-2/2017
Print ISSN: 1598-5865
Electronic ISSN: 1865-2085
DOI: https://doi.org/10.1007/s12190-016-1055-2

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1-2/2017

An algebraic approach to Wiener number

Ordering triangular type-2 fuzzy sets with an application to multicriteria decision making problems

Intuitionistic fuzzy soft graphs with applications

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

Existence of solutions for a class of the boundary value problem of fractional q-difference inclusions

On topological properties of hierarchical interconnection networks

Premium Partner