×

On the implementation and usage of SDPT3 – a Matlab software package for semidefinite-quadratic-linear programming, version 4.0. (English) Zbl 1334.90117

Anjos, Miguel F. (ed.) et al., Handbook on semidefinite, conic and polynomial optimization. New York, NY: Springer (ISBN 978-1-4614-0768-3/hbk; 978-1-4614-0769-0/ebook). International Series in Operations Research & Management Science 166, 715-754 (2012).
Summary: This software is designed to solve primal and dual semidefinite-quadratic-linear conic programming problems (known as SQLP problems) whose constraint conic is a product of semidefinite conics, second-order conics, nonnegative orthants and Euclidean spaces, and whose objective function is the sum of linear functions and log-barrier terms associated with the constraint conics. This includes the special case of determinant maximization problems with linear matrix inequalities. It employs an infeasible primal-dual predictor-corrector path-following method, with either the HKM or the NT search direction. The basic code is written in Matlab, but key subroutines in C are incorporated via Mex files. Routines are provided to read in problems in either SDPA or SeDuMi format. Sparsity and block diagonal structure are exploited. We also exploit low-rank structures in the constraint matrices associated with the semidefinite blocks if such structures are explicitly given. To help the users in using our software, we also include some examples to illustrate the coding of problem data for our solver. Various techniques to improve the efficiency and robustness of the main solver are incorporated. For example, step-lengths associated with semidefinite conics are calculated via the Lanczos method. The current version also implements algorithms for solving a 3-parameter homogeneous self-dual model of the primal and dual SQLP problems. Routines are also provided to determine whether the primal and dual feasible regions of a given SQLP have empty interiors. Numerical experiments show that this general-purpose code can solve more than 80% of a total of about 430 test problems to an accuracy of at least \(10^{6}\) in relative duality gap and infeasibilities.
For the entire collection see [Zbl 1235.90002].

MSC:

