×

zbMATH — the first resource for mathematics

Coordinate search algorithms in multilevel optimization. (English) Zbl 1305.90382
Summary: Many optimization problems of practical interest arise from the discretization of continuous problems. Classical examples can be found in calculus of variations, optimal control and image processing. In the recent years a number of strategies have been proposed for the solution of such problems, broadly known as multilevel methods. Inspired by classical multigrid schemes for linear systems, they exploit the possibility of solving the problem on coarser discretization levels to accelerate the computation of a finest-level solution. In this paper, we study the applicability of coordinate search algorithms in a multilevel optimization paradigm. We develop a multilevel derivative-free coordinate search method, where coarse-level objective functions are defined by suitable surrogate models. We employ a recursive v-cycle correction scheme, which exhibits multigrid-like error smoothing properties. On a practical level, the algorithm is implemented in tandem with a full-multilevel initialization. A suitable strategy to manage the coordinate search stepsize on different levels is also proposed, which gives a substantial contribution to the overall speed of the algorithm. Numerical experiments on several examples show promising results. The presented algorithm can solve large problems in a reasonable time, thus overcoming size and convergence speed limitations typical of coordinate search methods.

MSC:
90C30 Nonlinear programming
90C56 Derivative-free methods and methods using generalized derivatives
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
Software:
minpack
PDF BibTeX Cite
Full Text: DOI
References:
[1] Averick B.M., Tech. Rep (1992)
[2] DOI: 10.1080/10556780500099944 · Zbl 1136.49311
[3] W.L. Briggs, V.E. Henson, and S.F. McCormick,A Multigrid Tutorial, 2nd ed., SIAM, Philadelphia, 1999.
[4] DOI: 10.1137/050644999 · Zbl 1120.68108
[5] DOI: 10.1137/080741410 · Zbl 1217.68235
[6] DOI: 10.1080/10556780903239295 · Zbl 1190.90209
[7] DOI: 10.1093/imanum/drn034 · Zbl 1156.65060
[8] DOI: 10.1137/050623012 · Zbl 1163.90024
[9] DOI: 10.1137/S003614450242889
[10] DOI: 10.1137/S1064827502407792 · Zbl 1119.65346
[11] DOI: 10.1007/s10589-013-9546-7 · Zbl 1276.90069
[12] DOI: 10.1145/355934.355936 · Zbl 0454.65049
[13] DOI: 10.1080/10556780008805795 · Zbl 0988.90040
[14] Nash S.G., Tech. Rep (2010)
[15] DOI: 10.1109/TIP.2004.837555 · Zbl 1296.94042
[16] DOI: 10.1109/TIP.2006.877313 · Zbl 05453641
[17] DOI: 10.1080/10556780500137116 · Zbl 1136.90516
[18] U. Trottenberg, C. Oosterlee, and A. Schüller,Multigrid, Academic Press, London, 2001.
[19] DOI: 10.1007/s00607-008-0261-7 · Zbl 1156.65068
[20] Ye J.C., IEEE Trans. Image Proc 10 (5) pp 909– (2001)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.