A numerical feasible interior point method for linear semidefinite programs

Djamel Benterki; Jean-Pierre Crouzeix; Bachir Merikhi

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 1, page 49-59
  • ISSN: 0399-0559

Abstract

top
This paper presents a feasible primal algorithm for linear semidefinite programming. The algorithm starts with a strictly feasible solution, but in case where no such a solution is known, an application of the algorithm to an associate problem allows to obtain one. Finally, we present some numerical experiments which show that the algorithm works properly.

How to cite

top

Benterki, Djamel, Crouzeix, Jean-Pierre, and Merikhi, Bachir. "A numerical feasible interior point method for linear semidefinite programs." RAIRO - Operations Research 41.1 (2007): 49-59. <http://eudml.org/doc/250116>.

@article{Benterki2007,
abstract = { This paper presents a feasible primal algorithm for linear semidefinite programming. The algorithm starts with a strictly feasible solution, but in case where no such a solution is known, an application of the algorithm to an associate problem allows to obtain one. Finally, we present some numerical experiments which show that the algorithm works properly. },
author = {Benterki, Djamel, Crouzeix, Jean-Pierre, Merikhi, Bachir},
journal = {RAIRO - Operations Research},
keywords = {Linear programming; semidefinite programming; interior point methods.},
language = {eng},
month = {6},
number = {1},
pages = {49-59},
publisher = {EDP Sciences},
title = {A numerical feasible interior point method for linear semidefinite programs},
url = {http://eudml.org/doc/250116},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Benterki, Djamel
AU - Crouzeix, Jean-Pierre
AU - Merikhi, Bachir
TI - A numerical feasible interior point method for linear semidefinite programs
JO - RAIRO - Operations Research
DA - 2007/6//
PB - EDP Sciences
VL - 41
IS - 1
SP - 49
EP - 59
AB - This paper presents a feasible primal algorithm for linear semidefinite programming. The algorithm starts with a strictly feasible solution, but in case where no such a solution is known, an application of the algorithm to an associate problem allows to obtain one. Finally, we present some numerical experiments which show that the algorithm works properly.
LA - eng
KW - Linear programming; semidefinite programming; interior point methods.
UR - http://eudml.org/doc/250116
ER -

References

top
  1. F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim.5 (1995) 13–51.  Zbl0833.90087
  2. F. Alizadeh, J.P.A. Haeberly and M.L. Overton, Primal-dual interior point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM J. Optim.8 (1998) 746–768.  Zbl0911.65047
  3. S.J. Benson, Y. Ye and X. Zhang, Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim.10 (2000) 443–461.  Zbl0997.90059
  4. P. Gahinet, A. Nemirovski, The projective method for solving linear matrix inequalities. Math. Program.77 (1997) 163–190.  Zbl0890.90142
  5. C. Helmberg, F. Rendl, R.J. Vanderbei and H. Wolkowicz, An interior point method for semidefinite programming. SIAM J. Optim.6 (1996) 342–361.  Zbl0853.65066
  6. M. Kojima, S. Shindoh and S. Hara, Interior point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim.7 (1997) 86–125.  Zbl0872.90098
  7. Y. Nesterov and A. Nemirovski, Interior point polynomial algorithms in convex programming. SIAM Stud. Appl. Math.13, Society for Industrial and applied Mathematics (SIAM), Philadelphia, PA (1994).  
  8. A. Nemirovski and K. Scheinberg, Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems. Math. Program.72 (1996) 273–289.  Zbl0853.90092
  9. M. Overton and H. Wolkowicz, Semidefinite programming. Math. Program.77 (1997) 105–109.  Zbl0899.90135
  10. M.V. Ramana, L. Tuncel and H. Wolkowicz, Strong duality for semidefinite programming. SIAM J. Optim.7 (1997) 641–662.  Zbl0891.90129
  11. L. Vandenberghe and S. Boyd, Positive definite programming. SIAM Rev.38 (1996) 49–95.  Zbl0845.65023
  12. H. Wolkowicz, G.-P.-H. Styan, Bounds for eigenvalues using traces. Linear Algebra Appl.29 (1980) 471–506.  Zbl0435.15015
  13.  sdplib/  URIhttp://infohost.nmt.edu/

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.