×

Correlative sparsity in primal-dual interior-point methods for LP, SDP, and SOCP. (English) Zbl 1191.90032

Summary: Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the sparsity of the coefficient matrix of the equation which is determined by the sparsity of an optimization problem (linear program, semidefinite program or second-order cone program). We show if an optimization problem is correlatively sparse, then the coefficient matrix of the Schur complement equation inherits the sparsity, and a sparse Cholesky factorization applied to the matrix results in no fill-in.

MSC:

90C22 Semidefinite programming
90C51 Interior-point methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adler, I., Resende, M.G.C., Veiga, G., Karmarkar, N.: An implementation of Karmarkar’s algorithm for linear programming. Math. Program. 44, 297–335 (1989) · Zbl 0682.90061 · doi:10.1007/BF01587095
[2] Anderson, K.D.: A modified Schur complement method for handling dense columns in interior-point methods for linear programming. ACM Trans. Math. Softw. 22, 348–356 (1996) · Zbl 0884.65049 · doi:10.1145/232826.232937
[3] Ashcraft, C., Pierce, D., Wah, D.K., Wu, J.: The reference manual for SPOOLES, release 2.2: an object oriented software library for solving sparse linear systems of equations. Boeing Shared Services Group, P.O. Box 24346, Mail Stop 7L-22, Seattle, WA 98124 (January 1999). Available at http://netlib.bell-labs.com/netlib/linalg/spooles/spooles
[4] Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse Matrix Computation, pp. 1–29. Springer, New York (1993) · Zbl 0803.68081
[5] Coleman, T.F., Liao, A.: An efficient trust region method for unconstrained discrete-time optimal control problems. Comput. Optim. Appl. 4, 47–66 (1995) · Zbl 0876.49025 · doi:10.1007/BF01299158
[6] Conn, A.R., Gould, N.I.M., Toint, P.L.: Testing a class of methods for solving minimization problems with simple bounds on the variables. Math. Comput. 50, 399–430 (1988) · Zbl 0645.65033 · doi:10.1090/S0025-5718-1988-0929544-3
[7] Fujisawa, K., Kojima, M., Nakata, K.: Exploiting sparsity in primal-dual Interior-point methods for semidefinite programming. Math. Program. 79, 235–254 (1997) · Zbl 0887.90156
[8] Fukuda, M., Kojima, M., Murota, K., Nakata, K.: Exploiting sparsity in semidefinite programming via matrix completion I: general framework. SIAM J. Optim. 11, 647–674 (2001) · Zbl 1010.90053 · doi:10.1137/S1052623400366218
[9] GLOBAL Library, http://www.gamsworld.org/global/globallib.htm
[10] Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic, New York (1980) · Zbl 0541.05054
[11] Goldfarb, D., Scheinberg, K.: Product-form Cholesky factorization in interior-point methods for second order cone programming. Math. Program. 103, 153–179 (2005) · Zbl 1079.90157 · doi:10.1007/s10107-004-0556-1
[12] Griewank, A., Toint, P.L.: On the unconstrained optimization of partially separable functions. In: Powell, M.J.D. (ed.) Nonlinear Optimization 1981, pp. 301–312. Academic, New York (1982) · Zbl 0563.90085
[13] Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6, 342–361 (1996) · Zbl 0853.65066 · doi:10.1137/0806020
[14] Karypis, G., Kumar, V.: METIS–a software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, version 4.0. Department of Computer Science/Army HPC Research Center, University of Minnesota, Minneapolis, MN 55455 (September 1998); Available at http://www-users.cs.umn.edu/\(\sim\)karypis/metis/metis
[15] Kim, S., Kojima, M., Waki, H.: Generalized Lagrangian duals and sums of squares relaxations of sparse polynomial optimization problems. SIAM J. Optim. 15, 697–719 (2005) · Zbl 1114.90085 · doi:10.1137/030601260
[16] Kim, S., Kojima, M., Toint, P.L.: Recognizing underlying sparsity in optimization. Research Report B-428, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152-8552, Japan (May 2006) · Zbl 1163.90026
[17] Kojima, M., Muramatsu, M.: A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones. Research Report B-421, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-ku, Tokyo 152-8552, Japan (January 2006) · Zbl 1153.90545
[18] Kojima, M., Shindoh, S., Hara, S.: Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7, 86–125 (1997) · Zbl 0872.90098 · doi:10.1137/S1052623494269035
[19] Kojima, M., Kim, S., Waki, H.: Sparsity in sums of squares of polynomials. Math. Program. 103, 45–62 (2005) · Zbl 1079.90092 · doi:10.1007/s10107-004-0554-3
[20] Lasserre, J.B.: Global optimization with polynomials and the problems of moments. SIAM J. Optim. 11, 796–817 (2001) · Zbl 1010.90061 · doi:10.1137/S1052623400366802
[21] Lasserre, J.B.: Convergent semidefinite relaxation in polynomial optimization with sparsity. LAAS-CNRS, 7 Avenue du Colonel Roche, 31077 Toulouse, France (2005)
[22] Lewis, J.G., Peyton, B.W., Pothen, A.: A fast algorithm for reordering sparse matrices for parallel factorization. SIAM J. Sci. Comput. 10, 1146–1173 (1989) · Zbl 0693.65032 · doi:10.1137/0910070
[23] Monteiro, R.D.C.: Primal-dual path-following algorithms for semidefinite programming. SIAM J. Optim. 7, 663–678 (1997) · Zbl 0913.65051 · doi:10.1137/S1052623495293056
[24] More, J.J., Garbow, B.S., Hillstrom, K.E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7, 17–41 (1981) · Zbl 0454.65049 · doi:10.1145/355934.355936
[25] Nakata, K., Fujisawa, K., Kojima, M.: Using the conjugate gradient method in interior-point methods for semidefinite programs (in Japanese). Proc. Inst. Stat. Math. 46, 297–316 (1998)
[26] Nakata, K., Fujisawa, K., Fukuda, M., Kojima, M., Murota, K.: Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical results. Math. Program. 95, 303–327 (2003) · Zbl 1030.90081 · doi:10.1007/s10107-002-0351-9
[27] Nash, S.G.: Newton-type minimization via the Lanczos method. SIAM J. Numer. Anal. 21, 770–788 (1984) · Zbl 0558.65041 · doi:10.1137/0721052
[28] Nesterov, E.Yu., Todd, M.J.: Primal-dual interior-point for self-scaled cones. SIAM J. Optim. 8, 324–364 (1988) · Zbl 0922.90110 · doi:10.1137/S1052623495290209
[29] Sturm, F.J.: Implementation of interior point methods for mixed semidefinite and second order cone optimization. Optim. Methods Softw. 17, 1105–1154 (2002) · Zbl 1032.90021 · doi:10.1080/1055678021000045123
[30] Toh, K.C.: Solving large scale semidefinite programs via an iterative solver on the augmented systems. SIAM J. Optim. 14, 670–698 (2004) · Zbl 1071.90026 · doi:10.1137/S1052623402419819
[31] Toh, K.C., Kojima, M.: Solving some large scale semidefinite programs via the conjugate residual method. SIAM J. Optim. 12, 669–691 (2002) · Zbl 1008.90043 · doi:10.1137/S1052623400376378
[32] Tsuchiya, T.: A convergence analysis of the scaling-invariant primal-dual path-following algorithm for second-order cone programming. Optim. Methods Softw. 11/12, 141–182 (1999) · Zbl 0957.90129 · doi:10.1080/10556789908805750
[33] Vanderbei, R.J.: Symmetric quasidefinite matrices. SIAM J. Optim. 5, 100–113 (1995) · Zbl 0822.65017 · doi:10.1137/0805005
[34] Waki, H., Kim, S., Kojima, M., Muramatsu, M.: SparsePOP: a sparse semidefinite programming relaxation of polynomial optimization problems. Research Report B-414, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152-8552, Japan (March 2005)
[35] Waki, H., Kim, S., Kojima, M., Muramatsu, M.: Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17, 218–242 (2006) · Zbl 1109.65058 · doi:10.1137/050623802
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.