Logarithmic Barrier Method Via Minorant Function for Linear Semidefinite Programming

• Autorzy: Assma Leulmi
• Języki publikacji: EN

Abstrakty

EN

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. (original abstract)

Słowa kluczowe

EN

Mathematical functions; Linear programming; Log-linear models

PL

Funkcje matematyczne; Programowanie liniowe; Modele logarytmiczno-liniowe

• Czasopismo: Annales Mathematicae Silesianae
• Rocznik: 2023
• Tom: 37 (1)
• Strony: 95--116

Twórcy

autor

Assma Leulmi

• Ferhat Abbas University, Algeria

Bibliografia

• Alizadeh F., Haeberly J.-P.A., Overton M.L., Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results, SIAM J. Optim. 8 (1998), no. 3, 746-768.
• Benterki D., Crouzeix J.-P., Merikhi B., A numerical implementation of an interior point method for semidefinite programming, Pesqui. Oper. 23 (2003), no. 1, 49-59.
• Benterki D., Crouzeix J.-P., Merikhi B., A numerical feasible interior point method for linear semidefinite programs, RAIRO Oper. Res. 41 (2007), no. 1, 49-59.
• Crouzeix J.-P., Merikhi B., A logarithm barrier method for semi-definite programming, RAIRO Oper. Res. 42 (2008), no. 2, 123-139.
• Crouzeix J.-P., Seeger A., New bounds for the extreme values of a finite sample of real numbers, J. Math. Anal. Appl. 197 (1996), no. 2, 411-426.
• Ji J., Potra F.A., Sheng R., On the local convergence of a predictor-corrector method for semidefinite programming, SIAM J. Optim. 10 (1999), no. 1, 195-210.
• Merikhi B., 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.
• Monteiro R.D.C., Primal-dual path-following algorithms for semidefinite programming, SIAM J. Optim. 7 (1997), no. 3, 663-678.
• Nesterov Y.E., Nemirovskii A.S., Optimization Over Positive Semidefinite Matrices: Mathematical Background and User's Manual, Technical report, Central Economic & Mathematical Institute, USSR Academy of Science, Moscow, 1990.
• Rockafellar R.T., Convex Analysis, Princeton University Press, Princeton, N.J., 1970.
• Samia K., Benterki D., A relaxed logarithmic barrier method for semidefinite programming, RAIRO Oper. Res. 49 (2015), no. 3, 555-568.
• Toh K.-C., Some new search directions for primal-dual interior point methods in semidefinite programming, SIAM J. Optim. 11 (2000), no. 1, 223-242.
• Touil I., Benterki D., Yassine A., A feasible primal-dual interior point method for linear semidefinite programming, J. Comput. Appl. Math. 312 (2017), 216-230.
• Wolkowicz H., Styan G.P.H., Bounds for eigenvalues using traces, Linear Algebra Appl. 29 (1980), 471-506.

Identyfikatory

DOI

10.2478/amsil-2022-0021