×

An algorithm based on semidefinite programming for finding minimax optimal designs. (English) Zbl 1469.62058

Summary: An algorithm based on a delayed constraint generation method for solving semi-infinite programs for constructing minimax optimal designs for nonlinear models is proposed. The outer optimization level of the minimax optimization problem is solved using a semidefinite programming based approach that requires the design space be discretized. A nonlinear programming solver is then used to solve the inner program to determine the combination of the parameters that yields the worst-case value of the design criterion. The proposed algorithm is applied to find minimax optimal designs for the logistic model, the flexible 4-parameter Hill homoscedastic model and the general \(n\)th order consecutive reaction model, and shows that it (i) produces designs that compare well with minimax \(D\)-optimal designs obtained from semi-infinite programming method in the literature; (ii) can be applied to semidefinite representable optimality criteria, that include the common \(A\)-, \(E\)-, \(G\)-, \(I\)- and \(D\)-optimality criteria; (iii) can tackle design problems with arbitrary linear constraints on the weights; and (iv) is fast and relatively easy to use.

MSC:

62-08 Computational methods for problems pertaining to statistics
62K05 Optimal statistical designs
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Andersen, E., Jensen, B., Jensen, J., Sandvik, R., Worsøe, U., 2009. MOSEK version 6, Technical Report TR-2009-3, MOSEK.; Andersen, E., Jensen, B., Jensen, J., Sandvik, R., Worsøe, U., 2009. MOSEK version 6, Technical Report TR-2009-3, MOSEK.
[2] Atkinson, A. C.; Donev, A. N.; Tobias, R. D., Optimum Experimental Designs, with SAS, (2007), Oxford University Press Oxford · Zbl 1183.62129
[3] Ben-Tal, A.; Nemirovski, A. S., Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, (2001), Society for Industrial and Applied Mathematics Philadelphia · Zbl 0986.90032
[4] Berger, M. P.F.; Wong, W. K., An Introduction to Optimal Designs for Social and Biomedical Research, (2009), John Wiley & Sons Chichester · Zbl 1182.62154
[5] Bischof, C. H.; Bücker, H. M.; Lang, B.; Rasch, A.; Vehreschild, A., Combining source transformation and operator overloading techniques to compute derivatives for Matlab programs, (Proceedings of the Second IEEE International Workshop on Source Code Analysis and Manipulation, (SCAM 2002), (2002), IEEE Computer Society Los Alamitos, CA, USA), 65-72
[6] Blankenship, J. W.; Falk, J. E., Infinitely constrained optimization problems, J. Optim. Theory Appl., 19, 2, 261-281, (1976) · Zbl 0307.90071
[7] Boer, E. P.J.; Hendrix, E. M.T., Global optimization problems in optimal design of experiments in regression models, J. Global Optim., 18, 385-398, (2000) · Zbl 0980.62055
[8] Boyd, S.; Vandenberghe, L., Convex Optimization, (2004), University Press Cambridge · Zbl 1058.90049
[9] Burclová, K.; Pázman, A., Optimal design of experiments via linear programming, Statist. Papers, 57, 4, 893-910, (2016) · Zbl 1351.62145
[10] Byrd, R. H.; Hribar, M. E.; Nocedal, J., An interior point algorithm for large-scale nonlinear programming, SIAM J. Optim., 9, 4, 877-900, (1999) · Zbl 0957.65057
[11] Chaloner, K.; Larntz, K., Optimal Bayesian design applied to logistic regression experiments, J. Statist. Plann. Inference, 59, 191-208, (1989) · Zbl 0666.62073
[12] Chen, R.-B.; Chang, S.-P.; Wang, W.; Tung, H.-C.; Wong, W. K., Minimax optimal designs via particle swarm optimization methods, Stat. Comput., 25, 5, 975-988, (2015) · Zbl 1332.62265
[13] Coleman, T. F.; Li, Y., On the convergence of reflective Newton methods for large-scale nonlinear minimization subject to bounds, Math. Program., 67, 2, 189-224, (1994) · Zbl 0842.90106
[14] Cook, D.; Fedorov, V., Invited discussion paper constrained optimization of experimental design, Statistics, 26, 2, 129-148, (1995)
[15] Cook, R. D.; Nachtsheim, C. J., Model robust, linear-optimal designs, Technometrics, 24, 49-54, (1982) · Zbl 0483.62063
[16] Dette, H.; Haines, L. M.; Imhof, L. A., Maximin and Bayesian optimal designs for regression models, Statist. Sinica, 17, 463-480, (2007) · Zbl 1144.62056
[17] Drud, A., CONOPT: A GRG code for large sparse dynamic nonlinear optimization problems, Math. Program., 31, 153-191, (1985) · Zbl 0557.90088
[18] Drud, A., CONOPT - A large-scale GRG code, ORSA J. Comput., 6, 2, 207-216, (1994) · Zbl 0806.90113
[19] Duarte, B. P.M.; Wong, W. K., A semi-infinite programming based algorithm for finding minimax optimal designs for nonlinear models, Stat. Comput., 24, 6, 1063-1080, (2014) · Zbl 1332.90189
[20] Duarte, B. P.M.; Wong, W. K., Finding Bayesian optimal designs for nonlinear models: a semidefinite programming-based approach, Internat. Statist. Rev., 83, 2, 239-262, (2015)
[21] Duarte, B. P.M.; Wong, W. K.; Atkinson, A. C., A semi-infinite programming based algorithm for determining \(T -\)optimum designs for model discrimination, J. Multivariate Anal., 135, 11-24, (2015) · Zbl 1314.62164
[22] Duarte, B. P.M.; Wong, W. K.; Dette, H., Adaptive grid semidefinite programming for finding optimal designs, Stat. Comput., (2017)
[23] Duarte, B. P.M.; Wong, W. K.; Oliveira, N. M. C., Model-based optimal design of experiments - semidefinite and nonlinear programming formulations, Chemometr. Intell. Lab. Syst., 151, 153-163, (2016)
[24] Fackle-Fornius, E.; Miller, F.; Nyquist, H., Implementation of maximin efficient designs in dose-finding studies, Pharm. Stat., 14, 1, 63-73, (2015)
[25] Fedorov, V. V., Convex design theory, Math. Oper.forsch. Stat. Ser. Stat., 11, 403-413, (1980) · Zbl 0471.62075
[26] Fedorov, V. V.; Leonov, S. L., Optimal Design for Nonlinear Response Models, (2014), Chapman and Hall/CRC Press Boca Raton · Zbl 1373.62001
[27] Filová, L.; Trnovská, M.; Harman, R., Computing maximin efficient experimental designs using the methods of semidefinite programming, Metrika, 64, 1, 109-119, (2011)
[28] Gaivoronski, A., Linearization methods for optimization of functionals which depend on probability measures, (Prékopa, A.; Wets, R. J.-B., Stochastic Programming 84 Part II, Mathematical Programming Studies, vol. 28, (1986), Springer Berlin Heidelberg), 157-181 · Zbl 0596.90071
[29] Gill, P. E.; Murray, W.; Saunders, M. A., SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM Rev., 47, 1, 99-131, (2005) · Zbl 1210.90176
[30] Goos, P.; Jones, B., Optimal Design of Experiments: A Case Study Approach, (2011), Wiley New York
[31] Grant, M., Boyd, S., Ye, Y., 2012. cvx Users Guide for cvx version 1.22. CVX Research, Inc., 1104 Claire Ave., Austin, TX 78703-2502.; Grant, M., Boyd, S., Ye, Y., 2012. cvx Users Guide for cvx version 1.22. CVX Research, Inc., 1104 Claire Ave., Austin, TX 78703-2502.
[32] Harman, R.; Jurík, T., Computing \(c -\)optimal experimental designs using the simplex method of linear programming, Comput. Statist. Data Anal., 53, 2, 247-254, (2008) · Zbl 1231.62142
[33] Heredia-Langner, A.; Montgomery, D. C.; Carlyle, W. M.; Borror, C. M., Model-robust optimal designs: A genetic algorithm approach, J. Qual. Technol., 36, 263-279, (2004)
[34] Hettich, R.; Kaplan, A.; Tichatschke, R., Semi-infinite programming: numerical methods, (Encyclopedia of Optimization, Vol. 5, (2001), Kluwer Amsterdam), 112-117
[35] Hettich, R.; Kortanek, K. O., Semi-infinite programming: theory, methods and applications, SIAM Rev., 35, 380-429, (1993) · Zbl 0784.90090
[36] Hill, A., The possible effects of the aggregation of the molecules of haemoglobin on its dissociation curves, J. Physiol., 40, Suppl., iv-vii, (1910)
[37] Khinkis, L. A.; Levasseur, L.; Faessel, H.; Greco, W. R., Optimal design for estimating parameters of the 4-parameter Hill model, Nonlinearity Biol. Toxicol. Med., 1, 363-377, (2003)
[38] Kiefer, J., General equivalence theory for optimum design (approximate theory), Ann. Statist., 2, 849-879, (1974) · Zbl 0291.62093
[39] López, M.; Still, G., Semi-infinite programming, European J. Oper. Res., 180, 491-518, (2007) · Zbl 1124.90042
[40] Ludena, C. E.; Hertel, T. W.; Preckel, P. V.; Foster, K.; Nin, A., Productivity growth and convergence in crop, ruminant, and nonruminant production: measurement and forecasts, Agricult. Econ., 37, 1, 1-17, (2007)
[41] Mandal, A.; Wong, W. K.; Yu, Y., Algorithmic searches for optimal designs, (Handbook of Design and Analysis of Experiments, (2015), CRC Press Boca Ratton), 755-786 · Zbl 1352.62126
[42] Martín-Martín, R.; Torsney, B.; López-Fidalgo, J., Construction of marginally and conditionally restricted designs using multiplicative algorithms, Comput. Statist. Data Anal., 51, 12, 5547-5561, (2007) · Zbl 1445.62201
[43] Masoudi, E.; Holling, H.; Wong, W. K., Application of imperialist competitive algorithm to find minimax and standardized maximin optimal designs, Comput. Statist. Data Anal., 113, 330-345, (2017) · Zbl 1464.62129
[44] Melas, V., (Functional approach to optimal experimental design, Lecture Notes in Statistics, (2006), Springer) · Zbl 1094.62086
[45] Mitsos, A.; Tsoukalas, A., Global optimization of generalized semi-infinite programs via restriction of the right hand side, J. Global Optim., 61, 1, 1-17, (2015) · Zbl 1312.90063
[46] Molchanov, I.; Zuyev, S., Steepest descent algorithm in a space of measures, Stat. Comput., 12, 115-123, (2002)
[47] Mutapcic, A.; Boyd, S. P., Cutting-set methods for robust convex optimization with pessimizing oracles, Optim. Methods Softw., 24, 3, 381-406, (2009) · Zbl 1173.90502
[48] Noubiap, R. F.; Seidel, W., A minimax algorithm for constructing optimal symmetrical balanced designs for a logistic regression model, J. Statist. Plann. Inference, 91, 1, 151-168, (2000) · Zbl 0958.62065
[49] Papp, D., Optimal designs for rational function regression, J. Amer. Statist. Assoc., 107, 400-411, (2012) · Zbl 1261.62072
[50] Pázman, A.; Pronzato, L., Optimum design accounting for the global nonlinear behavior of the model., Ann. Statist., 42, 4, 1426-1451, (2014) · Zbl 1302.62174
[51] Prentice, R., A generalization of the probit and logit methods for dose response curves, Biometrics, 32, 761-768, (1976)
[52] Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P., Numerical recipes 3rd edition: The art of scientific computing, (2007), Cambridge University Press New York, NY, USA · Zbl 1132.65001
[53] Pronzato, L., Optimal experimental design and some related control problems, Automatica, 44, 303-325, (2008) · Zbl 1283.93154
[54] Pronzato, L.; Pázman, A., Design of Experiments in Nonlinear Models, (2013), Springer · Zbl 1275.62026
[55] Pronzato, L.; Walter, É., Robust experiment design via maximin optimization, Math. Biosci., 89, 2, 161-176, (1988) · Zbl 0654.62059
[56] Pukelsheim, F., Optimal Design of Experiments, (1993), SIAM Philadelphia · Zbl 0834.62068
[57] Qiu, J., Finding Optimal Experimental Designs for Models in Biomedical Studies via Particle Swarm Optimization, (2014), University of California Los Angeles, (Ph.D. thesis)
[58] Rao, C. R., Linear Statistical Inference and its Applications, (1973), Wiley
[59] Rustem, B.; Žakovíc, S.; Parpas, P., Convergence of an interior point algorithm for continuous minimax problems, J. Optim. Theory Appl., 136, 1, 87-103, (2008) · Zbl 1194.90118
[60] Ruszczyński, A. P., (Nonlinear Optimization, Nonlinear optimization, vol. 13, (2006), Princeton University Press) · Zbl 1108.90001
[61] Sagnol, G., Computing optimal designs of multiresponse experiments reduces to second-order cone programming, J. Statist. Plann. Inference, 141, 5, 1684-1708, (2011) · Zbl 1207.62156
[62] Sagnol, G., 2012. PICOS, a Python interface to conic optimization solvers, Tech. Rep., 12-48, ZIB.; Sagnol, G., 2012. PICOS, a Python interface to conic optimization solvers, Tech. Rep., 12-48, ZIB.
[63] Sagnol, G., On the semidefinite representation of real functions applied to symmetric matrices, Linear Algebra Appl., 439, 10, 2829-2843, (2013) · Zbl 1282.90122
[64] Sagnol, G.; Harman, R., Computing exact \(D -\)optimal designs by mixed integer second order cone programming, Ann. Statist., 43, 5, 2198-2224, (2015) · Zbl 1331.62384
[65] Sahinidis, N.V., 2014. BARON 14.3.1: Global Optimization of Mixed-Integer Nonlinear Programs,User’s Manual.; Sahinidis, N.V., 2014. BARON 14.3.1: Global Optimization of Mixed-Integer Nonlinear Programs,User’s Manual.
[66] Shimizu, K.; Aiyoshi, E., Necessary conditions for MIN-MAX problems and algorithms by a relaxation procedure, IEEE Trans. Automat. Control, 25, 62-66, (1980) · Zbl 0426.49008
[67] Sturm, J., Using sedumi 1.02, a Matlab toolbox for optimization oversymmetric cones, Optim. Methods Softw., 11, 625-653, (1999) · Zbl 0973.90526
[68] Terry, T. L., Robust Linear Optimization with Recourse: Solution Methods and Other Properties, (2009), University of Michigan, (Ph.D. thesis)
[69] Ting, N., (Dose Finding in Drug Development, Statistics for Biology and Health, (2006), Springer New York) · Zbl 1129.62106
[70] Tsoularis, A.; Wallace, J., Analysis of logistic growth models, Math. Biosci., 179, 1, 21-55, (2002) · Zbl 0993.92028
[71] Uciński, D., An algorithm for construction of constrained \(d -\) optimum designs, (Stochastic Models, Statistics and their Applications, (2015), Springer International Publishing), 461-468 · Zbl 1349.62349
[72] Ugray, Z.; Lasdon, L.; Plummer, J.; Glover, F.; Kelly, J.; Martí, R., A multistart scatter search heuristic for smooth NLP and MINLP problems, (Metaheuristic Optimization Via Memory and Evolution, (2005), Springer), 25-51 · Zbl 1072.90572
[73] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Rev., 8, 49-95, (1996) · Zbl 0845.65023
[74] Vandenberghe, L.; Boyd, S., Applications of semidefinite programming, Appl. Numer. Math., 29, 283-299, (1999) · Zbl 0956.90031
[75] Wächter, A.; Biegler, T. L., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57, (2005) · Zbl 1134.90542
[76] Walter, E.; Pronzato, L., Identification of Parametric Models from Experimental Data, (1997), Springer Verlag
[77] Welch, W. J., Algorithmic complexity: three NP-hard problems in computational statistics, J. Statist. Comput. Simul., 15, 1, 17-25, (1982) · Zbl 0482.65080
[78] Whitacre, J. M., Recent trends indicate rapid growth of nature-inspired optimization in academia and industry, Computing, 93, 2, 121-133, (2011) · Zbl 1293.90086
[79] Whitacre, J. M., Survival of the flexible: explaining the recent popularity of nature-inspired optimization within a rapidly evolving world, Computing, 93, 2, 135-146, (2011) · Zbl 1293.90087
[80] Whittle, P., Some general points in the theory of optimal experimental design, J. Roy. Statist. Soc. Ser. B, 35, 123-130, (1973) · Zbl 0282.62065
[81] Wong, W., A unified approach to the construction of minimax designs, Biometrika, 79, 611-620, (1992) · Zbl 0762.62019
[82] Yang, X.-S., Nature-Inspired Metaheuristic Algorithms, (2010), Luniver Press
[83] Žakovíc, S.; Rustem, B., Semi-infinite programming and applications to minimax problems, Ann. Oper. Res., 124, 1-4, 81-110, (2003) · Zbl 1074.90554
[84] Zhang, Y., Bayesian \(D -\)Optimal Design for Generalized Linear Models, (2006), Virginia Polytechnic Institute and State University, (Ph.D. thesis)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.