Derivative-Free Optimization with Transformed Objective Functions and the Algorithm Based on the Least Frobenius Norm Updating Quadratic Model

doi:10.1007/s40305-023-00532-x

Abstract

Abstract: Derivative-free optimization (DFO) problems are optimization problems where the derivative information is unavailable. The least Frobenius norm updating quadratic interpolation model function is one of the essential under-determined model functions for model-based derivative-free trust-region methods. This article proposes derivative-free optimization with transformed objective functions (DFOTO) and gives a model-based trust-region method with the least Frobenius norm model. The model updating formula is based on Powell’s formula and can be easily implemented. The method shares the same framework with those for problems without transformations, and its query scheme is given. We propose the definitions related to optimality-preserving transformations to understand the interpolation model in our method when minimizing transformed objective functions. We prove the existence of model optimality-preserving transformations beyond translation transformations. The necessary and sufficient condition for such transformations is given. An interesting discovery is that, as a fundamental transformation, the affine transformation with a (non-trivial) positive multiplication coefficient is not model optimality-preserving. We also analyze the corresponding least Frobenius norm updating model and its interpolation error when the objective function is affinely transformed. The convergence property of a provable algorithmic framework containing the least Frobenius norm updating quadratic model for minimizing transformed objective functions is given. Numerical results show that our method can successfully solve most test problems with objective optimality-preserving transformations, even though some of such transformations will change the optimality of the model function. To our best knowledge, this is the first work providing the model-based derivative-free algorithm and analysis for transformed problems with the function evaluation oracle. This article also proposes the “moving-target” optimization problem as an open problem.

Key words: Derivative-free optimization, Transformation, Quadratic model, Trust-region

CLC Number:

Peng-Cheng Xie, Ya-Xiang Yuan. Derivative-Free Optimization with Transformed Objective Functions and the Algorithm Based on the Least Frobenius Norm Updating Quadratic Model[J]. Journal of the Operations Research Society of China, 2025, 13(2): 327-363.

TrendMD

References

[1] Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. SIAM, Philadelphia (2009)
[2] Audet, C., Hare, W.: Derivative-Free and Blackbox Optimization. Springer, Berlin (2017)
[3] Audet, C., Orban, D.: Finding optimal algorithmic parameters using derivative-free optimization. SIAM J. Optim. 17(3), 642-664 (2006)
[4] Aly, A., Guadagni, G., Dugan, J.B.: Derivative-free optimization of neural networks using local search. In: 2019 IEEE 10th Annual Ubiquitous Computing, Electronics Mobile Communication Conference, pp. 293-299. IEEE, Piscataway (2019)
[5] Higham, N.J.: Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia (2002)
[6] Levina, T., Levin, Y., McGill, J., Nediak, M.: Dynamic pricing with online learning and strategic consumers: an application of the aggregating algorithm. Oper. Res. 57(2), 327-341 (2009)
[7] Li, S., Xie, P., Zhou, Z., Wang, Z., Li, Z., Liang, X., Qu, B.: Simulation of interaction of folded waveguide space traveling wave tubes with derivative-free mixedinteger based NEWUOA algorithm. In: 2021 7th International Conference on Computer and Communications, pp. 1215-1219. IEEE, Piscataway (2021)
[8] Hooke, R., Jeeves, T.A.: Direct search solution of numerical and statistical problems. J. ACM 8(2), 212-229 (1961)
[9] Nelder, J.A., Mead, R.: A simplex method for function minimization. Comput. J. 7(4), 308-313 (1965)
[10] Tseng, P.: Fortified-descent simplicial search method: a general approach. SIAM J. Optim. 10, 269-288 (1999)
[11] Kolda, T., Lewis, R., Torczon, V.: Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 45, 385-482 (2003)
[12] Audet, C., Le Digabel, S., Tribes, C.: NOMAD user guide. Technical report, Les Cahiers du GERAD (2009)
[13] Rosenbrock, H.: An automatic method for finding the greatest or least value of a function. Comput. J. 3(3), 175-184 (1960)
[14] Swann, W.H.: Direct search methods. In: Murray, W. (ed.) Numerical Methods for Unconstrained Optimization, pp. 13-28. Academic Press, London (1972)
[15] Smith, C.S.: The automatic computation of maximum likelihood estimates. Technical report, Scientific Department, National Coal Board (1962)
[16] Powell, M.J.D.: An efficient method for finding the minimum of a function of several variables without calculating derivatives. Comput. J. 7(2), 155-162 (1964)
[17] Stewart, G., III.: A modification of Davidon’s minimization method to accept difference approximations of derivatives. J. ACM 14(1), 72-83 (1967)
[18] Gill, P.E., Murray, W.: Quasi-Newton methods for unconstrained optimization. IMA J. Appl. Math. 9(1), 91-108 (1972)
[19] Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: Computing forward-difference intervals for numerical optimization. SIAM J. Sci. Stat. Comput. 4(2), 310-321 (1983)
[20] Nesterov, Y., Spokoiny, V.: Random gradient-free minimization of convex functions. Found. Comput. Math. 17(2), 527-566 (2017)
[21] Duchi, J.C., Jordan, M.I., Wainwright, M.J., Wibisono, A.: Optimal rates for zero-order convex optimization: the power of two function evaluations. IEEE Trans. Inf. Theory 61(5), 2788-2806 (2015)
[22] Scheinberg, K.: Finite difference gradient approximation: to randomize or not? INFORMS J. Comput. 34(5), 2384-2388 (2022)
[23] Zhigljavsky, A.A.: Theory of Global Random Search. Springer, Berlin (2012)
[24] Berahas, A.S., Cao, L., Choromanski, K., Scheinberg, K.: A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Found. Comput. Math. 22(2), 507-560 (2022)
[25] Winfield, D.: Function and Functional Optimization by Interpolation in Data Tables. PhD thesis, Harvard University, Cambridge (1969)
[26] Powell, M.J.D.: On trust region methods for unconstrained minimization without derivatives. Math. Program. 97, 605-623 (2003)
[27] Powell, M.J.D.: Least Frobenius norm updating of quadratic models that satisfy interpolation conditions. Math. Program. 100, 183-215 (2004)
[28] Powell, M.J.D.: The NEWUOA software for unconstrained optimization without derivatives. In: Pillo, G., Roma, M. (eds.) Large-scale Nonlinear Optimization, pp. 255-297. Springer, Boston (2006)
[29] Conn, A., Scheinberg, K., Vicente, L.N.: Geometry of sample sets in derivative free optimization. Part ii: polynomial regression and underdetermined interpolation. IMA J. Numer. Anal. 28, 721-748 (2008)
[30] Conn, A., Scheinberg, K., Vicente, L.N.: Global convergence of general derivative-free trust-region algorithms to first- and second-order critical points. SIAM J. Optim. 20, 387-415 (2009)
[31] Xie, P., Yuan, Y.-X.: Least

