Construction of constrained experimental designs on finite spaces for a modified Ek-optimality criterion

Uciński, Dariusz

International Journal of Applied Mathematics and Computer Science, Tome 30 (2020) no. 4, pp. 659-677.

Résumé

A simple computational algorithm is proposed for minimizing sums of largest eigenvalues of the matrix inverse over the set of all convex combinations of a finite number of nonnegative definite matrices subject to additional box constraints on the weights of those combinations. Such problems arise when experimental designs aiming at minimizing sums of largest asymptotic variances of the least-squares estimators are sought and the design region consists of finitely many support points, subject to the additional constraints that the corresponding design weights are to remain within certain limits. The underlying idea is to apply the method of outer approximations for solving the associated convex semi-infinite programming problem, which reduces to solving a sequence of finite min-max problems. A key novelty here is that solutions to the latter are found using generalized simplicial decomposition, which is a recent extension of the classical simplicial decomposition to nondifferentiable optimization. Thereby, the dimensionality of the design problem is drastically reduced. The use of the algorithm is illustrated by an example involving optimal sensor node activation in a large sensor network collecting measurements for parameter estimation of a spatiotemporal process.

Détail

Mots-clés : constrained optimum experimental design, minimal sum of largest eigenvalues, generalized simplicial decomposition, optimal measurement selection

Bibliographie

[1] [1] Atkinson, A.C., Donev, A.N. and Tobias, R.D. (2007). Optimum Experimental Designs, with SAS, Oxford University Press, Oxford.

[2] [2] Beddiaf, S., Autrique, L., Perez, L. and Jolly, J.-C. (2016). Heating source localization in a reduced time, International Journal of Applied Mathematics and Computer Science 26(3): 623–640, DOI: 10.1515/amcs-2016-0043.

[3] [3] Bernstein, D.S. (2005). Matrix Mathematics. Theory, Facts, and Formulas with Application to Linear Systems Theory, Princeton University Press, Princeton, NJ.

[4] [4] Bertsekas, D.P. (1999). Nonlinear Programming, 2nd Edn, Optimization and Computation Series, Athena Scientific, Belmont, MA.

[5] [5] Bertsekas, D.P. (2015). Convex Optimization Algorithms, Athena Scientific, Belmont, MA.

[6] [6] Bertsekas, D. and Yu, H. (2011). A unifying polyhedral approximation framework for convex optimization, SIAM Journal on Optimization 21(1): 333–360.

[7] [7] Böhning, D. (1986). A vertex-exchange-method in D-optimal design theory, Metrika 33(12): 337–347.

[8] [8] Botkin, N.D. and Stoer, J. (2005). Minimization of convex functions on the convex hull of a point set, Mathematical Methods of Operations Research 62(2): 167–18.

[9] [9] Boyd, S. and Vandenberghe, L. (2004). Convex Optimization, Cambridge University Press, Cambridge.

[10] [10] Burclová, K. and Pázman, A. (2016). Optimal design of experiments via linear programming, Statistical Papers 57(4): 893–910.

[11] [11] Chepuri, S.P. and Leus, G. (2015). Sparsity-promoting sensor selection for non-linear measurement models, IEEE Transactions on Signal Processing 63(3): 684–698.

[12] [12] Coll, C. and Sánchez, E. (2019). Parameter identification and estimation for stage-structured population models, International Journal of Applied Mathematics and Computer Science 29(2): 327–336, DOI: 10.2478/amcs-2019-0024.

[13] [13] Cook, D. and Fedorov, V. (1995). Constrained optimization of experimental design, Statistics 26: 129–178.

[14] [14] Djelassi, H., Glass, M. and Mitsos, A. (2019). Discretization-based algorithms for generalized semi-infinite and bilevel programs with coupling equality constraints, Journal of Global Optimization 75(2): 341–392.

[15] [15] Duarte, B.P.M., Granjo, J.F.O. and Wong, W.K. (2020). Optimal exact designs of experiments via mixed integer nonlinear programming, Statistics and Computing 30(1): 93–112.

[16] [16] Duarte, B.P.M. and Wong, W.K. (2014). A semi-infinite programming based algorithm for finding minimax optimal designs for nonlinear models, Statistics and Computing 24(6): 1063–1080.

[17] [17] Esteban-Bravo, M., Leszkiewicz, A. and Vidal-Sanz, J.M. (2017). Exact optimal experimental designs with constraints, Statistics and Computing 27(3): 845–863.

[18] [18] Fedorov, V.V. (1989). Optimal design with bounded density: Optimization algorithms of the exchange type, Journal of Statistical Planning and Inference 22: 1–13.

