nach oben

Optimization and Engineering

Erschienen in:

02.06.2020 | Research Article

A generic kernel function for interior point methods

verfasst von: S. Fathi-Hafshejani, Z. Moaberfard

Erschienen in: Optimization and Engineering | Ausgabe 1/2021

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, a new class of kernel functions is introduced. We show that most existing kernel functions belong to this class. All functions in the new class are eligible in the sense of Bai et al. (SIAM J Optim 15(1):101–128, 2004), and hence the analysis of the resulting interior-point methods can follow the scheme proposed in Bai et al. (2004). We introduce five new kernel functions and by using this scheme we show that primal-dual IPMs based on these functions enjoy the best known iteration bound for large-update methods, i.e., \(O(\sqrt{n}\log n\log \frac{n}{\epsilon }).\) Finally, to demonstrate the efficiency of IPMs based on the new kernel functions, some numerical results are provided.

Vorheriger Artikel Automatic repair of convex optimization problems

Nächster Artikel A new primal-dual interior-point method for semidefinite optimization based on a parameterized kernel function

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

Nur mit Berechtigung zugänglich

Amini K, Peyghami MR (2006) Complexity analysis of interior-point methods for linear optimization based on some conditions on kernel function. Appl Math Comput 176:194–207MathSciNetMATH

Bai YQ, El Ghami M, Roos C (2004) A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J Optim 15(1):101–128MathSciNetCrossRef

Bai YQ, El Ghami M, Roos C (2003) A new efficient large-updat primal-dual interior-point method based on a finite barrier. SIAM J Optim 13(3):766–782CrossRef

Bouafia M, Benterki D, Yassine A (2016) An efficient primal-dual interior point method for linear programming problems based on a new kernel function with a trigonometric barrier term. J Optim Theory Appl 170(2):528–545MathSciNetCrossRef

Cai XZ, Wang GQ, El Ghami M, Yue YJ Complexity analysis of primal-dual interior-point methods for linear optimization based on a new parametric kernel function with a trigonometric barrier term. Abstr Appl Anal (2014). https://doi.org/10.1155/2014/710158

El Ghamia M, Ivanov I, Melissen JBM, Roos C, Steihaug T (2009) A polynomial-time algorithm for linear optimization based on a new class of kernel functions. J Comput Appl Math 224:500–513MathSciNetCrossRef

El Ghami M, Guennoun ZA, Boula S, Steihaug T (2012) Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term. J Comput Appl Math 236:3613–3623MathSciNetCrossRef

Fathi-Hafshejani S, Fakharzadeh JA, Peyghami MR (2018) A unified complexity analysis of interior point methods for semidefinite problems based on trigonometric kernel functions. Optimization 67(1):113–137MathSciNetCrossRef

Fathi-Hafshejani S, Mansouri H, Peyghami MR (2016) A large-update primal-dual interior-point algorithm for second-order cone optimization based on a new proximity function. Optimization 65(7):1477–1496MathSciNetCrossRef

Fathi-Hafshejani S, Fatemi M, Peyghami MR (2015) An interior-point method for P_*(κ)-linear complementarity problem based on a trigonometric kernel function. J Appl Math Comput 48:111–128MathSciNetCrossRef

Güler O (1994) Limiting behavior of the weighted central paths in linear programming. Math Program 65:347–363MathSciNetCrossRef

Karmarkar NK (1984) A new polynomial-time algorithm for linear programming. In: Proceedings of the 16th annual ACM symposium on theory of computing, pp 302–311

Kheirfam B (2012) Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term. Numer Algorithms 61:659–680MathSciNetCrossRef

Kheirfam B (2017) A primal-dual interior-point algorithm for symmetric optimization based on a new kernel function with trigonometric barrier term yielding the best known iteration bounds. Afr Mat 28:389–406MathSciNetCrossRef

Kojima M, Mizuno S, Yoshise A (1989) A primal-dual interior point algorithm for linear programming. In: Megiddo N (ed) Progress in mathematical programming: interior point and related methods. Springer, New York, pp 29–47CrossRef

Lee YH, Cho YY, Cho GM (2014) Interior-point algorithms for P_*(κ)-LCP based on a new class of kernel functions. J Glob Optim 58:137–149MathSciNetCrossRef

Lesaja G, Roos C (2010) Unified analysis of kernel-based interior-point methods for P_*(κ)-linear complementarity problems. SIAM J Optim 20:3014–3039MathSciNetCrossRef

Li X, Zhang M, Chen Y (2017) An interior-point algorithm for P_*(κ)-LCP based on a new trigonometric kernel function with a double barrier term. J Appl Math Comput 53:487–506MathSciNetCrossRef

Li X, Zhang M (2015) Interior-point algorithm for linear optimization based on a new trigonometric kernel function. Oper Res Lett 43:471–475MathSciNetCrossRef

Liu Y, Bai YQ (2009) 13(2):95–101

Megiddo N (1989) Pathways to the optimal set in linear programming. In: Megiddo N (ed) Progress in mathematical programming: interior point and related methods. Springer, New York, pp 131–158CrossRef

Meszaros CS (1999) Steplengths in interior-point algorithms of quadratic programming. Oper Res Lett 213:39–45MathSciNetCrossRef

Monteiro RDC, Adler I (1989) Interior-point path following primal-dual algorithms: Part I: linear programming. Math Program 44:27–41CrossRef

Nesterov YE, Nemirovskii AS (1994) Interior point polynomial algorithms in convex programming. In: SIAM studies in applied mathematics, vol 13, SIAM, Philadelphia, PA

Peng J, Roos C, Terlaky T (2002) Self-eegularity a new paradigm for primal-dual interior-point algorithms. Princeton University Press, PrincetonMATH

Peyghami MR, Fathi-Hafshejani S (2014) Complexity analysis of an interior-point algorithm for linear optimization based on a new poriximity function. Numer Algorithms 67:33–48MathSciNetCrossRef

Peyghami MR, Fathi-Hafshejani S, Shirvani L (2014) Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function. J Comput Appl Math 255:74–85MathSciNetCrossRef

Peyghami MR, Fathi-Hafshejani S, Chen S (2016) A prima dual interior-point method for semidefinite optimization based on a class of trigonometric barrier functions. Oper Res Lett 44:319–323MathSciNetCrossRef

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

Sonnevend G (1986) An analytic center for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In: Prakopa A, Szelezsan J, Strazicky B (eds) Lecture Notes in Control and Information Sciences, vol 84. Springer, Berlin, pp 866–876

Titel: A generic kernel function for interior point methods
verfasst von: S. Fathi-Hafshejani
Z. Moaberfard
Publikationsdatum: 02.06.2020
Verlag: Springer US
Erschienen in: Optimization and Engineering / Ausgabe 1/2021
Print ISSN: 1389-4420
Elektronische ISSN: 1573-2924
DOI: https://doi.org/10.1007/s11081-020-09512-z

Premium Partner

Marktübersichten

Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.

Zur Marktübersicht

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"

Weitere Artikel der Ausgabe 1/2021

How to catch a lion in the desert: on the solution of the coverage directed generation (CDG) problem

A strongly convergent Mann-type inertial algorithm for solving split variational inclusion problems

Control trajectory optimisation and optimal control of an electric vehicle HVAC system for favourable efficiency and thermal comfort

Automatic repair of convex optimization problems

A preface to the special issue of optimization and engineering dedicated to SDEWES 2019 conference

Bilevel programming solution algorithms for optimal price-bidding of energy producers in multi-period day-ahead electricity markets with non-convexities

Premium Partner

Marktübersichten