Optimal uncertainty quantification for legacy data observations of Lipschitz functions
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 47 (2013) no. 6, p. 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.

DOI : https://doi.org/10.1051/m2an/2013083
Classification:  60E15,  62G99,  65C50,  90C26
Keywords: uncertainty quantification, probability inequalities, non-convex optimization, Lipschitz functions, legacy data, point observations
@article{M2AN_2013__47_6_1657_0,
     author = {Sullivan, T. J. and McKerns, M. and Meyer, Daniel and Theil, F. and Owhadi, H. and Ortiz, M.},
     title = {Optimal uncertainty quantification for legacy data observations of Lipschitz functions},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
     publisher = {EDP-Sciences},
     volume = {47},
     number = {6},
     year = {2013},
     pages = {1657-1689},
     doi = {10.1051/m2an/2013083},
     mrnumber = {3110491},
     language = {en},
     url = {http://www.numdam.org/item/M2AN_2013__47_6_1657_0}
}
Sullivan, T. J.; McKerns, M.; Meyer, D.; Theil, F.; Owhadi, H.; Ortiz, M. Optimal uncertainty quantification for legacy data observations of Lipschitz functions. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 47 (2013) no. 6, pp. 1657-1689. doi : 10.1051/m2an/2013083. http://www.numdam.org/item/M2AN_2013__47_6_1657_0/

[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 1048347 | Zbl 1168.49014

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

[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 1392947 | Zbl 0874.62111

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

[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 1700749 | Zbl 0172.21201

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

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

[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 84916 | Zbl 0074.13002

[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 182949 | Zbl 0151.30205

[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 1246501 | Zbl 0796.49032

[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 0009.03904

[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 332165 | Zbl 0297.90047

[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 1109.68620

[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 2464508 | Zbl 1194.74550

[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 1036755 | Zbl 0712.05012

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

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

[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 1562984 | Zbl 0010.34606

[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 3049922 | Zbl 1278.60040

[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 2191377 | Zbl 1186.90004

[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 2803123

[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 426084 | Zbl 0298.28001

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

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

[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 1479553 | Zbl 0888.90135

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

[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 2809903 | Zbl 1217.74151

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

[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 11702 | Zbl 0061.37507

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

[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 580635 | Zbl 0442.28011