Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones

被引:84
作者
Schmieta, SH [1 ]
Alizadeh, F
机构
[1] Axioma Inc, Marietta, GA 30068 USA
[2] Rutgers State Univ, RUTCOR, Piscataway, NJ 08854 USA
关键词
semidefinite programming; interior point methods; symmetric cones; Euclidean Jordan algebras;
D O I
10.1287/moor.26.3.543.10582
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We present a general framework whereby analysis of interior-point algorithms for semidefinite programming can be extended verbatim to optimization problems over all classes of symmetric cones derivable from associative algebras. In particular, such analyses are extendible to the cone of positive semidefinite Hermitian matrices with complex and quaternion entries, and to the Lorentz cone. We prove the case of the Lorentz cone by using the embedding of its associated Jordan algebra in the Clifford algebra. As an example of such extensions we take Momerio's polynomial-time complexity analysis of the family of similarly scaled directions-introduced by Monteiro and Zhang (1998) -and generalize it to cone-LP over all representable symmetric cones.
引用
收藏
页码:543 / 564
页数:22
相关论文
共 31 条
[1]  
ADLER I, 1995, RRR11195 RUTCOR RUTG
[2]   INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].
ALIZADEH, F .
SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (01) :13-51
[3]   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
[4]  
ALIZADEH F, 1997, 2397 RRR RUTCOR RUTG
[5]  
Faraut J., 1994, Analysis on symmetric cones
[6]   Linear systems in Jordan algebras and primal-dual interior-point algorithms [J].
Faybusovich, L .
JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 1997, 86 (01) :149-175
[7]   Euclidean Jordan algebras and interior-point algorithms [J].
Faybusovich, L .
POSITIVITY, 1997, 1 (04) :331-357
[8]   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
[9]  
Jacobson N., 1968, C PUBL, V39
[10]   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