Worst-case Complexity Bounds of Directional Direct-search Methods for Multiobjective Optimization

A. L. Custódio, Youssef Diouane, R. Garmanjani, Elisa RicciettiarXiv 2019 · DOI · arXiv

Abstract

Direct Multisearch is a well-established class of algorithms, suited for multiobjective derivative-free optimization. In this work, we analyze the worst-case complexity of this class of methods in its most general formulation for unconstrained optimization. Considering nonconvex smooth functions, we show that to drive a given criticality measure below a specific positive threshold, Direct Multisearch takes at most a number of iterations proportional to the square of the inverse of the threshold, raised to the number of components of the objective function. This number is also proportional to the size of the set of linked sequences between the first unsuccessful iteration and the iteration immediately before the one where the criticality condition is satisfied. We then focus on a particular instance of Direct Multisearch, which considers a more strict criterion for accepting new nondominated points. In this case, we can establish a better worst-case complexity bound, simply proportional to the square of the inverse of the threshold, for driving the same criticality measure below the considered threshold.

Introduction

In many engineering and scientific fields, optimization involves multiple conflicting goals, such as maximizing performance while minimizing cost. Often, these objective functions are evaluated through complex black-box simulations where derivatives are unavailable, necessitating Multiobjective Derivative-Free Optimization (MDFO).

Direct Multisearch (DMS) is a well-established tool for these problems, yet its worst-case complexity (WCC)—the maximum number of iterations required to reach a Pareto critical point within a tolerance $\epsilon$—was previously unknown. This paper provides the first rigorous analysis of these "speed limits," comparing general DMS with a specialized min-max variant.

Methods

The paper analyzes two main algorithmic frameworks for unconstrained optimization:

  1. General Direct Multisearch (Algorithm 1): This standard approach maintains a list of nondominated points (the Pareto front). It uses a poll step to search around current points and accepts new points if they provide a "sufficient decrease" in the objectives. The authors use the hypervolume indicator—a measure of the region in the objective space dominated by the current points—to track progress.
  2. Min-Max Direct Multisearch (Algorithm 2): This more restrictive version focuses on a single point by minimizing the maximum of all objective functions ($f(x) = \max f_i(x)$). This effectively transforms the multiobjective problem into a single-objective (though non-smooth) task.
Illustration of the hypervolume indicator and the sufficient decrease condition in multiobjective optimization.

Key Insights and Ideas

  • The Cost of the Front: The analysis reveals why finding the entire Pareto front is theoretically difficult. For general DMS, the complexity bound is $O(|L(\epsilon)|\epsilon^{-2m})$, where $m$ is the number of objectives. The complexity grows exponentially with the number of objectives as the algorithm attempts to populate a high-dimensional space of nondominated points.
  • Hypervolume as a Progress Gauge: The authors utilize the increase in hypervolume at each successful iteration to prove that the algorithm must eventually converge. The sufficient decrease condition, illustrated in the figure above, ensures that each accepted point significantly improves the current Pareto front approximation.
  • The Min-Max Shortcut: By switching to a min-max formulation, the algorithm becomes more aggressive. It no longer seeks to map the entire front, focusing instead on improving the worst-performing objective. This allows it to achieve a much better theoretical bound of $O(\epsilon^{-2})$.
  • Bridging the Gap: The $O(\epsilon^{-2})$ bound for the min-max variant is significant because it matches the bound of multiobjective gradient descent. This suggests that, in the worst case, the absence of derivatives does not necessarily make the problem harder in terms of iteration count, though it does increase the cost per iteration (function evaluations).

Key Results

  • General DMS Complexity: To drive a criticality measure below $\epsilon$, the algorithm takes at most $O(|L(\epsilon)|\epsilon^{-2m})$ iterations.
  • Min-Max DMS Complexity: This variant is significantly more efficient, requiring at most $O(\epsilon^{-2})$ iterations.
  • Function Evaluations: In terms of total function evaluations, the min-max variant takes $O(n\epsilon^{-2})$, where $n$ is the dimension of the search space, accounting for the multiple directions checked during a derivative-free poll step.

Limitations and Future Work

The analysis assumes the underlying objective functions are smooth (continuously differentiable), even though the algorithm is derivative-free. The results apply to general nonconvex functions; whether these bounds can be improved (e.g., to $O(\epsilon^{-1})$) under convexity assumptions remains an open question. Additionally, the $|L(\epsilon)|$ factor in the general case can be large, potentially making the bound loose for practical applications.

Summary updated

Abstract

Direct Multisearch is a well-established class of algorithms, suited for multiobjective derivative-free optimization. In this work, we analyze the worst-case complexity of this class of methods in its most general formulation for unconstrained optimization. Considering nonconvex smooth functions, we show that to drive a given criticality measure below a specific positive threshold, Direct Multisearch takes at most a number of iterations proportional to the square of the inverse of the threshold, raised to the number of components of the objective function. This number is also proportional to the size of the set of linked sequences between the first unsuccessful iteration and the iteration immediately before the one where the criticality condition is satisfied. We then focus on a particular instance of Direct Multisearch, which considers a more strict criterion for accepting new nondominated points. In this case, we can establish a better worst-case complexity bound, simply proportional to the square of the inverse of the threshold, for driving the same criticality measure below the considered threshold.
BibTeX
@misc{custodio2019worst,
  author = {A. L. Custódio and Youssef Diouane and R. Garmanjani and Elisa Riccietti},
  title = {{Worst-case Complexity Bounds of Directional Direct-search Methods for Multiobjective Optimization}},
  year = {2019},
  eprint = {1909.08099},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.08099},
}
Figure