A logarithm barrier method for semi-definite programming
RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 2, pp. 123-139.

This paper presents a logarithmic barrier method for solving a semi-definite linear program. The descent direction is the classical Newton direction. We propose alternative ways to determine the step-size along the direction which are more efficient than classical line-searches.

DOI : 10.1051/ro:2008005
Classification : 90C22, 90C05, 90C51
Mots-clés : linear semi-definite programming, barrier methods, line-search 
@article{RO_2008__42_2_123_0,
     author = {Crouzeix, Jean-Pierre and Merikhi, Bachir},
     title = {A logarithm barrier method for semi-definite programming},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {123--139},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {2},
     year = {2008},
     doi = {10.1051/ro:2008005},
     mrnumber = {2431396},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro:2008005/}
}
TY  - JOUR
AU  - Crouzeix, Jean-Pierre
AU  - Merikhi, Bachir
TI  - A logarithm barrier method for semi-definite programming
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2008
SP  - 123
EP  - 139
VL  - 42
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2008005/
DO  - 10.1051/ro:2008005
LA  - en
ID  - RO_2008__42_2_123_0
ER  - 
%0 Journal Article
%A Crouzeix, Jean-Pierre
%A Merikhi, Bachir
%T A logarithm barrier method for semi-definite programming
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2008
%P 123-139
%V 42
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2008005/
%R 10.1051/ro:2008005
%G en
%F RO_2008__42_2_123_0
Crouzeix, Jean-Pierre; Merikhi, Bachir. A logarithm barrier method for semi-definite programming. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 2, pp. 123-139. doi : 10.1051/ro:2008005. http://archive.numdam.org/articles/10.1051/ro:2008005/

[1] F. Alizadeh, Interior point methods in semi-definite programming with application to combinatorial optimization. SIAM J. Optim. 5 (1995) 13-55. | MR | Zbl

[2] F. Alizadeh, J.-P. Haberly, and M.-L. Overton, Primal-dual interior-point methods for semi-definite programming, convergence rates, stability and numerical results. SIAM J. Optim. 8 (1998) 746-768. | MR | Zbl

[3] D. Benterki, J.-P. Crouzeix, and B. Merikhi, A numerical implementation of an interior point method for semi-definite programming. Pesquisa Operacional 23-1 (2003) 49-59.

[4] J.-F. Bonnans, J.-C. Gilbert, C. Lemaréchal, and C. Sagastizàbal, Numerical optimization, theoretical and practical aspects. Mathematics and Applications 27, Springer-Verlag, Berlin (2003). | MR | Zbl

[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) 411-426. | MR | Zbl

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

[7] M. Overton and H. Wolkowicz, Semi-definite programming. Math. program. Serie B 77 (1997) 105-109. | Zbl

[8] R.T. Rockafellar, Convex analysis. Princeton University Press, New Jerzey (1970). | MR | Zbl

[9] L. Vanderberghe and S. Boyd, Positive definite programming. SIAM Review 38 (1996) 49-95. | Zbl

[10] H. Wolkowicz and G.-P.-H. Styan, Bounds for eigenvalues using traces. Linear Algebra Appl. 29 (1980) 471-506. | MR | Zbl

Cité par Sources :