2022
Journal article
Open Access
Exploiting problem structure in derivative free optimization
Porcelli M., Toint P. L.
Structured problems 65K05 direct-search method FOS: Mathematics Interpolation models Direct-search methods Derivative-free optimization 90C56 Optimization and Control (math.OC) interpolation model 90C90 Software Applied Mathematics Mathematics - Optimization and Control
A structured version of derivative-free random pattern search optimization algorithms is introduced, which is able to exploit coordinate partially separable structure (typically associated with sparsity) often present in unconstrained and bound-constrained optimization problems. This technique improves performance by orders of magnitude and makes it possible to solve large problems that otherwise are totally intractable by other derivative-free methods. A library of interpolation-based modelling tools is also described, which can be associated with the structured or unstructured versions of the initial pattern search algorithm. The use of the library further enhances performance, especially when associated with structure. The significant gains in performance associated with these two techniques are illustrated using a new freely-available release of the Brute Force Optimizer (BFO) package firstly introduced in [Porcelli and Toint 2017], which incorporates them. An interesting conclusion of the numerical results presented is that providing global structural information on a problem can result in significantly less evaluations of the objective function than attempting to building local Taylor-like models.
Source: ACM transactions on mathematical software (Online) 48 (2022). doi:10.1145/3474054
Publisher: Association for Computing Machinery, [New York] , Stati Uniti d'America
[1] M. A. Abramson, C. Audet, J. W. Chrissis, and J. G. Walston. Mesh adaptive direct search algorithms for mixed variable optimization. Optimization Letters, 3(1):35-47, 2009.
[2] C. Audet and J. E. Dennis. Pattern search algorithms for mixed variable programming. SIAM Journal on Optimization, 11(3):573-594, 2001.
[3] C. Audet and W. Hare. Derivative-free and blackbox optimization. Springer Verlag, Heidelberg, Berlin, New York, 2017.
[4] C. Audet, S. Le Digabel, and Ch. Tribes. The mesh adaptive direct search algorithm for granular and discrete variables. SIAM Journal on Optimization, 29(2):1164-1189, 2019.
[5] B. M. Averick and J. J. Mor´e. The Minpack-2 test problem collection. Technical Report ANL/MCSP153-0694, Mathematics and Computer Science, Argonne National Laboratory, Argonne, Illinois, USA, 1992.
[6] G. E. P. Box and K. B. Wilson. On the experimental attainment of optimum conditions. Journal of the Royal Statistical Society. Series B (Methodological), 13(1):1-45, 1951.
[7] C. Cartis, J. Fiala, B. Marteau, and L. Roberts. Improving the flexibility and robustness of modelbased derivative-free optimization solvers. ACM Transactions on Mathematical Software, 45(3):32, 2019.
[8] C. Cartis, N. I. M. Gould, and Ph. L. Toint. Trust-region and other regularization of linear leastsquares problems. BIT, 49(1):21-53, 2009.
[9] B. Colson and Ph. L. Toint. Exploiting band structure in unconstrained optimization without derivatives. Optimization and Engineering, 2:349-412, 2001.
[10] B. Colson and Ph. L. Toint. A derivative-free algorithm for sparse unconstrained optimization problems. In A. H. Siddiqi and M. Koˇcvara, editors, Trends in Industrial and Applied Mathematics, pages 131-149, Dordrecht, The Netherlands, 2002. Kluwer Academic Publishers.
[11] B. Colson and Ph. L. Toint. Optimizing partially separable functions without derivatives. Optimization Methods and Software, 20(4-5):493-508, 2005.
[12] A. R. Conn, N. I. M. Gould, and Ph. L. Toint. Trust-Region Methods. MPS-SIAM Series on Optimization. SIAM, Philadelphia, USA, 2000.
[13] A. R. Conn, K. Scheinberg, and Ph. L. Toint. On the convergence of derivative-free methods for unconstrained optimization. In A. Iserles and M. Buhmann, editors, Approximation Theory and Optimization: Tributes to M. J. D. Powell, pages 83-108, Cambridge, England, 1997. Cambridge University Press.
[14] A. R. Conn, K. Scheinberg, and L. N. Vicente. Geometry of sample sets in derivative free optimization. Part I: polynomial interpolation. Technical Report 03-09, Departamento de Matema´tica, Universidade de Coimbra, Portugal, 2003. Revised September 2004.
[15] A. R. Conn, K. Scheinberg, and L. N. Vicente. Geometry of interpolation sets in derivative free optimization. Mathematical Programming, Series B, 111(1-2):141-172, 2008.
[16] A. R. Conn, K. Scheinberg, and L. N. Vicente. Introduction to Derivative-free Optimization. MPSSIAM Series on Optimization. SIAM, Philadelphia, USA, 2009.
[17] A. R. Conn and Ph. L. Toint. An algorithm using quadratic interpolation for unconstrained derivative free optimization. In G. Di Pillo and F. Gianessi, editors, Nonlinear Optimization and Applications, pages 27-47, New York, 1996. Plenum Publishing.
[18] I. D. Coope and C. J. Price. Frame-based methods for unconstrained optimization. Journal of Optimization Theory and Applications, 107:261-274, 2000.
[19] I. D. Coope and C. J. Price. On the convergence of grid-based methods for unconstrained optimization. SIAM Journal on Optimization, 11:859-869, 2001.
[20] I. D. Coope and C. J. Price. Positive basis in numerical optimization. Computational Optimization and Applications, 21, 2002.
[21] J. E. Dennis and V. Torczon. Direct search methods on parallel machines. SIAM Journal on Optimization, 1(4):448-474, 1991.
[22] E. D. Dolan, R. M. Lewis, and V. Torczon. On the local convergence of pattern search. SIAM Journal on Optimization, 14(2):567-583, 2003.
[23] E. D. Dolan and J. J. Mor´e. Benchmarking optimization software with performance profiles. Mathematical Programming, 91(2):201-213, 2002.
[24] E. D. Dolan, J. J. Mor´e, and T. S. Munson. Optimality measures for performance profiles. SIAM Journal on Optimization, 16(3):891-909, 2006.
[25] N. I. M. Gould, D. Orban, and Ph. L. Toint. CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization. Computational Optimization and Applications, 60(3):545-557, 2015.
[26] S. Gratton, C. W. Royer, L. N. Vicente, and Z. Zhang. Direct search based on probabilistic descent. SIAM Journal on Optimization, 25(3):1515-1541, 2015.
[27] S. Gratton, Ph. L. Toint, and A. Tr¨oltzsch. An active-set trust-region method for derivative-free nonlinear bound-constrained optimization. Optimization Methods and Software, 21(4-5):873-894, 2011.
[28] R. Hooke and T. A. Jeeves. Direct search solution of numerical and statistical problems. Journal of the ACM, 8:212-229, 1961.
[29] J. C. Lagarias, B. Poonen, and M. H. Wright. Convergence of the restricted NelderMead algorithm in two dimensions. SIAM Journal on Optimization, 22:501-532, 2012.
[30] J. Larson, M. Menickelly, and S. M. Wild. Derivative-free optimization methods. Acta Numerica, 28:287-404, 2019.
[31] S. Le Digabel. Algorithm 909: NOMAD: Nonlinear optimization with the MADS algorithm. ACM Transactions on Mathematical Software, 37(4):1-44, 2011.
[32] R. M. Lewis and V. Torczon. Pattern search methods for linearly constrained minimization. SIAM Journal on Optimization, 10(3):917941, 2000.
[33] J. J. Mor´e and D. C. Sorensen. Computing a trust region step. SIAM Journal on Scientific and Statistical Computing, 4(3):553-572, 1983.
[34] J. J. Mor´e and S. M. Wild. Benchmarking derivative-free optimization algorithms. SIAM Journal on Optimization, 20(1):172-191, 2009.
[35] J. A. Nelder and R. Mead. A simplex method for function minimization. Computer Journal, 7:308-313, 1965.
[36] M. Porcelli and Ph. L. Toint. BFO, a trainable derivative-free brute force optimizer for nonlinear bound-constrained optimization and equilibrium computations with continuous and discrete variables. ACM Transactions on Mathematical Software, 44(1), 2017.
[37] M. Porcelli and Ph. L. Toint. A note on using performance and data profiles for training algorithms. ACM Transactions on Mathematical Software, 45(2), 2019.
[38] M. J. D. Powell. A direct search optimization method that models the objective and constraint functions by linear interpolation. In S. Gomez and J. P. Hennart, editors, Advances in Optimization and Numerical Analysis, Proceedings of the Sixth Workshop on Optimization and Numerical Analysis, Oaxaca, Mexico, volume 275, pages 51-67, Dordrecht, The Netherlands, 1994. Kluwer Academic Publishers.
[39] M. J. D. Powell. A direct search optimization method that models the objective by quadratic interpolation. Presentation at the 5th Stockholm Optimization Days, Stockholm, 1994.
[40] M. J. D. Powell. Trust region methods that employ quadratic interpolation to the objective function. Presentation at the 5th SIAM Conference on Optimization, Victoria, 1996.
[41] M. J. D. Powell. Direct search algorithms for optimization calculations. Acta Numerica, 7:287-336, 1998.
[42] M. J. D. Powell. The BOBYQA algorithm for bound constrained optimization without derivatives. Technical report, Department of Applied Mathematics and Theoretical Physics, Cambridge University, Cambridge, England, 2009.
[43] C. J. Price and Ph. L. Toint. Exploiting problem structure in pattern-search methods for unconstrained optimization. Optimization Methods and Software, 21(2):479-491, 2006.
[44] L. Roberts and C. Cartis. A derivative-free gauss-newton method. Mathematical Programming Computation, 11(4):631-674, 2019.
[45] H. H. Rosenbrock. An automatic method for finding the greatest or least value of a function. Computer Journal, 3:175-184, 1960.
[46] Ph. R. Sampaio and Ph. L. Toint. A derivative-free trust-funnel method for equality-constrained nonlinear optimization. Computational Optimization and Applications, 61(1):25-49, 2015.
[47] Ph. R. Sampaio and Ph. L. Toint. Numerical experience with a derivative-free trust-funnel method for nonlinear optimization problems with general nonlinear constraints. Optimization Methods and Software, 31(3):511-534, 2016.
[48] K. Scheinberg and Ph. L. Toint. Self-correcting geometry in model-based algorithms for derivativefree unconstrained optimization. SIAM Journal on Optimization, 20(6):3512-3532, 2010.
[49] T. Steihaug. The conjugate gradient method and trust regions in large scale optimization. SIAM Journal on Numerical Analysis, 20(3):626-637, 1983.
[50] Ph. L. Toint. Towards an efficient sparsity exploiting Newton method for minimization. In I. S. Duff, editor, Sparse Matrices and Their Uses, pages 57-88, London, 1981. Academic Press.
[51] V. Torczon. On the convergence of the multidirectional search algorithm. SIAM Journal on Optimization, 1(1):123-145, 1991.
[52] V. Torczon. On the convergence of pattern search algorithms. SIAM Journal on Optimization, 7(1):1-25, 1997.
[53] D. Winfield. Function minimization by interpolation in a data table. Journal of the Institute of Mathematics and its Applications, 12:339-347, 1973.
[2] C. Audet and J. E. Dennis. Pattern search algorithms for mixed variable programming. SIAM Journal on Optimization, 11(3):573-594, 2001.
[3] C. Audet and W. Hare. Derivative-free and blackbox optimization. Springer Verlag, Heidelberg, Berlin, New York, 2017.
[4] C. Audet, S. Le Digabel, and Ch. Tribes. The mesh adaptive direct search algorithm for granular and discrete variables. SIAM Journal on Optimization, 29(2):1164-1189, 2019.
[5] B. M. Averick and J. J. Mor´e. The Minpack-2 test problem collection. Technical Report ANL/MCSP153-0694, Mathematics and Computer Science, Argonne National Laboratory, Argonne, Illinois, USA, 1992.
[6] G. E. P. Box and K. B. Wilson. On the experimental attainment of optimum conditions. Journal of the Royal Statistical Society. Series B (Methodological), 13(1):1-45, 1951.
[7] C. Cartis, J. Fiala, B. Marteau, and L. Roberts. Improving the flexibility and robustness of modelbased derivative-free optimization solvers. ACM Transactions on Mathematical Software, 45(3):32, 2019.
[8] C. Cartis, N. I. M. Gould, and Ph. L. Toint. Trust-region and other regularization of linear leastsquares problems. BIT, 49(1):21-53, 2009.
[9] B. Colson and Ph. L. Toint. Exploiting band structure in unconstrained optimization without derivatives. Optimization and Engineering, 2:349-412, 2001.
[10] B. Colson and Ph. L. Toint. A derivative-free algorithm for sparse unconstrained optimization problems. In A. H. Siddiqi and M. Koˇcvara, editors, Trends in Industrial and Applied Mathematics, pages 131-149, Dordrecht, The Netherlands, 2002. Kluwer Academic Publishers.
[11] B. Colson and Ph. L. Toint. Optimizing partially separable functions without derivatives. Optimization Methods and Software, 20(4-5):493-508, 2005.
[12] A. R. Conn, N. I. M. Gould, and Ph. L. Toint. Trust-Region Methods. MPS-SIAM Series on Optimization. SIAM, Philadelphia, USA, 2000.
[13] A. R. Conn, K. Scheinberg, and Ph. L. Toint. On the convergence of derivative-free methods for unconstrained optimization. In A. Iserles and M. Buhmann, editors, Approximation Theory and Optimization: Tributes to M. J. D. Powell, pages 83-108, Cambridge, England, 1997. Cambridge University Press.
[14] A. R. Conn, K. Scheinberg, and L. N. Vicente. Geometry of sample sets in derivative free optimization. Part I: polynomial interpolation. Technical Report 03-09, Departamento de Matema´tica, Universidade de Coimbra, Portugal, 2003. Revised September 2004.
[15] A. R. Conn, K. Scheinberg, and L. N. Vicente. Geometry of interpolation sets in derivative free optimization. Mathematical Programming, Series B, 111(1-2):141-172, 2008.
[16] A. R. Conn, K. Scheinberg, and L. N. Vicente. Introduction to Derivative-free Optimization. MPSSIAM Series on Optimization. SIAM, Philadelphia, USA, 2009.
[17] A. R. Conn and Ph. L. Toint. An algorithm using quadratic interpolation for unconstrained derivative free optimization. In G. Di Pillo and F. Gianessi, editors, Nonlinear Optimization and Applications, pages 27-47, New York, 1996. Plenum Publishing.
[18] I. D. Coope and C. J. Price. Frame-based methods for unconstrained optimization. Journal of Optimization Theory and Applications, 107:261-274, 2000.
[19] I. D. Coope and C. J. Price. On the convergence of grid-based methods for unconstrained optimization. SIAM Journal on Optimization, 11:859-869, 2001.
[20] I. D. Coope and C. J. Price. Positive basis in numerical optimization. Computational Optimization and Applications, 21, 2002.
[21] J. E. Dennis and V. Torczon. Direct search methods on parallel machines. SIAM Journal on Optimization, 1(4):448-474, 1991.
[22] E. D. Dolan, R. M. Lewis, and V. Torczon. On the local convergence of pattern search. SIAM Journal on Optimization, 14(2):567-583, 2003.
[23] E. D. Dolan and J. J. Mor´e. Benchmarking optimization software with performance profiles. Mathematical Programming, 91(2):201-213, 2002.
[24] E. D. Dolan, J. J. Mor´e, and T. S. Munson. Optimality measures for performance profiles. SIAM Journal on Optimization, 16(3):891-909, 2006.
[25] N. I. M. Gould, D. Orban, and Ph. L. Toint. CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization. Computational Optimization and Applications, 60(3):545-557, 2015.
[26] S. Gratton, C. W. Royer, L. N. Vicente, and Z. Zhang. Direct search based on probabilistic descent. SIAM Journal on Optimization, 25(3):1515-1541, 2015.
[27] S. Gratton, Ph. L. Toint, and A. Tr¨oltzsch. An active-set trust-region method for derivative-free nonlinear bound-constrained optimization. Optimization Methods and Software, 21(4-5):873-894, 2011.
[28] R. Hooke and T. A. Jeeves. Direct search solution of numerical and statistical problems. Journal of the ACM, 8:212-229, 1961.
[29] J. C. Lagarias, B. Poonen, and M. H. Wright. Convergence of the restricted NelderMead algorithm in two dimensions. SIAM Journal on Optimization, 22:501-532, 2012.
[30] J. Larson, M. Menickelly, and S. M. Wild. Derivative-free optimization methods. Acta Numerica, 28:287-404, 2019.
[31] S. Le Digabel. Algorithm 909: NOMAD: Nonlinear optimization with the MADS algorithm. ACM Transactions on Mathematical Software, 37(4):1-44, 2011.
[32] R. M. Lewis and V. Torczon. Pattern search methods for linearly constrained minimization. SIAM Journal on Optimization, 10(3):917941, 2000.
[33] J. J. Mor´e and D. C. Sorensen. Computing a trust region step. SIAM Journal on Scientific and Statistical Computing, 4(3):553-572, 1983.
[34] J. J. Mor´e and S. M. Wild. Benchmarking derivative-free optimization algorithms. SIAM Journal on Optimization, 20(1):172-191, 2009.
[35] J. A. Nelder and R. Mead. A simplex method for function minimization. Computer Journal, 7:308-313, 1965.
[36] M. Porcelli and Ph. L. Toint. BFO, a trainable derivative-free brute force optimizer for nonlinear bound-constrained optimization and equilibrium computations with continuous and discrete variables. ACM Transactions on Mathematical Software, 44(1), 2017.
[37] M. Porcelli and Ph. L. Toint. A note on using performance and data profiles for training algorithms. ACM Transactions on Mathematical Software, 45(2), 2019.
[38] M. J. D. Powell. A direct search optimization method that models the objective and constraint functions by linear interpolation. In S. Gomez and J. P. Hennart, editors, Advances in Optimization and Numerical Analysis, Proceedings of the Sixth Workshop on Optimization and Numerical Analysis, Oaxaca, Mexico, volume 275, pages 51-67, Dordrecht, The Netherlands, 1994. Kluwer Academic Publishers.
[39] M. J. D. Powell. A direct search optimization method that models the objective by quadratic interpolation. Presentation at the 5th Stockholm Optimization Days, Stockholm, 1994.
[40] M. J. D. Powell. Trust region methods that employ quadratic interpolation to the objective function. Presentation at the 5th SIAM Conference on Optimization, Victoria, 1996.
[41] M. J. D. Powell. Direct search algorithms for optimization calculations. Acta Numerica, 7:287-336, 1998.
[42] M. J. D. Powell. The BOBYQA algorithm for bound constrained optimization without derivatives. Technical report, Department of Applied Mathematics and Theoretical Physics, Cambridge University, Cambridge, England, 2009.
[43] C. J. Price and Ph. L. Toint. Exploiting problem structure in pattern-search methods for unconstrained optimization. Optimization Methods and Software, 21(2):479-491, 2006.
[44] L. Roberts and C. Cartis. A derivative-free gauss-newton method. Mathematical Programming Computation, 11(4):631-674, 2019.
[45] H. H. Rosenbrock. An automatic method for finding the greatest or least value of a function. Computer Journal, 3:175-184, 1960.
[46] Ph. R. Sampaio and Ph. L. Toint. A derivative-free trust-funnel method for equality-constrained nonlinear optimization. Computational Optimization and Applications, 61(1):25-49, 2015.
[47] Ph. R. Sampaio and Ph. L. Toint. Numerical experience with a derivative-free trust-funnel method for nonlinear optimization problems with general nonlinear constraints. Optimization Methods and Software, 31(3):511-534, 2016.
[48] K. Scheinberg and Ph. L. Toint. Self-correcting geometry in model-based algorithms for derivativefree unconstrained optimization. SIAM Journal on Optimization, 20(6):3512-3532, 2010.
[49] T. Steihaug. The conjugate gradient method and trust regions in large scale optimization. SIAM Journal on Numerical Analysis, 20(3):626-637, 1983.
[50] Ph. L. Toint. Towards an efficient sparsity exploiting Newton method for minimization. In I. S. Duff, editor, Sparse Matrices and Their Uses, pages 57-88, London, 1981. Academic Press.
[51] V. Torczon. On the convergence of the multidirectional search algorithm. SIAM Journal on Optimization, 1(1):123-145, 1991.
[52] V. Torczon. On the convergence of pattern search algorithms. SIAM Journal on Optimization, 7(1):1-25, 1997.
[53] D. Winfield. Function minimization by interpolation in a data table. Journal of the Institute of Mathematics and its Applications, 12:339-347, 1973.
Metrics
Back to previous page
BibTeX entry
@article{oai:it.cnr:prodotti:468676,
title = {Exploiting problem structure in derivative free optimization},
author = {Porcelli M. and Toint P. L.},
publisher = {Association for Computing Machinery, [New York] , Stati Uniti d'America},
doi = {10.1145/3474054 and 10.48550/arxiv.2001.04801},
journal = {ACM transactions on mathematical software (Online)},
volume = {48},
year = {2022}
}
0000-0003-0183-1204