[19] [19] Fedorov, V.V. and Leonov, S.L. (2014). Optimal Design for Nonlinear Response Models, CRC Press, Boca Raton, FL.

[20] [20] Harman, R. (2004). Minimal efficiency of designs under the class of orthogonally invariant information criteria, Metrika 60(2): 137–153.

[21] [21] Harman, R. and Benková, E. (2017). Barycentric algorithm for computing d-optimal size- and cost-constrained designs of experiments, Metrika 80(2): 201–225.

[22] [22] Harman, R., Filová, L. and Richtárik, P. (2020). A randomized exchange algorithm for computing optimal approximate designs of experiments, Journal of the American Statistical Association 115(529): 348–361.

[23] [23] Harman, R. and Pronzato, L. (2007). Improvements on removing nonoptimal support points in d-optimum design algorithms, Statistics Probability Letters 77(1): 90–94.

[24] [24] Harville, D.A. (1997). Matrix Algebra From a Statistician’s Perspective, Springer-Verlag, New York, NY.

[25] [25] Herzog, R., Riedel, I. and Uciński, D. (2018). Optimal sensor placement for joint parameter and state estimation problems in large-scale dynamical systems with applications to thermo-mechanics, Optimization and Engineering 19(3): 591–627.

[26] [26] Hettich, R. and Kortanek, K.O. (1993). Semi-infinite programming: Theory, methods and applications, SIAM Review 35(3): 380–429.

[27] [27] Jacobson, M.Z. (1999). Fundamentals of Atmospheric Modeling, Cambridge University Press, Cambridge.

[28] [28] Joshi, S. and Boyd, S. (2009). Sensor selection via convex optimization, IEEE Transactions on Signal Processing 57(2): 451–462.

[29] [29] Katoh, N. (2001). Combinatorial optimization algorithms in resource allocation problems, in C.A. Floudas and P.M. Pardalos (Eds), Encyclopedia of Optimization, Vol. 1, Kluwer Academic Publishers, Dordrecht, pp. 259–264.

[30] [30] Khapalov, A.Y. (2010). Source localization and sensor placement in environmental monitoring, International Journal of Applied Mathematics and Computer Science 20(3): 445–458, DOI: 10.2478/v10006-010-0033-3.

[31] [31] Langtangen, H.P. and Logg, A. (2016). Solving PDEs in Python. The FEniCS Tutorial I, Springer-Verlag, Cham.

[32] [32] Larsson, T., Migdalas, A. and Patriksson, M. (2015). A generic column generation principle: Derivation and convergence analysis, Operational Research 15(2): 163–198.

[33] [33] Larsson, T., Patriksson, M. and Strömberg, A. (1998). Ergodic convergence in subgradient optimization, Optimization Methods and Software 9(1–3): 93–120.

[34] [34] Lu, Z. and Pong, T.K. (2013). Computing optimal experimental designs via interior point method, SIAM Journal on Matrix Analysis and Applications 34(4): 1556–1580.

[35] [35] Maculan, N., Santiago, C.P., Macambira, E.M. and Jardim, M.H.C. (2003). An O(n) algorithm for projecting a vector on the intersection of a hyperplane and a box in Rn, Journal of Optimization Theory and Applications 117(3): 553–574.

[36] [36] Marshall, A.W., Olkin, I. and Arnold, B.C. (2011). Inequalities: Theory of Majorization and Its Applications, 2nd Edn, Springer-Verlag, New York, NY.

[37] [37] Melas, V. (2006). Functional Approach to Optimal Experimental Design, Springer-Verlag, New York, NY.

[38] [38] Patan, M. and Kowalów, D. (2018). Distributed scheduling of measurements in a sensor network for parameter estimation of spatio-temporal systems, International Journal of Applied Mathematics and Computer Science 28(1): 39–54, DOI: 10.2478/amcs-2018-0003.

[39] [39] Patan, M. and Uciński, D. (2008). Configuring a sensor network for fault detection in distributed parameter systems, International Journal of Applied Mathematics and Computer Science 18(4): 513–524, DOI: 10.2478/v10006-008-0045-4.

[40] [40] Patan, M. and Uciński, D. (2019). Generalized simplicial decomposition for optimal sensor selection in parameter estimation of spatiotemporal processes, 2019 American Control Conference (ACC), Philadelphia, PA, USA, pp. 2546–2551.

[41] [41] Patriksson, M. (2001). Simplicial decomposition algorithms, in C.A. Floudas and P.M. Pardalos (Eds), Encyclopedia of Optimization, Vol. 5, Kluwer Academic Publishers, Dordrecht, pp. 205–212.

[42] [42] Pázman, A. (1986). Foundations of Optimum Experimental Design, Mathematics and Its Applications, D. Reidel Publishing Company, Dordrecht.

