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.
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro:2006022/
[1] , Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization. SIAM J. Optim. 5 (1995) 13-51. | Zbl
[2] ,, and, 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] and, Lower bounds for the partitioning of graphs. IBM J. Res. Devel. 17 (1973) 420-425. | Zbl
[4] , and, On the Convergence of the Central Path in Semidefinite Optimization. SIAM J. Optim. 12 (2002) 1090-1099. | Zbl
[5] and, Topics in Matrix Analysis. Cambridge University Press (1991). | MR | Zbl
[6] , and, Central Paths, Generalized Proximal Point Methods and Cauchy Trajectories in Riemannian Manifolds. SIAM J. Control Optim. 37 (1999) 566-588. | Zbl
[7] , Aspects of Semidefinite Programming. Kluwer Academic Publisher (2002). | MR | Zbl
[8] , and, Initialization in Semidefinite Programming Via a Self-Dual Skew-Symmetric Embedding. Oper. Res Lett. 20 (1997) 213-221. | Zbl
[9] , Ensembles semi-analytiques. I.H.E.S., Bures-sur-Yvette (1965).
[10] , and, Superlinear Convergence of a Symmetric Primal-Dual Path Following Algorithm for Semidefinite Programming. SIAM J. Optim. 8 (1998) 59-81. | Zbl
[11] and, Optimality Conditions and Duality Theory for Minimizing Sums of the Largest Eigenvalues of Symmetric Matrices. Math. Program. 62 (1993) 321-357. | Zbl
[12] and, A New Self-concordant Barrier for the Hypercube. J. Optim. Theory Appl. (JOTA), accepted.
Cité par Sources :
