Multiobjectivization of Local Search: Single-Objective Optimization Benefits From Multi-Objective Gradient Descent

Optimization is essentially everywhere and most real-world problems are of nonlinear and multimodal nature, i.e., there may exist multiple local optima that become traps for local search [23]. That is, classical local search based on gradient descent will get stuck in local optima unless restart mechanisms or search space exploration methods prevent premature convergence. Much effort has been put into this issue. Early attempts tried to make local search more flexible, e.g., by adding search points or spanning simplex structures, to discover patterns in search space and allow non-derivative descent to the optimum [20]. However, local search cannot solve these problems in general. Thus, later approaches [1] combine originally one-dimensional global search mechanisms like the STEP global search [30] and a local interpolation technique proposed by Brent [3] for the multivariate case. Others combine established stochastic global search mechanisms based on clustering [24] with newer elements of global optimizers [29] to gain quality improvements of solutions and to avoid finding only local optima [22].