×

Sobolev seminorm of quadratic functions with applications to derivative-free optimization. (English) Zbl 1315.90063

A problem of least-norm interpolation is considered where the interpolant is a polynomial with degree at least two. The problem is reduced to the minimization of the Sobolev seminorm over a ball. The obtained results are applied to improve updates used in derivative-free optimization algorithms. Numerical examples are presented to illustrate the improved performance of derivative-free solvers using the newly proposed update.

MSC:

90C56 Derivative-free methods and methods using generalized derivatives
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adams, R.A.: Sobolev Spaces. Pure and Applied Mathematics. Academic Press, London (1975)
[2] Bandeira, A.S., Scheinberg, K., Vicente, L.N.: Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization. Math. Program. 134(1), 223-257 (2012) · Zbl 1254.65072
[3] Booker, A.J., Dennis, J.E., Frank, P.D., Serafini, D.B., Torczon, V., Trosset, M.W.: A rigorous framework for optimization of expensive functions by surrogates. Struct. Multidiscip. Optim. 17(1), 1-13 (1999)
[4] Booker, A.J., Dennis Jr, J.E., Frank, P., Serafini, D.B., Torczon, V., Trosset, M.W.: Optimization using surrogate objectives on a helicopter test example. Prog. Syst. Control Theory 24, 49-58 (1998) · Zbl 0937.76067
[5] Booker, A.J., Frank, P., Dennis Jr, J.E., Moore, D.W., Serafini, D.B.: Managing surrogate objectives to optimize helicopter rotor design-further experiments. In: Proceedings of the Seventh AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization (1998) · Zbl 0969.65055
[6] Brent, R.P.: Algorithms for Minimization Without Derivatives. Prentice-Hall, Englewood Cliffs (1973) · Zbl 0245.65032
[7] Choi, T.D., Kelley, C.T.: Superlinear convergence and implicit filtering. SIAM J. Optim. 10(4), 1149-1162 (2000) · Zbl 0994.65071
[8] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Trust-Region Methods, MPS-SIAM series on optimization, Vol. 1. Society for Industrial Mathematics (2000) · Zbl 0958.65071
[9] Conn, A.R., Scheinberg, K., Toint, Ph.L.: On the convergence of derivative-free methods for unconstrained optimization. In: Buhmann, M.D., Iserles, A. (eds.) Approximation Theory and Optimization: Tributes to M. J. D. Powell, pp. 83-108. Cambridge University Press, Cambridge (1997) · Zbl 1042.90617
[10] Conn, A.R., Scheinberg, K., Toint, Ph.L.: Recent progress in unconstrained nonlinear optimization without derivatives. Math. Program. 79, 397-414 (1997) · Zbl 0887.90154
[11] Conn, A.R., Scheinberg, K., Toint, Ph.L.: A derivative free optimization algorithm in practice. In: Proceedings of 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization. St. Louis, MO (1998) · Zbl 1178.65065
[12] Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. Society for Industrial and Applied Mathematics, Philadelphia (2009) · Zbl 1163.49001
[13] Conn, A.R., Toint, Ph.L.: An algorithm using quadratic interpolation for unconstrained derivative free optimization. In: Di Pillo, G., Giannessi, F. (eds.) Nonlinear Optimization and Applications, pp. 27-47. Kluwer Academic/Plenum Publishers, New York (1996) · Zbl 0976.90102
[14] Custódio, A.L., Rocha, H., Vicente, L.N.: Incorporating minimum frobenius norm models in direct search. Comput. Optim. Appl. 46(2), 265-278 (2010) · Zbl 1190.90280
[15] Dennis Jr, J.E., Schnabel, R.B.: Least change secant updates for quasi-newton methods. SIAM Rev. 21(4), 443-459 (1979) · Zbl 0424.65020
[16] Diniz-Ehrhardt, M.A., Martínez, J.M., Raydán, M.: A derivative-free nonmonotone line-search technique for unconstrained optimization. J. Comput. Appl. Math. 219(2), 383-397 (2008) · Zbl 1149.65041
[17] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201-213 (2002) · Zbl 1049.90004
[18] Evans, L.C.: Partial Differential Equations. Graduate Studies in Mathematics. American Mathematical Society, Providence (1998) · Zbl 0902.35002
[19] Fletcher, R.: Practical Methods of Optimization, 2nd edn. Wiley, New York (1987) · Zbl 0905.65002
[20] Fowler, K.R., Reese, J.P., Kees, C.E., Kelley, C.T., Miller, C.T., Audet, C., Booker, A.J., Couture, G., Darwin, R.W.: Comparison of derivative-free optimization methods for groundwater supply and hydraulic capture community problems. Adv. Water Res. 31(5), 743-757 (2008)
[21] Gilmore, P., Kelley, C.T.: An implicit filtering algorithm for optimization of functions with many local minima. SIAM J. Optim. 5, 269 (1995) · Zbl 0828.65064
[22] Gould, N.I.M., Orban, D., Toint, PhL: CUTEr and SifDec: a constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. (TOMS) 29(4), 373-394 (2003) · Zbl 1068.90526
[23] Hemker, T., Fowler, K., Von Stryk, O.: Derivative-free optimization methods for handling fixed costs in optimal groundwater remediation design. In: Proceedings of the CMWR XVI-Computational Methods in Water Resources, pp. 19-22 (2006) · Zbl 0994.65071
[24] Kelley, C.: Iterative Methods for Optimization, Frontiers in Applied Mathematics, Vol. 18. Society for Industrial Mathematics (1999) · Zbl 0934.90082
[25] Kelley, C.T.: A brief introduction to implicit filtering. North Carolina State University, Raleigh, NC, CRSC, Technical Report CRSC-TR02-28 (2002) · Zbl 0994.65071
[26] Kelley, C.T.: Implicit Filtering. Society for Industrial and Applied Mathematics (2011) · Zbl 1246.68017
[27] Kolda, T.G., Lewis, R.M., Torczon, V.: Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 45(3), 385-482 (2003) · Zbl 1059.90146
[28] Lewis, R.M., Torczon, V., Trosset, M.W.: Direct search methods: then and now. J. Comput. Appl. Math. 124(1), 191-207 (2000) · Zbl 0969.65055
[29] Marazzi, M., Nocedal, J.: Wedge trust region methods for derivative free optimization. Math. Program. 91(2), 289-305 (2002) · Zbl 1049.90134
[30] Oeuvray, R.: Trust-region methods based on radial basis functions with application to biomedical imaging. Ph.D. thesis, École Polytechnique Fédérale de Lausanne (2005) · Zbl 1254.65072
[31] Oeuvray, R., Bierlaire, M.: A new derivative-free algorithm for the medical image registration problem. Int. J. Model. Simul. 27(2), 115-124 (2007)
[32] Oeuvray, R., Bierlaire, M.: BOOSTERS: A derivative-free algorithm based on radial basis functions. Int. J. Model. Simul. 29(1), 26-36 (2009) · Zbl 1106.90382
[33] 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: Proceedings of the Sixth Workshop on Optimization and Numerical Analysis (Oaxaca, Mexico), pp. 51-67. Kluwer Academic, Dordrecht (1994) · Zbl 0826.90108
[34] Powell, M.J.D.: Direct search algorithms for optimization calculations. Acta Numerica 7(1), 287-336 (1998) · Zbl 0911.65050
[35] Powell, M.J.D.: UOBYQA: unconstrained optimization by quadratic approximation. Technical Report in DAMTP NA2000/14, CMS, University of Cambridge (2000) · Zbl 1014.65050
[36] Powell, M.J.D.: On trust region methods for unconstrained minimization without derivatives. Math. Program. 97(3), 605-623 (2003) · Zbl 1106.90382
[37] Powell, M.J.D.: Least frobenius norm updating of quadratic models that satisfy interpolation conditions. Math. Program. 100, 183-215 (2004) · Zbl 1146.90526
[38] Powell, M.J.D.: The NEWUOA software for unconstrained optimization without derivatives. Technical Report in DAMTP NA2004/08, CMS, University of Cambridge (2004) · Zbl 1108.90005
[39] Powell, M.J.D.: Developments of NEWUOA for minimization without derivatives. IMA J. Numer. Anal. 649-664 (2008) doi:10.1093/imanum/drm047 · Zbl 1154.65049
[40] Powell, M.J.D.: The BOBYQA algorithm for bound constrained optimization without derivatives. Technical Report in DAMTP 2009/NA06, CMS, University of Cambridge (2009)
[41] Powell, M.J.D.: Beyond symmetric Broyden for updating quadratic models in minimization without derivatives. Math. Program. 1-26 (2012) doi:10.1007/s10107-011-0510-y
[42] Stewart III, G.: A modification of davidon’s minimization method to accept difference approximations of derivatives. J. ACM (JACM) 14(1), 72-83 (1967) · Zbl 0239.65056
[43] Berghen Vanden, F., Bersini, H.: CONDOR, a new parallel, constrained extension of powell’s UOBYQA algorithm: Experimental results and comparison with the DFO algorithm. J. Comput. Appl. Math. 181(1), 157-175 (2005) · Zbl 1072.65088
[44] Wild, S.M.: MNH: a derivative-free optimization algorithm using minimal norm Hessians. In: Tenth Copper Mountain Conference on Iterative Methods (2008)
[45] 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) · Zbl 1178.65065
[46] Winfield, D.H.: Function minimization by interpolation in a data table. IMA J. Appl. Math. 12(3), 339 (1973) · Zbl 0274.90060
[47] Wright, M.H.: Direct search methods: Once scorned, now respectable. Pitman Research Notes in Mathematics Series, pp. 191-208 (1996) · Zbl 0844.65057
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.