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.

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

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

[8]

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

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

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

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

[12] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, USA, 2004.  doi: 10.1017/CBO9780511804441.
[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.

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

[15]

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

[16]

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

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

[18]

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

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

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

[21]

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

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

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

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

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

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

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

[28]

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

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

[30]

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

[31] S. Reich and C. J. Cotter, Probabilistic Forecasting and Bayesian Data Assimilation, Cambridge University Press, New York, 2015.  doi: 10.1017/CBO9781107706804.
[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.

[33]

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

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

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

[36]

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

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

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

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.

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

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

[8]

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

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

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

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

[12] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, USA, 2004.  doi: 10.1017/CBO9780511804441.
[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.

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

[15]

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

[16]

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

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

[18]

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

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

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

[21]

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

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

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

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

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

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

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

[28]

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

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

[30]

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

[31] S. Reich and C. J. Cotter, Probabilistic Forecasting and Bayesian Data Assimilation, Cambridge University Press, New York, 2015.  doi: 10.1017/CBO9781107706804.
[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.

[33]

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

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

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

[36]

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

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

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

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]

Jiangqi Wu, Linjie Wen, Jinglai Li. Resampled ensemble Kalman inversion for Bayesian parameter estimation with sequential data. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 837-850. doi: 10.3934/dcdss.2021045

[2]

Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2021, 3 (3) : 371-411. doi: 10.3934/fods.2020018

[3]

Zhuoyi Xu, Yong Xia, Deren Han. On box-constrained total least squares problem. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 439-449. doi: 10.3934/naco.2020043

[4]

Philipp Hungerländer, Barbara Kaltenbacher, Franz Rendl. Regularization of inverse problems via box constrained minimization. Inverse Problems and Imaging, 2020, 14 (3) : 437-461. doi: 10.3934/ipi.2020021

[5]

Weina Wang, Chunlin Wu, Yiming Gao. A nonconvex truncated regularization and box-constrained model for CT reconstruction. Inverse Problems and Imaging, 2020, 14 (5) : 867-890. doi: 10.3934/ipi.2020040

[6]

Alexey Penenko. Convergence analysis of the adjoint ensemble method in inverse source problems for advection-diffusion-reaction models with image-type measurements. Inverse Problems and Imaging, 2020, 14 (5) : 757-782. doi: 10.3934/ipi.2020035

[7]

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

[8]

Tan Bui-Thanh, Quoc P. Nguyen. FEM-based discretization-invariant MCMC methods for PDE-constrained Bayesian inverse problems. Inverse Problems and Imaging, 2016, 10 (4) : 943-975. doi: 10.3934/ipi.2016028

[9]

Masoumeh Dashti, Stephen Harris, Andrew Stuart. Besov priors for Bayesian inverse problems. Inverse Problems and Imaging, 2012, 6 (2) : 183-200. doi: 10.3934/ipi.2012.6.183

[10]

Li Wang, Yang Li, Liwei Zhang. A differential equation method for solving box constrained variational inequality problems. Journal of Industrial and Management Optimization, 2011, 7 (1) : 183-198. doi: 10.3934/jimo.2011.7.183

[11]

David Yang Gao. Solutions and optimality criteria to box constrained nonconvex minimization problems. Journal of Industrial and Management Optimization, 2007, 3 (2) : 293-304. doi: 10.3934/jimo.2007.3.293

[12]

Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1943-1971. doi: 10.3934/jimo.2020053

[13]

Guillaume Bal, Ian Langmore, Youssef Marzouk. Bayesian inverse problems with Monte Carlo forward models. Inverse Problems and Imaging, 2013, 7 (1) : 81-105. doi: 10.3934/ipi.2013.7.81

[14]

Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial and Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485

[15]

Xiaodi Bai, Xiaojin Zheng, Xiaoling Sun. A survey on probabilistically constrained optimization problems. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 767-778. doi: 10.3934/naco.2012.2.767

[16]

Matthias Gerdts, Martin Kunkel. Convergence analysis of Euler discretization of control-state constrained optimal control problems with controls of bounded variation. Journal of Industrial and Management Optimization, 2014, 10 (1) : 311-336. doi: 10.3934/jimo.2014.10.311

[17]

Tan Bui-Thanh, Omar Ghattas. A scalable algorithm for MAP estimators in Bayesian inverse problems with Besov priors. Inverse Problems and Imaging, 2015, 9 (1) : 27-53. doi: 10.3934/ipi.2015.9.27

[18]

Kui Lin, Shuai Lu, Peter Mathé. Oracle-type posterior contraction rates in Bayesian inverse problems. Inverse Problems and Imaging, 2015, 9 (3) : 895-915. doi: 10.3934/ipi.2015.9.895

[19]

Lacramioara Grecu, Constantin Popa. Constrained SART algorithm for inverse problems in image reconstruction. Inverse Problems and Imaging, 2013, 7 (1) : 199-216. doi: 10.3934/ipi.2013.7.199

[20]

Andreas Bock, Colin J. Cotter. Learning landmark geodesics using the ensemble Kalman filter. Foundations of Data Science, 2021, 3 (4) : 701-727. doi: 10.3934/fods.2021020

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]