no. 3
A new barrier for a class of semidefinite problems
RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 3, pp. 303-323.

We introduce a new barrier function to solve a class of Semidefinite Optimization Problems (SOP) with bounded variables. That class is motivated by some (SOP) as the minimization of the sum of the first few eigenvalues of symmetric matrices and graph partitioning problems. We study the primal-dual central path defined by the new barrier and we show that this path is analytic, bounded and that all cluster points are optimal solutions of the primal-dual pair of problems. Then, using some ideas from semi-analytic geometry we prove its full convergence. Finally, we introduce a new proximal point algorithm for that class of problems and prove its convergence.

DOI : 10.1051/ro:2006022
Mots clés : interior point methods, barrier function, central path, semidefinite optimization 
@article{RO_2006__40_3_303_0,
     author = {Papa Quiroz, Erik A. and Oliveira, Paolo Roberto},
     title = {A new barrier for a class of semidefinite problems},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {303--323},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {3},
     year = {2006},
     doi = {10.1051/ro:2006022},
     mrnumber = {2276161},
     zbl = {1190.90277},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro:2006022/}
}
TY  - JOUR
AU  - Papa Quiroz, Erik A.
AU  - Oliveira, Paolo Roberto
TI  - A new barrier for a class of semidefinite problems
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2006
SP  - 303
EP  - 323
VL  - 40
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2006022/
DO  - 10.1051/ro:2006022
LA  - en
ID  - RO_2006__40_3_303_0
ER  - 
%0 Journal Article
%A Papa Quiroz, Erik A.
%A Oliveira, Paolo Roberto
%T A new barrier for a class of semidefinite problems
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2006
%P 303-323
%V 40
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2006022/
%R 10.1051/ro:2006022
%G en
%F RO_2006__40_3_303_0
Papa Quiroz, Erik A.; Oliveira, Paolo Roberto. A new barrier for a class of semidefinite problems. RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 3, pp. 303-323. doi : 10.1051/ro:2006022. http://archive.numdam.org/articles/10.1051/ro:2006022/

[1] F. Alizadeh, Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization. SIAM J. Optim. 5 (1995) 13-51. | Zbl

[2] J.X. Da Cruz Neto, O.P. Ferreira, P.R. Oliveira and R.C.M. Silva, Central Paths in Semidefinite Programming, Generalized Proximal Point Method and Cauchy Trajectories in Riemannian Manifolds, submitted, http://www.optimization-online.org/DB_FILE/2006/02/1327.pdf

[3] W.E. Donath and A.J. Hoffman, Lower bounds for the partitioning of graphs. IBM J. Res. Devel. 17 (1973) 420-425. | Zbl

[4] M. Halická, E. De Klerk and C. Roos, On the Convergence of the Central Path in Semidefinite Optimization. SIAM J. Optim. 12 (2002) 1090-1099. | Zbl

[5] R.A. Horn and C.R. Johnson, Topics in Matrix Analysis. Cambridge University Press (1991). | MR | Zbl

[6] A.N. Iusem, B.S. Svaiter and J.X. Da Cruz Neto, Central Paths, Generalized Proximal Point Methods and Cauchy Trajectories in Riemannian Manifolds. SIAM J. Control Optim. 37 (1999) 566-588. | Zbl

[7] E. De Klerk, Aspects of Semidefinite Programming. Kluwer Academic Publisher (2002). | MR | Zbl

[8] E. De Klerk, C. Roos and T. Terlaky, Initialization in Semidefinite Programming Via a Self-Dual Skew-Symmetric Embedding. Oper. Res Lett. 20 (1997) 213-221. | Zbl

[9] S. Lojasiewicz, Ensembles semi-analytiques. I.H.E.S., Bures-sur-Yvette (1965).

[10] Z.-Q. Luo, J.F. Sturm and S. Zhang, Superlinear Convergence of a Symmetric Primal-Dual Path Following Algorithm for Semidefinite Programming. SIAM J. Optim. 8 (1998) 59-81. | Zbl

[11] M.L. Overton and R.S. Womersley, Optimality Conditions and Duality Theory for Minimizing Sums of the Largest Eigenvalues of Symmetric Matrices. Math. Program. 62 (1993) 321-357. | Zbl

[12] E.A. Papa Quiroz and P.R. Oliveira, A New Self-concordant Barrier for the Hypercube. J. Optim. Theory Appl. (JOTA), accepted.

Cité par Sources :