Decomposition-based method for sparse semidefinite relaxations of polynomial optimization problems. (English) Zbl 1197.90332

Summary: We consider polynomial optimization problems pervaded by a sparsity pattern. It has been shown by J. B. Lasserre [SIAM J. Optim. 17, No. 3, 822–843 (2006; Zbl 1119.90036)] and H. Waki et al. [SIAM J. Optim. 17, No. 1, 218–242 (2006; Zbl 1109.65058)] that the optimal solution of a polynomial programming problem with structured sparsity can be computed by solving a series of semidefinite relaxations that possess the same kind of sparsity. We aim at solving the former relaxations with a decomposition-based method, which partitions the relaxations according to their sparsity pattern. The decomposition-based method that we propose is an extension to semidefinite programming of the Benders decomposition for linear programs [J. F. Benders, Comput. Manag. Sci. 2, No. 1, 3–19 (2005; Zbl 1115.90361)].


90C30 Nonlinear programming
90C22 Semidefinite programming
Full Text: DOI


[1] Lasserre, J.B.: Convergent SDP-relaxations in polynomial optimization with sparsity. SIAM J. Optim. 17(3), 822–843 (2006) · Zbl 1119.90036
[2] Waki, H., Kim, S., Kojima, M., Muramatsu, M.: Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17(1), 218–242 (2006) (electronic) · Zbl 1109.65058
[3] Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Comput. Manag. Sci. 2(1), 3–19 (2005). Reprinted from Numer. Math. 4, 238–252 (1962) · Zbl 1115.90361
[4] Ramana, M., Goldman, A.J.: Some geometric results in semidefinite programming. J. Glob. Optim. 7(1), 33–50 (1995) · Zbl 0839.90093
[5] Kim, S., Kojima, M., Toint, P.: Recognizing underlying sparsity in optimization. Technical Report, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology (2006) · Zbl 1163.90026
[6] Waki, H., Kim, S., Kojima, M., Muramatsu, M.: SparsePOP: a sparse semidefinite programming relaxation of polynomial optimization problems. ACM Trans. Math. Softw. 35(2) (2008)
[7] Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5(1), 13–51 (1995) · Zbl 0833.90087
[8] Pardalos, P.M., Wolkowicz, H. (eds.): Topics in Semidefinite and Interior-point Methods. Fields Institute Communications, vol. 18. American Mathematical Society, Providence (1998) · Zbl 0890.00019
[9] Ramana, M.V., Pardalos, P.M.: Semidefinite programming. In: Interior Point Methods of Mathematical Programming. Appl. Optim., vol. 5, pp. 369–398. Kluwer Academic, Dordrecht (1996) · Zbl 0874.90131
[10] Pataki, G.: The geometry of semidefinite programming. In: Handbook of Semidefinite Programming. Internat. Ser. Oper. Res. Management Sci., vol. 27, pp. 29–65. Kluwer Academic, Dordrecht (2000) · Zbl 0957.90531
[11] Yajima, Y., Ramana, M.V., Pardalos, P.M.: Cuts and semidefinite relaxations for nonconvex quadratic problems. In: Generalized Convexity and Generalized Monotonicity, Karlovassi, 1999. Lecture Notes in Econom. and Math. Systems, vol. 502, pp. 48–70. Springer, Berlin (2001) · Zbl 0986.90030
[12] Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796–817 (2000/01) · Zbl 1010.90061
[13] Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program., Ser. B 96(2), 293–320 (2003). Algebraic and geometric methods in discrete optimization · Zbl 1043.14018
[14] Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications of Algebraic Geometry. IMA Vol. Math. Appl., vol. 149, pp. 157–270. Springer, New York (2009) · Zbl 1163.13021
[15] Floudas, C.A., Pardalos, P.M.: A collection of test problems for constrained global optimization algorithms. Lecture Notes in Computer Science, vol. 455. Springer, Berlin (1990) · Zbl 0718.90054
[16] LP_SOLVE Description (2008). tech.groups.yahoo.com/group/lp_solve
[17] Geoffrion, A.M.: Generalized Benders decomposition. J. Optim. Theory Appl. 10, 237–260 (1972) · Zbl 0229.90024
[18] Meyer, R.: The validity of a family of optimization methods. SIAM J. Control Optim. 8, 41–54 (1970) · Zbl 0194.20501
[19] Grothey, A., Leyffer, S., Mckinnon, K.I.M.: A note on feasibility in benders decomposition (1999)
[20] Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: An interior point method for semidefinite programming. SIAM J. Optim. 6(2), 342–361 (1996) · Zbl 0853.65066
[21] GLOBAL Lib: www.gamsworld.org/global/globallib/globalstat.htm (2008)
[22] Davis, T.A.: User Guide for CHOLMOD: a sparse Cholesky factorization and modification package. Technical Report, Dept. of Computer and Information Science and Engineering, University of Florida (2006)
[23] Borchers, B.: CSDP, A C library for semidefinite programming. Optim. Methods Softw. 11, 613–623 (1999) · Zbl 0973.90524
[24] Benson, S.J., Ye, Y.: DSDP5: Software for semidefinite programming. Technical Report, Mathematics and Computer Science Division, Argonne National Laboratory (2005) · Zbl 1291.65173
[25] Fujisawa, K., Kojima, M., Nakata, K., Yamashita, M.: SDPA (SemiDefinite Programming Algorithm) User’s Manual–Version 5.01. Technical Report, Tokyo Institute of Technology (1995)
[26] Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11/12(1–4), 625–653 (1999) · Zbl 0973.90526
[27] Kleniati, P.M.: Decomposition Schemes for Polynomial Optimization, Semidefinite Programming and Applications to Nonconvex Portfolio Decisions. Ph.D. Thesis, Imperial College London (2009)
[28] Zhao, G.: A log-barrier method with Benders decomposition for solving two-stage stochastic linear programs. Math. Program., Ser. A 90(3), 507–536 (2001) · Zbl 1023.90045
[29] Sivaramakrishnan, K.K., Plaza, G., Terlaky, T.: A conic interior point decomposition approach for large scale semidefinite programming (2005)
[30] Sivaramakrishnan, K.K.: A parallel interior point decomposition algorithm for block angular semidefinite programs. Comput. Optim. Appl. (2008) · Zbl 1189.90200
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.