December  2019, 1(4): 433-456. doi: 10.3934/fods.2019018

On the incorporation of box-constraints for ensemble Kalman inversion

1. 

Department of Statistics and Applied Probability, National University of Singapore, 119077, Singapore

2. 

Institute of Mathematics, University of Mannheim, 68131 Mannheim, Germany

* Corresponding author: Neil K. Chada

Published  December 2019

Fund Project: The first author is supported by a Singapore Ministry of Education Academic Research Funds Tier 2 grant [MOE2016-T2-2-135]. The third author is grateful to the DFG RTG1953 "Statistical Modeling of Complex Systems and Processes" for funding of this research.

The Bayesian approach to inverse problems is widely used in practice to infer unknown parameters from noisy observations. In this framework, the ensemble Kalman inversion has been successfully applied for the quantification of uncertainties in various areas of applications. In recent years, a complete analysis of the method has been developed for linear inverse problems adopting an optimization viewpoint. However, many applications require the incorporation of additional constraints on the parameters, e.g. arising due to physical constraints. We propose a new variant of the ensemble Kalman inversion to include box constraints on the unknown parameters motivated by the theory of projected preconditioned gradient flows. Based on the continuous time limit of the constrained ensemble Kalman inversion, we discuss a complete convergence analysis for linear forward problems. We adopt techniques from filtering, such as variance inflation, which are crucial in order to improve the performance and establish a correct descent. These benefits are highlighted through a number of numerical examples on various inverse problems based on partial differential equations.

Citation: Neil K. Chada, Claudia Schillings, Simon Weissmann. On the incorporation of box-constraints for ensemble Kalman inversion. Foundations of Data Science, 2019, 1 (4) : 433-456. doi: 10.3934/fods.2019018
References:
[1]

E. E. S. D. Albers, P.-A. Blacquart and A. M. Stuart, Ensemble Kalman Methods with Constraints, , In preparation, 2019. Google Scholar

[2]

N. Amor, G. Rasool and N. C. Bouaynaya, Constrained State Estimation - A Review, arXiv preprint, arXiv: 1807.03463. Google Scholar

[3]

J. L. Anderson, An adaptive covariance inflation error correction algorithm for ensemble filters, Tellus A, 59 (2007), 210-224.   Google Scholar

[4]

————, Spatially and temporally varying adaptive covariance inflation for ensemble filters, Tellus A, 61 (2009), 72–83. Google Scholar

[5]

K. Bergemann and S. Reich, A localization technique for ensemble Kalman filters, Quarterly Journal of the Royal Meteorological Society, 136 (2010), 701-707.   Google Scholar

[6]

————, A mollified ensemble Kalman filter, Quarterly Journal of the Royal Meteorological Society, 136 (2010), 1636–1643. Google Scholar

[7]

D. Bertsekas, Projected newton methods for optimization problems with simple constraints, SIAM Journal on Control and Optimization, 20 (1982), 221-246.  doi: 10.1137/0320018.  Google Scholar

[8]

D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Belmont, MA, 1999.  Google Scholar

[9]

A. N. Bishop and P. Del Moral, On the stability of matrix-valued Riccati diffusions, Electron. J. Probab., 24 (2019), Paper No. 84, 40 pp, arXiv: 1808.00235.  Google Scholar

[10]

D. BlömkerC. Schillings and P. Wacker, A strongly convergent numerical scheme from ensemble kalman inversion, SIAM Journal on Numerical Analysis, 56 (2018), 2537-2562.  doi: 10.1137/17M1132367.  Google Scholar

[11]

D. Blömker, C. Schillings, P. Wacker and S. Weissmann, Well posedness and convergence analysis of the ensemble kalman inversion, Inverse Problems, 35 (2019), 085007, 32pp. doi: 10.1088/1361-6420/ab149c.  Google Scholar

[12] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, USA, 2004.  doi: 10.1017/CBO9780511804441.  Google Scholar
[13]

N. K. Chada, M. A. Iglesias, L. Roininen and A. M. Stuart, Parameterizations for ensemble Kalman inversion, Inverse Problems, 34 (2018), 055009, 31pp. doi: 10.1088/1361-6420/aab6d9.  Google Scholar

[14]

