Optimal uncertainty quantification for legacy data observations of Lipschitz functions

Sullivan, T. J.; McKerns, M.; Meyer, D.; Theil, F.; Owhadi, H.; Ortiz, M.

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 47 (2013) no. 6, pp. 1657-1689.

We consider the problem of providing optimal uncertainty quantification (UQ) - and hence rigorous certification - for partially-observed functions. We present a UQ framework within which the observations may be small or large in number, and need not carry information about the probability distribution of the system in operation. The UQ objectives are posed as optimization problems, the solutions of which are optimal bounds on the quantities of interest; we consider two typical settings, namely parameter sensitivities (McDiarmid diameters) and output deviation (or failure) probabilities. The solutions of these optimization problems depend non-trivially (even non-monotonically and discontinuously) upon the specified legacy data. Furthermore, the extreme values are often determined by only a few members of the data set; in our principal physically-motivated example, the bounds are determined by just 2 out of 32 data points, and the remainder carry no information and could be neglected without changing the final answer. We propose an analogue of the simplex algorithm from linear programming that uses these observations to offer efficient and rigorous UQ for high-dimensional systems with high-cardinality legacy data. These findings suggest natural methods for selecting optimal (maximally informative) next experiments.

Classification : 60E15, 62G99, 65C50, 90C26
Mots clés : uncertainty quantification, probability inequalities, non-convex optimization, Lipschitz functions, legacy data, point observations

[1] M. Adams, A. Lashgari, B. Li, M. Mckerns, J.M. Mihaly, M. Ortiz, H. Owhadi, A.J. Rosakis, M. Stalzer T.J. Sullivan, Rigorous model-based uncertainty quantification with application to terminal ballistics. Part II: Systems with uncontrollable inputs and large scatter. J. Mech. Phys. Solids 60 (2011) 1002-1019.

[2] J.-P. Aubin and H. Frankowska, Set-Valued Analysis, Modern Birkhäuser Classics, Birkhäuser Boston Inc., Boston, MA (2009), Reprint of the 1990 edition [MR1048347]. | MR | Zbl

[3] I. Babuška, F. Nobile and R. Tempone, Reliability of computational science. Numer. Methods Partial Differ. Eq. 23 (2007) 753-784. | MR | Zbl

[4] R. E. Barlow and F. Proschan, Mathematical Theory of Reliability, in vol. 17 of Classics in Applied Mathematics. Society Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1996). With contributions by L. C. Hunter, Reprint of the 1965 original [MR 0195566]. | MR | Zbl

[5] D. Bertsimas and I. Popescu, Optimal inequalities in probability theory: a convex optimization approach. SIAM J. Optim. 15 (2005) 780-804. | MR | Zbl

[6] P. Billingsley, Convergence of Probability Measures, 2nd edn., Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley and Sons Inc., New York (1999). http://dx.doi.org/10.1002/9780470316962. MR 1700749 (2000e:60008) | MR | Zbl

[7] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, Cambridge (2004). | MR | Zbl

[8] H. Federer, Geometric Measure Theory, Die Grundlehren der Mathematischen Wissenschaften, Band 153. Springer-Verlag New York Inc., New York (1969). | MR | Zbl

[9] W. Hoeffding, The role of assumptions in statistical decisions. Proc. of the Third Berkeley Symposium on Mathematical Statistics and Probability, vol. I, 1954-1955 (Berkeley and Los Angeles). University of California Press (1956) 105-114. | MR | Zbl

[10] A. Holder, Mathematical Programming Glossary, INFORMS Computing Society, http://glossary.computing.society.informs.org (2006). Originally authored by H. J. Greenberg, 1999-2006.

[11] J.R. Isbell, Six theorems about injective metric spaces, Comment. Math. Helv. 39 (1964), 65-76. | MR | Zbl

[12] D.R. Jones, C.D. Perttunen and B.E. Stuckman, Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79 (1993) 157-181. | MR | Zbl

[13] A.A. Kidane, A. Lashgari, B. Li, M. Mckerns, M. Ortiz, H. Owhadi, G. Ravichandran, M. Stalzer and T.J. Sullivan, Rigorous model-based uncertainty quantification with application to terminal ballistics. Part I: Systems with controllable inputs and small scatter. J. Mech. Phys. Solids 60 (2011) 983-1001.

[14] M.D. Kirszbraun, Über die zusammenziehende und Lipschitzsche Transformationen. Fund. Math. 22 (1934) 77-108. | Zbl

[15] V. Klee and G.J. Minty, How good is the simplex algorithm?, Inequalities, III, in Proc. Third Sympos. (Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin). Academic Press, New York (1972) 159-175. | MR | Zbl

[16] P. Limbourg, Multi-objective optimization of problems with epistemic uncertainty, Evolutionary Multi-Criterion Optimization, in Lect. Notes Comput. Sci., of vol. 3410, edited by C.A. Coello Coello, A. Hernández Aguirre and E. Zitzler. Springer Berlin/Heidelberg (2005) 413-427. | Zbl

