Kernel-function Based Algorithms for Semidefinite Optimization

M. EL Ghami; Y. Q. Bai; C. Roos

RAIRO - Operations Research (2009)

  • Volume: 43, Issue: 2, page 189-199
  • ISSN: 0399-0559

Abstract

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

How to cite

top

EL Ghami, M., Bai, Y. Q., and Roos, C.. "Kernel-function Based Algorithms for Semidefinite Optimization." RAIRO - Operations Research 43.2 (2009): 189-199. <http://eudml.org/doc/250634>.

@article{ELGhami2009,
abstract = { 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. },
author = {EL Ghami, M., Bai, Y. Q., Roos, C.},
journal = {RAIRO - Operations Research},
keywords = {Semidefinite optimization; interior-point methods; primal-dual method; complexity.; interior-point methods; complexity},
language = {eng},
month = {4},
number = {2},
pages = {189-199},
publisher = {EDP Sciences},
title = {Kernel-function Based Algorithms for Semidefinite Optimization},
url = {http://eudml.org/doc/250634},
volume = {43},
year = {2009},
}

TY - JOUR
AU - EL Ghami, M.
AU - Bai, Y. Q.
AU - Roos, C.
TI - Kernel-function Based Algorithms for Semidefinite Optimization
JO - RAIRO - Operations Research
DA - 2009/4//
PB - EDP Sciences
VL - 43
IS - 2
SP - 189
EP - 199
AB - 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.
LA - eng
KW - Semidefinite optimization; interior-point methods; primal-dual method; complexity.; interior-point methods; complexity
UR - http://eudml.org/doc/250634
ER -

References

top
  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.  Zbl0833.90087
  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.  Zbl1077.90038
  4. E. de Klerk, Aspects of semidefinite programming, Applied Optimization 65. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002).  
  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.  Zbl1211.90117
  7. R.A. Horn and C.R. Johnson, Matrix analysis. Cambridge University Press, Cambridge, UK (1985).  Zbl0576.15001
  8. Y.E. Nesterov and A.S. Nemirovskii, Interior point polynomial methods in convex programming: theory and algorithms. SIAM Publications, SIAM, Philadelphia, USA (1993).  Zbl0824.90112
  9. J. Peng, C. Roos and T. Terlaky, Self-regularity, a new paradigm for primal-dual interior-point algorithms. Princeton University Press (2002).  Zbl1136.90045
  10. W. Rudin, Principles of mathematical analysis. Mac-Graw Hill Book Company, New York (1978).  
  11. J.F. Sturm and S. Zhang, Symmetric primal-dual path following algorithms for semidefinite programming. Appl. Num. Math.29 (1999) 301–315.  Zbl0956.90027
  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. Algorithms4 (2005) 409–433.  Zbl1111.90083

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.