X. Chen, J. D. Lee, X. T. Tong and Y. Zhang, Statistical Inference for Model Parameters in Stochastic Gradient Descent, arXiv e-prints, 2016, arXiv: 1610.08637. Google Scholar

[15]

H. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Mathematics and its Applications, 375. Kluwer Academic Publishers Group, Dordrecht, 1996.  Google Scholar

[16]

G. Evensen, The ensemble Kalman filter: Theoretical formulation and practical implementation, Ocean Dynamics, 53 (2003), 343-367.   Google Scholar

[17]

G. Evensen, Data Assimilation: The Ensemble Kalman Filter, Earth and Environmental Science, Springer Berlin Heidelberg, 2009. doi: 10.1007/978-3-642-03711-5.  Google Scholar

[18]

B. K. P. Hungerlander and F. Rendl, Regularization of inverse problems via box constrained minimization, arXiv preprint, arXiv: 1807.11316, (2018). Google Scholar

[19]

M. A. Iglesias, A regularizing iterative ensemble Kalman method for PDE-constrained inverse problems, Inverse Problems, 32 (2016), 025002, 45pp. doi: 10.1088/0266-5611/32/2/025002.  Google Scholar

[20]

M. A. Iglesias, K. Law and A. M. Stuart, Ensemble Kalman methods for inverse problems, Inverse Problems, 29 (2013), 045001, 20pp. doi: 10.1088/0266-5611/29/4/045001.  Google Scholar

[21]

J. Kaipio and E. Somersalo, Statistical and Computational Inverse Problems, Applied Mathematical Sciences, 160. Springer-Verlag, New York, 2005.  Google Scholar

[22]

R. Kandepu, L. Imsland and B. A. Foss, Constrained State Estimation Using the Unscented Kalman Filter, 16th Mediterranean Conference on Control and Automation, 2008. Google Scholar

[23]

D. KellyK. Law and A. M. Stuart, Well-posedness and accuracy of the ensemble Kalman filter in discrete and continuous time, Nonlinearity, 27 (2014), 2579-2604.  doi: 10.1088/0951-7715/27/10/2579.  Google Scholar

[24]

D. Kelly, A. J. Majda and X. T. Tong, Concrete Ensemble Kalman Filters with Rigorous Catastrophic Filter Divergence, Proceedings of the National Academy of Sciences, 2015. Google Scholar

[25]

E. Kwiatkowski and J. Mandel, Convergence of the square root ensemble Kalman filter in the large ensemble limit, SIAM/ASA Journal on Uncertainty Quantification, 3 (2015), 1-17.  doi: 10.1137/140965363.  Google Scholar

[26]

K. Law, A. M. Stuart and K. Zygalakis, Data Assimilation: A Mathematical Introduction, Texts in Applied Mathematics, 62. Springer, Cham, 2015. doi: 10.1007/978-3-319-20325-6.  Google Scholar

[27]

F. Le Gland, V. Monbet and V.-D. Tran, Large sample asymptotics for the ensemble Kalman filter, The Oxford Handbook of Nonlinear Filtering, 598–631, Oxford Univ. Press, Oxford, 2011.  Google Scholar

[28]

G. Li and A. C. Reynolds, Iterative Ensemble Kalman Filters for Data Assimilation, Society of Petroleum Engineers, 2009. Google Scholar

[29]

D. M. LivingsS. L. Dance and N. K. Nichols, Unbiased ensemble square root filters, Physica D: Nonlinear Phenomena, 237 (2008), 1021-1028.  doi: 10.1016/j.physd.2008.01.005.  Google Scholar

[30]

S. Reich, Data assimilation, Acta Numer., 28 (2019), 635-711.  doi: 10.1017/S0962492919000011.  Google Scholar

[31] S. Reich and C. J. Cotter, Probabilistic Forecasting and Bayesian Data Assimilation, Cambridge University Press, New York, 2015.  doi: 10.1017/CBO9781107706804.  Google Scholar
[32]

C. Schillings and A. M. Stuart, Analysis of the ensemble Kalman filter for inverse problems, SIAM Journal on Numerical Analysis, 55 (2017), 1264-1290.  doi: 10.1137/16M105959X.  Google Scholar

[33]

M. Schmidt, D. Kim and S. Sra, Projected Newton-type Methods in Machine Learning, 2013. Google Scholar

