Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-26T21:03:03.878Z Has data issue: false hasContentIssue false
  • English
  • Français

A numerical feasible interior point method for linear semidefiniteprograms

Published online by Cambridge University Press:  15 June 2007

Djamel Benterki ,
Jean-Pierre Crouzeix  and
Bachir Merikhi
Djamel Benterki
Affiliation:
Département de Mathématiques, Faculté des sciences, Université Ferhat Abbas, Sétif, 19000, Algérie ; [email protected]; [email protected]
Jean-Pierre Crouzeix
Affiliation:
LIMOS, Université Blaise Pascal, 63177 Aubière Cedex, France; [email protected]
Bachir Merikhi
Affiliation:
Département de Mathématiques, Faculté des sciences, Université Ferhat Abbas, Sétif, 19000, Algérie ; [email protected]; [email protected]
Get access

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.

Keywords

Linear programmingsemidefinite programminginterior point methods.
Type
Research Article
Information
RAIRO - Operations Research , Volume 41 , Issue 1 , January 2007 , pp. 49 - 59
Copyright
© EDP Sciences, ROADEF, SMAI, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alizadeh, F., Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (1995) 13–51. CrossRef
Alizadeh, F., Haeberly, J.P.A. and Overton, M.L., Primal-dual interior point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM J. Optim. 8 (1998) 746–768. CrossRef
Benson, S.J., Ye, Y. and Zhang, X., Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10 (2000) 443–461. CrossRef
Gahinet, P., Nemirovski, A., The projective method for solving linear matrix inequalities. Math. Program. 77 (1997) 163–190. CrossRef
Helmberg, C., Rendl, F., Vanderbei, R.J. and Wolkowicz, H., An interior point method for semidefinite programming. SIAM J. Optim. 6 (1996) 342–361. CrossRef
Kojima, M., Shindoh, S. and Hara, S., Interior point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7 (1997) 86–125. CrossRef
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).
Nemirovski, A. and Scheinberg, K., Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems. Math. Program. 72 (1996) 273–289. CrossRef
Overton, M. and Wolkowicz, H., Semidefinite programming. Math. Program. 77 (1997) 105–109. CrossRef
Ramana, M.V., Tuncel, L. and Wolkowicz, H., Strong duality for semidefinite programming. SIAM J. Optim. 7 (1997) 641–662. CrossRef
Vandenberghe, L. and Boyd, S., Positive definite programming. SIAM Rev. 38 (1996) 49–95. CrossRef
Wolkowicz, H., Styan, G.-P.-H., Bounds for eigenvalues using traces. Linear Algebra Appl. 29 (1980) 471–506. CrossRef
http://infohost.nmt.edu/ sdplib/