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.
Accepté le :
DOI : 10.1051/ro/2014055
Mots-clés : Linear programming, semidefinite programming, central trajectory Methods
@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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ro/2014055/
, and , Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results. SIAM J. Optim. 8 (1998) 746–768. | DOI | MR | Zbl
, and , A numerical implementation of an interior point method for semidefinite programming. Pesquisa Operacional 23 (2003) 49–59. | DOI
, and , A numerical feasible interior point method for linear semidefinite programs. Oper. Res. 41 (2007) 49–59. | DOI | Numdam | MR | Zbl
, and , Nonsymmetric search directions for semidefinite programming. SIAM J. Optim. 9 (1999) 863–876. | DOI | MR | Zbl
, A new notion of weighted centers for semidefinite programming. SIAM J. Optim. 16 (2006) 1092–1109. | DOI | MR | Zbl
, and , On the local convergence of a predictor-corrector method for semidefinite programming. SIAM J. Optim. 10 (1999) 195–210. | DOI | MR | Zbl
, and , On the convergence of the central path in semidefinite optimization. SIAM J. Optim. 12 (2002) 1090–1099. | DOI | MR | Zbl
, , and , An interior-point method for semidefinite programming. SIAM J. Optim. 6 (1996) 342–361. | DOI | MR | Zbl
and , Semidefinite programs: New search directions, smoothing-type methods, and numerical results. SIAM J. Optim. 13 (2002) 1–23. | DOI | MR | Zbl
, A new polynomial-time algorithm for linear programming. Combinatorica 4 (1984) 373–395. | DOI | MR | Zbl
, and , 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
, and , Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7 (1997) 86–125. | DOI | MR | Zbl
, Primal-dual path-following algorithms for semidefinite programming. SIAM J. Optim. 7 (1997) 663–678. | DOI | MR | Zbl
, 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
and , 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
and , 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).
, and , On the Nesterov-Todd direction in semidefinite programming. SIAM J. Optim. 8 (1998) 769–796. | DOI | MR | Zbl
, 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).
, 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 :
