  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.
