Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones

被引：35

作者：

Andersen M.S. ^{[1
]}

Dahl J. ^{[2
]}

Vandenberghe L. ^{[1
]}

机构：

[1] Electrical Engineering Department, University of California, Los Angeles

[2] MOSEK ApS, 2100 Copenhagen Ø

来源：

Mathematical Programming Computation | 2010年 / 2卷 / 3-4期

基金：

美国国家科学基金会;

关键词：

The authors’ (Andersen and Vandenberghe) research was supported in part by NSF grants ECS-0524663 and ECCS-0824003;

D O I：

10.1007/s12532-010-0016-2

中图分类号：

学科分类号：

摘要：

We describe an implementation of nonsymmetric interior-point methods for linear cone programs defined by two types of matrix cones: the cone of positive semidefinite matrices with a given chordal sparsity pattern and its dual cone, the cone of chordal sparse matrices that have a positive semidefinite completion. The implementation takes advantage of fast recursive algorithms for evaluating the function values and derivatives of the logarithmic barrier functions for these cones.We present experimental results of two implementations, one of which is based on an augmented system approach, and a comparison with publicly available interior-point solvers for semidefinite programming. © The Author(s) 2010.

引用

页码：167 / 201

页数：34

共 56 条

[1]

Amestoy P., Davis T., Duff I., An approximate minimum degree ordering, SIAM J. Matrix Anal. Appl., 17, 4, pp. 886-905, (1996)

[2]

Alizadeh F., Goldfarb D., Second-order cone programming, Math. Program. Ser. B, 95, pp. 3-51, (2003)

[3]

Alizadeh F., Haeberly J.-P.A., Overton M.L., Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results, SIAMJ. Optim., 8, 3, pp. 746-768, (1998)

[4]

Barrett W.W., Johnson C.R., Lundquist M., Determinantal formulation for matrix completions associated with chordal graphs, Linear Algebra Appl., 121, pp. 265-289, (1989)

[5]

Borchers B., CSDP, a C library for semidefinite programming, Optim. Methods Softw., 11, 1, pp. 613-623, (1999)

[6]

Borchers B., SDPLIB 1.2, a library of semidefinite programming test problems, Optim. Methods Soft., 11, 1, pp. 683-690, (1999)

[7]

Blair J.R.S., Peyton B., An introduction to chordal graphs and clique trees, Graph Theory and Sparse Matrix Computation, (1993)

[8]

Ben-Tal A., Nemirovski A., Lectures on Modern Convex Optimization, Analysis, Algorithms, and Engineering Applications, (2001)

[9]

Burer S., Semidefinite programming in the space of partial positive semidefinite matrices, SIAM J. Optim., 14, 1, pp. 139-172, (2003)

[10]

Boyd S., Vandenberghe L., Convex Optimization, (2004)

← 1 2 3 4 5 6 →