Complexity analysis and numerical implementation of large-update interior-point methods for SDLCP based on a new parametric barrier kernel function. (English) Zbl 1402.90188
Summary: In this paper, we deal with the complexity analysis and the numerical implementation of primal-dual interior-point methods for monotone semidefinite linear complementarity problems based on a new parametric kernel function. The proposed kernel function is neither a self-regular and nor the usual logarithmic barrier function. By means of the feature of the parametric kernel function, we study the complexity analysis of primal-dual IPMs and derive the currently best known iteration bound for the large-update algorithm, namely, \(O(\sqrt{n}\log n\log \frac{n}{\epsilon})\) which is as good as the linear and the semidefinite optimization analogue. Finally, we report some numerical results to show the practical performance of the proposed algorithm with different parameters.
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 90C51 | Interior-point methods |
Keywords:
semidefinite linear complementarity problems; interior-point methods; kernel function; large-step method; iteration boundReferences:
| [1] | Achache, M; Boudiaf, N; Keraghel, A, Le problè me de complémentarité linéaire semi-défini, Rev Anal Numér Théor Approx, 38, 2, 115-129, (2009) · Zbl 1224.90191 |
| [2] | Song, Y, The P and globally uniquely solvable properties in semidefinite linear complementarity problems [Phd thesis], (2000), The University of Maryland, USA |
| [3] | Achache, M, A new primal-dual path-following method for convex quadratic programming, Comput Appl Math, 25, 1, 97-110, (2006) · Zbl 1213.90187 |
| [4] | Achache, M; Guerra, L, A full Nesterov-Todd-step feasible primal-dual interior point algorithm for convex quadratic semi-definite optimization, Appl Math Comput, 231, 581-590, (2014) · Zbl 1410.90230 |
| [5] | Achache, M; Boudiaf, N, Complexity analysis of primal-dual algorithms for semidefinite linear complementarity problems, Rev Anal Numér Théor Approx, 40, 2, 95-106, (2011) · Zbl 1274.90371 |
| [6] | Darvay, Zs, New interior point algorithms for linear optimization, Adv Model Optim, 5, 1, 51-92, (2003) · Zbl 1136.90509 |
| [7] | De Klerk, E, Interior point methods for semidefinite programming, (1997), Master of Science in the Faculty of Engineering, University of Pretoria |
| [8] | Horn, RA; Johnson, CR, Topics in matrix analysis, (1991), Cambridge University Press, UK · Zbl 0729.15001 |
| [9] | Peng, J; Roos, C; Terlaky, T, New complexity analysis of the primal-dual Newton method for linear optimization, Ann Oper Res, 99, 23-39, (2000) · Zbl 0990.90065 |
| [10] | Tseng, P, Search directions and convergence analysis of some infeasible path-following methods for the monotone semi-definite LCP, J Optim Methods Softw, 59, 245-268, (1998) · Zbl 0918.90129 |
| [11] | Achache, M, Complexity analysis of an interior point algorithm for the semidefinite optimization based on a kernel function with a double barrier term, Acta Math Sin, 31, 3, 543-556, (2015) · Zbl 1308.65086 |
| [12] | Balaji, R; Parthasarathy, T, The Q-property of a multiplicative transformation in semidefinite linear complementarity problems, Electron J Linear Algebra, 16, 419-428, (2007) · Zbl 1254.90251 |
| [13] | Chen, F, Polynomial convergence of primal-dual algorithms for SDLCP based on the M-Z family of directions, Appl Math Sci, 5, 39, 1903-1907, (2011) · Zbl 1242.90257 |
| [14] | Gowda, MS; Song, Y, On semidefinite linear complementarity problem, Math Program Ser A, 88, 575-587, (2000) · Zbl 0987.90082 |
| [15] | Kojima, M; Shindoh, M; Hara, S, Interior point methods for the monotone semidefinite linear complementarity in symmetric matrices, SIAM J Optim, 7, 86-125, (1997) · Zbl 0872.90098 |
| [16] | Peng, J; Roos, C; Terlaky, T, Self-regular functions and new search directions for linear and semidefinite optimization, Math Program, 93, 1, 129-171, (2002) · Zbl 1007.90037 |
| [17] | Bai, YQ; El Ghami, M; Roos, C, A comparative study of kernel functions for primal-dual interior point algorithms in linear optimization, SIAM J Optim, 15, 1, 101-128, (2004) · Zbl 1077.90038 |
| [18] | Achache, M, A new parameterized kernel function for LO yielding the best known iteration bound for a large-update interior point algorithm, Afrika Mat, 27, 3, 591-601, (2016) · Zbl 1378.90089 |
| [19] | Amini, K; Haseli, A, A new proximity function generating the best known iteration bounds for both large-update and small-update interior-point methods, ANZIAM J, 49, 259-270, (2007) · Zbl 1142.90039 |
| [20] | Bai, YQ; Roos, C, Proceedings of Industrial Optimization Symposium and Optimization Day, Australia, A primal-dual interior-point method based on a new kernel function with linear growth rate, (2002) |
| [21] | Kheirfam, M, A generic interior-point algorithm for monotone symmetric cone linear complementarity problems based on a new kernel function, J Math Model Algorithms Oper Res, 13, 471-491, (2014) · Zbl 1311.90179 |
| [22] | Lee, YH; Cho, YY; Cho, G-M, Interior point algorithms for P*(κ)-LCP based on a new class of kernel functions, J Global Optim, 58, 137-149, (2014) · Zbl 1319.90069 |
| [23] | Liu, Z; Sun, W; Tian, F, A full-Newton step infeasible interior-poit algorithm for linear programming based on a kernel function, Appl Math Optim, 60, 2, 237, (2009) · Zbl 1206.90084 |
| [24] | Luo, X; Ma, G; Hu, X; Fu, Y, A parametric kernel function yielding the best known iteration bound of interior point methods for semidefinite optimization, Am J Appl Math, 4, 6, 316-323, (2016) |
| [25] | Wang, GQ; Bai, YQ, A new primal-dual path-following interior point algorithm for semidefinte optimization, J Math Anal Appl, 353, 339-349, (2009) · Zbl 1172.90011 |
| [26] | Wang, G; Zhu, D, A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO, Numer Algorithms, 57, 537-558, (2011) · Zbl 1223.65046 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
