Optimal uncertainty quantification for legacy data observations of Lipschitz functions

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

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique (2013)

  • Volume: 47, Issue: 6, page 1657-1689
  • ISSN: 0764-583X

Abstract

top
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.

How to cite

top

Sullivan, T. J., et al. "Optimal uncertainty quantification for legacy data observations of Lipschitz functions." ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique 47.6 (2013): 1657-1689. <http://eudml.org/doc/273325>.

@article{Sullivan2013,
abstract = {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.},
author = {Sullivan, T. J., McKerns, M., Meyer, D., Theil, F., Owhadi, H., Ortiz, M.},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique},
keywords = {uncertainty quantification; probability inequalities; non-convex optimization; Lipschitz functions; legacy data; point observations},
language = {eng},
number = {6},
pages = {1657-1689},
publisher = {EDP-Sciences},
title = {Optimal uncertainty quantification for legacy data observations of Lipschitz functions},
url = {http://eudml.org/doc/273325},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Sullivan, T. J.
AU - McKerns, M.
AU - Meyer, D.
AU - Theil, F.
AU - Owhadi, H.
AU - Ortiz, M.
TI - Optimal uncertainty quantification for legacy data observations of Lipschitz functions
JO - ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 6
SP - 1657
EP - 1689
AB - 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.
LA - eng
KW - uncertainty quantification; probability inequalities; non-convex optimization; Lipschitz functions; legacy data; point observations
UR - http://eudml.org/doc/273325
ER -

References

top
  1. [1] M. Adams, A. Lashgari, B. Li, M. McKerns, J.M. Mihaly, M. Ortiz, H. Owhadi, A.J. Rosakis, M. StalzerT.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. [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]. Zbl1168.49014MR1048347
  3. [3] I. Babuška, F. Nobile and R. Tempone, Reliability of computational science. Numer. Methods Partial Differ. Eq.23 (2007) 753–784. Zbl1118.65030MR2326192
  4. [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]. Zbl0874.62111MR1392947
  5. [5] D. Bertsimas and I. Popescu, Optimal inequalities in probability theory: a convex optimization approach. SIAM J. Optim.15 (2005) 780–804. Zbl1077.60020MR2142860
  6. [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) Zbl0172.21201MR1700749
  7. [7] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, Cambridge (2004). Zbl1058.90049MR2061575
  8. [8] H. Federer, Geometric Measure Theory, Die Grundlehren der Mathematischen Wissenschaften, Band 153. Springer-Verlag New York Inc., New York (1969). Zbl0176.00801MR257325
  9. [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. Zbl0074.13002MR84916
  10. [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. [11] J.R. Isbell, Six theorems about injective metric spaces, Comment. Math. Helv.39 (1964), 65–76. Zbl0151.30205MR182949
  12. [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. Zbl0796.49032MR1246501
  13. [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. [14] M.D. Kirszbraun, Über die zusammenziehende und Lipschitzsche Transformationen. Fund. Math.22 (1934) 77–108. Zbl0009.03904
  15. [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. Zbl0297.90047MR332165
  16. [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. Zbl1109.68620
  17. [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. Zbl1194.74550MR2464508
  18. [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. Zbl0712.05012MR1036755
  19. [19] C. McDiarmid, Centering sequences with bounded differences, Combin. Probab. Comput.6 (1997) 79–86, Zbl0869.60040MR1436721
  20. [20] C. McDiarmid, Concentration, Probabilistic Methods for Algorithmic Discrete Mathematics. In vol. 16 of Algorithms Combin. Springer, Berlin (1998) 195–248. Zbl0927.60027MR1678578
  21. [21] M. McKerns, P. Hung and M. Aivazis, Mystic: A simple model-independent inversion framework (2009). 
  22. [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. Zbl1278.60040
  23. [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. [24] E.J. McShane, Extension of range of functions. Bull. Amer. Math. Soc.40 (1934) 837–842. Zbl0010.34606MR1562984
  25. [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. [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. Safety85 (2004) 11–19. 
  27. [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. [28] H. Owhadi, C. Scovel, T. J. Sullivan, M. McKerns and M. Ortiz, Optimal Uncertainty Quantification. SIAM Rev. To appear. Zbl1278.60040MR3049922
  29. [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). Zbl1186.90004MR2191377
  30. [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). Zbl1230.76049MR2803123
  31. [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. Zbl0298.28001MR426084
  32. [32] A.V. Skorohod, Limit theorems for stochastic processes, Teor. Veroyatnost. i Primenen. (Theor. Probab. Appl.) 1 (1956), 289–319. Zbl0074.33802MR84897
  33. [33] L.A. Steen and J.A. Seebach, Jr., Counterexamples in Topology, 2nd edn. Springer-Verlag, New York (1978). Zbl0211.54401MR507446
  34. [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. Zbl0888.90135MR1479553
  35. [35] A.M. Stuart, Inverse problems: a Bayesian perspective. Acta Numer.19 (2010) 451–559. Zbl1242.65142MR2652785
  36. [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. Zbl1217.74151MR2809903
  37. [37] M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. (1995) 73–205. Zbl0864.60013MR1361756
  38. [38] U. Topcu, L. J. Lucas, H. Owhadi and M. Ortiz, Rigorous uncertainty quantification without integral testing. Reliab. Eng. Sys. Safety96 (2011) 1085–1091. 
  39. [39] F.A. Valentine, A Lipschitz condition preserving extension for a vector function. Amer. J. Math.67 (1945) 83–93. Zbl0061.37507MR11702
  40. [40] V.H. Vu, Concentration of non-Lipschitz functions and applications, Random Structures Algorithms20 (2002) 262–316. Zbl0999.60027MR1900610
  41. [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ĭ. Zbl0442.28011MR580635

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.