×

zbMATH — the first resource for mathematics

Solving equations and optimization problems with uncertainty. (English) Zbl 1416.65141
Summary: We study the problem of detecting zeros of continuous functions that are known only up to an error bound, extending our theoretical work [J. ACM 62, No. 4, Paper No. 26, 19 p. (2015; Zbl 1423.68208)] with explicit algorithms and experiments with an implementation (https://bitbucket.org/robsatteam/rob-sat). Further, we show how to use the algorithm for approximating worst-case optima in optimization problems in which the feasible domain is defined by the zero set of a function \(f: X\rightarrow\mathbb{R}^n\) which is only known approximately. The algorithm first identifies a subdomain \(A\) where the function \(f\) is provably non-zero, a simplicial approximation \(f': A\rightarrow S^{n-1}\) of \(f/|f|\), and then verifies non-extendability of \(f'\) to \(X\) to certify a zero. Deciding extendability is based on computing the cohomological obstructions and their persistence. We describe an explicit algorithm for the primary and secondary obstruction, two stages of a sequence of algorithms with increasing complexity. Using elements and techniques of persistent homology, we quantify the persistence of these obstructions and hence of the robustness of zero. We provide experimental evidence that for random Gaussian fields, the primary obstruction – a much less computationally demanding test than the secondary obstruction – is typically sufficient for approximating robustness of zero.
MSC:
65H10 Numerical computation of solutions to systems of equations
55U10 Simplicial sets and complexes in algebraic topology
Software:
Gudhi; TopDeg; PHAT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adler, R.J.: The Geometry of Random Fields, vol. 62. SIAM, Philadelphia (1981) · Zbl 0478.60059
[2] Adler, R.J., Bobrowski, O., Borman, M.S., Subag, E., Weinberger, S.: Persistent homology for random fields and complexes (2010)
[3] Alefeld, G.E., Shen, Z.: Miranda’s theorem and the verification of solution of linear complementarity problems. Technical Report 01/05, Institut für Wissenschaftliches Rechnen und Mathematische Modellbildung (2001)
[4] Alefeld, G; Frommer, A; Heindl, G; Mayer, J, On the existence theorems of Kantorovich, miranda and Borsuk, Electron. Trans. Numer. Anal., 17, 102-111, (2004) · Zbl 1080.47042
[5] Allgower, E.L., Georg, K.: Introduction to Numerical Continuation Methods, vol. 45. SIAM, Philadelphia (2003) · Zbl 1036.65047
[6] Aubry, C; Desmare, R; Jaulin, L, Loop detection of mobile robots using interval analysis, Automatica, 49, 463-470, (2013) · Zbl 1259.93078
[7] Aubry, C; Desmare, R; Jaulin, L, Kernel characterization of an interval function, Math. Comput. Sci., 8, 379-390, (2014) · Zbl 1302.65117
[8] Bauer, U., Kerber, M., Reininghaus, J., Wagner, H.: Phat—persistent homology algorithms toolbox. In: Mathematical Software—ICMS 2014, pp. 137-143. Springer, Berlin (2014) · Zbl 1402.65187
[9] Bendich, P., Edelsbrunner, H., Morozov, D., Patel, A.: The robustness of level sets. In: Berg, M., Meyer, U. (eds.) Algorithms—ESA 2010. Lecture Notes in Computer Science, vol. 6346, pp. 1-10. Springer, Berlin (2010). https://doi.org/10.1007/978-3-642-15775-2_1 · Zbl 1287.68167
[10] Bendich, P., Edelsbrunner, H., Morozov, D., Patel, A.: Homology and robustness of level and interlevel sets. Homol. Homotopy Appl. 15(1), 51-72 (2013). http://projecteuclid.org/euclid.hha/1383943667 · Zbl 1266.55004
[11] Ben-Tal, A; Nemirovski, A, Robust optimization—methodology and applications, Math. Program., 92, 453-480, (2002) · Zbl 1007.90047
[12] Ben-Tal, A., Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2009). http://books.google.cz/books?id=DttjR7IpjUEC · Zbl 1221.90001
[13] Bertsimas, D; Brown, DB; Caramanis, C, Theory and applications of robust optimization, SIAM Rev., 53, 464-501, (2011) · Zbl 1233.90259
[14] Beyer, HG; Sendhoff, B, Robust optimization—a comprehensive survey, Comput. Methods Appl. Mech. Eng., 196, 3190-3218, (2007) · Zbl 1173.74376
[15] Bredon, G.: Topology and Geometry. Graduate Texts in Mathematics, vol. 139. Springer, Berlin (1993) · Zbl 0791.55001
[16] Buchmann, J., Squirrel, D.: Kernels of integer matrices via modular arithmetic. Technical report (1999). https://www.researchgate.net/publication/2611992_Kernels_of_Integer_Matrices_via_Modular_Arithmetic
[17] Čadek, M., Krčál, M., Matoušek, J., Vokřínek, L., Wagner, U.: Extendability of continuous maps is undecidable. Discret. Comput. Geom. 51(1), 24-66 (2013, to appear). Preprint. arXiv:1302.2370 · Zbl 1358.68297
[18] Čadek, M; Krčál, M; Matoušek, J; Sergeraert, F; Vokřínek, L; Wagner, U, Computing all maps into a sphere, J. ACM, 61, 17:1-17:44, (2014) · Zbl 1295.68196
[19] Čadek, M; Krčál, M; Matoušek, J; Vokřínek, L; Wagner, U, Polynomial-time computation of homotopy groups and postnikov systems in fixed dimension, SIAM J. Comput., 43, 1728-1780, (2014) · Zbl 1320.68099
[20] Chazal, F., Patel, A., Škraba, P.: Computing the robustness of roots. Appl. Math. Lett. 25(11), 1725—1728 (2012). http://ailab.ijs.si/primoz_skraba/papers/fp.pdf · Zbl 1253.65076
[21] Chung, M.K., Bubenik, P., Kim, P.T.: Persistence diagrams of cortical surface data. In: Information Processing in Medical Imaging: 21st International Conference, IPMI 2009, Williamsburg, VA, USA, July 5-10, 2009. Proceedings, pp. 386-397. Springer, Berlin (2009). https://doi.org/10.1007/978-3-642-02498-6_32
[22] Dian, J; Kearfott, RB, Existence verification for singular and nonsmooth zeros of real nonlinear systems, Math. Comput., 72, 757-766, (2003) · Zbl 1025.65030
[23] Edelsbrunner, H; Letscher, D; Zomorodian, A, Topological persistence and simplification, Discret. Comput. Geom., 28, 511-533, (2002) · Zbl 1011.68152
[24] Eilenberg, S., Zilber, J.A.: On products of complexes. Am. J. Math. 200-204 (1953) · Zbl 0050.17301
[25] Franek, P., Krčál, M.: On computability and triviality of well groups. In: Arge, L., Pach, J. (eds.) 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), vol. 34, pp. 842-856. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015a). https://doi.org/10.4230/LIPIcs.SOCG.2015.842 · Zbl 1386.65144
[26] Franek, P; Krčál, M, Robust satisfiability of systems of equations, J. ACM, 62, 26:1-26:19, (2015) · Zbl 1386.65144
[27] Franek, P., Krčál, M.: Persistence of zero sets. Homol. Homotopy Appl. (2016, to appear). arXiv preprint. arXiv:1507.04310
[28] Franek, P; Ratschan, S, Effective topological degree computation based on interval arithmetic, AMS Math. Comput., 84, 1265-1290, (2015) · Zbl 1318.55002
[29] Franek, P., Ratschan, S., Zgliczynski, P.: Satisfiability of systems of equations of real analytic functions is quasi-decidable. In: Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS). LNCS, vol. 6907, pp. 315-326. Springer, Berlin (2011) · Zbl 1343.03036
[30] Franek, P., Ratschan, S., Zgliczynski, P.: Quasi-decidability of a fragment of the first-order theory of real numbers. J. Autom. Reason. 1-29 (2015). https://doi.org/10.1007/s10817-015-9351-3 · Zbl 1437.03047
[31] Friedman, G, An elementary illustrated introduction to simplicial sets, Rocky Mt. J. Math., 42, 353-423, (2012) · Zbl 1248.55001
[32] Frommer, A., Lang, B.: Existence tests for solutions of nonlinear equations using Borsuk’s theorem. SIAM J. Numer. Anal. 43(3), 1348-1361 (2005). https://doi.org/10.1137/S0036142903438148. http://link.aip.org/link/?SNA/43/1348/1 · Zbl 1095.47057
[33] Gao, M., Chen, C., Zhang, S., Qian, Z., Metaxas, D., Axel, L.: Segmenting the papillary muscles and the trabeculae from high resolution cardiac ct through restoration of topological handles. In: International Conference on Information Processing in Medical Imaging (IPMI) (2013)
[34] Goldsztejn, A., Jaulin, L.: Inner and outer approximations of existentially quantified equality constraints. In: Principles and practice of constraint programming-CP 2006, pp. 198-212 (2006) · Zbl 1160.68546
[35] Goldsztejn, A., Jaulin, L.: Inner approximation of the range of vector-valued functions. Reliab. Comput. 1-23 (2010)
[36] Gonzalez-Diaz, R; Real, P, Simplification techniques for maps in simplicial topology, J. Symb. Comput., 40, 1208-1224, (2005) · Zbl 1138.55013
[37] Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2001). https://www.math.cornell.edu/ hatcher/AT/ATpage.html · Zbl 1044.55001
[38] Jeannerod, CP; Pernet, C; Storjohann, A, Rank-profile revealing Gaussian elimination and the cup matrix decomposition, J. Symb. Comput., 56, 46-68, (2013) · Zbl 1329.65065
[39] Krčál, M., Pilarczyk, P.: Computation of Cubical Steenrod Squares, pp. 140-151. Springer International Publishing, Cham (2016). https://doi.org/10.1007/978-3-319-39441-1_13 · Zbl 1339.68273
[40] Krčál, M., Matoušek, J., Sergeraert, F.: Polynomial-time homology for simplicial Eilenberg-MacLane spaces. J. Found. Comput. Math. 13, 935-963 (2013). Preprint. arXiv:1201.6222
[41] Lang, A; Potthoff, J, Fast simulation of Gaussian random fields, Monte Carlo Methods Appl., 17, 195-214, (2011) · Zbl 1226.65008
[42] Maria, C., Boissonnat, J.D., Glisse, M., Yvinec, M.: The Gudhi library: simplicial complexes and persistent homology. In: Hong, H., Yap, C. (eds.) Mathematical Software—ICMS 2014. Lecture Notes in Computer Science, vol. 8592, pp. 167-174. Springer, Berlin (2014). https://doi.org/10.1007/978-3-662-44199-2_28 · Zbl 1402.57001
[43] Merlet, JP, Interval analysis and reliability in robotics, Int. J. Reliab. Saf., 3, 104-130, (2009)
[44] Prasolov, V.V.: Elements of Homology Theory. Graduate Studies in Mathematics. American Mathematical Society, Providence (2007) · Zbl 1120.55001
[45] Rump, S.M.: Verification methods: rigorous results using floating-point arithmetic. Acta Numer. 19, 287-449 (2010). https://doi.org/10.1017/S096249291000005X. http://journals.cambridge.org/article_S096249291000005X · Zbl 1323.65046
[46] Steenrod, NE, Products of cocycles and extensions of mappings, Ann. Math., 48, 290-320, (1947) · Zbl 0030.41602
[47] Steenrod, NE, Cohomology operations, and obstructions to extending continuous functions, Adv. Math., 8, 371-416, (1972) · Zbl 0236.55018
[48] Storjohann, A.: A fast + practical + deterministic algorithm for triangularizing integer matrices (1996). http://e-collection.library.ethz.ch/eserv/eth:3348/eth-3348-01.pdf
[49] Storjohann, A, The shifted number system for fast linear algebra on integer matrices, J. Complex., 21, 609-650, (2005) · Zbl 1101.68045
[50] Vokřínek, L.: Decidability of the extension problem for maps into odd-dimensional spheres. ArXiv e-prints (2014)
[51] Wang, PS, The undecidability of the existence of zeros of real elementary functions, J. ACM, 21, 586-589, (1974) · Zbl 0289.68017
[52] Wofsey, E.: Triviality of relative cup product \({H}^2({X},{A})× {H}^2({X},{A})→ {H}^4({X},{A})\) for spaces embeddable to \({R}^4\). Math. Stack Exch. https://math.stackexchange.com/q/1612524 (version: 2017-04-13)
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.