×

zbMATH — the first resource for mathematics

Certification of real inequalities: templates and sums of squares. (English) Zbl 1328.90101
Summary: We consider the problem of certifying lower bounds for real-valued multivariate transcendental functions. The functions we are dealing with are nonlinear and involve semialgebraic operations as well as some transcendental functions like \(\cos\), \(\arctan\), \(\exp\), etc. Our general framework is to use different approximation methods to relax the original problem into polynomial optimization problems, which we solve by sparse sums of squares relaxations. In particular, we combine the ideas of the maxplus approximations (originally introduced in optimal control) and of the linear templates (originally introduced in static analysis by abstract interpretation). The nonlinear templates control the complexity of the semialgebraic relaxations at the price of coarsening the maxplus approximations. In that way, we arrive at a new – template based – certified global optimization method, which exploits both the precision of sums of squares relaxations and the scalability of abstraction methods. We analyze the performance of the method on problems from the global optimization literature, as well as medium-size inequalities issued from the Flyspeck project.

MSC:
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
90C59 Approximation methods and heuristics in mathematical programming
11E25 Sums of squares and representations by other particular quadratic forms
41A10 Approximation by polynomials
41A50 Best approximation, Chebyshev systems
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Adje, A; Gaubert, S; Goubault, E, Coupling policy iteration with semi-definite relaxation to compute accurate numerical invariants in static analysis, Log. Methods Comput. Sci., 8, 1-32, (2012) · Zbl 1237.68054
[2] Akian, M; Gaubert, S; Kolokoltsov, V; Litvinov, G (ed.); Maslov, V (ed.), Set coverings and invertibility of functional Galois connections, No. 377, 19-51, (2005), Providence, RI · Zbl 1080.06001
[3] Akian, M; Gaubert, S; Lakhoua, A, The MAX-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis, SIAM J. Control Optim., 47, 817-848, (2008) · Zbl 1157.49034
[4] Ali, MM; Khompatraporn, C; Zabinsky, ZB, A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems, J. Glob. Optim., 31, 635-672, (2005) · Zbl 1093.90028
[5] Allamigeon, X., Gaubert, S., Magron, V., Werner, B.: Certification of bounds of non-linear functions: the templates method. To appear in the Proceedings of Conferences on Intelligent Computer Mathematics, CICM 2013 Calculemus, Bath (2013a) · Zbl 1390.68570
[6] Allamigeon, X., Gaubert, S., Magron, V., Werner, B.: Certification of inequalities involving transcendental functions: combining SDP and max-plus approximation. To appear in the Proceedings of the European Control Conference, ECC’13, Zurich (2013b) · Zbl 1390.68570
[7] Allamigeon, X., Gaubert, S., Magron, V., Werner, B.: Formal Proofs for Nonlinear Optimization. ArXiv e-prints 1404.7282 (2014)
[8] Berz, M., Makino, K.: Rigorous global search using taylor models. In: Proceedings of the 2009 Conference on Symbolic Numeric Computation, ACM, New York, NY, USA, SNC ’09, pp. 11-20 (2009). doi:10.1145/1577190.1577198 · Zbl 1356.90110
[9] Calafiore, G; Dabbene, F, Reduced vertex set result for interval semidefinite optimization problems, J. Optim. Theory Appl., 139, 17-33, (2008) · Zbl 1189.90114
[10] Cannarsa, P., Sinestrari, C.: Semiconcave functions, Hamilton-Jacobi equations, and optimal control. In: Progress in Nonlinear Differential Equations and Their Applications, Birkhäuser, Boston (2004) http://books.google.fr/books?id=kr-8FpVY2ooC · Zbl 1095.49003
[11] Cartis, C; Gould, NIM; Toint, PL, Adaptive cubic regularisation methods for unconstrained optimization. part i: motivation, convergence and numerical results, Math. Program., 127, 245-295, (2011) · Zbl 1229.90192
[12] Chevillard, S., Joldes, M., Lauter, C.: Sollya: An environment for the development of numerical codes. In: Fukuda, K., van der Hoeven, J., Joswig, M., Takayama, N. (eds). Mathematical Software—ICMS 2010, Springer, Heidelberg, Germany, Lecture Notes in Computer Science, vol. 6327, pp. 28-31 (2010) · Zbl 1295.65143
[13] Fleming, WH; McEneaney, WM, A MAX-plus-based algorithm for a Hamilton-Jacobi-Bellman equation of nonlinear filtering, SIAM J. Control Optim., 38, 683-710, (2000) · Zbl 0949.35039
[14] Gaubert, S., McEneaney, W.M., Qu, Z.: Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms. In: CDC-ECC, IEEE, pp. 1054-1061 (2011)
[15] Gil, A., Segura, J., Temme, N.M.: Numerical Methods for Special Functions, 1st edn. Society for Industrial and Applied Mathematics, Philadelphia, PA (2007) · Zbl 1144.65016
[16] Gruber, P.M.: Convex and Discrete Geometry. Springer, Berlin (2007) · Zbl 1139.52001
[17] Hales, TC, A proof of the Kepler conjecture, Math. Intell., 16, 47-58, (1994) · Zbl 0844.52018
[18] Hales, T.C.: A proof of the Kepler conjecture. Ann. Math. (2) 162(3), 1065-1185 (2005). doi:10.4007/annals.2005.162.1065 · Zbl 1096.52010
[19] Hansen, E., Greenberg, R.: An interval newton method. Appl. Math. Comput. 12(2-3):89-98 (1983). doi:10.1016/0096-3003(83)90001-2, http://www.sciencedirect.com/science/article/pii/0096300383900012 · Zbl 0526.65040
[20] Hansen, ER, Sharpening interval computations, Reliab. Comput., 12, 21-34, (2006) · Zbl 1088.65025
[21] Kaltofen, E.L., Li, B., Yang, Z., Zhi, L.: Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients. JSC 47(1), 1-15 (2012). in memory of Wenda Wu (1929-2009) · Zbl 1229.90115
[22] Lakhoua, A.: Max-Plus Finite Element Method for the Numerical Resolution of Deterministic Optimal Control Problems. PhD thesis. University of Paris 6 (2007)
[23] Lasserre, J; Thanh, T, Convex underestimators of polynomials, J. Glob. Optim., 56, 1-25, (2013) · Zbl 1273.90160
[24] Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 796-817, (2001) · Zbl 1010.90061
[25] Lasserre, JB; Putinar, M, Positivity and optimization for semi-algebraic functions, SIAM J. Optim., 20, 3364-3383, (2010) · Zbl 1210.14068
[26] Magron, V.: Nlcertify: A tool for formal nonlinear optimization. In: Hong, H., Yap, C. (eds). Mathematical Software—ICMS 2014, Lecture Notes in Computer Science, vol. 8592, pp. 315-320. Springer, Berlin (2014). doi:10.1007/978-3-662-44199-2_49 · Zbl 1251.65168
[27] Maso, G.: An Introduction to Gamma-Convergence. Birkhäuser, Basel (1993) · Zbl 0816.49001
[28] McEneaney, W.M.: Max-plus methods for nonlinear control and estimation. In: Systems & Control: Foundations & Applications. Birkhäuser Boston Inc., Boston, MA (2006) · Zbl 1103.93005
[29] McEneaney, WM, A curse-of-dimensionality-free numerical method for solution of certain HJB pdes, SIAM J. Control Optim., 46, 1239-1276, (2007) · Zbl 1251.65168
[30] McEneaney, WM., Deshpande, A., Gaubert, S.: Curse-of-complexity attenuation in the curse-of-dimensionality-free method for HJB PDEs. In: Proceedings of the 2008 American Control Conference, Seattle, Washington, USA, pp. 4684-4690 (2008). doi:10.1109/ACC.2008.458723 · Zbl 1237.68054
[31] Messine, F.: Extensions of affine arithmetic: application to unconstrained global optimization. JUCS 8(11), 992-1015 (2002) · Zbl 1274.65184
[32] Montanher, T.M.: Intsolver: An Interval Based Toolbox for Global Optimization. Version 1.0, www.mathworks.com (2009) · Zbl 1229.90192
[33] Nagata, J.: Modern General Topology. Bibliotheca Mathematica. North-Holland Pub. Co, Amsterdam (1974) · Zbl 0181.25401
[34] Parrilo, P.A., Sturmfels, B.: Minimizing polynomial functions, DIMACS Ser. In: Discrete Math. Theoret. Comput. Sci., vol. 60, American Mathematical Society, Providence, RI, pp 83-99 (2003) · Zbl 1099.13516
[35] Peyrl, H; Parrilo, PA, Computing sum of squares decompositions with rational coefficients, Theor. Comput. Sci., 409, 269-281, (2008) · Zbl 1156.65062
[36] Putinar, M, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42, 969-984, (1993) · Zbl 0796.12002
[37] Rockafellar, R.T.: Convex Analysis. Princeton Mathematical Series. Princeton University Press, Princeton, NJ (1970)
[38] Sankaranarayanan, S., Sipma, H.B., Manna, Z.: Scalable analysis of linear systems using mathematical programming. In: Cousot, R. (ed) Proceedings of the Verification, Model Checking and Abstract Interpretation (VMCAI), Springer, Paris, France, LNCS, vol. 3385, pp. 21-47 (2005) · Zbl 1111.68514
[39] Sridharan, S; Gu, M; James, MR; McEneaney, WM, Reduced-complexity numerical method for optimal gate synthesis, Phys. Rev. A, 82, 319, (2010)
[40] 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
[41] Zumkeller, R.: Rigorous Global Optimization. PhD thesis. École Polytechnique (2008) · Zbl 1237.68054
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.