Kernel-function based algorithms for semidefinite optimization
RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 2, pp. 189-199.

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.

DOI : 10.1051/ro/2009011
Classification : 90C22, 90C31
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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro/2009011/

[1] F. Alizadeh, Combinatorial optimization with interior point methods and semi-definite matrices. Ph.D. thesis, University of Minnesota, Minneapolis, Minnesota, USA (1991).

[2] F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (1995) 13-51. | MR | Zbl

[3] Y.Q. Bai, M. El Ghami and C. Roos, 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] E. De Klerk, Aspects of semidefinite programming, Applied Optimization 65. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002). | MR | Zbl

[5] M. El Ghami, New primal-dual interior-point methods based on kernel functions. Ph.D. thesis, TU Delft, The Netherlands (2005).

[6] M. El Ghami and C. Roos, Generic primal-dual interior point methods based on a new Kernel function. RAIRO-Oper. Res. 42 (2008) 199-213. | Numdam | MR

[7] R.A. Horn and C.R. Johnson, Matrix analysis. Cambridge University Press, Cambridge, UK (1985). | MR | Zbl

[8] Y.E. Nesterov and A.S. Nemirovskii, Interior point polynomial methods in convex programming: theory and algorithms. SIAM Publications, SIAM, Philadelphia, USA (1993).

[9] J. Peng, C. Roos and T. Terlaky, Self-regularity, a new paradigm for primal-dual interior-point algorithms. Princeton University Press (2002). | MR | Zbl

[10] W. Rudin, Principles of mathematical analysis. Mac-Graw Hill Book Company, New York (1978). | Zbl

[11] J.F. Sturm and S. Zhang, Symmetric primal-dual path following algorithms for semidefinite programming. Appl. Num. Math. 29 (1999) 301-315. | MR | Zbl

[12] G.Q. Wang, Y.Q. Bai and C. Roos, 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 :