[34]

V. Shikhman and O. Stein, Constrained optimization: Projected gradient flows, Journal of Optimization Theory and Applications, 140 (2009), 117-130.  doi: 10.1007/s10957-008-9445-8.  Google Scholar

[35]

D. Simon, Kalman filtering with state constraints: A survey of linear and nonlinear algorithms, IET Control Theory Appl., 4 (2010), 1303-1318.  doi: 10.1049/iet-cta.2009.0032.  Google Scholar

[36]

A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numerica, 19 (2010), 451-559.  doi: 10.1017/S0962492910000061.  Google Scholar

[37]

M. K. TippettJ. L. AndersonC. H. BishopT. M. Hamill and J. S. Whitaker, Ensemble square root filters, Monthly Weather Review, 131 (2003), 1485-1490.   Google Scholar

[38]

D. Wang, Y. Chen and X. Cai, State and Parameter Estimation of Hydrologic Models Using the Constrained Ensemble Kalman Filter, Monthly Resources Research, 2009. Google Scholar

show all references

References:
[1]

E. E. S. D. Albers, P.-A. Blacquart and A. M. Stuart, Ensemble Kalman Methods with Constraints, , In preparation, 2019. Google Scholar

[2]

N. Amor, G. Rasool and N. C. Bouaynaya, Constrained State Estimation - A Review, arXiv preprint, arXiv: 1807.03463. Google Scholar

[3]

J. L. Anderson, An adaptive covariance inflation error correction algorithm for ensemble filters, Tellus A, 59 (2007), 210-224.   Google Scholar

[4]

————, Spatially and temporally varying adaptive covariance inflation for ensemble filters, Tellus A, 61 (2009), 72–83. Google Scholar

[5]

K. Bergemann and S. Reich, A localization technique for ensemble Kalman filters, Quarterly Journal of the Royal Meteorological Society, 136 (2010), 701-707.   Google Scholar

[6]

————, A mollified ensemble Kalman filter, Quarterly Journal of the Royal Meteorological Society, 136 (2010), 1636–1643. Google Scholar

[7]

D. Bertsekas, Projected newton methods for optimization problems with simple constraints, SIAM Journal on Control and Optimization, 20 (1982), 221-246.  doi: 10.1137/0320018.  Google Scholar

[8]

D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Belmont, MA, 1999.  Google Scholar

[9]

A. N. Bishop and P. Del Moral, On the stability of matrix-valued Riccati diffusions, Electron. J. Probab., 24 (2019), Paper No. 84, 40 pp, arXiv: 1808.00235.  Google Scholar

[10]

D. BlömkerC. Schillings and P. Wacker, A strongly convergent numerical scheme from ensemble kalman inversion, SIAM Journal on Numerical Analysis, 56 (2018), 2537-2562.  doi: 10.1137/17M1132367.  Google Scholar

[11]

D. Blömker, C. Schillings, P. Wacker and S. Weissmann, Well posedness and convergence analysis of the ensemble kalman inversion, Inverse Problems, 35 (2019), 085007, 32pp. doi: 10.1088/1361-6420/ab149c.  Google Scholar

[12] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, USA, 2004.  doi: 10.1017/CBO9780511804441.  Google Scholar
[13]

N. K. Chada, M. A. Iglesias, L. Roininen and A. M. Stuart, Parameterizations for ensemble Kalman inversion, Inverse Problems, 34 (2018), 055009, 31pp. doi: 10.1088/1361-6420/aab6d9.  Google Scholar

[14]

X. Chen, J. D. Lee, X. T. Tong and Y. Zhang, Statistical Inference for Model Parameters in Stochastic Gradient Descent, arXiv e-prints, 2016, arXiv: 1610.08637. Google Scholar

[15]

H. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, Mathematics and its Applications, 375. Kluwer Academic Publishers Group, Dordrecht, 1996.  Google Scholar

[16]

G. Evensen, The ensemble Kalman filter: Theoretical formulation and practical implementation, Ocean Dynamics, 53 (2003), 343-367.   Google Scholar

[17]

G. Evensen, Data Assimilation: The Ensemble Kalman Filter, Earth and Environmental Science, Springer Berlin Heidelberg, 2009. doi: 10.1007/978-3-642-03711-5.  Google Scholar