\begin{document}$ H^2 $\end{document}

norm updating quadratic interpolation model function for derivative-free trust-region algorithms. arXiv:2302.12017 (2023)
[32] Xie, P., Yuan, Y.-X.: A new two-dimensional model-based subspace method for large-scale unconstrained derivative-free optimization: 2D-MoSub. arXiv:2309.14855 (2023)
[33] Xie, P.: Sufficient conditions for distance reduction between the minimizers of non-convex quadratic functions in the trust region. arXiv:2310.08603 (2023)
[34] Björkman, M., Holmström, K.: Global optimization of costly nonconvex functions using radial basis functions. Optim. Eng. 1, 373-397 (2000)
[35] Wild, S.M., Regis, R.G., Shoemaker, C.A.: ORBIT: optimization by radial basis function interpolation in trust-regions. SIAM J. Sci. Comput. 30(6), 3197-3219 (2008)
[36] Xie, P., Yuan, Y.-X.: A derivative-free optimization algorithm combining line-search and trust-region techniques. Chin. Ann. Math. Ser. B 44(5), 719-734 (2023)
[37] Bandeira, A.S., Scheinberg, K., Vicente, L.N.: Convergence of trust-region methods based on probabilistic models. SIAM J. Optim. 24(3), 1238-1264 (2014)
[38] Gratton, S., Royer, C.W., Vicente, L.N., Zhang, Z.: Complexity and global rates of trust-region methods based on probabilistic models. IMA J. Numer. Anal. 38(3), 1579-1597 (2018)
[39] Van Laarhoven, P.J.M., Aarts, E.H.L.: Simulated Annealing: Theory and Applications. Springer, Dordrecht (1987)
[40] Pelikan, M., Goldberg, D.E., Cantú-Paz, E.: BOA: The Bayesian optimization algorithm. In: Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99, vol. 1, pp. 525-532. Morgan Kaufmann Publishers, Burlington (1999)
[41] Gratton, S., Royer, C.W., Vicente, L.N., Zhang, Z.: Direct search based on probabilistic descent. SIAM J. Optim. 25(3), 1515-1541 (2015)
[42] Ghadimi, S., Lan, G.: Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim. 23(4), 2341-2368 (2013)
[43] Larson, J., Wild, S.M.: A batch, derivative-free algorithm for finding multiple local minima. Optim. Eng. 17(1), 205-228 (2016)
[44] Zhang, H., Conn, A.R., Scheinberg, K.: A derivative-free algorithm for least-squares minimization. SIAM J. Optim. 20(6), 3555-3576 (2010)
[45] Cartis, C., Roberts, L.: A derivative-free Gauss-Newton method. Math. Program. Comput. 11(4), 631-674 (2019)
[46] Xie, P.: A derivative-free trust-region method for optimization on the ellipsoid. J. Phys. Conf. Ser. 2620(1), 012007 (2023)
[47] Larson, J., Menickelly, M., Wild, S.M.: Derivative-free optimization methods. Acta Numer. 28, 287-404 (2019)
[48] Zhang, Z.: Derivative-free optimization. In: Yuan, Y.-X. (ed.) China Discipline Development Strategy: Mathematical Optimization, pp. 84-92. Science Press, Beijing (2021). (in Chinese)
[49] Rios, L.M., Sahinidis, N.V.: Derivative-free optimization: a review of algorithms and comparison of software implementations. J. Glob. Optim. 56(3), 1247-1293 (2013)
[50] Hansen, N., Müller, S.D., Koumoutsakos, P.: Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evol. Comput. 11(1), 1-18 (2003)
[51] Scheinberg, K.: Manual for Fortran software package DFO version 2.0. Technical report (2003)
[52] Kelley, C.T.: Users guide for IMFIL version 1.0. Technical report (2011)
[53] Powell, M.J.D.: A tolerant algorithm for linearly constrained optimization calculations. Math. Program. 45, 547-566 (1989)
[54] Powell, M.J.D.: A direct search optimization method that models the objective and constraint functions by linear interpolation. In: Gomez, S., Hennart, J.-P. (eds.) Advances in Optimization and Numerical Analysis, pp. 51-67. Springer, Dordrecht (1994)
[55] Powell, M.J.D.: UOBYQA: unconstrained optimization by quadratic approximation. Math. Program. Ser. B 92, 555-582 (2002)
[56] Powell, M.J.D.: The BOBYQA algorithm for bound constrained optimization without derivatives. Technical report, University of Cambridge (2009)
[57] Powell, M.J.D.: On fast trust region methods for quadratic models with linear constraints. Math. Program. Comput. 7(3), 237-267 (2015)
[58] Cartis, C., Fiala, J., Marteau, B., Roberts, L.: Improving the flexibility and robustness of model-based derivative-free optimization solvers. ACM Trans. Math. 45(3), 1-41 (2019)
[59] Cartis, C., Roberts, L.: Scalable subspace methods for derivative-free nonlinear least-squares optimization. Math. Program. 199(1-2), 461-524 (2023)
[60] Ragonneau, T.M., Zhang, Z.: PDFO: a cross-platform package for Powell’s derivative-free optimization solvers. arXiv:2302.13246 (2023)
[61] Ragonneau, T.M.: Model-based derivative-free optimization methods and software. PhD thesis, Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong (2022)
[62] Xie, P.: NEWUOA-Matlab-Version-2.0 (2022)
[63] Xie, P.: BOBYQA-Matlab-Version-1.0 (2023)
[64] Zhang, Z.: PRIMA: reference implementation for Powell’s methods with modernization and amelioration. http://www.libprima.net, https://doi.org/10.5281/zenodo.8052654(2023)
[65] Dinur, I., Nissim, K.: Revealing information while preserving privacy. In: Proceedings of the 22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 202-210. ACM, New York (2003)
[66] Dwork, C., Nissim, K.: Privacy-preserving datamining on vertically partitioned databases. In: Advances in Cryptology—CRYPTO 2004, pp. 528-544. Springer, Berlin (2004)
[67] Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Halevi, S., Rabin, T. (eds.) Theory of Cryptography: Third Theory of Cryptography Conference, pp. 265-284. Springer, Berlin (2006)
[68] Nissim, K., Raskhodnikova, S., Smith, A.: Smooth sensitivity and sampling in private data analysis. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 75-84. ACM, New York
[69] Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.: What can we learn privately? SIAM J. Comput. 40(3), 793-826 (2011)
[70] McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: 48th Annual IEEE Symposium on Foundations of Computer Science. IEEE, Piscataway (2007)
[71] Wang, Y., Hale, M., Egerstedt, M., Dullerud, G.E.: Differentially private objective functions in distributed cloud-based optimization. In: 2016 IEEE 55th Conference on Decision and Control, pp. 3688-3694. IEEE, Piscataway (2016)
[72] Liu, J., Huang, X., Liu, J.K.: Secure sharing of personal health records in cloud computing: ciphertext-policy attribute-based signcryption. Future Gener. Comput. Syst. 52, 67-76 (2015)
[73] Kusner, M., Gardner, J., Garnett, R., Weinberger, K.: Differentially private Bayesian optimization. In: Proceedings of the 32nd International Conference on Machine Learning, vol. 37, pp. 918-927. PMLR, Lille, France (2015)
[74] Grapiglia, G.N., Yuan, J., Yuan, Y.-x: A derivative-free trust-region algorithm for composite nonsmooth optimization. Comput. Appl. Math. 35(2), 475-499 (2016)
[75] Deng, G., Ferris, M.C.: Adaptation of the UOBYQA algorithm for noisy functions. In: Proceedings of the 2006 Winter Simulation Conference, pp. 312-319. IEEE, Piscataway (2006)
[76] Jamieson, K.G., Nowak, R., Recht, B.: Query complexity of derivative-free optimization. In: Pereira, F., Burges, C.J., Bottou, L., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems, vol. 25. Curran Associates Inc., New York (2012)
[77] Conn, A.R., Scheinberg, K., Toint, Ph. L.: On the convergence of derivative-free methods for unconstrained optimization. In: Iserles, A., Buhmann, M. (eds.) Approximation Theory and Optimization: Tributes to M. J. D. Powell, pp. 83-108. Cambridge University Press, Cambridge (1997)
[78] Conn, A.R., Scheinberg, K., Toint, Ph.L.: Recent progress in unconstrained nonlinear optimization without derivatives. Math. Program. 79(1), 397-414 (1997)
[79] Conn, A.R., Scheinberg, K., Toint, Ph. L.: A derivative free optimization algorithm in practice. In: 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, p. 4718. AIAA, Reston (1998)
[80] Powell, M.J.D.: On updating the inverse of a KKT matrix. In: Yuan, Y.-X. (ed.) Numerical Linear Algebra and Optimization, pp. 56-78. Science Press, Beijing (2004)
[81] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, Berlin (2006)
[82] Moré, J.J., Wild, S.M.: Benchmarking derivative-free optimization algorithms. SIAM J. on Optim. 20(1), 172-191 (2009)
[83] Conn, A.R., Gould, N., Lescrenier, M., Toint, Ph.L.: Performance of a multifrontal scheme for partially separable optimization. In: Gomez, S., Hennart, J.-P. (eds.) Advances in Optimization and Numerical Analysis, pp. 79-96. Springer, Dordrecht (1994)
[84] Toint, Ph.L.: Some numerical results using a sparse matrix updating formula in unconstrained optimization. Math. Comput. 32(143), 839-851 (1978)
[85] Li, Y.J., Li, D.H.: Truncated regularized Newton method for convex minimizations. Comput. Optim. Appl. 43, 119-131 (2009)
[86] Lukšan, L., Matonoha, C., Vlcek, J.: Modified CUTE problems for sparse unconstrained optimization. Technical report, Institute of Computer Science AS ČR (2010)
[87] Andrei, N.: An unconstrained optimization test functions collection. Adv. Model. Optim. 10(1), 147-161 (2008)
[88] Li, G.: The secant/finite difference algorithm for solving sparse nonlinear systems of equations. SIAM J. Numer. Anal. 25, 1181-1196 (1988)
[89] Gould, N., Orban, D., Toint, Ph. L.: General CUTEr documentation. Technical report (2001)
[90] Moré, J.J., Garbow, B.S., Hillstrom, K.E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7(1), 17-41 (1981)
[91] Zhang, Z.: The Research on Derivative-free Optimization Methods. PhD thesis, Graduate School of the Chinese Academy of Sciences, University of Chinese Academy of Sciences, Beijing (2012)
[92] Wilson, J.D., Wintucky, E.G., Vaden, K.R., Force, D.A., Krainsky, I.L., Simons, R.N., Robbins, N.R., Menninger, W.L., Dibb, D.R., Lewis, D.E.: Advances in space traveling-wave tubes for NASA missions. Proc. IEEE 95(10), 1958-1967 (2007)
[93] Levush, B.: The design and manufacture of vacuum electronic amplifiers: progress and challenges. In: 2019 International Vacuum Electronics Conference (IVEC), pp. 1-5. IEEE, Piscataway (2019)