Logarithmic Barrier Method Via Minorant Function for Linear Semidefinite Programming

Leulmi, Assma

doi:10.2478/amsil-2022-0021

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 e˙ectiveness of the algorithm developed in this work, which are presented in the last section of this paper.

References

[1] 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.
Search in Google Scholar Back to article
[2] 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.
Search in Google Scholar Back to article
[3] 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.
Search in Google Scholar Back to article
[4] J.-P. Crouzeix and B. Merikhi, A logarithm barrier method for semi-definite programming, RAIRO Oper. Res. 42 (2008), no. 2, 123–139.
Search in Google Scholar Back to article
[5] 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.
Search in Google Scholar Back to article
[6] 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.
Search in Google Scholar Back to article
[7] 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.
Search in Google Scholar Back to article
[8] R.D.C. Monteiro, Primal-dual path-following algorithms for semidefinite programming, SIAM J. Optim. 7 (1997), no. 3, 663–678.
Search in Google Scholar Back to article
[9] 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.
Search in Google Scholar Back to article
[10] R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N.J., 1970.
Search in Google Scholar Back to article
[11] K. Samia and D. Benterki, A relaxed logarithmic barrier method for semidefinite programming, RAIRO Oper. Res. 49 (2015), no. 3, 555–568.
Search in Google Scholar Back to article
[12] K.-C. Toh, Some new search directions for primal-dual interior point methods in semi-definite programming, SIAM J. Optim. 11 (2000), no. 1, 223–242.
Search in Google Scholar Back to article
[13] 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.10.1016/j.cam.2016.05.008
Search in Google Scholar Back to article
[14] H. Wolkowicz and G.P.H. Styan, Bounds for eigenvalues using traces, Linear Algebra Appl. 29 (1980), 471–506.10.1016/0024-3795(80)90258-X
Search in Google Scholar Back to article

Logarithmic Barrier Method Via Minorant Function for Linear Semidefinite Programming

Abstract

Paradigm

My account