Top

Numerical Algorithms

Published in:

31-05-2019 | Original Paper

An arc-search predictor-corrector infeasible-interior-point algorithm for P_∗(κ)-SCLCPs

Authors: M. Sayadi Shahraki, A. Delavarkhalafi

Published in: Numerical Algorithms | Issue 4/2020

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 arc-search predictor-corrector infeasible-interior-point algorithm for linear complementarity problems over symmetric cones with the Cartesian P_∗(κ)-property (P_∗(κ)-SCLCP). 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. The algorithm uses a commutative class of search directions, which includes the Nesterov-Todd direction and the xs and sx directions. To the best of our knowledge, this is using a new strategy in the complexity analysis; we improve the theoretical complexity bound of an arc-search infeasible-interior-point method for P_∗(κ)-SCLCP. Some preliminary numerical results are provided to demonstrate the computational performance of the proposed algorithm.

previous article Stationary distribution of the stochastic theta method for nonlinear stochastic differential equations

next article Strong convergence of an extragradient-like algorithm involving pseudo-monotone mappings

Dont have a licence yet? Then find out more about our products and how to get one 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

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

Faybusovich, L.: Linear systems in Jordan algebras and primal-dual interior-point algorithms. J. Comput. Appl. Math. 86, 149–175 (1997)MathSciNetCrossRef

Kojima, M., Shindoh, S., Hara, S.: Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7, 86–125 (1997)MathSciNetCrossRef

Nesterov, Y.E., Todd, M.J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8, 324–364 (1998)MathSciNetCrossRef

Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A unified approach to interior point algorithms for linear complementarity problems. Lecture notes in computer science. Springer, New York (1991)CrossRef

Luo, Z.Y., Xiu, N.H.: Solution existence and boundedness of symmetric cone linear complementarity problems with the Cartesian p_∗(κ)-property. Preprint, Department of Applied Mathematics Beijing Jiaotong University (2007)

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

Ai, W., Zhang, S.: An \({\mathrm {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)MathSciNetCrossRef

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)MathSciNetCrossRef

Sayadi Shahraki, M., Mansouri, H., Zangiabadi, M.: Two wide neighborhood interior-point methods for symmetric cone optimization. Comput. Optim. Appl. 68, 29–55 (2017)MathSciNetCrossRef

10.

Sayadi Shahraki, M., Mansouri, H., Zangiabadi, M., Mahdavi-amiri, N.: A wide neighborhood primal-dual predictor-corrector interior-point method for symmetric cone optimization. Numer. Algor. 78, 535–552 (2018)MathSciNetCrossRef

11.

Yang, X., Liu, H., Zhang, Y.: A new strategy in the complexity analysis of an infeasible-interior-point method for symmetric cone programming. J Optim Theory Appl. 166, 572–587 (2015)MathSciNetCrossRef

12.

Sayadi Shahraki, M., Mansouri, H., Zangiabadi, M.: A predictor-corrector infeasible-interior-point method for the Cartesian P_∗, (κ)-LCP over symmetric cones with \({\mathrm {O}}({\sqrt {\text {cond}(G)}(1+\kappa )^{2}r \varepsilon ^{-1}})\) iteration complexity. Optim 65, 2293–2308 (2016)CrossRef

13.

Yang, Y.: Arc-search path-following interior-point algorithms for linear programming. Optimization, Online. http://www.optimization-online.org/ARCHIVE_CAT/LINSDP/2009.html (2009)

14.

Yang, X., Liu, H., Zhang, Y.: An arc-search infeasible-interior-point method for symmetric optimization in a wide neighborhood of the central path. Optim. Lett. 11, 135–152 (2017)MathSciNetCrossRef

15.

Sayadi Shahraki, M., Mansouri, H., Zangiabadi, M.: A wide neighborhood infeasible-interior-point method with arc-search for P_∗(κ)-SCLCPs. Optim 67, 409–425 (2018)MathSciNetCrossRef

16.

Yang, Y.: Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming. Numer. Algor. 79, 957–992 (2018)MathSciNetCrossRef

17.

Faraut, J., Korányi, A.: Analysis on symmetric cones. Oxford University Press, New York (1994)MATH

18.

Schmieta, S.H., Alizadeh, F.: Extension of primal-dual interior-point algorithms to symmetric cones. Math. Program. 96, 409–438 (2003)MathSciNetCrossRef

19.

Liu, C.: Study on Complexity of Some Interior-Point Algorithms in Conic Programming. Ph.D. Thesis, Xidian University, Chinese (2012)

20.

Luo, Z.Y., Xiu, N.H.: Path-following interior point algorithms for the Cartesian p_∗(κ)-LCP over symmetric cones. Sci. China Ser A: Math. 52, 1769–1784 (2009)MathSciNetCrossRef

21.

Liu, X., Liu, H., Liu, C.: Infeasible Mehrotra-type predictor-corrector interior-point algorithm for the Cartesian p_∗(κ)-LCP over symmetric cones. Numer. Funct. Anal. Optim. 35, 588–610 (2014)MathSciNetCrossRef

22.

Liu, X., Liu, H., Wang, W.: Polynomial convergence of Mehrotra-type predictor-corrector algorithm for the Cartesian P_∗, (κ)-LCP over symmetric cones. Optim 64, 815–837 (2015)MathSciNetCrossRef

Title: An arc-search predictor-corrector infeasible-interior-point algorithm for P∗(κ)-SCLCPs
Authors: M. Sayadi Shahraki
A. Delavarkhalafi
Publication date: 31-05-2019
Publisher: Springer US
Published in: Numerical Algorithms / Issue 4/2020
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI: https://doi.org/10.1007/s11075-019-00736-4

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"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 4/2020

A decoupling two-grid method for the time-dependent Poisson-Nernst-Planck equations

Convergence analysis of positive-indefinite proximal ADMM with a Glowinski’s relaxation factor

Stationary distribution of the stochastic theta method for nonlinear stochastic differential equations

Symbolic-numeric integration of rational functions

Efficient high-order compact exponential time differencing method for space-fractional reaction-diffusion systems with nonhomogeneous boundary conditions

A coercive heterogeneous media Helmholtz model: formulation, wavenumber-explicit analysis, and preconditioned high-order FEM

Premium Partner