nach oben

Journal of Applied Mathematics and Computing

Erschienen in:

01.06.2016 | Original Research

A wide neighborhood infeasible-interior-point method with arc-search for linear programming

verfasst von: Ximei Yang, Yinkui Zhang, Hongwei Liu

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

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 an arc-search infeasible-interior-point method for linear programming. The proposed algorithm is based on a wide neighborhood of the central path and searches the optimizers along the ellipses that approximate the entire the central path. We also establish polynomial complexity of the proposed algorithm. Finally, numerical experiments show that the proposed algorithm is efficient and reliable.

Vorheriger Artikel Matrix method based on the second kind Chebyshev polynomials for solving time fractional diffusion-wave equations

Nächster Artikel Modeling sheep brucellosis transmission with a multi-stage model in Changling County of Jilin Province, China

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

Ai, W.: Neighborhood-following algorithms for linear programming. Sci. China Ser. A 47, 812–820 (2004)MathSciNetCrossRefMATH

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

Anstreicher, K., Bosch, R.: A new infinity-norm path following algorithm for linear programming. SIAM J. Optim. 5, 236–246 (1995)MathSciNetCrossRefMATH

Browne, S., Dongarra, J., Grosse, E., Rowan, T.: The netlib mathematical software repository. Corporation for National Research Initiatives (1995)

Hung, P., Ye, Y.: An asymptotical \(O(\sqrt{n}L)\)-iteration path-following linear programming algorithm that use wide neighborhoods. SIAM J. Optim. 6, 570–586 (1996)MathSciNetCrossRefMATH

Jansen, B., Roos, C., Terlaky, T.: Improved complexity using higher-order correctors for primal-dual Dikin affine scaling. Math. Program. 76, 117–130 (1996)MathSciNetMATH

Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 373–393 (1984)MathSciNetCrossRefMATH

Lustig, I.J.: Feasible issues in a primal-dual interior-point method. Math. Program. 67, 145–162 (1990)MathSciNetCrossRefMATH

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

10.

Mizuno, S.: Polynomiality of infeasible-interior-point algorithms for linear programming. Math. Program. 67, 109–119 (1994)MathSciNetCrossRefMATH

11.

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

12.

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

13.

Monteiro, R.D., Adler, I., Resende, M.G.: A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. Math. Oper. Res. 15, 191–214 (1990)MathSciNetCrossRefMATH

14.

Nesterov, Y.: Long-step strategies in interior-point primal-dual methods. Math. Program. 76, 47–94 (1996)MathSciNetMATH

15.

Potra, F.: An infeasible-interior-point predictor-corrector algorithm for linear programming. SIAM J. Optim. 6, 19–32 (1996)MathSciNetCrossRefMATH

16.

Roos, C., Terlarky, T., Vial, J.P.: Theory and algorithms for linear optimization: an interior-point approach. Springer, New York (2006)

17.

Tanabe, K.: Centered newton method for linear programming: interior and ‘exterior’ point method. New Methods Linear Program. 3, 98–100 (1990). (in janpanese)

18.

Tian, D.G.: An entire space polynomial-time algorithm for linear programming. J. Glob. Optim. 58, 109–135 (2014)MathSciNetCrossRefMATH

19.

Tian, D.G.: An exterior point polynomial-time algorithm for convex quadratic programming. Comput. Optim. Appl., 1–28 (2014)

20.

Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM Publications, Philsdephia (1997)CrossRefMATH

21.

Yang, Y.: Arc-search path-following interior-point algorithms for linear programming. Optim. Online (2009)

22.

Yang, Y.: A polynomial arc-search interior-point algorithm for convex quadratic programming. Eur. J. Oper. Res. 215, 25–38 (2011)MathSciNetCrossRefMATH

23.

Yang, Y.: A polynomial arc-search interior-point algorithm for linear programming. J. Optim. Theory Appl. 158, 859–873 (2013)MathSciNetCrossRefMATH

24.

Yang, Y.: Arc-Search Infeasible Interior-Point Algorithm for Linear Programming. arXiv preprint arXiv:1406.4539 (2014)

25.

Zhang, Y., Zhang, D.: On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms. Math. Program. 68, 303–318 (1995)MathSciNetCrossRefMATH

26.

Zhang, Y.: On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J. Optim. 4, 208–227 (1994)MathSciNetCrossRefMATH

Titel: A wide neighborhood infeasible-interior-point method with arc-search for linear programming
verfasst von: Ximei Yang
Yinkui Zhang
Hongwei Liu
Publikationsdatum: 01.06.2016
Verlag: Springer Berlin Heidelberg
Erschienen in: Journal of Applied Mathematics and Computing / Ausgabe 1-2/2016
Print ISSN: 1598-5865
Elektronische ISSN: 1865-2085
DOI: https://doi.org/10.1007/s12190-015-0900-z

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/2016

Positive solutions for a second order boundary value problem on time scales

Critical curves and non-extinction conditions for a 2-dimensional non-Newtonian polytropic filtration equations coupled via nonlinear boundary flux

Existence results for boundary value problems of fractional functional differential equations with delay

Nonmonotone smoothing inexact Newton method for the nonlinear complementarity problem

Dynamics of a periodic switched predator–prey system with hibernation, birth pulse and impulsive harvesting

Application of two-dimensional hat functions for solving space-time integral equations