×

zbMATH — the first resource for mathematics

Implementation of interior point methods for mixed semidefinite and second order cone optimization problems. (English) Zbl 1032.90021
Summary: There is a large number of design choices to be made in the implementation of the primal-dual interior point method for mixed semidefinite and second order cone optimization. This article presents such issues in a unified framework whenever possible. However, semidefinite and second-order cone components are sometimes treated separately to highlight the differences that are necessary for efficient implementations. While this article provides a comparison of choices made by different research groups, it is also the first article to provide an elaborate discussion of the implementation in SeDuMi.

MSC:
90C22 Semidefinite programming
90C51 Interior-point methods
90C20 Quadratic programming
Software:
SDPA; SDPpack; Sp; CSDP; Mosek; SeDuMi; SDPT3
PDF BibTeX Cite
Full Text: DOI
References:
[1] Alizadeh F., SIAM Journal on Optimization 5 pp 13– (1995) · Zbl 0833.90087
[2] Alizadeh F., SDP Pack user’s guide (1997)
[3] Alizadeh, F., Haeberly, J.A. and Overton, M. A new primal-dual interior point method for semidefinite programming. Proceedings of the Fifth SIAM Conference on Applied Linear Algebra. Edited by: Lewis, J.G. pp.113–117. Philadelpha: SIAM. · Zbl 0819.65098
[4] Alizadeh F., SIAM Journal on Optimization 8 (3) pp 746– (1998) · Zbl 0911.65047
[5] Andersen E., Interior point methods for mathematical programming pp 189– (1996)
[6] Andersen E.D., High performance optimization pp 441– (2000)
[7] Andersen E.D., On implementing a primal-dual interior point method for conic quadratic optimization (2002)
[8] Andersen K.D., Software 22 (3) pp 348– (1996)
[9] Horchers B., CSDP, a C library for semidefinite programming (1997)
[10] Boyd S., Linear Matrix Inequalities in System and Control Theory, volume 15 of Studies in Applied Mathematics (1994) · Zbl 0816.93004
[11] Dennis J.E., Schnabel Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1983)
[12] Duffin R.J., Linear Inequalities and Related Systems pp 157– (1956)
[13] Faraut J., Analysis on Symmetric Cones (1994) · Zbl 0841.43002
[14] Faybusovich L., Jordan algebras, symmetric cones and interior point methods (1995)
[15] Faybusovich, L. 1997.Euclidean Jordan algebras and interior-point algorithms, Positivity 1 331–357. Kluwer Academic Publishers. · Zbl 0973.90095
[16] Faybusovich L., Journal of Computational and Applied Mathematics 86 pp 149– (1997) · Zbl 0889.65066
[17] Faybusovich L., Technical Report, in: A Jordan-algebraic approach to potential-reduction algorithms (1998)
[18] Freund R.M., High performance optimization pp 441– (2000)
[19] Fujisawa K., High Performance Optimization pp 267– (2000)
[20] Fujisawa K., Mathematical Programming 79 pp 235– (1997) · Zbl 0953.90043
[21] Goemans M.X., Journal ACM 42 pp 1115– (1995) · Zbl 0885.68088
[22] Goldfarb D., Technical Report, in: A product form Cholesky factorization implementation of an interior point method for second order cone programming (2001)
[23] Goldfarb D., Technical Report, in: A product form Cholesky factorization method for handling dense columns in interior point methods for linear programming (2001)
[24] Gondzio J., Computational Optimization and Applications 6 pp 137– (1996) · Zbl 0860.90084
[25] Gonzaga C.C., SIAM Review 34 (2) pp 167– (1992) · Zbl 0763.90063
[26] Güter O., Mathematical Programming 81 pp 55– (1998)
[27] Haeberly J.-P., Optimization Methods and Software 11 pp 67– (1999) · Zbl 0957.90102
[28] Helmberg C., SIAM Journal on Optimization 6 pp 342– (1996) · Zbl 0853.65066
[29] Horn R.A., Matrix Analysis (1985) · Zbl 0576.15001
[30] Karmarkar N.K., Combinatorica 4 pp 373– (1984) · Zbl 0557.90065
[31] de Klerk E., Interior point methods for semidefinite programming (1997)
[32] Kojima M., A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems (1991) · Zbl 0766.90077
[33] Kojima M., Progress in Mathematical Programming: Interior Point and Related Methods pp 29– (1989)
[34] Kojima M., Technical Report B-311, in: A predictor-corrector interior-point algorithm for the semidefinite linear complementarity problem using the alizadehhaeberly-overton search direction (1996)
[35] Kojima M., SIAM Journal on Optimization 7 (1) pp 86– (1997) · Zbl 0872.90098
[36] Kruk S., High accuracy algorithms for the solutions of semideflnite linear programs (2001)
[37] Lobo M.S., Linear Algebra and its Applications 284 pp 193– (1998) · Zbl 0946.90050
[38] Luo Z.-Q., Technical Report 9620/A, in: Duality and self-duality for conic convex programming (1996)
[39] Luo Z.-Q., Optimization Methods and Software 14 pp 196– (2000)
[40] Lustig I.J., Mathematical Programming 49 pp 145– (1990) · Zbl 0726.90050
[41] Lustig I.J., Linear Algebra and its Applications 152 pp 191– (1991) · Zbl 0731.65049
[42] Lustig I.J., SIAM Journal on Optimization 2 pp 435– (1992) · Zbl 0771.90066
[43] Lustig I.J., ORSA Journal on Computing 6 (1) pp 1– (1994) · Zbl 0798.90100
[44] Mehrotra S., SIAM Journal on Optimization 2 pp 575– (1992) · Zbl 0773.90047
[45] Mizuno S., Interior Point Methods of Mathematical Programming, Volume 5 of Applied Optimization (1996)
[46] Mizuno S., Mathematics of Operations Research 18 pp 964– (1993) · Zbl 0810.90091
[47] Monteiro R.D.C., SIAM Journal on Optimization 7 (3) pp 663– (1997) · Zbl 0913.65051
[48] Monteiro R.D.C, Mathematics of Operations Research 15 pp 191– (1990) · Zbl 0714.90060
[49] Monteiro R.D.C., Technical Report, in: Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming (1996)
[50] Monteiro R.D.C., Technical Report, in: A note on the existence of the Alizadeh-Haeberly-Overton direction for semidefinite programming (1996)
[51] Monteiro R.D.C., Mathematics of Operations Research 25 pp 381– (2000) · Zbl 1073.90571
[52] Monteiro R.D.C., Mathematical Programming 81 pp 281– (1998)
[53] Nesterov Y., Interior point polynomial methods in convex programming, Volume 13 of Studies in Applied Mathematics (1994) · Zbl 0824.90112
[54] Nesterov Y., Mathematics of Operations Research 22 (1) pp 1– (1997) · Zbl 0871.90064
[55] Nesterov Y., SIAM Journal on Optimization 8 pp 324– (1998) · Zbl 0922.90110
[56] Pataki G., Technical Report, in: The DIMACS library of semidefinite-quadraticlinear programs (1999)
[57] Portugal L., SIAM Journal on Scientific Computing 17 (5) pp 1202– (1996) · Zbl 0858.90099
[58] PreiU+03B2 M., Technical Report, in: Analysis of infesible interior point paths arising with semidefinite linear complementarity problems (2002)
[59] Saunders M.A., ORSA Journal on Computing 6 (1) pp 23– (1994) · Zbl 0800.90698
[60] Shida M., SIAM Journal on Optimization 8 (2) pp 387– (1998) · Zbl 0913.90252
[61] Sonnevend G., Methods of Operations Research 63 pp 19– (1989)
[62] Sturm J.F., Primal-Dual Interior Point Approach to Semidefinite Programming, Volume 156 of Tinbergen Institute Research Series (1997)
[63] Sturm J.F., Optimization Methods and Software 11 pp 625– (1999) · Zbl 0973.90526
[64] Sturm J.F., High Performance Optimization pp 157– (2000)
[65] Sturm J.F., Linear Algebra and its Applications 312 pp 135– (2000) · Zbl 0973.90093
[66] Sturm J.F., Technical Report 2001-27, in: Avoiding numerical cancellation in the interior point method for solving semidefinite programs (2001)
[67] Sturm J.F., Mathematics of Operations Research 22 (2) pp 408– (1997) · Zbl 0883.90093
[68] Sturm J.F., Applied Numerical Mathematics 29 pp 301– (1999) · Zbl 0956.90027
[69] Sturm J.F., European Journal of Operational Research 126 pp 391– (2000) · Zbl 0971.90058
[70] Todd M.J., Optimization Methods and Software 11 pp 1– (1999) · Zbl 0971.90109
[71] Todd M.J., SIAM Journal on Optimization 8 (3) pp 769– (1998) · Zbl 0913.90217
[72] Toh K.C., Optimization Methods and Software 11 pp 545– (1999) · Zbl 0997.90060
[73] Tunçel L., Mathematics of Operations Research pp 23– (1998)
[74] Tutüncü R.H., Solving semidefinite-quadraticlinear programs using sdpt3 (2002)
[75] Vandenberghe L., SP: Software for Semidefinite Programming (1994)
[76] Vandenberghe L., Mathematical Programming 69 pp 205– (1995)
[77] Vanderbei R.J., Linear Programming. Foundations and Extensions (1997)
[78] Wolkowicz Henry, Handbook on Semidefinite Programming (2000)
[79] Wright S., Mathematical Programming 73 pp 269– (1996)
[80] Xu X., Annals of Operations Research 62 pp 151– (1996) · Zbl 0848.90095
[81] Ye Y., Mathematics of Operations Research 19 pp 53– (1994) · Zbl 0799.90087
[82] Zhang Y., SIAM Journal on Optimization 8 (2) pp 365– (1998) · Zbl 0913.65050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.