[18]

B. K. P. Hungerlander and F. Rendl, Regularization of inverse problems via box constrained minimization, arXiv preprint, arXiv: 1807.11316, (2018). Google Scholar

[19]

M. A. Iglesias, A regularizing iterative ensemble Kalman method for PDE-constrained inverse problems, Inverse Problems, 32 (2016), 025002, 45pp. doi: 10.1088/0266-5611/32/2/025002.  Google Scholar

[20]

M. A. Iglesias, K. Law and A. M. Stuart, Ensemble Kalman methods for inverse problems, Inverse Problems, 29 (2013), 045001, 20pp. doi: 10.1088/0266-5611/29/4/045001.  Google Scholar

[21]

J. Kaipio and E. Somersalo, Statistical and Computational Inverse Problems, Applied Mathematical Sciences, 160. Springer-Verlag, New York, 2005.  Google Scholar

[22]

R. Kandepu, L. Imsland and B. A. Foss, Constrained State Estimation Using the Unscented Kalman Filter, 16th Mediterranean Conference on Control and Automation, 2008. Google Scholar

[23]

D. KellyK. Law and A. M. Stuart, Well-posedness and accuracy of the ensemble Kalman filter in discrete and continuous time, Nonlinearity, 27 (2014), 2579-2604.  doi: 10.1088/0951-7715/27/10/2579.  Google Scholar

[24]

D. Kelly, A. J. Majda and X. T. Tong, Concrete Ensemble Kalman Filters with Rigorous Catastrophic Filter Divergence, Proceedings of the National Academy of Sciences, 2015. Google Scholar

[25]

E. Kwiatkowski and J. Mandel, Convergence of the square root ensemble Kalman filter in the large ensemble limit, SIAM/ASA Journal on Uncertainty Quantification, 3 (2015), 1-17.  doi: 10.1137/140965363.  Google Scholar

[26]

K. Law, A. M. Stuart and K. Zygalakis, Data Assimilation: A Mathematical Introduction, Texts in Applied Mathematics, 62. Springer, Cham, 2015. doi: 10.1007/978-3-319-20325-6.  Google Scholar

[27]

F. Le Gland, V. Monbet and V.-D. Tran, Large sample asymptotics for the ensemble Kalman filter, The Oxford Handbook of Nonlinear Filtering, 598–631, Oxford Univ. Press, Oxford, 2011.  Google Scholar

[28]

G. Li and A. C. Reynolds, Iterative Ensemble Kalman Filters for Data Assimilation, Society of Petroleum Engineers, 2009. Google Scholar

[29]

D. M. LivingsS. L. Dance and N. K. Nichols, Unbiased ensemble square root filters, Physica D: Nonlinear Phenomena, 237 (2008), 1021-1028.  doi: 10.1016/j.physd.2008.01.005.  Google Scholar

[30]

S. Reich, Data assimilation, Acta Numer., 28 (2019), 635-711.  doi: 10.1017/S0962492919000011.  Google Scholar

[31] S. Reich and C. J. Cotter, Probabilistic Forecasting and Bayesian Data Assimilation, Cambridge University Press, New York, 2015.  doi: 10.1017/CBO9781107706804.  Google Scholar
[32]

C. Schillings and A. M. Stuart, Analysis of the ensemble Kalman filter for inverse problems, SIAM Journal on Numerical Analysis, 55 (2017), 1264-1290.  doi: 10.1137/16M105959X.  Google Scholar

[33]

M. Schmidt, D. Kim and S. Sra, Projected Newton-type Methods in Machine Learning, 2013. Google Scholar

[34]

V. Shikhman and O. Stein, Constrained optimization: Projected gradient flows, Journal of Optimization Theory and Applications, 140 (2009), 117-130.  doi: 10.1007/s10957-008-9445-8.  Google Scholar

[35]

D. Simon, Kalman filtering with state constraints: A survey of linear and nonlinear algorithms, IET Control Theory Appl., 4 (2010), 1303-1318.  doi: 10.1049/iet-cta.2009.0032.  Google Scholar

[36]

A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numerica, 19 (2010), 451-559.  doi: 10.1017/S0962492910000061.  Google Scholar

[37]