[43] [43] Polak, E. (1987). On the mathematical foundations of nondifferentiable optimization in engineering design, SIAM Review 29(1): 21–89.

[44] [44] Polak, E. (1997). Optimization. Algorithms and Consistent Approximations, Applied Mathematical Sciences, Springer-Verlag, New York, NY.

[45] [45] Pronzato, L. (2003). Removing non-optimal support points in D-optimum design algorithms, Statistics Probability Letters 63: 223–228.

[46] [46] Pronzato, L. and Pázman, A. (2013). Design of Experiments in Nonlinear Models. Asymptotic Normality, Optimality Criteria and Small-Sample Properties, Springer-Verlag, New York, NY.

[47] [47] Pronzato, L. and Zhigljavsky, A.A. (2014). Algorithmic construction of optimal designs on compact sets for concave and differentiable criteria, Journal of Statistical Planning and Inference 154: 141–155.

[48] [48] Pukelsheim, F. (1993). Optimal Design of Experiments, Probability and Mathematical Statistics, John Wiley Sons, New York, NY.

[49] [49] Reemtsen, R. and Görner, S. (1998). Numerical methods for semi-infinite programming: A survey, in R. Reemtsen and J.-J. Rückmann (Eds), Semi-Infinite Programming, Kluwer Academic Publishers, Boston, MA, pp. 195–275.

[50] [50] Sagnol, G. (2011). Computing optimal designs of multiresponse experiments reduces to second-order cone programming, Journal of Statistical Planning and Inference 141(5): 1684–1708.

[51] [51] Sagnol, G. and Harman, R. (2015). Computing exact D-optimal designs by mixed integer second-order cone programming, The Annals of Statistics 43(5): 2198–2224.

[52] [52] Sahm, M. and Schwabe, R. (2001). A note on optimal bounded designs, in A. Atkinson et al. (Eds), Optimum Design 2000, Kluwer Academic Publishers, Dordrecht, Chapter 13, pp. 131–140.

[53] [53] Seber, G.A.F. and Wild, C.J. (1989). Nonlinear Regression, John Wiley Sons, New York, NY.

[54] [54] Shimizu, K. and Aiyoshi, E. (1980). Necessary conditions for min-max problems and algorithms by a relaxation procedure, IEEE Transactions on Automatic Control AC-25(1): 62–66.

[55] [55] Silvey, S.D., Titterington, D.M. and Torsney, B. (1978). An algorithm for optimal designs on a finite design space, Communications in Statistics—Theory and Methods 14: 1379–1389.

[56] [56] Torsney, B. and Mandal, S. (2001). Construction of constrained optimal designs, in A. Atkinson et al. (Eds), Optimum Design 2000, Kluwer Academic Publishers, Dordrecht, Chapter 14, pp. 141–152.

[57] [57] Uciński, D. (2005). Optimal Measurement Methods for Distributed-Parameter System Identification, CRC Press, Boca Raton, FL.

[58] [58] Uciński, D. (2012). Sensor network scheduling for identification of spatially distributed processes, International Journal of Applied Mathematics and Computer Science 22(1): 25–40, DOI: 10.2478/v10006-012-0002-0.

[59] [59] Uciński, D. (2015). An algorithm for construction of constrained D-optimum designs, in A. Steland et al. (Eds), Stochastic Models, Statistics and Their Applications, Springer Proceedings in Mathematics Statistics, Springer-Verlag, Cham, pp. 461–468.

[60] [60] Uciński, D. (2020). D-optimal sensor selection in the presence of correlated measurement noise, Measurement 164: 107873.

[61] [61] Uciński, D. and Patan, M. (2007). D-optimal design of a monitoring network for parameter estimation of distributed systems, Journal of Global Optimization 39(2): 291–322.

[62] [62] Wu, C.-F. (1978). Some algorithmic aspects of the theory of optimal designs, The Annals of Statistics 6(6): 1286–1301.

[63] [63] Yu, Y. (2010). Monotonic convergence of a general algorithm for computing optimal designs, The Annals of Statistics 38(3): 1593–1606.

[64] [64] Yu, Y. (2011). D-optimal designs via a cocktail algorithm, Statistics and Computing 21(3): 475–481.

[65] [65] Zarrop, M.B. and Goodwin, G.C. (1975). Comments on “Optimal inputs for system identification”, IEEE Transactions on Automatic Control AC-20(2): 299–300.

[66] [66] Zhang, L., Wu, S.-Y. and López, M.A. (2010). A new exchange method for convex semi-infinite programming, SIAM Journal on Optimization 20(6): 2959–2977.