Recently, Y.Q. Bai, M. El Ghami and C. Roos [3] introduced a new class of so-called eligible kernel functions which are defined by some simple conditions. The authors designed primal-dual interior-point methods for linear optimization (LO) based on eligible kernel functions and simplified the analysis of these methods considerably. In this paper we consider the semidefinite optimization (SDO) problem and we generalize the aforementioned results for LO to SDO. The iteration bounds obtained are analogous to the results in [3] for LO.
Mots clés : semidefinite optimization, interior-point methods, primal-dual method, complexity
@article{RO_2009__43_2_189_0,
author = {Ghami, M. El and Bai, Y. Q. and roos, C.},
title = {Kernel-function based algorithms for semidefinite optimization},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {189--199},
publisher = {EDP-Sciences},
volume = {43},
number = {2},
year = {2009},
doi = {10.1051/ro/2009011},
mrnumber = {2527862},
zbl = {1170.90455},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2009011/}
}
TY - JOUR AU - Ghami, M. El AU - Bai, Y. Q. AU - roos, C. TI - Kernel-function based algorithms for semidefinite optimization JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2009 SP - 189 EP - 199 VL - 43 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2009011/ DO - 10.1051/ro/2009011 LA - en ID - RO_2009__43_2_189_0 ER -
%0 Journal Article %A Ghami, M. El %A Bai, Y. Q. %A roos, C. %T Kernel-function based algorithms for semidefinite optimization %J RAIRO - Operations Research - Recherche Opérationnelle %D 2009 %P 189-199 %V 43 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2009011/ %R 10.1051/ro/2009011 %G en %F RO_2009__43_2_189_0
Ghami, M. El; Bai, Y. Q.; roos, C. Kernel-function based algorithms for semidefinite optimization. RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 2, pp. 189-199. doi : 10.1051/ro/2009011. http://archive.numdam.org/articles/10.1051/ro/2009011/
[1] , Combinatorial optimization with interior point methods and semi-definite matrices. Ph.D. thesis, University of Minnesota, Minneapolis, Minnesota, USA (1991).
[2] , Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (1995) 13-51. | MR | Zbl
[3] , and , A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15 (2004) 101-128. | MR | Zbl
[4] , Aspects of semidefinite programming, Applied Optimization 65. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002). | MR | Zbl
[5] , New primal-dual interior-point methods based on kernel functions. Ph.D. thesis, TU Delft, The Netherlands (2005).
[6] and , Generic primal-dual interior point methods based on a new Kernel function. RAIRO-Oper. Res. 42 (2008) 199-213. | Numdam | MR
[7] and , Matrix analysis. Cambridge University Press, Cambridge, UK (1985). | MR | Zbl
[8] and , Interior point polynomial methods in convex programming: theory and algorithms. SIAM Publications, SIAM, Philadelphia, USA (1993).
[9] , and , Self-regularity, a new paradigm for primal-dual interior-point algorithms. Princeton University Press (2002). | MR | Zbl
[10] , Principles of mathematical analysis. Mac-Graw Hill Book Company, New York (1978). | Zbl
[11] and , Symmetric primal-dual path following algorithms for semidefinite programming. Appl. Num. Math. 29 (1999) 301-315. | MR | Zbl
[12] , and , Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function. J. Math. Model. Algorithms 4 (2005) 409-433. | MR | Zbl
Cité par Sources :
