Logarithmic barriers for sparse matrix cones

被引：17

作者：

Andersen, Martin S. ^{[1
]}

Dahl, Joachim ^{[2
]}

Vandenberghe, Lieven ^{[1
]}

机构：

[1] Univ Calif Los Angeles, Dept Elect Engn, Los Angeles, CA 90024 USA

[2] MOSEK ApS, DK-2100 Copenhagen O, Denmark

来源：

OPTIMIZATION METHODS & SOFTWARE | 2013年 / 28卷 / 03期

基金：

美国国家科学基金会;

关键词：

multifrontal method; sparse matrices; semidefinite programming; 65F05; 65F50; 65K05; 90C06; 90C22; MULTIFRONTAL METHOD; SELECTION; IMPLEMENTATION; SET;

D O I：

10.1080/10556788.2012.684353

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Algorithms are presented for evaluating gradients and Hessians of logarithmic barrier functions for two types of convex cones: the cone of positive semidefinite matrices with a given sparsity pattern and its dual cone, the cone of sparse matrices with the same pattern that have a positive semidefinite completion. Efficient large-scale algorithms for evaluating these barriers and their derivatives are important in interior-point methods for nonsymmetric conic formulations of sparse semidefinite programs. The algorithms are based on the multifrontal method for sparse Cholesky factorization.

引用

页码：396 / 423

页数：28

共 40 条

[1]

Amestoy P., 2010, TRPA1059 CERFACS

[2] Multifrontal parallel distributed symmetric and unsymmetric solvers [J].

Amestoy, PR ;

Duff, IS ;

L'Excellent, JY .

COMPUTER METHODS IN APPLIED MECHANICS AND ENGINEERING, 2000, 184 (2-4) :501-520

[3] Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones [J].

Andersen M.S. ;

Dahl J. ;

Vandenberghe L. .

Mathematical Programming Computation, 2010, 2 (3-4) :167-201

[4]

[Anonymous], 2010, Advances in neural information processing systems

[5] THE INFLUENCE OF RELAXED SUPERNODE PARTITIONS ON THE MULTIFRONTAL METHOD [J].

ASHCRAFT, C ;

GRIMES, R .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1989, 15 (04) :291-309

[6]

Banerjee O, 2008, J MACH LEARN RES, V9, P485

[7]

Blair Jean R. S., 1993, GRAPH THEORY SPARSE, P1, DOI [DOI 10.1007/978-1-4613-8369-7, DOI 10.1007/978-1-4613-8369-71]

[8] Semidefinite programming in the space of partial positive semidefinite matrices [J].

Burer, S .

SIAM JOURNAL ON OPTIMIZATION, 2003, 14 (01) :139-172

[9]

Campbell Y., 1995, TR95021 U FLOR COMP

[10] Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate [J].

Chen, Yanqing ;

Davis, Timothy A. ;

Hager, William W. ;

Rajamanickam, Sivasankaran .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2008, 35 (03)

← 1 2 3 4 →