A logarithm barrier method for semi-definite programming

Jean-Pierre Crouzeix; Bachir Merikhi

RAIRO - Operations Research (2008)

  • Volume: 42, Issue: 2, page 123-139
  • ISSN: 0399-0559

Abstract

top
This paper presents a logarithmic barrier method for solving a semi-definite linear program. The descent direction is the classical Newton direction. We propose alternative ways to determine the step-size along the direction which are more efficient than classical line-searches.

How to cite

top

Crouzeix, Jean-Pierre, and Merikhi, Bachir. "A logarithm barrier method for semi-definite programming." RAIRO - Operations Research 42.2 (2008): 123-139. <http://eudml.org/doc/250394>.

@article{Crouzeix2008,
abstract = { This paper presents a logarithmic barrier method for solving a semi-definite linear program. The descent direction is the classical Newton direction. We propose alternative ways to determine the step-size along the direction which are more efficient than classical line-searches. },
author = {Crouzeix, Jean-Pierre, Merikhi, Bachir},
journal = {RAIRO - Operations Research},
keywords = {Linear semi-definite programming; barrier methods; line-search.; linear semi-definite programming; line-search},
language = {eng},
month = {5},
number = {2},
pages = {123-139},
publisher = {EDP Sciences},
title = {A logarithm barrier method for semi-definite programming},
url = {http://eudml.org/doc/250394},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Crouzeix, Jean-Pierre
AU - Merikhi, Bachir
TI - A logarithm barrier method for semi-definite programming
JO - RAIRO - Operations Research
DA - 2008/5//
PB - EDP Sciences
VL - 42
IS - 2
SP - 123
EP - 139
AB - This paper presents a logarithmic barrier method for solving a semi-definite linear program. The descent direction is the classical Newton direction. We propose alternative ways to determine the step-size along the direction which are more efficient than classical line-searches.
LA - eng
KW - Linear semi-definite programming; barrier methods; line-search.; linear semi-definite programming; line-search
UR - http://eudml.org/doc/250394
ER -

References

top
  1. F. Alizadeh, Interior point methods in semi-definite programming with application to combinatorial optimization. SIAM J. Optim.5 (1995) 13–55.  Zbl0833.90087
  2. F. Alizadeh, J.-P. Haberly, and M.-L. Overton, Primal-dual interior-point methods for semi-definite programming, convergence rates, stability and numerical results. SIAM J. Optim.8 (1998) 746–768.  Zbl0911.65047
  3. D. Benterki, J.-P. Crouzeix, and B. Merikhi, A numerical implementation of an interior point method for semi-definite programming. Pesquisa Operacional23–1 (2003) 49–59.  
  4. J.-F. Bonnans, J.-C. Gilbert, C. Lemaréchal, and C. Sagastizàbal, Numerical optimization, theoretical and practical aspects. Mathematics and Applications27, Springer-Verlag, Berlin (2003).  Zbl1014.65045
  5. J.-P. Crouzeix and A. Seeger, New bounds for the extreme values of a finite sample of real numbers. J. Math. Anal. Appl.197 (1996) 411–426.  Zbl0869.49017
  6. M. Kojima, S. Shindoh, and S. Hara, Interior point methods for the monotone semi-definite linear complementarity problem in symmetric matrices. SIAM J. Optim.7 (1997) 86–125.  Zbl0872.90098
  7. M. Overton and H. Wolkowicz, Semi-definite programming. Math. program. Serie B77 (1997) 105–109.  
  8. R.T. Rockafellar, Convex analysis. Princeton University Press, New Jerzey (1970).  Zbl0193.18401
  9. L. Vanderberghe and S. Boyd, Positive definite programming. SIAM Review38 (1996) 49–95.  
  10. H. Wolkowicz and G.-P.-H. Styan, Bounds for eigenvalues using traces. Linear Algebra Appl.29 (1980) 471–506.  Zbl0435.15015

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.