A relaxed logarithmic barrier method for semidefinite programming
RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 3, pp. 555-568.

Interior point methods applied to optimization problems have known a remarkable evolution in the last decades. They are used with success in linear, quadratic and semidefinite programming. Among these methods, primal-dual central trajectory methods have a polynomial convergence and are credited of a good numerical behavior. In this paper, we propose a new central trajectory method where a relaxation parameter is introduced in order to give more flexibility to the theoretical and numerical aspects of the perturbed problems and accelerate the convergence of the algorithm. This claim is confirmed by numerical tests showing the good behavior of the algorithm which is proposed in this paper.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2014055
Classification : 90C22, 90C51
Mots clés : Linear programming, semidefinite programming, central trajectory Methods
Samia, Kettab 1 ; Djamel, Benterki 1

1 Laboratory of Fundamental and Numerical Mathematics, Setif-1 University, 19000 Setif, Algeria.
@article{RO_2015__49_3_555_0,
     author = {Samia, Kettab and Djamel, Benterki},
     title = {A relaxed logarithmic barrier method for semidefinite programming},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {555--568},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {3},
     year = {2015},
     doi = {10.1051/ro/2014055},
     mrnumber = {3349134},
     zbl = {1327.90179},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2014055/}
}
TY  - JOUR
AU  - Samia, Kettab
AU  - Djamel, Benterki
TI  - A relaxed logarithmic barrier method for semidefinite programming
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2015
SP  - 555
EP  - 568
VL  - 49
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2014055/
DO  - 10.1051/ro/2014055
LA  - en
ID  - RO_2015__49_3_555_0
ER  - 
%0 Journal Article
%A Samia, Kettab
%A Djamel, Benterki
%T A relaxed logarithmic barrier method for semidefinite programming
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2015
%P 555-568
%V 49
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2014055/
%R 10.1051/ro/2014055
%G en
%F RO_2015__49_3_555_0
Samia, Kettab; Djamel, Benterki. A relaxed logarithmic barrier method for semidefinite programming. RAIRO - Operations Research - Recherche Opérationnelle, Tome 49 (2015) no. 3, pp. 555-568. doi : 10.1051/ro/2014055. http://www.numdam.org/articles/10.1051/ro/2014055/

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) 746–768. | DOI | MR | Zbl

D. Benterki, J.P. Crouzeix and B. Merikhi, A numerical implementation of an interior point method for semidefinite programming. Pesquisa Operacional 23 (2003) 49–59. | DOI

D. Benterki, J.P. Crouzeix and B. Merikhi, A numerical feasible interior point method for linear semidefinite programs. Oper. Res. 41 (2007) 49–59. | DOI | Numdam | MR | Zbl

N. Brixius, F.A. Porta and R. Sheng, Nonsymmetric search directions for semidefinite programming. SIAM J. Optim. 9 (1999) 863–876. | DOI | MR | Zbl

C.B. Chua, A new notion of weighted centers for semidefinite programming. SIAM J. Optim. 16 (2006) 1092–1109. | DOI | MR | Zbl

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) 195–210. | DOI | MR | Zbl

M. Halicka, E. De Klerk and C. Roos, On the convergence of the central path in semidefinite optimization. SIAM J. Optim. 12 (2002) 1090–1099. | DOI | MR | Zbl

C. Helmberg, F. Rendl, R.J. Vanderbei and H. Wolkowicz, An interior-point method for semidefinite programming. SIAM J. Optim. 6 (1996) 342–361. | DOI | MR | Zbl

C. Kanzow and C. Nagel, Semidefinite programs: New search directions, smoothing-type methods, and numerical results. SIAM J. Optim. 13 (2002) 1–23. | DOI | MR | Zbl

N. Karmarkar, A new polynomial-time algorithm for linear programming. Combinatorica 4 (1984) 373–395. | DOI | MR | Zbl

M. Kojima, M. Shida and S. Shindoh, A predictor-corrector interior-point algorithm for the semidefinite linear complementarity problem using the Alizadeh-Haeberly-Overton search direction. SIAM J. Optim. 9 (1999) 444–465. | DOI | MR | Zbl

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

R.D.C. Monteiro, Primal-dual path-following algorithms for semidefinite programming. SIAM J. Optim. 7 (1997) 663–678. | DOI | MR | Zbl

R.D.C. Monteiro, Polynomial convergence of primal-dual algorithms for semidefinite programming based on Monteiro and Zhang family of directions. SIAM J. Optim. 8 (1998) 797–812. | DOI | MR | Zbl

R.D.C. Monteiro and T. Tsuchiya, Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming. SIAM J. Optim. 9 (1999) 551–577. | DOI | MR | Zbl

R.D.C. Monteiro and P.R. Zanjacomo, A note on the existence of the Alizadeh–Haeberly–Overton direction for semidefinite programming. School of Industrial and Systems Engineering, Georgia Institute of Technology Atlanta 78 (1997) 393–396. | MR | Zbl

Y.E. Nesterov and A.S. Nemirovskii, Interior point polynomial algorithms in convex programming: theory and applications. SIAM, Philadelphia, PA (1994). | MR | Zbl

A.M. Nunez and R.M. Freund, Condition-measure bounds on the behavior of the central trajectory of semidefinite program. SIAM J. Optim. 12 (2001) 818–836. | DOI | MR | Zbl

M.J. Todd, Semidefinite optimization. School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York (2001). | MR | Zbl

M.J. Todd, On search directions in interior-point methods for semidefinite programming. School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York (1997).

M.J. Todd, K.C. Toh and R.H. Tütüncü, On the Nesterov-Todd direction in semidefinite programming. SIAM J. Optim. 8 (1998) 769–796. | DOI | MR | Zbl

K.C. Toh, Some new search directions for primal-dual interior point methods in semidefinite programming. SIAM J. Optim. 11 (2000) 223–242. | DOI | MR | Zbl

I. Touil, Étude comparative des performances d’une méthode de points intérieurs de type trajectoire centrale pour la programmation semi-définie linéaire. Thèse de magister, département de mathématique, Universit*error*éFerhat Abbas, Sétif, Algérie (2005).

Y. Zhang, On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8 (1998) 365–386. | DOI | MR | Zbl

L. Zhaosong, Algorithm design and analysis for large-scale semidefinite programming and nonlinear programming. Doctor of Philosophy thesis School of Industrial and Systems Engineering Georgia Institute of Technology (2005).

Cité par Sources :