A new barrier for a class of semidefinite problems

Erik A. Papa Quiroz; Paolo Roberto Oliveira

RAIRO - Operations Research (2006)

  • Volume: 40, Issue: 3, page 303-323
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Papa Quiroz, Erik A., and Oliveira, Paolo Roberto. "A new barrier for a class of semidefinite problems." RAIRO - Operations Research 40.3 (2006): 303-323. <http://eudml.org/doc/249760>.

@article{PapaQuiroz2006,
abstract = { 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. },
author = {Papa Quiroz, Erik A., Oliveira, Paolo Roberto},
journal = {RAIRO - Operations Research},
keywords = {Interior point methods; barrier function; central path; semidefinite optimization.; interior point methods; semidefinite optimization},
language = {eng},
month = {11},
number = {3},
pages = {303-323},
publisher = {EDP Sciences},
title = {A new barrier for a class of semidefinite problems},
url = {http://eudml.org/doc/249760},
volume = {40},
year = {2006},
}

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
DA - 2006/11//
PB - EDP Sciences
VL - 40
IS - 3
SP - 303
EP - 323
AB - 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.
LA - eng
KW - Interior point methods; barrier function; central path; semidefinite optimization.; interior point methods; semidefinite optimization
UR - http://eudml.org/doc/249760
ER -

References

top
  1. F. Alizadeh, Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization. SIAM J. Optim.5 (1995) 13–51.  
  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,  URIhttp://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.  
  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.  
  5. R.A. Horn and C.R. Johnson, Topics in Matrix Analysis. Cambridge University Press (1991).  
  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.  
  7. E. de Klerk, Aspects of Semidefinite Programming. Kluwer Academic Publisher (2002).  
  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.  
  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.  
  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.  
  12. E.A. Papa Quiroz and P.R. Oliveira, A New Self-concordant Barrier for the Hypercube. J. Optim. Theory Appl. (JOTA), accepted.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.