M. K. TippettJ. L. AndersonC. H. BishopT. M. Hamill and J. S. Whitaker, Ensemble square root filters, Monthly Weather Review, 131 (2003), 1485-1490.   Google Scholar

[38]

D. Wang, Y. Chen and X. Cai, State and Parameter Estimation of Hydrologic Models Using the Constrained Ensemble Kalman Filter, Monthly Resources Research, 2009. Google Scholar

Figure 1.  Varying contour lines of the function $ \Phi(x) $ defined in Example 2.2, with both the preconditioned descent direction in the unconstrained case and the projected preconditioned descent direction
Figure 2.  Transformed EnKF estimation in comparison to the EnKF estimation and the projected EnKF estimation. $ J = 5 $ particles have been simulated
Figure 3.  Ensemble spread in the transformed EnKF in comparison to the EnKF and the projected EnKF. $ J = 5 $ particles have been simulated
Figure 4.  KKT-Residuals and difference of the misfit functional and the global minimum in the transformed EnKF in comparison to the projected EnKF. $ J = 5 $ particles have been simulated
Figure 5.  Transformed EnKF estimation in comparison to the EnKF estimation and the projected EnKF estimation. $ J = 5 $ particles have been simulated
Figure 6.  Difference of the misfit functional and the global minimum in the transformed EnKF in comparison to the EnKF and the projected EnKF. $ J = 5 $ particles have been simulated
Figure 7.  Transformed EnKF parameter estimation in comparison to the EnKF estimation and the projected EnKF estimation. $ J = 5 $ particles have been simulated
Figure 8.  Transformed EnKF observation estimation in comparison to the EnKF estimation and the projected EnKF estimation. $ J = 5 $ particles have been simulated
Figure 9.  Ensemble spread in the transformed EnKF in comparison to the EnKF and the projected EnKF. $ J = 5 $ particles have been simulated
Figure 10.  Difference of the misfit functional and the global minimum in the transformed EnKF in comparison to the projected EnKF. $ J = 5 $ particles have been simulated
[1]

Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2020  doi: 10.3934/fods.2020018

[2]

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007

[3]

Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020, 2 (4) : 351-390. doi: 10.3934/fods.2020017

[4]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003

[5]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380

[6]

C. J. Price. A modified Nelder-Mead barrier method for constrained optimization. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020058

[7]

Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021006

[8]

Marek Macák, Róbert Čunderlík, Karol Mikula, Zuzana Minarechová. Computational optimization in solving the geodetic boundary value problems. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 987-999. doi: 10.3934/dcdss.2020381

[9]

Matúš Tibenský, Angela Handlovičová. Convergence analysis of the discrete duality finite volume scheme for the regularised Heston model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1181-1195. doi: 10.3934/dcdss.2020226

[10]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020446

[11]

Yi-Hsuan Lin, Gen Nakamura, Roland Potthast, Haibing Wang. Duality between range and no-response tests and its application for inverse problems. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020072

[12]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074

[13]

Xinlin Cao, Huaian Diao, Jinhong Li. Some recent progress on inverse scattering problems within general polyhedral geometry. Electronic Research Archive, 2021, 29 (1) : 1753-1782. doi: 10.3934/era.2020090

[14]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[15]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105

[16]

Tetsuya Ishiwata, Young Chol Yang. Numerical and mathematical analysis of blow-up problems for a stochastic differential equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 909-918. doi: 10.3934/dcdss.2020391

[17]

Vadim Azhmyakov, Juan P. Fernández-Gutiérrez, Erik I. Verriest, Stefan W. Pickl. A separation based optimization approach to Dynamic Maximal Covering Location Problems with switched structure. Journal of Industrial & Management Optimization, 2021, 17 (2) : 669-686. doi: 10.3934/jimo.2019128

[18]

Qing-Hu Hou, Yarong Wei. Telescoping method, summation formulas, and inversion pairs. Electronic Research Archive, , () : -. doi: 10.3934/era.2021007

[19]

Arthur Fleig, Lars Grüne. Strict dissipativity analysis for classes of optimal control problems involving probability density functions. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020053

[20]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

 Impact Factor: 

Metrics

  • PDF downloads (95)
  • HTML views (657)
  • Cited by (1)

[Back to Top]