Logarithmic barrier method via minorant function for linear semidefinite programming
Abstract
We propose in this study, a new logarithmic barrier approach to solve linear semidefinite programming problem. We are interested in computation of the direction by Newton’s method and of the displacement step using minorant functions instead of line search methods in order to reduce the computation cost.
Our new approach is even more beneficial than classical line search methods. This purpose is confirmed by some numerical simulations showing the effectiveness of the algorithm developed in this work, which are presented in the last section of this paper.
Keywords
linear semidefinite programming; barrier methods; line search
References
F. Alizadeh, J.-P.A. Haeberly, and M.L. Overton, Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results, SIAM J. Optim. 8 (1998), no. 3, 746–768.
D. Benterki, J.-P. Crouzeix, and B. Merikhi, A numerical implementation of an interior point method for semidefinite programming, Pesqui. Oper. 23 (2003), no. 1, 49–59.
D. Benterki, J.-P. Crouzeix, and B. Merikhi, A numerical feasible interior point method for linear semidefinite programs, RAIRO Oper. Res. 41 (2007), no. 1, 49–59.
J.-P. Crouzeix and B. Merikhi, A logarithm barrier method for semi-definite programming, RAIRO Oper. Res. 42 (2008), no. 2, 123–139.
J.-P. Crouzeix and A. Seeger, New bounds for the extreme values of a finite sample of real numbers, J. Math. Anal. Appl. 197 (1996), no. 2, 411–426.
J. Ji, F.A. Potra, and R. Sheng, On the local convergence of a predictor-corrector method for semidefinite programming, SIAM J. Optim. 10 (1999), no. 1, 195–210.
B. Merikhi, Extension de Quelques Méthodes de Points Intérieurs pour la Programmation Semi-Définie, Thèse de Doctorat, Département de Mathématiques, Université Ferhat Abbas, Sétif, 2006.
R.D.C. Monteiro, Primal-dual path-following algorithms for semidefinite programming, SIAM J. Optim. 7 (1997), no. 3, 663–678.
Y.E. Nesterov and A.S. Nemirovskii, Optimization Over Positive Semidefinite Matrices: Mathematical Background and User’s Manual, Technical report, Central Economic & Mathematical Institute, USSR Academy of Science, Moscow, 1990.
R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N.J., 1970.
K. Samia and D. Benterki, A relaxed logarithmic barrier method for semidefinite programming, RAIRO Oper. Res. 49 (2015), no. 3, 555–568.
K.-C. Toh, Some new search directions for primal-dual interior point methods in semidefinite programming, SIAM J. Optim. 11 (2000), no. 1, 223–242.
I. Touil, D. Benterki, and A. Yassine, A feasible primal-dual interior point method for linear semidefinite programming, J. Comput. Appl. Math. 312 (2017), 216–230.
H. Wolkowicz and G.P.H. Styan, Bounds for eigenvalues using traces, Linear Algebra Appl. 29 (1980), 471–506.
Department of Mathematics, Ferhat Abbas University of Setif-1 Algeria
https://orcid.org/0000-0002-5458-9119
This work is licensed under a Creative Commons Attribution 4.0 International License.
The Copyright Holders of the submitted text are the Author and the Journal. The Reader is granted the right to use the pdf documents under the provisions of the Creative Commons 4.0 International License: Attribution (CC BY). The user can copy and redistribute the material in any medium or format and remix, transform, and build upon the material for any purpose.
- License
This journal provides immediate open access to its content under the Creative Commons BY 4.0 license (http://creativecommons.org/licenses/by/4.0/). Authors who publish with this journal retain all copyrights and agree to the terms of the above-mentioned CC BY 4.0 license. - Author’s Warranties
The author warrants that the article is original, written by stated author/s, has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author/s. - User Rights
Under the Creative Commons Attribution license, the users are free to share (copy, distribute and transmit the contribution) and adapt (remix, transform, and build upon the material) the article for any purpose, provided they attribute the contribution in the manner specified by the author or licensor. - Co-Authorship
If the article was prepared jointly with other authors, the signatory of this form warrants that he/she has been authorized by all co-authors to sign this agreement on their behalf, and agrees to inform his/her co-authors of the terms of this agreement.
