A numerical feasible interior point method for linear semidefinite programs

被引：10

作者：

Benterki, Djamel ^{[1
]}

Crouzeix, Jean-Pierre

Merikhi, Bachir

机构：

[1] Univ Ferhat Abbas, Fac Sci, Dept Math, Setif 19000, Algeria

[2] Univ Clermont Ferrand, LIMOS, F-63177 Aubiere, France

来源：

RAIRO-OPERATIONS RESEARCH | 2007年 / 41卷 / 01期

关键词：

linear programming; semidefinite programming; interior point methods;

D O I：

10.1051/ro:2007006

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：49 / 59

页数：11

共 12 条

[1] INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].

ALIZADEH, F .

SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (01) :13-51

[2] Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results [J].

Alizadeh, F ;

Haeberly, JPA ;

Overton, ML .

SIAM JOURNAL ON OPTIMIZATION, 1998, 8 (03) :746-768

[3] Solving large-scale sparse semidefinite programs for combinatorial optimization [J].

Benson, SJ ;

Ye, YY ;

Zhang, X .

SIAM JOURNAL ON OPTIMIZATION, 2000, 10 (02) :443-461

[4] The projective method for solving linear matrix inequalities [J].

Gahinet, P ;

Nemirovski, A .

MATHEMATICAL PROGRAMMING, 1997, 77 (02) :163-190

[5] An interior-point method for semidefinite programming [J].

Helmberg, C ;

Rendl, F ;

Vanderbei, RJ ;

Wolkowicz, H .

SIAM JOURNAL ON OPTIMIZATION, 1996, 6 (02) :342-361

[6] Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices [J].

Kojima, M ;

Shindoh, S ;

Hara, S .

SIAM JOURNAL ON OPTIMIZATION, 1997, 7 (01) :86-125

[7] Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems [J].

Nemirovskii, A ;

Scheinberg, K .

MATHEMATICAL PROGRAMMING, 1996, 72 (03) :273-289

[8]

NESTEROV Y., 1994, SIAM STUDIES APPL MA, V13

[9] Semidefinite programming - Foreword [J].

Overton, M ;

Wolkowicz, H .

MATHEMATICAL PROGRAMMING, 1997, 77 (02) :105-109

[10] Strong duality for semidefinite programming [J].

Ramana, MV ;

Tuncel, L ;

Wolkowicz, H .

SIAM JOURNAL ON OPTIMIZATION, 1997, 7 (03) :641-662

← 1 2 →