×

zbMATH — the first resource for mathematics

A multigrid approach to SDP relaxations of sparse polynomial optimization problems. (English) Zbl 1398.90118

MSC:
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
35G30 Boundary value problems for nonlinear higher-order PDEs
65H10 Numerical computation of solutions to systems of equations
65N06 Finite difference methods for boundary value problems involving PDEs
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
90C51 Interior-point methods
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J. R. S. Blair and B. Peyton, An introduction to chordal graphs and clique trees, in Graph Theory and Sparse Matrix Computation, IMA Vol. Math. Appl. 56, A. George, J. R. Gilbert, and J. W. H. Liu, eds., Springer-Verlag, 1993, pp. 1–29. · Zbl 0803.68081
[2] I. M. Bomze, M. Budinich, P. M. Pardalos, and M. Pelillo, The maximum clique problem, in Handbook of Combinatorial Optimization, Springer, 1999, pp. 1–74. · Zbl 1253.90188
[3] A. Borzì, K. Kunisch, and D. Y. Kwak, Accuracy and convergence properties of the finite difference multigrid solution of an optimal control optimality system, SIAM J. Control Optim., 41 (2003), pp. 1477–1497, . · Zbl 1031.49029
[4] A. Borzì and V. Schulz, Computational Optimization of Systems Governed by Partial Differential Equations, Comput. Sci. Eng. 8, SIAM, 2011, .
[5] A. Borzì and V. Schulz, Multigrid methods for PDE optimization, SIAM Rev., 51 (2009), pp. 361–395, .
[6] W. L. Briggs, V. E. Henson, and S. F. McCormick, A Multigrid Tutorial, 2nd ed., SIAM, Philadelphia, 2000, .
[7] D. Cox, J. Little, and D. O’shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer-Verlag, 1992. · Zbl 0756.13017
[8] A. Dontchev and W. Hager, The Euler approximation in state constrained optimal control, Math. Comp., 70 (2001), pp. 173–203. · Zbl 0987.49017
[9] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, 2nd ed., Ann. Discrete Math. 57, Elsevier, 2004. · Zbl 1050.05002
[10] S. Gratton, A. Sartenaer, and P. L. Toint, Recursive trust-region methods for multiscale nonlinear optimization, SIAM J. Optim., 19 (2008), pp. 414–444, . · Zbl 1163.90024
[11] D. Henrion and J.-B. Lasserre, Detecting global optimality and extracting solutions in gloptipoly, in Positive Polynomials in Control, Springer, 2005, pp. 293–310. · Zbl 1119.93301
[12] M. Hinze, R. Pinnau, M. Ulbrich, and S. Ulbrich, Optimization with PDE Constraints, Math. Model. Theory Appl. 23, Springer Science+Business Media, 2008. · Zbl 1167.49001
[13] C. P. Ho and P. Parpas, Singularly perturbed Markov decision processes: A multiresolution algorithm, SIAM J. Control Optim., 52 (2014), pp. 3854–3886, . · Zbl 1319.49048
[14] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 2012.
[15] V. Hovhannisyan, P. Parpas, and S. Zafeiriou, Magma: Multi-level accelerated gradient mirror descent algorithm for large-scale convex composite minimization, SIAM J. Imaging Sci., 9 (2016), pp. 1829–1857, . · Zbl 1358.90097
[16] J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796–817, . · Zbl 1010.90061
[17] J. B. Lasserre, Convergent SDP-relaxations in polynomial optimization with sparsity, SIAM J. Optim., 17 (2006), pp. 822–843, . · Zbl 1119.90036
[18] J. B. Lasserre, An Introduction to Polynomial and Semi-algebraic Optimization, Cambridge Texts Appl. Math. 52, Cambridge University Press, 2015.
[19] J. B. Lasserre, D. Henrion, C. Prieur, and E. Trélat, Nonlinear optimal control via occupation measures and lmi-relaxations, SIAM J. Control Optim., 47 (2008), pp. 1643–1666, . · Zbl 1188.90193
[20] F. Lin, Z. Di, and S. Leyffer, A multiscale approach to a class of semidefinite programs, to in Proceedings of the 2016 American Control Conference, IEEE, pp. 7153–7158.
[21] M. Mevissen, M. Kojima, J. Nie, and N. Takayama, Solving partial differential equations via sparse sdp relaxations, P. J. Optim., 4 (2008), pp. 213–241. · Zbl 1161.90458
[22] M. Mevissen, J. B. Lasserre, and D. Henrion, Moment and SDP relaxation techniques for smooth approximations of problems involving nonlinear differential equations, in Proceedings of the 18th IFAC World Congress on Automatic Control, Elsevier, 2011, pp. 10887–10892.
[23] M. Mevissen, K. Yokoyama, and N. Takayama, Solutions of polynomial systems derived from the steady cavity flow problem, in Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, ACM, 2009, pp. 252–262. · Zbl 1237.65052
[24] J. J. More, B. S. Garbow, and K. E. Hillstrom, Testing unconstrained optimization software, ACM Trans. Math. Software, 7 (1981), pp. 17–41. · Zbl 0454.65049
[25] S. G. Nash, Newton-type minimization via Lanczos method, SIAM J. Numer. Anal., 21 (1984), pp. 770–788, . · Zbl 0558.65041
[26] S. G. Nash, A multigrid approach to discretized optimization problems, Optim. Methods Softw., 14 (2000), pp. 99–116. · Zbl 0988.90040
[27] J. Nie and J. Demmel, Sparse SOS relaxations for minimizing functions that are summations of small polynomials, SIAM J. Optim., 19 (2008), pp. 1534–1558, . · Zbl 1178.65048
[28] I. Papamichail and C. S. Adjiman, A rigorous global optimization algorithm for problems with ordinary differential equations, J. Global Optim., 24 (2002), pp. 1–33. · Zbl 1026.90071
[29] P. A. Parrilo, Semidefinite programming relaxations for semialgebraic problems, Math. Programming, 96 (2003), pp. 293–320. · Zbl 1043.14018
[30] P. A. Parrilo and B. Sturmfels, Minimizing polynomial functions, in Algorithmic and Quantitative Real Algebraic Geometry, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 60, S. Basu and L. Gonzalez-Vega, eds., American Mathematical Society, 2003, pp. 83–100. · Zbl 1099.13516
[31] F. A. Potra and R. Sheng, A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming, SIAM J. Optim., 8 (1998), pp. 1007–1028, . · Zbl 0917.65058
[32] A. U. Raghunathan and A. V. Knyazev, Degeneracy in maximal clique decomposition for semidefinite programs, in Proceedings of the 2016 American Control Conference (ACC), IEEE, 2016, pp. 5605–5611.
[33] Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, 2003, . · Zbl 1031.65046
[34] K.-C. Toh, M. J. Todd, and R. H. Tütüncü, On the implementation and usage of sdpt3–a MATLAB software package for semidefinite-quadratic-linear programming, version 4.0, in Handbook on Semidefinite, Conic and Polynomial Optimization, Springer, 2012, pp. 715–754. · Zbl 1334.90117
[35] L. Vandenberghe and M. S. Andersen, Chordal Graphs and Semidefinite Optimization, Now Publishers Incorporated, 2015.
[36] H. Waki, S. Kim, M. Kojima, and M. Muramatsu, Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity, SIAM J. Optim., 17 (2006), pp. 218–242, . · Zbl 1109.65058
[37] H. Waki, S. Kim, M. Kojima, M. Muramatsu, and H. Sugimoto, Algorithm 883: Sparsepop—a sparse semidefinite programming relaxation of polynomial optimization problems, ACM Trans. Math. Software (TOMS), 35 (2008), 15.
[38] T. Weisser, J. B. Lasserre, and K.-C. Toh, Sparse-bsos: A bounded degree SOS hierarchy for large scale polynomial optimization with sparsity, Math. Prog. Comput., 2017, pp. 1–32, . · Zbl 1402.90136
[39] Z. Wen and D. Goldfarb, A line search multigrid method for large-scale nonlinear optimization, SIAM J. Optim., 20 (2009), pp. 1478–1503, . · Zbl 1203.65095
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.