[17] L.J. Lucas, H. Owhadi and M. Ortiz, Rigorous verification, validation, uncertainty quantification and certification through concentration-of-measure inequalities. Comput. Methods Appl. Mech. Engrg. 197 (2008) 51-52, 4591-4609. | MR | Zbl

[18] C. Mcdiarmid, On the method of bounded differences, Surveys in combinatorics, London Math. Soc. in vol. 141 of Lecture Note Ser. Cambridge Univ. Press, Cambridge (1989) 148-188. | MR | Zbl

[19] C. Mcdiarmid, Centering sequences with bounded differences, Combin. Probab. Comput. 6 (1997) 79-86, | MR | Zbl

[20] C. Mcdiarmid, Concentration, Probabilistic Methods for Algorithmic Discrete Mathematics. In vol. 16 of Algorithms Combin. Springer, Berlin (1998) 195-248. | MR | Zbl

[21] M. Mckerns, P. Hung and M. Aivazis, Mystic: A simple model-independent inversion framework (2009).

[22] M. Mckerns, H. Owhadi, C. Scovel, T.J. Sullivan and M. Ortiz, The optimal uncertainty algorithm in the mystic framework, Caltech CACR Technical Report, August 2010, available at http://arxiv.org/pdf/1202.1055v1.

[23] M.M. Mckerns, L. Strand, T.J. Sullivan, A. Fang and M.A.G. Aivazis, Building a framework for predictive science. Proc. of the 10th Python in Science Conference (SciPy 2011), edited by S. van der Walt and J. Millman (2011) 67-78. Available at http://jarrodmillman.com/scipy2011/pdfs/mckerns.pdf.

[24] E.J. Mcshane, Extension of range of functions. Bull. Amer. Math. Soc. 40 (1934) 837-842. | MR | Zbl

[25] R. Morrison, C. Bryant, G. Terejanu, K. Miki and S. Prudhomme, Optimal data split methodology for model validation, Proc. of World Congress on Engrg and Comput. Sci. (2011) vol. II, 1038-1043.

[26] W.L. Oberkampf, J.C. Helton, C.A. Joslyn, S.F. Wojtkiewicz and S. Ferson, Challenge problems: Uncertainty in system response given uncertain parameters. Reliab. Eng. Sys. Safety 85 (2004) 11-19.

[27] W.L. Oberkampf, T.G. Trucano and C. Hirsch, Verification, validation and predictive capability in computational engineering and physics. Appl. Mech. Rev. 57 (2004) 345-384.

[28] H. Owhadi, C. Scovel, T. J. Sullivan, M. Mckerns and M. Ortiz, Optimal Uncertainty Quantification. SIAM Rev. To appear. | MR | Zbl

[29] K.V. Price, R.M. Storn and J.A. Lampinen, Differential Evolution: A Practical Approach to Global Optimization, Natural Comput. Ser. Springer-Verlag, Berlin (2005). | MR | Zbl

[30] C.J. Roy and W.L. Oberkampf, A complete framework for verification, validation and uncertainty quantification in scientific computing, 48th AIAA Aerospace Sciences Meeting Including the New Horizons Forum and Aerospace Exposition (2010). | MR

[31] L. Schwartz, Radon Measures on Arbitrary Topological Spaces and Cylindrical Measures, Published for the Tata Institute of Fundamental Research, Bombay by Oxford University Press, London (1973). Tata Institute of Fundamental Research Studies in Mathematics, No. 6. | MR | Zbl

[32] A.V. Skorohod, Limit theorems for stochastic processes, Teor. Veroyatnost. i Primenen. (Theor. Probab. Appl.) 1 (1956), 289-319. | MR | Zbl

[33] L.A. Steen and J.A. Seebach, Jr., Counterexamples in Topology, 2nd edn. Springer-Verlag, New York (1978). | MR | Zbl

[34] R. Storn and K. Price, Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11 (1997) 341-359. | MR | Zbl

[35] A.M. Stuart, Inverse problems: a Bayesian perspective. Acta Numer. 19 (2010) 451-559. | MR | Zbl

[36] T. J. Sullivan, U. Topcu, M. Mckerns and H. Owhadi, Uncertainty quantification via codimension-one partitioning. Int. J. Numer. Meth. Engng. 85 (2011) 1499-1521. | MR | Zbl

[37] M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. (1995) 73-205. | Numdam | MR | Zbl

[38] U. Topcu, L. J. Lucas, H. Owhadi and M. Ortiz, Rigorous uncertainty quantification without integral testing. Reliab. Eng. Sys. Safety 96 (2011) 1085-1091.

[39] F.A. Valentine, A Lipschitz condition preserving extension for a vector function. Amer. J. Math. 67 (1945) 83-93. | MR | Zbl

[40] V.H. Vu, Concentration of non-Lipschitz functions and applications, Random Structures Algorithms 20 (2002) 262-316. | MR | Zbl

[41] M.L. Wage, The product of Radon spaces, Uspekhi Mat. Nauk 35 (1980) 151-153, International Topology Conference (Moscow State Univ., Moscow, 1979), Translated from the English by A.V. Arhangel′skiĭ. | MR | Zbl