90C22 Semidefinite programming
90C20 Quadratic programming
90C05 Linear programming
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alizadeh, F.; Haeberly, J-PA; Overton, ML, Primal-dual interior-point methods for semidefinite programming: convergence results, stability and numerical results, SIAM J. Optimization, 8, 746-768 (1998) · Zbl 0911.65047
[2] Borchers, B.: SDPLIB 1.2, a library of semidefinite programming test problems. Optimization Methods and Software 11 & 12, 683-690 (1999) · Zbl 0973.90522
[3] Boyd, S., El Ghaoui, L., Feron, E., Balakrishnan, V.: Linear Matrix Inequalities in System and Control Theory. SIAM, Philadelphia (1994) · Zbl 0816.93004
[4] Cai, Z.; Toh, KC, Solving second order cone programming via the augmented systems, SIAM J. Optimization, 17, 711-737 (2006) · Zbl 1128.90045
[5] Davis, T.A.: CHOLMOD Version 1.0 User Guide. Technical Report, University of Florida, Gainesville, Florida (2005). http://www.cise.ufl.edu/research/sparse/cholmod
[6] Davis, T.A.: UMFPACK Version 4.6 User Guide. Technical Report, University of Florida, Gainesville, Florida (2002). http://www.cise.ufl.edu/research/sparse/umfpack
[7] Duff, I.S.: MA57 - A new code for the solution of sparse symmetric definite and indefinite systems. Technical Report RAL-TR-2002-024, Rutherford Appleton Laboratory, Oxford (2002)
[8] Freund, RM, Complexity of convex optimization using geometry-based measures and a reference point, Mathematical Programming, 99, 197-221 (2004) · Zbl 1098.90095
[9] Freund, RM; Ordóñez, F.; Toh, KC, Behavioral Measures and their Correlation with IPM Iteration Counts on Semi-Definite Programming Problems, Mathematical Programming, 109, 445-475 (2007) · Zbl 1278.90447
[10] Freund, R.W., Nachtigal, N.M.: A new Krylov-subspace method for symmetric indefinite linear systems. In: Ames, W.F. (ed) Proceedings of the 14th IMACS World Congress on Computational and Applied Mathematics, Atlanta (1994)
[11] Fujisawa, K.; Kojima, M.; Nakata, K., Exploiting sparsity in primal-dual interior-point method for semidefinite programming, Mathematical Programming, 79, 235-253 (1997) · Zbl 0887.90156
[12] Grant, M., Boyd, S.: Graph implementations for nonsmooth convex programs. In: Blondel, V., Boyd, S., Kimura, H. (eds.) Recent Advances in Learning and Control (a tribute to M. Vidyasagar). Lecture Notes in Control and Information Sciences. Springer, Berlin Heidelberg New York (2008). Software is available at http://cvxr.com/cvx/ · Zbl 1205.90223
[13] Harwell Subroutine Library: http://www.cse.clrc.ac.uk/Activity/HSL (1963)
[14] Helmberg, C.; Rendl, F.; Vanderbei, R.; Wolkowicz, H., An interior-point method for semidefinite programming, SIAM Journal on Optimization, 6, 342-361 (1996) · Zbl 0853.65066
[15] Henrion, D.; Lasserre, JB, GloptiPoly: Global optimization over polynomials with Matlab and SeDuMi, ACM Transactions on Mathematical Software, 29, 165-194 (2003) · Zbl 1070.65549
[16] Henrion, D.; Lasserre, JB; Loefberg, J., GloptiPoly 3: moments, optimization and semidefinite programming, Optimization Methods and Software, 24, 761-779 (2009) · Zbl 1178.90277
[17] Kojima, M.; Shindoh, S.; Hara, S., Interior-point methods for the monotone linear complementarity problem in symmetric matrices, SIAM J. Optimization, 7, 86-125 (1997) · Zbl 0872.90098
[18] Liu, JW; Ng, EG; Peyton, BW, On finding supernodes for sparse matrix computations, SIAM J. Matrix Anal. Appl., 1, 242-252 (1993) · Zbl 0765.65034
[19] Löfberg, J.: A Toolbox for Modeling and Optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei, Taiwan (2004). http://control.ee.ethz.ch/ joloef/yalmip.php
[20] Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM J. Optimization, 2, 575-601 (1992) · Zbl 0773.90047
[21] Monteiro, RDC, Primal-dual path-following algorithms for semidefinite programming, SIAM J. Optimization, 7, 663-678 (1997) · Zbl 0913.65051
[22] Monteiro, RDC; Tsuchiya, T., Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions, Mathematical Programming, 88, 61-83 (2000) · Zbl 0967.65077
[23] Nesterov, Y.; Todd, MJ, Self-scaled barriers and interior-point methods in convex programming, Mathematics of Operations Research, 22, 1-42 (1997) · Zbl 0871.90064
[24] Pataki, G., Schmieta, S.: The DIMACS library of mixed semidefinite-quadratic-linear programs. http://dimacs.rutgers.edu/Challenges/Seventh/Instances (1999)
[25] Renegar, J., Linear programming, complexity theory, and elementary functional analysis, Mathematical Programming, 70, 279-351 (1995) · Zbl 0855.90085
[26] Sturm, J. F., Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones, Optimization Methods and Software, 11, 625-653 (1999) · Zbl 0973.90526
[27] Todd, MJ; Toh, KC; Tütüncü, RH, On the Nesterov-Todd direction in semidefinite programming, SIAM J. Optimization, 8, 769-796 (1998) · Zbl 0913.90217
[28] Toh, KC, A note on the calculation of step-lengths in interior-point methods for semidefinite programming, Computational Optimization and Applications, 21, 301-310 (2002) · Zbl 0994.90105
[29] Toh, KC, Some new search directions for primal-dual interior point methods in semidefinite programming, SIAM J. Optimization, 11, 223-242 (2000) · Zbl 0990.90091
[30] Toh, KC, Primal-dual path-following algorithms for determinant maximization problems with linear matrix inequalities, Computational Optimization and Applications, 14, 309-330 (1999) · Zbl 0961.90129
[31] Toh, K.C., Todd, M.J., Tütüncü, R.H.: SDPT3 — a Matlab software package for semidefinite programming. Optimization Methods and Software 11 & 12, 545-581 (1999) · Zbl 0997.90060
[32] Toh, KC, Solving large scale semidefinite programs via an iterative solver on the augmented systems, SIAM J. Optim., 14, 670-698 (2004) · Zbl 1071.90026
[33] Tütüncü, RH; Toh, KC; Todd, MJ, Solving semidefinite-quadratic-linear programs using SDPT3, Mathematical Programming, 95, 189-217 (2003) · Zbl 1030.90082
[34] Tsuchiya, T., A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming, Optimization Methods and Software, 11, 141-182 (1999) · Zbl 0957.90129
[35] Vandenberghe, L.; Boyd, S.; Wu, S-P, Determinant maximization with linear matrix inequalities, SIAM J. Matrix Analysis and Applications, 19, 499-533 (1998) · Zbl 0959.90039
[36] Waki, H.; Kim, S.; Kojima, M.; Muramatsu, M.; Sugimoto, H., SparsePOP: a sparse semidefinite programming relaxation of polynomial optimization problems, ACM Transactions on Mathematical Software, 35, 15 (2008)
[37] Yamashita, M.; Fujisawa, K.; Kojima, M., Implementation and evaluation of SDPA 6.0 (SemiDefinite Programming Algorithm 6.0), Optimization Methods and Software, 18, 491-505 (2003) · Zbl 1106.90366
[38] Ye, Y., Todd, M.J., Mizuno, S.: An \(O( \sqrt{n}\) L)-iteration homogeneous and self-dual linear programming algorithm. Mathematics of Operations Research 19, 53-67 (1994) · Zbl 0799.90087
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.