×

zbMATH — the first resource for mathematics

Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets. (English) Zbl 1369.90136
Summary: We propose a hierarchy of semidefinite programming (SDP) relaxations for polynomial optimization with sparse patterns over unbounded feasible sets. The convergence of the proposed SDP hierarchy is established for a class of polynomial optimization problems. This is done by employing known sums-of-squares sparsity techniques of M. Kojima and M. Muramatsu [Comput. Optim. Appl. 42, No. 1, 31–41 (2009; Zbl 1153.90545)] and J. B. Lasserre [SIAM J. Optim. 17, No. 3, 822–843 (2006; Zbl 1119.90036)] together with a representation theorem for polynomials over unbounded sets obtained recently in [V. Jeyakumar et al., J. Optim. Theory Appl. 163, No. 3, 707–718 (2014; Zbl 1302.90208)]. We demonstrate that the proposed sparse SDP hierarchy can solve some classes of large scale polynomial optimization problems with unbounded feasible sets using the polynomial optimization solver SparsePOP developed by H. Waki et al. [“Algorithm 883: SparsePOP: a sparse semidefinite programming relaxation of polynomial optimization problems”, ACM Trans. Math. Softw. 35, 15 (2008)].

MSC:
90C26 Nonconvex programming, global optimization
90C22 Semidefinite programming
Software:
SeDuMi; SFSDP; SparsePOP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersen, M., Vandenberghe, L., Dahl, J.: Linear matrix inequalities with chordal sparsity patterns and applications to robust quadratic optimization. In: Proceedings of IEEE International Symposium on Computer-Aided Control System Design (CACSD) (2010) · Zbl 1226.90077
[2] Bruckstein, AM; Donoho, DL; Elad, M, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., 51, 34-81, (2009) · Zbl 1178.68619
[3] Candés, EJ; Tao, T, Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 4203-4215, (2005) · Zbl 1264.94121
[4] Candés, EJ; Wakin, MB; Boyd, S, Enhancing sparsity by re-weighted \(l_1\) minimization, J. Fourier Anal. Appl., 14, 877-905, (2008) · Zbl 1176.94014
[5] Demmel, J; Nie, JW, Sparse SOS relaxations for minimizing functions that are summations of small polynomials, SIAM J. Optim., 19, 1534-1558, (2008) · Zbl 1178.65048
[6] Feng, M., Mitchell, J.E., Pang, J.S., Shen, X., Wachter, A.: Complementarity formulations of \(l_0\)-norm optimization problems. http://www.optimization-online.org/DB_HTML/2013/09/4053.html · Zbl 0744.44008
[7] Feng, C., Lagoa, C., Sznaier, M.: Hybrid system identification via sparse polynomial optimization. In: American Control Conference (ACC), pp. 160-165 (2010) · Zbl 1156.90011
[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, (2000) · Zbl 1010.90053
[9] Ghaddar, B; Marecek, J; Mevissen, M, Optimal power flow as a polynomial optimization problem, IEEE Trans. Power Syst., 99, 1-8, (2015)
[10] Hà, HV; Phạm, TS, Representations of positive polynomials and optimization on noncompact semi-algebraic sets, SIAM J. Optim., 20, 3082-3103, (2010) · Zbl 1279.14071
[11] Jeyakumar, V; Lasserre, JB; Li, G, On polynomial optimization over non-compact semi-algebraic sets, J. Optim. Theory Appl., 163, 707-718, (2014) · Zbl 1302.90208
[12] Jeyakumar, V; Li, G; Pham, TS, Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness, Oper. Res. Lett., 42, 34-40, (2014) · Zbl 1408.90227
[13] Jeyakumar, V; Li, G, A new class of alternative theorems for SOS-convex inequalities and robust optimization, Appl. Anal., 94, 56-74, (2015) · Zbl 1338.90302
[14] Jeyakumar, V; Li, G, Exact SDP relaxations for classes of nonlinear semidefinite programming problems, Oper. Res. Lett., 40, 529-536, (2012) · Zbl 1287.90047
[15] Kleniati, P; Parpas, P; Rustem, B, Partitioning procedure for polynomial optimization, J. Glob. Optim., 48, 549-567, (2010) · Zbl 1226.90077
[16] Kim, S; Kojima, M; Mevissen, M; Yamashita, M, Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion, Math. Program., 129, 33-68, (2011) · Zbl 1229.90116
[17] Kim, S; Kojima, M; Waki, H; Yamashita, M, Algorithm 920: SFSDP: a sparse version of full semidefinite programming relaxation for sensor network localization problems, ACM Trans. Math. Softw., 38, 1-19, (2012) · Zbl 1365.65163
[18] Kojima, M; Muramatsu, M, A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones, Comput. Optim. Appl., 42, 31-41, (2009) · Zbl 1153.90545
[19] Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 796-817, (2001) · Zbl 1010.90061
[20] Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2009)
[21] Lasserre, JB, Convergent SDP-relaxations in polynomial optimization with sparsity, SIAM J. Optim., 17, 822-843, (2006) · Zbl 1119.90036
[22] Lu, W.-S., Hinamoto, T.: Design of FIR filters with discrete coefficients via polynomial programming: towards the global solution. In: IEEE International Symposium on Circuit and Systems, pp. 2048-2051 (2007) · Zbl 1279.14071
[23] Luo, Z-Q; Sidiropoulos, ND; Tseng, P; Zhang, S, Approximation bounds for quadratic optimization with homogeneous quadratic constraints, SIAM J. Optim., 18, 1-28, (2007) · Zbl 1156.90011
[24] Marshall, M.: Positive Polynomials and Sums of Squares, Mathematical Surveys and Monographs, vol. 146. American Mathematical Society, Providence (2008) · Zbl 1169.13001
[25] Nie, JW, Sum of squares method for sensor network localization, Comput. Optim. Appl., 43, 151-179, (2009) · Zbl 1170.90510
[26] Nie, JW, An exact Jacobian SDP relaxation for polynomial optimization, Math. Program., 137, 225-255, (2013) · Zbl 1266.65094
[27] Nie, J, Optimality conditions and finite convergence of lasserre’s hierarchy, Math. Program., 146, 97-121, (2014) · Zbl 1300.65041
[28] Parrilo, P.A.: Structured semidefinite programs and semi-algebraic geometry methods in robustness and optimization, Ph.D. thesis, California Institute of Technology (2000) · Zbl 1109.65058
[29] Putinar, M, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 41, 49-95, (1993) · Zbl 0796.12002
[30] Scheiderer, C, Sums of squares on real algebraic curves, Math. Z., 245, 725-760, (2003) · Zbl 1056.14078
[31] Schmüdgen, K, The K-moment problem for compact semi-algebraic sets, Math. Ann., 289, 203-206, (1991) · Zbl 0744.44008
[32] Schweighofer, M, Global optimization of polynomials using gradient tentacles and sums of squares, SIAM J. Optim., 17, 920-942, (2006) · Zbl 1118.13026
[33] Simon, F., Holger, R.: A Mathematical Introduction to Compressive Sensing, Applied and Numerical Harmonic Analysis, Chapter 15. Birkhauser/Springer, New York (2013)
[34] Strum, JF, Sedumi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11—-12, 625-653, (1999) · Zbl 0973.90526
[35] Vandenberghe, L; Andersen, M, Chordal graphs and semidefinite optimization, Found. Trends Optim., 1, 241-433, (2014)
[36] 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
[37] Waki, H; Kim, S; Kojima, M; Muramtasu, M; Sugimoto, H, Algorithm 883: sparsepop: a sparse semidefinite programming relaxation of polynomial optimization problems, ACM Trans. Math. Softw., 35, 15, (2008)
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.