6.8cm Convergence towards a local minimum by direct search methods with a
covering step JanvierJanuary 2024 TBD B. Hamel, K. Hébert Hamel, Hébert Hamel,
Benoit, Karine Hébert (2021). Un exemple de citation , _Journal of Journals_ ,
vol. X issue Y, p. n-mhttps://www.gerad.ca/fr MaiMay2022

Pierre-Yves Bouchet LABEL:affil:polymtlLABEL:affil:gerad Charles Audet
LABEL:affil:polymtlLABEL:affil:gerad Loïc Bourdin LABEL:affil:unilim

affil:polymtlÉcole Polytechnique de Montréal, Montréal (Qc), Canada, H3T 1J4
affil:geradGERAD, Montréal (Qc), Canada, H3T 1J4 affil:unilimXLIM Research
Institute, University of Limoges, France

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Abstract This paper introduces a new step to the Direct Search Method (DSM) to
strengthen its convergence analysis. By design, this so-called covering step
may ensure that for all refined points of the sequence of incumbent solutions
generated by the resulting cDSM (covering DSM), the set of all evaluated trial
points is dense in a neighborhood of that refined point. We prove that this
additional property guarantees that all refined points are local solutions to
the optimization problem. This new result holds true even for discontinuous
objective function, under a mild assumption that we discuss in details. We
also provide a practical construction scheme for the covering step that works
at low additional cost per iteration.

#### Keywords:

Discontinuous optimization, nonsmooth optimization, derivative-free
optimization, Direct Search Method, convergence, local solution.

Résumé Cet article propose une nouvelle étape à ajouter à chaque itération de
la Méthode de Recherche Directe (Direct Search Method (DSM) en anglais) pour
renforcer son analyse de convergence. Cette nouvelle étape, nommée covering
step, peut garantir par construction que pour tout point raffiné de la suite
de points générée par cDSM (covering DSM), un ensemble dense de points est
évalué dans un voisinage de ce point raffiné. Nous prouvons que cette
propriété permet de certifier l’optimalité locale de tous les points raffinés.
Ce nouveau résultat est valide pour des fonctions objectif potentiellement
discontinues, sous une hypothèse légère que nous discutons en détails. Nous
proposons également un schéma de construction pratique pour la covering step
qui mène à un faible surcoût par itération.

#### Mots clés :

Optimisation discontinue, optimisation non lisse, optimisation sans dérivées,
Direct Search Methods, convergence, solution locale.

We thank Dr. Solène Kojtych for her insightful comments when we were
investigating the properties of the revealing step. She deserves credit for
Theorem 1 since she also foresaw that the revealing step could strengthen the
convergence analysis of DSM. This work was funded by Audet’s NSERC Canada
Discovery Grant 2020–04448.

##  1 Introduction

Consider the generic optimization problem

$\underset{\scriptsize\begin{array}[]{c}x\in\mathbb{R}^{n}\end{array}}{\operatorname*{minimize}}\quad
f(x),$ ($\mathbf{P}$)

where $f:\mathbb{R}^{n}\to\mathbb{R}\cup\\{+\infty\\}$ is possibly
discontinuous and has a nonempty effective domain $X\subseteq\mathbb{R}^{n}$.
The Direct Search Method (DSM) addresses Problem ($\mathbf{P}$) by generating
sequences $(x^{k})_{k\in\mathbb{N}}$ of incumbent solutions and
$(\delta^{k})_{k\in\mathbb{N}}$ of poll radii, where $(x^{k},\delta^{k})\in
X\times\mathbb{R}_{+}^{*}$ for all $k\in\mathbb{N}$. The literature about DSM
extracts refining subsequences from $(x^{k},\delta^{k})_{k\in\mathbb{N}}$ and
studies the properties of their associated refined points. A subsequence
$(x^{k},\delta^{k})_{k\in K^{*}}$, where $K^{*}\subseteq\mathbb{N}$ is
infinite, is said to be refining [3, 4] if all iterations indexed by $k\in
K^{*}$ fail (that is, $x^{k+1}=x^{k}$), $(\delta^{k})_{k\in K^{*}}$ converges
to zero and $(x^{k})_{k\in K^{*}}$ converges to a limit $x^{*}$ named the
refined point. It is proved in [18] that, for all sets
$K^{*}\subseteq\mathbb{N}$ indexing a refining subsequence, the corresponding
refined point $x^{*}$ satisfies a necessary optimality condition expressed in
term of the Rockafellar derivative [17, 18] of $f$ at $x^{*}$, provided that
$(f(x^{k}))_{k\in K^{*}}$ converges to $f(x^{*})$. Then, our previous work [2]
extends [18] to ensure this last requirement under the assumption that all
refining subsequences admit the same refined point. These results are valid
for two standard classes of DSM: the mesh-based method [6, Part 3] and the
sufficient decrease-based method [9, Section 7.7].

The main goal of this paper is to strengthen the above convergence analysis,
via the addition of a new step to the DSM to guarantee that all refined points
are local minima. First, we introduce the covering DSM (cDSM), relying on the
so-called covering step which aims to ensure that for all refined points, the
set of all evaluated trial points is dense in a neighborhood of that refined
point. We refer to Property 1 for details. Second, we prove that this property
implies that, for all $K^{*}\subseteq\mathbb{N}$ indexing a refining
subsequence with refined point denoted by $x^{*}$, either $x^{*}\in X$ is a
local solution to Problem ($\mathbf{P}$), or $x^{*}\notin X$ is such that
$(f(x^{k}))_{k\in K^{*}}$ converges to the infimum of $f$ over a neighborhood
of $x^{*}$. This result is formalized in Theorem 1. Third, we propose a
practical construction scheme for the covering step to indeed ensure Property
1 by design. This scheme fits in both the mesh-based cDSM and the sufficient
decrease-based cDSM, and the additional cost per iteration it induces is low.
Finally, this paper has an auxiliary goal in proving that our framework is
tight and broader than others in the literature. Our assumptions cannot be
relaxed in general, and they are weaker than in former work.

The covering step generalizes the revealing step from [1, 2]. Actually, our
initial motivation was to better study this revealing step. Its goal in [1] is
to reveal local discontinuities, but we observe in [2] that when the DSM
generates a unique refined point, the revealing step provides the density of
the trial points in a neighborhood of the refined point. However, [1, 2] fail
to deduce the local optimality of the refined point. Thus, the current work
originally aimed to state this property. Yet, we eventually found that the
revealing step admits a generalization providing the density of the set of
trial points around an arbitrary number of refined points. The formalization
of this generalization and the study of its properties constitute the core of
the present work. Note that we decided to change the terminology because, in
comparison with the name revealing, we believe that the name covering better
captures what this step actually does.

This paper is organized as follows. Section 2 formalizes the cDSM and states
its convergence analysis in Theorem 1. Section 3 proves Theorem 1. Section 4
provides a construction scheme for the covering step. Section 5 discusses our
assumptions about $f$. Finally, Section 6 identifies some extensions of our
work. Appendix A contains proofs of auxiliary results used in the paper.

Notation: For all $r>0$ and all $x\in\mathbb{R}^{n}$, we denote by
$\mathcal{B}_{r}(x)$ the open ball of radius $r$ in infinite norm centered at
$x$, and by $\mathcal{B}_{r}\triangleq\mathcal{B}_{r}(0)$. For all
$x\in\mathbb{R}^{n}$ and all $\mathcal{S}\subseteq\mathbb{R}^{n}$, we denote
by $\\{x\\}+\mathcal{S}\triangleq\\{x+s:s\in\mathcal{S}\\}$ and
$f(\mathcal{S})\triangleq\\{f(s):s\in\mathcal{S}\\}$ and
$\mathrm{dist}(x,\mathcal{S})\triangleq\inf\\{\lVert{x-s}\rVert:s\in\mathcal{S}\\}$.
For all $\delta\in\mathbb{R}_{+}^{*}$ and all
$\mathcal{S}\subseteq\mathbb{R}$, we define
$\delta\mathcal{S}\triangleq\\{\delta s:s\in\mathcal{S}\\}$. For all
$\mathcal{S}\subseteq\mathbb{R}^{n}$, $\mathcal{S}$ is said to be ample if
$\mathcal{S}\subseteq\mathrm{cl}(\mathrm{int}(\mathcal{S}))$, or locally thin
if there exists $\mathcal{N}\subseteq\mathbb{R}^{n}$ open so that
$\mathcal{S}\cap\mathcal{N}\neq\emptyset=\mathrm{int}(\mathcal{S})\cap\mathcal{N}$.
Note that a set is either ample or locally thin (see Proposition 7.a) in
Appendix A), and that the definition of an ample set is equivalent to that of
a semi-open set introduced in [15]. We denote by $\mathbb{S}^{n}$ the unit
sphere of $\mathbb{R}^{n}$.

##  2 Formal covering step and convergence result of cDSM

This section formalizes the cDSM as Algorithm 1 and its convergence analysis
in Theorem 1. Theorem 1 is based on Property 1 regarding a dense covering
property ($\mathrm{DCP}$) provided by the covering step and on Assumption 1
regarding the objective function $f$. The proof of Theorem 1 follows in
Section 3.

The cDSM matches the usual DSM in most of its aspects. The only novelty lies
in the covering step, with its parameter $r\in\mathbb{R}_{+}^{*}$, detailed in
Section 4. The other steps and parameters may be designed as in all mesh-based
DSM [6, Part 3] and all sufficient decrease-based DSM [9, Section 7.7].

Algorithm 1 cDSM (covering DSM) solving Problem ($\mathbf{P}$).

Initialization:

set a covering radius $r\in\mathbb{R}_{+}^{*}$ and the trial points history as
$\mathcal{V}^{0}\triangleq\emptyset$; set the incumbent solution and poll
radius as $(x^{0},\delta^{0})\in X\times\mathbb{R}_{+}^{*}$, and set
$\underline{\delta}^{0}\triangleq\delta^{0}$; set
$\mathcal{M}:\mathbb{R}_{+}^{*}\to 2^{\mathbb{R}^{n}}$ and
$\rho:\mathbb{R}_{+}^{*}\to\mathbb{R}_{+}$ and $\Lambda\subset{]}0,1[$ and
$\Upsilon\subset[1,+\infty[$ according to one of • the mesh-based DSM:
$\mathcal{M}(\nu)\triangleq\min\\{\nu,\frac{\nu^{2}}{\delta^{0}}\\}M\mathbb{Z}^{p}$
for all $\nu\in\mathbb{R}_{+}^{*}$, where $p>n$ and $M\in\mathbb{R}^{n\times
p}$ positively spans $\mathbb{R}^{n}$, and $\rho(\cdot)\triangleq 0$, and
$\Lambda\subseteq\\{\tau^{\ell}:\ell\in\llbracket 1,m\rrbracket\\}$ and
$\Upsilon\subseteq\\{\tau^{\ell}:\ell\in\llbracket-m,0\rrbracket\\}$ where
$\tau\in\mathbb{Q}\cap{]}0,1[$ and $m\in\mathbb{N}^{*}$; • the sufficient
decrease-based DSM: $\mathcal{M}(\cdot)\triangleq\mathbb{R}^{n}$, and $\rho$
increasing with $0<\rho(\nu)\in o(\nu)$ as $\nu\searrow 0$, and
$\Lambda\subseteq[\underline{\lambda},\overline{\lambda}]$ and
$\Upsilon\subseteq[\underline{\upsilon},\overline{\upsilon}]$ where
$0<\underline{\lambda}\leq\overline{\lambda}<1\leq\underline{\upsilon}\leq\overline{\upsilon}<+\infty$.

For $k\in\mathbb{N}$ do:

search step:

set $\mathcal{D}_{\tt{S}}^{k}\subseteq\mathcal{M}(\underline{\delta}^{k})$
finite; if
$\mathcal{T}_{\tt{S}}^{k}\triangleq\\{x^{k}\\}+\mathcal{D}_{\tt{S}}^{k}$ is
nonempty, then set
$t_{\tt{S}}^{k}\in\operatorname*{argmin}f(\mathcal{T}_{\tt{S}}^{k})$; if also
$f(t_{\tt{S}}^{k})<f(x^{k})-\rho(\underline{\delta}^{k})$, then set
$t^{k}\triangleq t_{\tt{S}}^{k}$ and
$\mathcal{T}_{\tt{C}}^{k}=\mathcal{T}_{\tt{P}}^{k}\triangleq\emptyset$ and go
to the update step;

covering step:

set
$\mathcal{D}_{\tt{C}}^{k}\subseteq\mathcal{M}(\underline{\delta}^{k})\cap\mathrm{cl}(\mathcal{B}_{r})$
finite; if
$\mathcal{T}_{\tt{C}}^{k}\triangleq\\{x^{k}\\}+\mathcal{D}_{\tt{C}}^{k}$ is
nonempty, then set
$t_{\tt{C}}^{k}\in\operatorname*{argmin}f(\mathcal{T}_{\tt{C}}^{k})$; if also
$f(t_{\tt{C}}^{k})<f(x^{k})-\rho(\underline{\delta}^{k})$, then set
$t^{k}\triangleq t_{\tt{C}}^{k}$ and
$\mathcal{T}_{\tt{P}}^{k}\triangleq\emptyset$ and go to the update step;

poll step:

set
$\mathcal{D}_{\tt{P}}^{k}\subseteq\mathcal{M}(\underline{\delta}^{k})\cap\mathrm{cl}(\mathcal{B}_{\delta^{k}})$
a positive basis of $\mathbb{R}^{n}$; set
$\mathcal{T}_{\tt{P}}^{k}\triangleq\\{x^{k}\\}+\mathcal{D}_{\tt{P}}^{k}$; set
$t_{\tt{P}}^{k}\in\operatorname*{argmin}f(\mathcal{T}_{\tt{P}}^{k})$; if
$f(t_{\tt{P}}^{k})<f(x^{k})-\rho(\underline{\delta}^{k})$, then set
$t^{k}\triangleq t_{\tt{P}}^{k}$, otherwise set $t^{k}\triangleq x^{k}$;

update step:

set $\mathcal{V}^{k+1}\triangleq\mathcal{V}^{k}\cup\mathcal{T}^{k}$, where
$\mathcal{T}^{k}\triangleq\mathcal{T}_{\tt{S}}^{k}\cup\mathcal{T}_{\tt{C}}^{k}\cup\mathcal{T}_{\tt{P}}^{k}$;
set $x^{k+1}\triangleq t^{k}$; set $\delta^{k+1}$ as
$\delta^{k+1}\in\delta^{k}\Upsilon$ if $t^{k}\neq x^{k}$ and
$\delta^{k+1}\in\delta^{k}\Lambda$ otherwise; set
$\underline{\delta}^{k+1}\triangleq\min_{\ell\leq k+1}\delta^{k}$.

A carefully constructed covering step ensures that all executions of the cDSM
satisfy the next Property 1. A practical construction scheme to indeed meet
this property is stated in Section 4.3.

######  Property 1 (dense covering property provided by the covering step).

The covering step ensures that the trial points history
$\mathcal{V}\triangleq\cup_{k\in\mathbb{N}}\mathcal{V}^{k}$ generated by
Algorithm 1 satisfies, for all refined points $x^{*}$,

$\mathcal{B}_{r}(x^{*})\ \subseteq\ \mathrm{cl}\left(\mathcal{V}\right).$
($\mathrm{DCP}$)

Theorem 1 also requires the following assumptions about $f$. Assumptions 1.a)
and 1.b) match usual assumptions used in the literature, while the unusual
Assumption 1.c) is discussed in Section 5.

######  Assumption 1 (on the objective function $f$).

The objective function $f$ in Problem ($\mathbf{P}$) is such that

  1. a)

$f$ is bounded below and has bounded sublevel sets;

  2. b)

the restriction $f_{|X}:X\to\mathbb{R}$ is lower semicontinuous;

  3. c)

$X$ admits a partition $X=\sqcup_{i=1}^{N}X_{i}$ (where
$N\in\mathbb{N}^{*}\cup\\{+\infty\\}$) such that, for all $i\in\llbracket
1,N\rrbracket$, $X_{i}$ is an ample continuity set of $f$ (that is, $X_{i}$ is
ample and the restriction $f_{|X_{i}}:X_{i}\to\mathbb{R}$ is continuous).

######  Theorem 1.

Under Assumption 1, Algorithm 1 generates at least one refining subsequence
and, if Property 1 holds, then for all $K^{*}\subseteq\mathbb{N}$ indexing a
refining subsequence, the refined point $x^{*}$ satisfies

$\underset{k\in K^{*}}{\lim}f(x^{k})\ =\ \left\\{\begin{array}[]{rl}\min
f(\mathcal{B}_{r}(x^{*})){\leavevmode\nobreak\
=f(x^{*})}&\mbox{if}\leavevmode\nobreak\ x^{*}\in X,\\\ \inf
f(\mathcal{B}_{r}(x^{*}))\phantom{\leavevmode\nobreak\
=f(x^{*})}&\mbox{if}\leavevmode\nobreak\ x^{*}\notin X.\end{array}\right.$

Before proving Theorem 1 in Section 3, several comments are in order. First,
the covering step fits in the framework of the search step. Yet, to the best
of our knowledge, no DSM from the literature ensures Property 1, except
instances of the cDSM relying on the scheme for the covering step we propose
in Section 4. Second, when Assumption 1 holds, Property 1 ensures that all
refined points are local solutions to Problem ($\mathbf{P}$), in a generalized
sense enclosing the case where some refined points lie outside the effective
domain $X$. Last, in practice the cDSM likely generates exactly one refined
point which moreover lies in $X$. This point is therefore a local solution to
Problem ($\mathbf{P}$) in the usual sense.

##  3 Proof of Theorem 1

Preliminary results. The covering step is a specific search step, thus
Algorithm 1 inherits all the properties of the usual DSM. Hence, the next
Proposition 1 holds. It is stated as [6, Theorem 8.1] for the mesh-based DSM
and as [9, Corollary 7.2] for the sufficient decrease-based DSM.

######  Proposition 1.

Under Assumption 1.a), Algorithm 1 generates at least one refining
subsequence.

The rest of this section relies on the following unusual topological concepts.
A set $\mathcal{S}\subseteq\mathbb{R}^{n}$ is said to be ample if
$\mathcal{S}\subseteq\mathrm{cl}(\mathrm{int}(\mathcal{S}))$, and a set
$\mathcal{S}_{1}\subseteq\mathbb{R}^{n}$ is said to have a dense intersection
with another set $\mathcal{S}_{2}\subseteq\mathbb{R}^{n}$ if
$\mathcal{S}_{2}\subseteq\mathrm{cl}(\mathcal{S}_{1}\cap\mathcal{S}_{2})$. We
leave some related properties to Proposition 7 in Appendix A.

The next Lemma 1 highlights what Property 1 provides. It leads to Proposition
2, which settles the ground for the proof of Theorem 1.

######  Lemma 1.

Under Assumption 1.c), if Algorithm 1 satisfies Property 1, then for all
refined points $x^{*}$, all $i\in\llbracket 1,N\rrbracket$ and all
$x\in\mathcal{B}_{r}(x^{*})\cap X_{i}$, the set $\mathcal{V}\setminus\\{x\\}$
has a dense intersection with $\mathcal{B}_{r}(x^{*})\cap X_{i}$.

###### Proof.

Let $x^{*}$ be a refined point generated by Algorithm 1 satisfying Property 1
and let $i\in\llbracket 1,N\rrbracket$. Then $\mathcal{V}$ has a dense
intersection with $\mathcal{B}_{r}(x^{*})$, via Property 1 and Proposition
7.c) applied to $\mathcal{S}_{1}\triangleq\mathcal{V}$ and
$\mathcal{S}_{2}\triangleq\mathrm{cl}(\mathcal{V})$ and
$\mathcal{S}_{3}\triangleq\mathcal{B}_{r}(x^{*})$. Also, $X_{i}$ is ample by
Assumption 1.c) so $\mathcal{B}_{r}(x^{*})\cap X_{i}$ is an ample subset of
$\mathcal{B}_{r}(x^{*})$ by Proposition 7.b). It follows that $\mathcal{V}$
has a dense intersection with $\mathcal{B}_{r}(x^{*})\cap X_{i}$, from
Proposition 7.c) applied to $\mathcal{S}_{1}\triangleq\mathcal{V}$,
$\mathcal{S}_{2}\triangleq\mathcal{B}_{r}(x^{*})$ and
$\mathcal{S}_{3}\triangleq\mathcal{B}_{r}(x^{*})\cap X_{i}$. The claim follows
from Proposition 7.d) applied to $\mathcal{S}_{1}\triangleq\mathcal{V}$ and
$\mathcal{S}_{2}\triangleq\mathcal{B}_{r}(x^{*})\cap X_{i}$. ∎

######  Proposition 2.

Under Assumption 1, if Algorithm 1 satisfies Property 1, then for all refined
points $x^{*}$, we have $\lim_{k\in\mathbb{N}}f(x^{k})\leq f(x)$ for all
$x\in\mathcal{B}_{r}(x^{*})$.

###### Proof.

First, $f^{*}\triangleq\lim_{k\in\mathbb{N}}f(x^{k})\in\mathbb{R}$ exists
since $(f(x^{k}))_{k\in\mathbb{N}}$ is bounded below by Assumption 1.a) and
decreasing by construction. Second, let $x^{*}$ be a refined point generated
by Algorithm 1 satisfying Property 1 and take $x\in\mathcal{B}_{r}(x^{*})$.
The result holds if $x\notin X$, so assume that $x\in X_{i}$ for some
$i\in\llbracket 1,N\rrbracket$. Let $(y_{\ell})_{\ell\in\mathbb{N}}$
converging to $x$ with $y_{\ell}\in\mathcal{B}_{r}(x^{*})\cap
X_{i}\cap\mathcal{V}\setminus\\{x\\}$ for all $\ell\in\mathbb{N}$ (it exists
by Lemma 1). Let
$\kappa(\ell)\triangleq\min\\{k\in\mathbb{N}:y_{\ell}\in\mathcal{T}^{k}\\}$
for all $\ell\in\mathbb{N}$. Then $(\kappa(\ell))_{\ell\in\mathbb{N}}$
diverges to $+\infty$, since $\mathcal{T}^{k}$ is finite for all
$k\in\mathbb{N}$ and every subsequence of $(y_{\ell})_{\ell\in\mathbb{N}}$
takes infinitely many values (since $(y_{\ell})_{\ell\in\mathbb{N}}$ converges
to $x$ with $y_{\ell}\neq x$ for all $\ell\in\mathbb{N}$). Also, for all
$\ell\in\mathbb{N}$ we have $f(t^{\kappa(\ell)})\geq
f(x^{\kappa(\ell)})-\rho(\underline{\delta}^{\kappa(\ell)})$ if iteration
$\kappa(\ell)$ fails and $f(t^{\kappa(\ell)})=f(x^{\kappa(\ell)+1})$
otherwise, and $f(y_{\ell})\geq f(t^{\kappa(\ell)})$ by construction. Hence,
for all $\ell\in\mathbb{N}$ we have
$f(y_{\ell})+\rho(\underline{\delta}^{\kappa(\ell)})\geq
f(x^{\kappa(\ell)+1})$. The result follows by taking $\ell\to+\infty$, since
$(f(y_{\ell}))_{\ell\in\mathbb{N}}$ converges to $f(x)$ by continuity of
$f_{|X_{i}}$ and $(f(x^{\kappa(\ell)+1}))_{\ell\in\mathbb{N}}$ converges to
$f^{*}$ and $(\rho(\underline{\delta}^{\kappa(\ell)}))_{\ell\in\mathbb{N}}$
converges to $0$. ∎

Proof of Theorem 1. Consider that Assumption 1 is satisfied. Proposition 1
states that at least one refining subsequence is generated. Assume that
Property 1 holds. Let $K^{*}\subseteq\mathbb{N}$ indexing a refining
subsequence, $x^{*}$ denoting its refined point, and let
$f^{*}\triangleq\lim_{k\in K^{*}}f(x^{k})=\lim_{k\in\mathbb{N}}f(x^{k})$. Let
us show that $f^{*}=\inf f(\mathcal{B}_{r}(x^{*}))$. We have $f^{*}\geq\inf
f(\mathcal{B}_{r}(x^{*}))$ since $x^{k}\in\mathcal{B}_{r}(x^{*})$ for all
$k\in K^{*}$ large enough, and $f^{*}\leq\inf f(\mathcal{B}_{r}(x^{*}))$ is
proved by contradiction: if $f^{*}>\inf f(\mathcal{B}_{r}(x^{*}))$, then there
exists $x^{\sharp}\in\mathcal{B}_{r}(x^{*})$ such that $f^{*}>f(x^{\sharp})$,
but then $f^{*}>f(x^{\sharp})\geq f^{*}$ by Proposition 2. Note that this
already concludes the proof of the case where $x^{*}\notin X$. Now assume that
$x^{*}\in X$. Then $f^{*}\geq f(x^{*})$ by Assumption 1.b) and $f^{*}\leq
f(x^{*})$ by Proposition 2, so $f(x^{*})=f^{*}=\inf
f(\mathcal{B}_{r}(x^{*}))=\min f(\mathcal{B}_{r}(x^{*}))$. ∎

##  4 Discussion on the covering step and Property 1

This section discusses the novel algorithmic aspect of the cDSM, that is, the
covering step with Property 1 it ensures a posteriori (that is, after the
execution of cDSM). Section 4.1 highlights the differences between the
covering step and the revealing step it is inspired from. Section 4.2 provides
a sufficient condition about a construction scheme for the covering step to
guarantee a priori (that is, prior to the execution of cDSM) that an execution
of the cDSM will satisfy Property 1. It is presumably easier to check this
condition a priori than to verify a posteriori that Property 1 holds. Section
4.3 provides a tractable construction scheme for the covering step which
checks this sufficient condition.

###  4.1 The revealing step from prior work may not provide Property 1 a
posteriori

As stated in Section 1, the covering step is inspired from the revealing step
in a DSM that we hereafter call the revealing DSM (rDSM) [2, Algorithm 1].
Nevertheless, we show in this section that the rDSM may fail to ensure
Property 1 when more than one refined point is generated.

Expressed in our notation, the revealing step in [2] relies on a sequence
$(\mathcal{D}_{\ell})_{\ell\in\mathbb{N}}$ with
$\mathcal{D}_{\ell}\subset\mathrm{cl}(\mathcal{B}_{r})$ finite for all
$\ell\in\mathbb{N}$ and such that
$\mathcal{B}_{r}\subseteq\mathrm{cl}(\cup_{\ell\in\mathbb{N}}\mathcal{D}_{\ell})$.
For all $k\in\mathbb{N}$, $\mathcal{D}_{\tt{C}}^{k}$ is the rounding of
$\mathcal{D}_{\ell(k)}$ onto $\mathcal{M}(\underline{\delta}^{k})$, where
$\ell(k)$ denotes the number of iterations indices $u<k$ such that
$\underline{\delta}^{u+1}<\underline{\delta}^{u}$. Thus, the revealing step
ensures that

$\mathcal{B}_{r}\subseteq\mathrm{cl}\left(\underset{k\in\mathbb{N}}{\cup}\mathcal{D}_{\tt{C}}^{k}\right)$

when the rDSM generates at least one refining subsequence, which is certified
a priori by Proposition 1. Nevertheless, this property states only the dense
intersection of the trial directions history with $\mathcal{B}_{r}$. Property
1 follows when the rDSM generates exactly one refined point [2, Lemma 2].
However, this fails when more than one refined point exist. The following
example illustrates this observation.

######  Example 1.

Consider the objective function $f:\mathbb{R}^{2}\to\mathbb{R}$ defined as
$f(x)\triangleq\lVert{x}\rVert_{\infty}$ for all $x\in\mathbb{R}^{2}$ and the
algorithmic parameters $r\triangleq 1$, $x^{0}\triangleq-3\mathds{1}$ where
$\mathds{1}\triangleq(1,1)$, $\delta^{0}\triangleq 1$,
$\mathcal{M}(\nu)\triangleq\min\\{\nu,\nu^{2}\\}\mathbb{Z}^{2}$ and
$\rho(\nu)\triangleq 0$ for all $\nu\in\mathbb{R}_{+}^{*}$,
$\Lambda\triangleq\\{\frac{1}{2}\\}$ and $\Upsilon\triangleq\\{1\\}$. Define
the poll step as
$\mathcal{D}_{\tt{P}}^{k}\triangleq\\{(\pm\delta^{k},0),(0,\pm\delta^{k})\\}$
for all $k\in\mathbb{N}$. Define the revealing step such that the sequence
$(\mathcal{D}_{\ell})_{\ell\in\mathbb{N}}$ satisfies

$\forall
q\in\mathbb{N},\qquad\mathcal{D}_{4q}\subset\mathbb{R}_{+}\times\mathbb{R}_{+},\quad\mathcal{D}_{4q+1}\subset\mathbb{R}_{-}\times\mathbb{R}_{+},\quad\mathcal{D}_{4q+2}\subset\mathbb{R}_{-}\times\mathbb{R}_{-},\quad\mathcal{D}_{4q+3}\subset\mathbb{R}_{+}\times\mathbb{R}_{-}.$

Define the search step at each iteration $k\in\mathbb{N}$ so that
$\mathcal{T}_{\tt{S}}^{k}\triangleq\emptyset$ if $k\notin 3\mathbb{N}$, and so
that $\mathcal{T}_{\tt{S}}^{3q}\triangleq\\{t_{\tt{S}}^{3q}\\}$ for all
$k=3q\in 3\mathbb{N}$, where

$t_{\tt{S}}^{3q}\triangleq\left(-1\right)^{q}\left(1+2^{-q}\right)\mathds{1}.$

This instance of rDSM has a predictable behavior. Using induction, one can
show that

$\forall
q\in\mathbb{N},\quad\left\\{\begin{array}[]{llll}x^{3q\phantom{+1}}=(-1)^{q-1}\left(1+2^{-(q-1)}\right)\mathds{1},&\delta^{3q\phantom{+1}}=\phantom{\frac{1}{2}}4^{-q},&\mathcal{D}_{\tt{C}}^{3q\phantom{+1}}=\mathcal{D}_{2q},&\mbox{{search}
success,}\\\
x^{3q+1}=(-1)^{q\phantom{-1}}\left(1+2^{-q}\right)\mathds{1},&\delta^{3q+1}=\phantom{\frac{1}{2}}4^{-q},&\mathcal{D}_{\tt{C}}^{3q+1}=\mathcal{D}_{2q},&\mbox{iteration
fails,}\\\
x^{3q+2}=(-1)^{q\phantom{-1}}\left(1+2^{-q}\right)\mathds{1},&\delta^{3q+2}=\frac{1}{2}4^{-q},&\mathcal{D}_{\tt{C}}^{3q+2}=\mathcal{D}_{2q+1},&\mbox{iteration
fails.}\end{array}\right.$

Thus, there are two refined point, $x^{*}_{+}=\mathds{1}$ and
$x^{*}_{-}=-\mathds{1}$, and none is a local minimizer of $f$. However, this
does not contradict Theorem 1 because Property 1 is not satisfied. Indeed, we
have

$\mathrm{cl}(\mathcal{V})\leavevmode\nobreak\ \cap\leavevmode\nobreak\
{]}-1,1{[}\leavevmode\nobreak\
^{2}=\emptyset\quad\mbox{while}\quad\mathcal{B}_{r}(x^{*}_{+})={]}1-r,1+r{[}\leavevmode\nobreak\
^{2}\quad\mbox{and}\quad\mathcal{B}_{r}(x^{*}_{-})={]}-1-r,-1+r{[}\leavevmode\nobreak\
^{2},\quad\forall r\in\mathbb{R}_{+}^{*}.$

Example 1 shows that the revealing step from [2] focuses only on the
asymptotic density of the trial directions, and that this may not translate to
the density of the trial points in some neighborhoods of the refined points.
The original instance of the revealing step provided in [1] differs from whose
in [2] (in [1], the revealing step draws at each iteration a direction in
$\mathrm{cl}(\mathcal{B}_{r})$ according to the independent uniform
distribution), but it also fails to provide Property 1 when more than one
refined point exists. Accordingly, in Section 4.2 we study schemes for the
covering step that focus instead on satisfying directly the dense intersection
of the trial points with a neighborhood of all refined points.

###  4.2 Sufficient condition to ensure a priori that Property 1 will hold

This section focuses on covering step instances relying only, at each
iteration $k\in\mathbb{N}$, on the current couple
$(x^{k},\underline{\delta}^{k})$, and the current history
$\mathcal{V}^{k}=\cup_{\ell<k}\mathcal{T}^{\ell}$. We prove in Proposition 3
that if the covering step relies on a covering oracle from Definition 1, then
all executions of the cDSM satisfy Property 1.

######  Definition 1 (covering oracle).

Given a covering radius $r\in\mathbb{R}_{+}^{*}$ and a mesh
$\mathcal{M}:\mathbb{R}_{+}^{*}\to 2^{\mathbb{R}^{n}}$ defined either as in
the mesh-based DSM or the sufficient decrease-based DSM, a function
$\mathbb{O}:\mathbb{R}^{n}\times\mathbb{R}_{+}^{*}\times 2^{\mathbb{R}^{n}}\to
2^{\mathbb{R}^{n}}$ is said to be a covering oracle if
$\mathbb{O}(y,\nu,\mathcal{S})\subseteq\mathcal{M}(\nu)\cap\mathrm{cl}(\mathcal{B}_{r})$
for all points $y\in\mathbb{R}^{n}$, all radii $\nu\in\mathbb{R}_{+}^{*}$ and
all sets $\mathcal{S}\subseteq\mathbb{R}^{n}$, and if

$\underset{{k\in\mathbb{N}}}{\lim}\quad\underset{d\in\mathcal{M}(\nu^{k})\cap\mathrm{cl}(\mathcal{B}_{r})}{\max}\leavevmode\nobreak\
\mathrm{dist}\left(y^{k}+d,\leavevmode\nobreak\
\mathcal{S}^{k}\right)\quad=\quad 0$

for all sequences $(y^{k},\nu^{k},\mathcal{S}^{k})_{k\in\mathbb{N}}$ of
elements of $\mathbb{R}^{n}\times\mathbb{R}_{+}^{*}\times 2^{\mathbb{R}^{n}}$
such that $(y^{k})_{k\in\mathbb{N}}$ converges and
$(\nu^{k})_{k\in\mathbb{N}}$ converges to $0$ and
$\mathcal{S}^{k+1}\supseteq\mathcal{S}^{k}\cup(\\{y^{k}\\}+\mathbb{O}(y^{k},\nu^{k},\mathcal{S}^{k}))$
for all $k\in\mathbb{N}$.

######  Proposition 3.

If Algorithm 1 has its covering step constructed as

$\forall
k\in\mathbb{N},\qquad\mathcal{D}_{\tt{C}}^{k}\triangleq\mathbb{O}\left(x^{k},\underline{\delta}^{k},\mathcal{V}^{k}\right),$

where $\mathbb{O}$ satisfies Definition 1, then Property 1 holds a posteriori
for all executions of Algorithm 1.

###### Proof.

Consider the framework of Proposition 3. Denote by
$\mathcal{M}_{r}(y,\nu)\triangleq\\{y\\}+(\mathcal{M}(\nu)\cap\mathrm{cl}(\mathcal{B}_{r}))$
for all $(y,\nu)\in\mathbb{R}^{n}\times\mathbb{R}_{+}^{*}$. Let
$K^{*}\subseteq\mathbb{N}$ indexing a refining subsequence, with refined point
$x^{*}$. We state Property 1 by checking that
$\mathcal{V}\cap\mathcal{B}_{\varepsilon}(x)\neq\emptyset$, for all
$\varepsilon>0$ and all $x\in\mathcal{B}_{r}(x^{*})$. Let $\varepsilon>0$ and
$x\in\mathcal{B}_{r}(x^{*})$. By construction of the covering step, we have
$\mathcal{V}^{k+1}\supseteq\mathcal{V}^{k}\cup\mathcal{T}_{\tt{C}}^{k}=\mathcal{V}^{k}\cup(\\{x^{k}\\}+\mathbb{O}(x^{k},\underline{\delta}^{k},\mathcal{V}^{k}))$
for all $k\in K^{*}$. Then, we may apply the definition of the covering oracle
with $(x^{k},\underline{\delta}^{k},\mathcal{V}^{k})_{k\in K^{*}}$ as the
sequence $(y^{k},\nu^{k},\mathcal{S}^{k})_{k\in\mathbb{N}}$. This leads to
$\mathrm{dist}(\mathcal{M}_{r}(x^{k},\underline{\delta}^{k}),\mathcal{V}^{k})<\frac{\varepsilon}{2}$
for all $k\in K^{*}$ large enough. By construction of
$\mathcal{M}(\underline{\delta}^{k})$, we also have
$\mathrm{dist}(x,\mathcal{M}_{r}(x^{k},\underline{\delta}^{k}))<\frac{\varepsilon}{2}$
for all $k\in K^{*}$ large enough. Then, let $k\in K^{*}$ satisfying these two
conditions, define $y$ as the rounding of $x$ onto
$\mathcal{M}_{r}(x^{k},\underline{\delta}^{k})$ and $c\in\mathcal{V}$ as the
rounding of $y$ onto $\mathcal{V}^{k}$. Thus,
$\left\lVert{x-c}\right\rVert\leq\left\lVert{x-y}\right\rVert+\left\lVert{y-c}\right\rVert<\frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon$,
so $c\in\mathcal{B}_{\varepsilon}(x)\cap\mathcal{V}$. ∎

Proposition 3 depends only on the oracle $\mathbb{O}$ driving the covering
step, so it may be checked a priori. In contrast, Property 1 must be checked a
posteriori, as this requires the whole sequence
$(x^{k},\delta^{k},\mathcal{V}^{k})_{k\in\mathbb{N}}$ to identify the refined
points and check ($\mathrm{DCP}$). Thus, checking Proposition 3 prior to
executing the cDSM is presumably a good strategy to ensure that Property 1
will be satisfied. The construction scheme for the covering step we introduce
in Section 4.3 relies on Definition 1 and Proposition 3.

###  4.3 Construction of a covering step instance usable in practice

In practice, an instance of the covering step must satisfy two criteria. The
first is that the resulting trial points history $\mathcal{V}$ must satisfy
Property 1. The second is that the number of covering trial points must be
small at each iteration. This section proposes a practical scheme that meets
these two criteria. We follow the guideline from Section 4.2, that is,
$\mathcal{D}_{\tt{C}}^{k}\triangleq\mathbb{O}(x^{k},\underline{\delta}^{k},\mathcal{V}^{k})$
at each $k\in\mathbb{N}$, where $\mathbb{O}$ is a covering oracle from
Definition 1. Our scheme designs a tractable expression for $\mathbb{O}$.

The baseline scheme we suggest for the covering step relies on the following
oracle:

$\forall
y\in\mathbb{R}^{n},\quad\forall\nu\in\mathbb{R}_{+}^{*},\quad\forall\mathcal{S}\subseteq\mathbb{R}^{n},\qquad\mathbb{O}(y,\nu,\mathcal{S})\triangleq\underset{d\in\mathcal{M}(\nu)\cap\mathrm{cl}(\mathcal{B}_{r})}{\operatorname*{argmax}}\mathrm{dist}\left(y+d,\mathcal{S}\right).$
(1)

Proposition 8 states that Oracle 1 is indeed a covering oracle. Then, a
covering step instance relying on Oracle 1 ensures Property 1, as claimed by
Proposition 3. This instance selects
$\mathcal{D}_{\tt{C}}^{k}\triangleq\mathbb{O}(x^{k},\underline{\delta}^{k},\mathcal{V}^{k})$
at each $k\in\mathbb{N}$ as the set of all directions
$d_{\tt{C}}^{k}\in\mathcal{M}(\underline{\delta}^{k})\cap\mathrm{cl}(\mathcal{B}_{r})$
such that $t_{\tt{C}}^{k}\triangleq x^{k}+d_{\tt{C}}^{k}$ is the farthest
possible from the set $\mathcal{V}^{k}$ of all past trial points. Moreover,
Property 1 remains valid if we actually compute only one such direction. This
computation is costly when $k$ is large, but it may be alleviated.

First, in the mesh-based cDSM, computing Oracle 1 is a combinatorial problem,
since $\mathcal{M}(\nu)$ is a discrete set for all $\nu\in\mathbb{R}_{+}^{*}$.
It may be solved using a distance transform algorithm, such as whose in [16],
which works in a number of operations linear with the cardinality of
$\mathcal{M}(\nu)\cap\mathrm{cl}(\mathcal{B}_{r})$ and most of them are
feasible in parallel. In the sufficient decrease-based cDSM (where
$\mathcal{M}(\nu)\triangleq\mathbb{R}^{n}$ for all
$\nu\in\mathbb{R}_{+}^{*}$), computing Oracle 1 is a continuous and piecewise
smooth problem. This problem admits surrogates, such as
$\overline{\mathbb{O}}(y,\gamma,\mathcal{S})\triangleq\operatorname*{argmax}_{d\in\mathrm{cl}(\mathcal{B}_{r})}\Sigma_{s\in\mathcal{S}}\frac{-1}{\left\lVert{y+d-s}\right\rVert}$.
Also, at each iteration $k\in\mathbb{N}^{*}$ the computation of
$\mathcal{D}_{\tt{C}}^{k}$ may start from the point $t_{\tt{C}}^{k-1}$
calculated at the preceding iteration.

Second, in practice we may alter Oracle 1 as

$\forall
y\in\mathbb{R}^{n},\quad\forall\nu\in\mathbb{R}_{+}^{*},\quad\forall\mathcal{S}\subseteq\mathbb{R}^{n},\qquad\mathbb{O}(y,\nu,\mathcal{S})\triangleq\underset{d\in\mathcal{M}(\nu)\cap\mathrm{cl}(\mathcal{B}_{r})}{\operatorname*{argmax}}\mathrm{dist}\left(y+d,\mathcal{S}\cap\mathrm{cl}(\mathcal{B}_{r})\right).$
(2)

This reduces the number of elements to consider in the computation of the
point-set distance, and this alteration remains a covering oracle (the proof
of Proposition 8 admits an adaptation to this oracle).

Third, we may also consider the following alteration of Oracle 2. Let
$\alpha\in{]}0,1]$ and consider

$\mathbb{O}_{\alpha}(y,\nu,\mathcal{S})\triangleq\left\\{d_{\alpha}\in\mathcal{M}(\nu)\cap\mathrm{cl}(\mathcal{B}_{r}):\dfrac{\mathrm{dist}\left(y+d_{\alpha},\mathcal{S}\cap\mathrm{cl}(\mathcal{B}_{r})\right)}{\underset{d\in\mathcal{M}(\nu)\cap\mathrm{cl}(\mathcal{B}_{r})}{\max}\mathrm{dist}\left(y+d,\mathcal{S}\cap\mathrm{cl}(\mathcal{B}_{r})\right)}\geq\alpha\right\\},$
(3)

for all $(y,\nu,\mathcal{S})\in\mathbb{R}^{n}\times\mathbb{R}_{+}^{*}\times
2^{\mathbb{R}^{n}}$. Oracle 3 remains a covering oracle (the proof of
Proposition 8 may be adapted accordingly). Oracle 3 usually contains numerous
elements, but recall that in practice we do not need to compute more than one.
It is presumably easier to compute an element of the set defined by Oracle 3
than one of the set defined by Oracle 1, especially when $\alpha$ is chosen
close to $0$. A simple heuristic approach to localize such an element
$d_{\alpha}$ may use a grid search on a grid thin enough, or some space-
filling sequences such as the Halton sequence [12].

Last, let us stress that in practice, we may perform a revealing step such as
in [1, 2] instead of a covering step relying on a covering oracle. Indeed, in
practice the revealing step usually ensures Property 1. Moreover, the
computational cost required by the revealing step is almost null.
Nevertheless, despite its more expensive cost, Oracle 1 ensures that the trial
points are well spread in a neighborhood of the current incumbent solution at
each iteration. This contrasts with the revealing step, which offers no such
guarantee. In addition, in a blackbox context the cost to compute Oracle 1 may
be negligible anyway, since the bottleneck in this context is the cost to
evaluate $f(x)$ for all $x\in X$, and this computation involves no call to the
objective function. For comparison, our scheme constructs a covering step
instance evaluating at most $1$ point per iteration while the poll step
considers at least $n+1$ points per iteration since it relies on a positive
basis of $\mathbb{R}^{n}$.

Let us discuss also the covering radius $r$. All $r\in\mathbb{R}_{+}^{*}$ are
accepted, but fine-tuning this value in practice is a problem-dependent
concern. Indeed, the smaller $r$ is, the faster the covering step covers
$\mathcal{B}_{r}(x^{*})$ well, while in contrast, the larger $r$ is, the more
likely the cDSM escapes poor local solutions. Following this observation, two
simple choices when no information about Problem ($\mathbf{P}$) is available
are $r\triangleq\frac{\delta^{0}}{10}$ or $r\triangleq\delta^{0}$. We may also
consider a sequence $(r^{k})_{k\in\mathbb{N}}$ instead of a fixed $r$,
provided that $\underline{r}\triangleq\inf_{k\in\mathbb{N}}r^{k}>0$. In that
case, replace $\mathcal{B}_{r}(x^{*})$ by $\mathcal{B}_{\underline{r}}(x^{*})$
in Property 1 and Theorem 1. This alteration of Theorem 1 is proved by a
rewording of Section 3 where $\mathcal{B}_{r}(x^{*})$ is replaced accordingly.

##  5 Discussion on Assumption 1.c)

This section discusses our novel assumption describing the continuity sets of
$f$, that is, Assumption 1.c). In Section 5.1, we prove that Assumption 1.c)
is strictly weaker than similar assumptions considered in former work [1, 2,
18]. In Section 5.2, we show that Assumption 1.c) is tight.

###  5.1 Comparison of Assumption 1.c) with similar assumptions in prior work

In this section, we compare Assumption 1.c) to similar assumptions considered
by former work [1, 2, 18]. Precisely, we show that Assumption 1.c) is strictly
weaker than either [1, Assumption 4.4] and [2, Assumption 1]. The work [18] is
not considered since [2] is an extension of it.

First, let us compare Assumption 1.c) to [1, Assumption 4.4], recalled below
as Assumption 2. We prove in Proposition 4 that Assumption 1.c) is strictly
weaker than Assumption 2.

######  Assumption 2 (Assumption 4.4 in [1]).

There exists $N\in\mathbb{N}^{*}\cup\\{+\infty\\}$ nonintersecting open sets
$X_{i}$ such that $\mathrm{cl}(X)=\cup_{i=1}^{N}\mathrm{cl}(X_{i})$ and
$f_{|X_{i}}$ is continuous for all $i\in\llbracket 1,N\rrbracket$ and, for all
$x\in X$, there exists $j\in\llbracket 1,N\rrbracket$ such that
$x\in\mathrm{cl}(X_{j})$ and $f_{|X_{j}\cup\\{x\\}}$ is continuous.

######  Proposition 4.

Assumption 1.c) is strictly weaker than Assumption 2.

###### Proof.

Suppose that Assumption 2 holds. Denote by $(X_{i})_{i=1}^{N}$ the family it
provides. For all $i\in\llbracket 1,N\rrbracket$, let
$\mathrm{cl}_{f}(X_{i})\triangleq\\{x\in\mathrm{cl}(X_{i}):f_{|X_{i}\cup\\{x\\}}$
is continuous$\\}$. Let $I(x)\triangleq\min\\{i\in\llbracket
1,N\rrbracket:x\in\mathrm{cl}_{f}(X_{i})\\}$ for all $x\in X$. Then let
$Y_{i}\triangleq\\{x\in X:I(x)=i\\}$ for every $i\in\llbracket 1,N\rrbracket$.
Thus $(Y_{i})_{i=1}^{N}$ passes all the requirements in Assumption 1.c) (see
Proposition 9), so Assumption 1.c) is weaker than Assumption 2. Now, to prove
that Assumption 2 is not weaker than Assumption 1.c), consider the case

$f:\left\\{\begin{array}[]{ccl}X\triangleq[-1,1]\setminus\\{0\\}&\to&\mathbb{R}\\\
x&\mapsto&\dfrac{1}{i}\leavevmode\nobreak\ \mbox{if}\leavevmode\nobreak\
\lvert{x}\rvert\in\left]\dfrac{1}{i+1},\dfrac{1}{i}\right]\leavevmode\nobreak\
\mbox{for some}\leavevmode\nobreak\ i\in\mathbb{N}^{*}.\end{array}\right.$

The continuity sets of $f$ are
$X_{i}\triangleq[\frac{-1}{i},\frac{-1}{i+1}{[}\cup{]}\frac{1}{i+1},\frac{1}{i}]$
for all $i\in\mathbb{N}^{*}$. Assumption 1.c) holds since $X_{i}$ is ample for
all $i\in\mathbb{N}^{*}$. Nevertheless Assumption 2 does not hold since the
continuity sets must be adapted as $Y_{i}\triangleq\mathrm{int}(X_{i})$ for
all $i\in\mathbb{N}^{*}$ to be open, but then
$\mathrm{cl}(X)=[-1,1]\neq\cup_{i=1}^{\infty}\mathrm{cl}(Y_{i})=[-1,1]\setminus\\{0\\}$.
∎

Second, let us compare Assumption 1.c) to [2, Assumption 1], reformulated
below in Assumption 3. We prove in Proposition 5 that Assumption 1.c) is
strictly weaker than Assumption 3.

######  Assumption 3 (Global reformulation of Assumption 1 in [2]).

The set $X$ admits a partition $X=\sqcup_{i=1}^{N}X_{i}$ (where
$N\in\mathbb{N}^{*}\cup\\{+\infty\\}$) such that, for all $i\in\llbracket
1,N\rrbracket$, $X_{i}$ is a continuity set of $f$ with the interior cone
property (that is, $X_{i}$ satisfies Definition 2 below and
$f_{|X_{i}}:X_{i}\to\mathbb{R}$ is continuous).

######  Definition 2 (Interior cone property and exterior cone property).

A set $\mathcal{S}\subseteq\mathbb{R}^{n}$ is said to have the interior cone
property (ICP) if

$\forall
x\in\partial\mathcal{S},\quad\exists\left\\{\begin{array}[]{ll}\lx@intercol\mathcal{U}\subseteq\mathbb{S}^{n}\leavevmode\nobreak\
\mbox{nonempty, open in the topology induced by}\leavevmode\nobreak\
\mathbb{S}^{n}\hfil\lx@intercol\\\
\mathcal{K}\triangleq\mathbb{R}_{+}^{*}\mathcal{U}\leavevmode\nobreak\
\mbox{the cone generated by}\leavevmode\nobreak\
\mathcal{U},&\mathcal{K}_{x}\triangleq\\{x\\}+\mathcal{K}\\\
\mathcal{O}\leavevmode\nobreak\ \mbox{an open neighborhood
of}\leavevmode\nobreak\ 0\leavevmode\nobreak\ \mbox{in}\leavevmode\nobreak\
\mathbb{R}^{n},&\mathcal{O}_{x}\triangleq\\{x\\}+\mathcal{O}\end{array}\right.:\qquad\left(\mathcal{K}_{x}\cap\mathcal{O}_{x}\right)\subseteq\mathcal{S}.$

Similarly, $\mathcal{S}$ is said to have the exterior cone property (ECP) if
$(\mathbb{R}^{n}\setminus\mathcal{S})$ has the ICP.

Assumption 3 differs from [2, Assumption 1] in three aspects. Let us stress
those and argue that they do not spoil the assumption. First, Assumption 3 is
a global statement, while [2, Assumption 1] states a local property but for
each $x\in X$. Second, [2, Assumption 1] requires Lipschitz-continuity of $f$
on each continuity set, while Assumption 3 calls for continuity only. Indeed
[2] requires Lipschitz-continuity only to evaluate some generalized
derivatives. We do not consider those in the current work, so we weaken the
assumption accordingly. Third, [2, Assumption 1] requires an exterior cone
property for $X\setminus X_{i}$ for all $i\in\llbracket 1,N\rrbracket$, while
Assumption 3 demands an interior cone property for $X_{i}$. Moreover the
exterior cone property required in [2, Assumption 1] is [18, Definition 4.1],
which differs from Definition 2. However, these two approaches are equivalent
(see Proposition 10). Hence, Assumption 3 and [2, Assumption 1] differ only in
the nature of the continuity of $f$ on each continuity set.

######  Proposition 5.

Assumption 1.c) is strictly weaker than Assumption 3.

###### Proof.

For all $\mathcal{S}\subseteq\mathbb{R}^{n}$, if $\mathcal{S}$ has the ICP,
then $\mathcal{S}$ is ample, but the reciprocal implication may fail (see
Proposition 11). The result follows directly. ∎

###  5.2 Tightness of Assumption 1.c)

In this section, we show that Assumption 1.c) is tight, in the sense that the
conclusion of Theorem 1 may not hold if Assumption 1.c) is not satisfied.
Relaxing it as a local property is possible, but then the convergence analysis
relies on some information accessible only a posteriori (after the
optimization process ends). Hence our framework cannot be broadened using only
information available a priori.

######  Proposition 6.

If Assumption 1.c) does not hold, then the conclusion of Theorem 1 may not
hold.

###### Proof.

Let us develop a counterexample. Let $n=2$ and $f:\mathbb{R}^{2}\to\mathbb{R}$
be defined by

$\forall x\in X\triangleq\mathbb{R}^{2},\qquad
f(x)\triangleq\left\\{\begin{array}[]{ll}\lvert{x_{1}-1}\rvert+\lvert{x_{2}}\rvert-1,&\mbox{if}\leavevmode\nobreak\
x\in
X_{1}\triangleq(\mathbb{R}_{-}\times\mathbb{R})\cup(\mathbb{R}^{*}_{+}\times\\{0\\}),\\\
\lvert{x_{1}}\rvert+\lvert{x_{2}}\rvert,&\mbox{if}\leavevmode\nobreak\ x\in
X_{2}\triangleq X\setminus X_{1}.\end{array}\right.$

Assumptions 1.a) and 1.b) hold, but Assumption 1.c) does not since $X_{1}$ is
locally thin and thus not ample. Consider an instance of Algorithm 1 such that
$(\mathcal{D}_{\tt{S}}^{k}\cup\mathcal{D}_{\tt{C}}^{k}\cup\mathcal{D}_{\tt{P}}^{k})\cap(\mathbb{R}^{*}_{+}\times\\{0\\})=\emptyset$
for all $k\in\mathbb{N}$ and satisfying Property 1 and starting from the
origin. This instance remains at the origin, since it evaluates only points in
$\mathrm{cl}(\mathrm{int}(X_{1}))\cup
X_{2}=\mathbb{R}^{2}\setminus(\mathbb{R}_{+}^{*}\times\\{0\\})$ and the origin
is the global minimizer of the restriction of $f$ to
$\mathrm{cl}(\mathrm{int}(X_{1}))\cup X_{2}$. In that situation, the origin is
a refined point lying in $X$ but is not a local minimizer of $f$, which
contradicts the conclusion of Theorem 1. ∎

Assumption 1.c) allows a broad class of discontinuous functions, as it only
rejects discontinuous functions for which at least one of the continuity sets
is locally thin. It is possible to relax it as a local assumption holding only
near some refined points and to adapt Theorem 1 accordingly. We leave this
theorem as Assertion 1, although its proof is similar to whose provided in
Section 3. Nevertheless, Assertion 1 is only usable a posteriori, since it is
impossible to determine the refined points a priori.

######  Assertion 1.

Under Assumptions 1.a) and 1.b), Algorithm 1 generates at least one refining
subsequence and, if Property 1 holds, then for all $K^{*}\subseteq\mathbb{N}$
indexing a refining subsequence, with refined point $x^{*}$,

  1. a)

if $\mathcal{X}_{i}$ is ample for all $i\in\llbracket 1,N\rrbracket$, then
$\lim_{k\in K^{*}}f(x^{k})=\inf f(\mathcal{B}_{r}(x^{*}))$;

  2. b)

if moreover $x^{*}\in\mathcal{X}_{i}$ for some $i\in\llbracket 1,N\rrbracket$,
then $\lim_{k\in K^{*}}f(x^{k})=\min f(\mathcal{B}_{r}(x^{*}))=f(x^{*})$;

where we denote by $(\mathcal{X}_{i})_{i=0}^{N}$ a partition of
$\mathcal{B}_{r}(x^{*})$, for some $N\in\mathbb{N}^{*}\cup\\{+\infty\\}$, such
that $\mathcal{X}_{0}\triangleq\mathcal{B}_{r}(x^{*})\setminus X$ and
$\mathcal{X}_{i}$ is a continuity set of $f$ for all $i\in\llbracket
1,N\rrbracket$.

##  6 General comments and main extensions for future work

Theorem 1 is stronger than most results from the literature about DSM in two
aspects. First, Theorem 1 ensures the local optimality of all refined points,
while usual results claim only some necessary local optimality conditions.
Second, Theorem 1 holds for all refining subsequence. In contrast, the
literature usually consider only refining subsequences such that the set of
associated refined directions is dense in the unit sphere, and no ways to
identify such a refining subsequence are provided.

Assumption 1.b), the assumption that $f$ is lower semicontinuous, may be
relaxed. The proof of Theorem 1 highlights that if only Assumption 1.b) fails,
the equality $\lim_{k\in K^{*}}f(x^{k})=\inf f(\mathcal{B}_{r}(x^{*}))$ holds
for all $K^{*}\subseteq\mathbb{N}$ indexing a refining subsequence, with
refined point denoted by $x^{*}$. Nevertheless, assuming the lower
semicontinuity of $f$ at $x^{*}$ recovers $\inf f(\mathcal{B}_{r}(x^{*}))=\min
f(\mathcal{B}_{r}(x^{*}))=f(x^{*})$.

The cDSM currently requires some structure on $X$ to select $x^{0}\in X$.
Following the terminology in [14], this is manageable when Problem
($\mathbf{P}$) is the extreme barrier reformulation of a constrained problem
with quantifiable constraints. Some two-phase algorithms exist [6, Algorithm
12.1], where the first phase minimizes the constraints violation function [10]
to identify a feasible point.

Only the covering step matters to establish Theorem 1, in the sense that a
variant of Algorithm 1 performing only the covering step and the update step,
and with either $\rho(\nu)\triangleq 0$ and
$\mathcal{M}(\nu)\triangleq\mathbb{R}^{n}$ for all $\nu\in\mathbb{R}_{+}^{*}$,
still generates a refining subsequence and thus satisfies Theorem 1. This
shares similarity with derivative-free line search algorithms [8, 11].
Similarly, all algorithms generating a refining subsequence may satisfy
Theorem 1, when enhanced with the covering step. Then, future work may add a
covering step into such algorithms. For example, Bayesian-based methods,
model-based methods, and most methods listed in the survey [13]. This also
includes algorithms handling constraints via advanced techniques, such as the
progressive barrier [5] which iteratively reduces the infeasibility of the
incumbent solution.

Nevertheless, the search and poll steps are important in practice. The search
step allows for global exploration, and the poll step usually contributes to
many successful iterations. In contrast, the current purpose of the covering
step is to ensure the asymptotic Property 1, so a poor instance may be
inefficient in finite time. Our scheme for the covering step discussed in
Section 4.3 ensures that the trial points are well spread in a neighborhood of
the current incumbent solution at each iteration. Yet, it is only a baseline,
so additional investigations and careful implementations may identify more
efficient schemes. A future work may verify these suppositions and quantify
the relevance of each step during the entire optimization process. We may also
study how well the cDSM performs when Assumption 1.c) holds but its stronger
variant Assumption 3 does not. Presumably, the interior cone property provided
by Assumption 3 is important for practical efficiency.

With an involved construction scheme, the covering step may help to capture
and exploit the local shape of $f$ and to evaluate some neighbors of the
current incumbent in potential areas missed by the poll step. In this aspect,
a promising covering oracle may derive from model-based techniques [6, Part
4], or from an expected improvement [19]. Indeed, they aim to identify some
points that are relevant candidates (see also [7]) or that may help to gather
the local structure of $f$.

The covering step is also compatible with the DiscoMads algorithm [1], which
designs the original revealing step for the purpose to detect discontinuities
and repel its incumbent solution from those. This discontinuities detection is
more accurate with the covering step than with the revealing step, since the
latter may fail to detect discontinuities when more than one refined point is
eventually generated. Also, when the covering step relies on Oracle 1, it
presumably has better practical guarantees to efficiently detect
discontinuities than both the the original revealing step from [1] and the
adapted revealing step from [2]. Then, for reliability reasons, it may be
safer to use the DiscoMads algorithm with a covering step instead of a
revealing step.

We conclude this paper with the next Table 1. It summarizes the conceptual
differences between the usual DSM and our cDSM, and it highlights the
aforementioned ideas to extend the cDSM.

step | method
---|---
|  DSM |  cDSM |  cDSM with involved covering step design
search | Optional. Allows the use of heuristics and globalization strategies.
poll |  Required. Converges towards a refined point satisfying necessary optimality conditions. |  Optional. But in practice, it performs well in converging towards a good refined point.
covering |  Undefined. |  Required. Safeguard to asymptotically ensure that all refined points are local solutions, low cost per iteration, but may be inefficient in practice. |  Required. Asymptotically ensures that all refined points are local solutions; also rapidly collects local information about the objective function.
Table 1: Differences between DSM and cDSM, and possible extension of cDSM with
new covering step goals.

## References

  * [1] C. Audet, A. Batailly, and S. Kojtych.  Escaping unknown discontinuous regions in blackbox optimization.  SIAM Journal on Optimization, 32(3):1843–1870, 2022.
  * [2] C. Audet, P.-Y. Bouchet, and L. Bourdin.  Counterexample and an additional revealing poll step for a result of “analysis of direct searches for discontinuous functions”.  Mathematical Programming, 2024.
  * [3] C. Audet and J.E. Dennis, Jr.  Analysis of generalized pattern searches.  SIAM Journal on Optimization, 13(3):889–903, 2003.
  * [4] C. Audet and J.E. Dennis, Jr.  Mesh Adaptive Direct Search Algorithms for Constrained Optimization.  SIAM Journal on Optimization, 17(1):188–217, 2006.
  * [5] C. Audet and J.E. Dennis, Jr.  A Progressive Barrier for Derivative-Free Nonlinear Programming.  SIAM Journal on Optimization, 20(1):445–472, 2009.
  * [6] C. Audet and W. Hare.  Derivative-Free and Blackbox Optimization.  Springer Series in Operations Research and Financial Engineering. Springer, Cham, Switzerland, 2017.
  * [7] C. Audet and W. Hare.  Model-based methods in derivative-free nonsmooth optimization.  In A.M. Bagirov, M. Gaudioso, N. Karmitsa, M.M. Mäkelä, and S. Taheri, editors, Numerical nonsmooth optimization, chapter 15. Springer, 2020.
  * [8] A.S. Berahas, L. Cao, and K. Scheinberg.  Global convergence rate analysis of a generic line search algorithm with noise.  SIAM Journal on Optimization, 31(2):1489–1518, 2021.
  * [9] A.R. Conn, K. Scheinberg, and L.N. Vicente.  Introduction to Derivative-Free Optimization.  MOS-SIAM Series on Optimization. SIAM, Philadelphia, 2009.
  * [10] R. Fletcher and S. Leyffer.  Nonlinear programming without a penalty function.  Mathematical Programming, Series A, 91:239–269, 2002.
  * [11] S. Gratton, C.W. Royer, L.N. Vicente, and Z. Zhang.  Direct search based on probabilistic descent.  SIAM Journal on Optimization, 25(3):1515–1541, 2015.
  * [12] J.H. Halton.  On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals.  Numerische Mathematik, 2(1):84–90, 1960.
  * [13] J. Larson, M. Menickelly, and S.M. Wild.  Derivative-free optimization methods.  Acta Numerica, 28:287–404, 2019.
  * [14] S. Le Digabel and S.M. Wild.  A Taxonomy of Constraints in Simulation-Based Optimization.  Technical Report G-2015-57, Les cahiers du GERAD, 2015.  To appear in Optimization and Engineering.
  * [15] N. Levine.  Semi-open sets and semi-continuity in topological spaces.  American Mathematical Monthly, 70:36–41, 1963.
  * [16] A. Meijster, J.B.T.N. Roerdink, and W.H. Hesselink.  A General Algorithm for Computing Distance Transforms in Linear Time, pages 331–340.  Springer US, Boston, MA, 2000.
  * [17] R.T. Rockafellar.  Generalized directional derivatives and subgradients of nonconvex functions.  Canadian Journal of Mathematics. Journal Canadien de Mathématiques, 32(2):257–280, 1980.
  * [18] L.N. Vicente and A.L. Custódio.  Analysis of direct searches for discontinuous functions.  Mathematical Programming, 133(1-2):299–325, 2012.
  * [19] D. Zhan and H. Xing.  Expected improvement for expensive optimization: a review.  Journal of Global Optimization, 78(3):507–544, 2020.

##  Appendix A Proofs of auxiliary results

######  Proposition 7.

Let $\mathcal{S}_{1}\subseteq\mathbb{R}^{n}$,
$\mathcal{S}_{2}\subseteq\mathbb{R}^{n}$ and
$\mathcal{S}_{3}\subseteq\mathbb{R}^{n}$. Then,

  1. a)

$\mathcal{S}_{1}$ is locally thin if and only if it is not ample;

  2. b)

if $\mathcal{S}_{1}$ is ample and $\mathcal{S}_{2}$ is open, then
$\mathcal{S}_{1}\cap\mathcal{S}_{2}$ is ample;

  3. c)

if $\mathcal{S}_{1}$ has a dense intersection with $\mathcal{S}_{2}$ and
$\mathcal{S}_{3}$ is an ample subset of $\mathcal{S}_{2}$, then
$\mathcal{S}_{1}$ has a dense intersection with $\mathcal{S}_{3}$;

  4. d)

if $\mathcal{S}_{1}$ has a dense intersection with $\mathcal{S}_{2}$ and
$\mathcal{S}_{2}$ is ample, then, for all $x\in\mathcal{S}_{2}$,
$\mathcal{S}_{1}\setminus\\{x\\}$ has a dense intersection with
$\mathcal{S}_{2}$.

###### Proof.

Let us prove the first statement. Let $\mathcal{S}_{1}\subseteq\mathbb{R}^{n}$
be locally thin and let us prove by contradiction that it is not ample. Assume
that $\mathcal{S}_{1}$ is ample. Define $\mathcal{N}\subseteq\mathbb{R}^{n}$
open such that
$\mathcal{S}_{1}\cap\mathcal{N}\neq\emptyset=\mathrm{int}(\mathcal{S}_{1})\cap\mathcal{N}$,
and take $x\in\mathcal{S}_{1}\cap\mathcal{N}$. Then
$x\in\mathrm{cl}(\mathrm{int}(\mathcal{S}_{1}))\cap\mathcal{N}$ and thus there
exists $\varepsilon>0$ such that
$\mathcal{B}_{\varepsilon}(x)\subseteq\mathcal{N}$ and
$\mathcal{B}_{\varepsilon}(x)\cap\mathrm{int}(\mathcal{S}_{1})\neq\emptyset$.
Hence $\mathrm{int}(\mathcal{S}_{1})\cap\mathcal{N}\neq\emptyset$ which raises
a contradiction. Reciprocally, let $\mathcal{S}_{1}\subseteq\mathbb{R}^{n}$ be
not ample. Then
$\mathcal{N}\triangleq\mathbb{R}^{n}\setminus\mathrm{cl}(\mathrm{int}(\mathcal{S}_{1}))$
is open, and
$\mathcal{S}_{1}\cap\mathcal{N}\neq\emptyset=\mathrm{int}(\mathcal{S}_{1})\cap\mathcal{N}$
by construction. Then $\mathcal{S}_{1}$ is locally thin.

Now let us prove the second statement. Let
$\mathcal{S}_{1}\subseteq\mathbb{R}^{n}$ be ample and
$\mathcal{S}_{2}\subseteq\mathbb{R}^{n}$ be open, and let
$x\in\mathcal{S}_{1}\cap\mathcal{S}_{2}$. We have
$x\in\mathcal{S}_{1}\subseteq\mathrm{cl}(\mathrm{int}(\mathcal{S}_{1}))$, so
there exists $(x^{k})_{k\in\mathbb{N}}$ converging to $x$ with
$x^{k}\in\mathrm{int}(\mathcal{S}_{1})$ for all $k\in\mathbb{N}$. Since
$x^{k}\to x\in\mathcal{S}_{2}$ with $\mathcal{S}_{2}$ open, it holds that
$x^{k}\in\mathcal{S}_{2}$ for all $k$ large enough. Finally, we have
$x^{k}\in\mathrm{int}(\mathcal{S}_{1})\cap\mathcal{S}_{2}=\mathrm{int}(\mathcal{S}_{1})\cap\mathrm{int}(\mathcal{S}_{2})=\mathrm{int}(\mathcal{S}_{1}\cap\mathcal{S}_{2})$
for all $k$ large enough. We deduce that
$x\in\mathrm{cl}(\mathrm{int}(\mathcal{S}_{1}\cap\mathcal{S}_{2}))$.

Next, let us prove the third statement. Let
$\mathcal{S}_{1}\subseteq\mathbb{R}^{n}$ having a dense intersection with
$\mathcal{S}_{2}\subseteq\mathbb{R}^{n}$ and let
$\mathcal{S}_{3}\subseteq\mathcal{S}_{2}$ be ample, and let
$x\in\mathcal{S}_{3}$. We have
$x\in\mathrm{cl}(\mathrm{int}(\mathcal{S}_{3}))$ so there exists
$(x^{k})_{k\in\mathbb{N}}$ converging to $x$ with
$x^{k}\in\mathrm{int}(\mathcal{S}_{3})\subseteq\mathcal{S}_{2}\subseteq\mathrm{cl}(\mathcal{S}_{1}\cap\mathcal{S}_{2})$
for all $k\in\mathbb{N}$. Then, for all $k\in\mathbb{N}$, there exists
$(x^{k}_{\ell})_{\ell\in\mathbb{N}}$ converging to $x^{k}$ with
$x^{k}_{\ell}\in\mathcal{S}_{1}\cap\mathcal{S}_{2}\cap\mathrm{int}(\mathcal{S}_{3})$
for all $\ell\in\mathbb{N}$. For all $k\in\mathbb{N}$, let
$\ell(k)\in\mathbb{N}$ be such that $\lVert{x^{k}_{\ell(k)}-x^{k}}\rVert\leq
2^{-k}$. It follows that $(x^{k}_{\ell(k)})_{k\in\mathbb{N}}$ converges to $x$
and
$x^{k}_{\ell(k)}\in\mathcal{S}_{1}\cap\mathcal{S}_{2}\cap\mathrm{int}(\mathcal{S}_{3})\subseteq\mathcal{S}_{1}\cap\mathcal{S}_{3}$
for all $k\in\mathbb{N}$. Hence, we get that
$x\in\mathrm{cl}(\mathcal{S}_{1}\cap\mathcal{S}_{3})$.

Last, let us prove the fourth statement. Let
$\mathcal{S}_{1}\subseteq\mathbb{R}^{n}$ and let
$\mathcal{S}_{2}\subseteq\mathbb{R}^{n}$ be ample. Assume that
$\mathcal{S}_{1}$ has a dense intersection with $\mathcal{S}_{2}$ and let
$x\in\mathcal{S}_{2}$. Let $y\in\mathcal{S}_{2}$. Then
$y\in\mathrm{cl}(\mathrm{int}(\mathcal{S}_{2}))$, so there exists
$(y^{k})_{k\in\mathbb{N}}$ converging to $y$ with $y\neq
y^{k}\in\mathrm{int}(\mathcal{S}_{2})\subseteq\mathcal{S}_{2}$ for all
$k\in\mathbb{N}$. Let $\varepsilon^{k}\triangleq\lVert{y^{k}-y}\rVert>0$ for
all $k\in\mathbb{N}$. Then $(\varepsilon^{k})_{k\in\mathbb{N}}$ converges to
$0$. Now, remark that by dense intersection of $\mathcal{S}_{1}$ with
$\mathcal{S}_{2}$, for all $k\in\mathbb{N}$ there exists
$z^{k}\in\mathcal{S}_{1}\cap\mathcal{S}_{2}\cap\mathcal{B}_{\varepsilon^{k}}(y^{k})$.
Finally, let $\kappa\triangleq\min\\{p\in\mathbb{N}:\max_{k\geq
p}\lVert{y^{k}-y}\rVert\leq\frac{1}{2}\lVert{y-x}\rVert\\}$ if $y\neq x$ and
$\kappa\triangleq 0$ if $y=x$. Hence, for all $k\geq\kappa$ we have
$x\notin\mathcal{B}_{\varepsilon^{k}}(y^{k})$, and thus
$z^{k}\in\mathcal{S}_{1}\cap\mathcal{S}_{2}\cap\mathcal{B}_{\varepsilon^{k}}(y^{k})\setminus\\{x\\}$.
Since $(z^{k})_{k\in\mathbb{N}}$ converges to $y$, it follows that
$y\in\mathrm{cl}((\mathcal{S}_{1}\setminus\\{x\\})\cap\mathcal{S}_{2})$ as
desired. ∎

######  Proposition 8.

The function $\mathbb{O}$ defined as Oracle 1 satisfies Definition 1.

###### Proof.

Consider $\mathbb{O}$ from Equation (1). The first requirement in Definition 1
is satisfied, since by construction
$\mathbb{O}(y,\nu,\mathcal{S})\subseteq\mathcal{M}(\nu)\cap\mathrm{cl}(\mathcal{B}_{r})$
for all $y\in\mathbb{R}^{n}$, all $\nu\in\mathbb{R}_{+}^{*}$ and all
$\mathcal{S}\subseteq\mathbb{R}^{n}$. To verify the second requirement, let
$y\in\mathbb{R}^{n}$ and let
$(y^{k},\nu^{k},\mathcal{S}^{k})\in\mathbb{R}^{n}\times\mathbb{R}_{+}^{*}\times
2^{\mathbb{R}^{n}}$ for all $k\in\mathbb{N}$ such that
$(y^{k})_{k\in\mathbb{N}}$ converges to $y$ and $(\nu^{k})_{k\in\mathbb{N}}$
converges to $0$ and
$\mathcal{S}^{k+1}\supseteq\mathcal{S}^{k}\cup(\\{y^{k}\\}+\mathbb{O}(y^{k},\nu^{k},\mathcal{S}^{k}))$
for all $k\in\mathbb{N}$. Then define $\kappa\in\mathbb{N}$ such that
$y^{k}\in\mathcal{B}_{r}(y)$ for all $k\geq\kappa$. Define also
$t^{k}\triangleq y^{k}+d^{k}\in\mathcal{S}^{k+1}$ for all $k\in\mathbb{N}$,
where $d^{k}\in\mathbb{O}(y^{k},\nu^{k},\mathcal{S}^{k})$. Thus,
$\max_{d\in\mathcal{M}(\nu^{k})\cap\mathrm{cl}(\mathcal{B}_{r})}\mathrm{dist}(y^{k}+d,\mathcal{S}^{k})=\mathrm{dist}(t^{k},\mathcal{S}^{k})\leq\min_{\ell<k}\left\lVert{t^{k}-t^{\ell}}\right\rVert$
for all $k\in\mathbb{N}^{*}$ by construction of $\mathbb{O}$. Also, by
construction $(t^{k})_{k\geq\kappa}$ lies in the compact set
$\mathrm{cl}(\mathcal{B}_{2r}(y))$, and then
$\min_{\ell<k}\left\lVert{t^{k}-t^{\ell}}\right\rVert\to 0$ as $k\to+\infty$.
Indeed, assuming that this is not true, there exists $\varepsilon>0$ and
$K\subseteq\mathbb{N}$ infinite such that
$\min_{\ell<k}\left\lVert{t^{k}-t^{\ell}}\right\rVert\geq\varepsilon$ for all
$k\in K$, but this contradicts the Bolzano-Weierstrass theorem applied to
$(t^{k})_{k\in K}$. Hence the second requirement in Definition 1 also holds. ∎

######  Proposition 9.

Under Assumption 2, consider the family $(X_{i})_{i=1}^{N}$ it provides. For
all $i\in\llbracket 1,N\rrbracket$, denote by
$\mathrm{cl}_{f}(X_{i})\triangleq\\{x\in\mathrm{cl}(X_{i}):f_{|X_{i}\cup\\{x\\}}$
is continuous$\\}$. Define $I(x)\triangleq\min\\{i\in\llbracket
1,N\rrbracket:x\in\mathrm{cl}_{f}(X_{i})\\}$ for all $x\in X$. Define
$Y_{i}\triangleq\\{x\in X:I(x)=i\\}$ for all $i\in\llbracket 1,N\rrbracket$.
Then, $X=\sqcup_{i=1}^{N}Y_{i}$ and $Y_{i}$ is an ample continuity set of $f$
for all $i\in\llbracket 1,N\rrbracket$.

###### Proof.

Consider the notation from Proposition 9. By design, the sets
$(Y_{i})_{i=1}^{N}$ are pairwise disjoint and their union covers $X$, so
$X=\sqcup_{i=1}^{N}Y_{i}$. Then we prove that for all $i\in\llbracket
1,N\rrbracket$, $Y_{i}$ is ample and $f_{|Y_{i}}$ is continuous. Let
$i\in\llbracket 1,N\rrbracket$. First, the properties of the sets
$(X_{i})_{i=1}^{N}$ and the construction of $I$ lead to

$\mathrm{int}(X_{i})\underset{\scriptsize{\overbrace{\vbox{\Let@\restore@math@cr\default@tag\halign{\subarrayfill{cr}{r}$\m@th\scriptstyle#$\subarrayfill{cl}{r}\cr\hfil$\scriptstyle
X_{i}\leavevmode\nobreak\
\mbox{open}\crcr}}}}}{=}X_{i}\underset{\scriptsize{\overbrace{\vbox{\Let@\restore@math@cr\default@tag\halign{\subarrayfill{cr}{r}$\m@th\scriptstyle#$\subarrayfill{cl}{r}\cr\hfil$\scriptstyle
I(X_{i})=\\{i\\}\crcr}}}}}{\subseteq}Y_{i}\underset{\scriptsize{\overbrace{\vbox{\Let@\restore@math@cr\default@tag\halign{\subarrayfill{cr}{r}$\m@th\scriptstyle#$\subarrayfill{cl}{r}\cr\hfil$\scriptstyle
x\notin\mathrm{cl}_{f}(X_{i})\implies I(x)\neq i\\\
x\in\mathrm{cl}_{f}(X_{i})\implies I(x)\leq
i\crcr}}}}}{\subseteq}\mathrm{cl}_{f}(X_{i})\underset{\scriptsize{\overbrace{\vbox{\Let@\restore@math@cr\default@tag\halign{\subarrayfill{cr}{r}$\m@th\scriptstyle#$\subarrayfill{cl}{r}\cr\hfil$\scriptstyle\mbox{by
construction}\crcr}}}}}{\subseteq}\mathrm{cl}(X_{i}).$

Then, $\mathrm{int}(Y_{i})\supseteq\mathrm{int}(X_{i})$ and
$Y_{i}\subseteq\mathrm{cl}(\mathrm{int}(X_{i}))$ so $Y_{i}$ is ample.
Moreover, let $x\in Y_{i}$ and let $(x^{k})_{k\in\mathbb{N}}$ converging to
$x$ with $x^{k}\in Y_{i}$ for all $k\in\mathbb{N}$. For all $k\in\mathbb{N}$,
$f_{|X_{i}\cup\\{x^{k}\\}}$ is continuous so there exists
$(x^{k}_{\ell})_{\ell\in\mathbb{N}}$ converging to $x^{k}$ such that
$x^{k}_{\ell}\in X_{i}$ for all $\ell\in\mathbb{N}$ and
$(f(x^{k}_{\ell}))_{\ell\in\mathbb{N}}$ converges to $f(x^{k})$. Let
$\ell(k)\in\mathbb{N}$ such that
$\lvert{f(x^{k}_{\ell(k)})-f(x^{k})}\rvert\leq 2^{-k}$ and
$\lVert{x^{k}_{\ell(k)}-x^{k}}\rVert\leq 2^{-k}$. Then
$(x^{k}_{\ell(k)})_{k\in\mathbb{N}}$ converges to $x$ and $x^{k}_{\ell(k)}\in
X_{i}$ for all $k\in\mathbb{N}$, so $(f(x^{k}_{\ell(k)}))_{k\in\mathbb{N}}$
converges to $f(x)$ by continuity of $f_{|X_{i}\cup\\{x\\}}$. Hence
$(f(x^{k}))_{k\in\mathbb{N}}$ converges to $f(x)$. Thus $f_{|Y_{i}}$ is
continuous at $x$, as desired. ∎

######  Proposition 10.

A set has the interior cone property from Definition 2 if and only if its
complement has the exterior cone property from [18, Definition 4.1] (quoted
below).

> [18, Definition 4.1] A set $\mathcal{S}\subseteq\mathbb{R}^{n}$ is said to
> have the exterior cone property if at all points $x\in\partial\mathcal{S}$
> there exists a cone
> $\mathcal{K}_{x}\triangleq\\{x\\}+\mathbb{R}_{+}^{*}\mathcal{U}$ (with
> $\emptyset\neq\mathcal{U}\subseteq\mathbb{S}^{n}$ open in induced topology)
> emanating from $x$, a neighborhood $\mathcal{O}_{x}$ of $x$ and an angle
> $\theta>0$ such that $\mathcal{E}_{x}\subseteq\mathcal{S}^{c}$ and
> $\Theta(e-x,a-x)\geq\theta$ for all
> $(e,a)\in\mathcal{E}_{x}\times\mathcal{S}_{x}$, where $\Theta(\cdot,\cdot)$
> computes the unsigned internal angle between two vectors and
> $\mathcal{S}^{c}\triangleq(\mathbb{R}^{n}\setminus\mathcal{S})$ and
> $\mathcal{E}_{x}\triangleq(\mathcal{K}_{x}\cap\mathcal{O}_{x})$ and
> $\mathcal{S}_{x}\triangleq(\mathcal{S}\cap\mathcal{O}_{x}\setminus\\{x\\})$.

###### Proof.

Denote by $(ICP)$ and $(ECP)$ the interior and exterior cone properties stated
in Definition 2, and by $[ECP]$ the exterior cone property stated in [2,
Definition 4.1]. A set has the $(ICP)$ if and only if its complement has the
$(ECP)$, so we only need to prove that the $(ECP)$ is equivalent to the
$[ECP]$. Denote by $[x,y]\triangleq\\{x+t(y-x):t\in[0,1]\\}$, for all
$(x,y)\in(\mathbb{R}^{n})^{2}$. Let $\mathcal{S}\subseteq\mathbb{R}^{n}$ and
$\mathcal{S}^{c}\triangleq(\mathbb{R}^{n}\setminus\mathcal{S})$.

Assume that $\mathcal{S}$ has the $[ECP]$. For all
$x\in\partial\mathcal{S}^{c}=\partial\mathcal{S}$, the $[ECP]$ of
$\mathcal{S}$ applied to $x$ provides the cone $\mathcal{K}_{x}$ and the
neighborhood $\mathcal{O}_{x}$ such that
$(\mathcal{K}_{x}\cap\mathcal{O}_{x})\subseteq\mathcal{S}^{c}$. Then
$\mathcal{S}^{c}$ has the $(ICP)$, so $\mathcal{S}$ has the $(ECP)$. Thus the
$[ECP]$ implies the $(ECP)$.

Assume that $\mathcal{S}$ has the $(ECP)$. Let $x\in\partial\mathcal{S}$. The
$(ECP)$ of $\mathcal{S}$ applied to $x$ provides
$\emptyset\neq\mathcal{U}\subsetneq\mathbb{S}^{n}$ open in $\mathbb{S}^{n}$
and $\mathcal{K}\triangleq\mathbb{R}_{+}^{*}\mathcal{U}$ and the neighborhood
$\mathcal{O}$ of $0$ such that
$(\mathcal{K}_{x}\cap\mathcal{O}_{x})\subseteq\mathcal{S}^{c}$, where
$\mathcal{K}_{x}\triangleq\\{x\\}+\mathcal{K}$ and
$\mathcal{O}_{x}\triangleq\\{x\\}+\mathcal{O}$. Let $\theta>0$ small enough so
that the open set
$\mathcal{U}^{\prime}\triangleq\\{u\in\mathcal{U}:\Theta(u,v)>\theta,\leavevmode\nobreak\
\forall v\in\mathbb{S}^{n}\setminus\mathcal{U}\\}$ is nonempty. Define
$\mathcal{K}^{\prime}\triangleq\mathbb{R}_{+}^{*}\mathcal{U}^{\prime}$ and
$\mathcal{K}^{\prime}_{x}\triangleq\\{x\\}+\mathcal{K}^{\prime}\subseteq\mathcal{K}_{x}$
and $\mathcal{E}_{x}\triangleq(\mathcal{K}^{\prime}_{x}\cap\mathcal{O}_{x})$
and
$\mathcal{S}_{x}\triangleq(\mathcal{S}\cap\mathcal{O}_{x}\setminus\\{x\\})$.
Then $\mathcal{E}_{x}\subseteq\mathcal{S}^{c}$ and $\theta$ satisfies the
requirement in the $[ECP]$. Indeed, $\mathcal{E}_{x}\subseteq\mathcal{K}_{x}$
while $\mathcal{S}_{x}\cap\mathcal{K}_{x}=\emptyset$, thus for all
$(e,a)\in\mathcal{E}_{x}\times\mathcal{S}_{x}$ there exists
$y\in\partial\mathcal{K}_{x}\cap[e,a]\neq\emptyset$. Since $e$ and $y$ and $a$
belong to the same line, we get
$\Theta(e-x,a-x)=\Theta(e-x,y-x)+\Theta(y-x,a-x)=\Theta(\frac{e-x}{\lVert{e-x}\rVert},\frac{y-x}{\lVert{y-x}\rVert})+\Theta(y-x,a-x)\geq\theta+0$.
The first term is greater than $\theta$ since
$\frac{e-x}{\lVert{e-x}\rVert}\in\mathcal{U}^{\prime}$ while
$\frac{y-x}{\lVert{y-x}\rVert}\in\mathbb{S}^{n}\setminus\mathcal{U}$, and the
second term is positive by definition of $\Theta$. Thus, $\mathcal{S}$ has the
$[ECP]$ at $x$. Hence the $(ECP)$ implies the $[ECP]$. ∎

######  Proposition 11.

If $\mathcal{S}\subseteq\mathbb{R}^{n}$ has the ICP from Definition 2, then
$\mathcal{S}$ is ample. The reciprocal is not true.

###### Proof.

Let $\mathcal{S}\subseteq\mathbb{R}^{n}$ having the ICP. Let
$x\in\mathcal{S}$. The ICP provides $\mathcal{K}_{x}$ and $\mathcal{O}_{x}$
satisfying $(\mathcal{K}_{x}\cap\mathcal{O}_{x})\subseteq\mathcal{S}$ and
$x\in\mathrm{cl}(\mathcal{K}_{x}\cap\mathcal{O}_{x})$. Moreover, $\mathcal{K}$
is open as the image of $\mathbb{R}_{+}^{*}\times\mathcal{U}$ (an open subset
of $\mathbb{R}_{+}^{*}\times\mathbb{S}^{n}$) by the homeomorphism
$(\lambda,u)\in\mathbb{R}_{+}^{*}\times\mathbb{S}^{n}\mapsto\lambda
u\in\mathbb{R}^{n}\setminus\\{0\\}$. Thus,
$\mathcal{K}_{x}\cap\mathcal{O}_{x}$ is also open, so
$(\mathcal{K}_{x}\cap\mathcal{O}_{x})\subseteq\mathrm{int}(\mathcal{S})$.
Hence, $x\in\mathrm{cl}(\mathrm{int}(\mathcal{S}))$, which proves the direct
implication. To observe that the reciprocal implication fails, consider
$n\triangleq 2$ and
$\mathcal{S}\triangleq\mathrm{epi}(\sqrt{\lvert{\cdot}\rvert})$. Then
$\mathcal{S}$ is ample but the ICP fails at
$x=(0,0)\in\mathrm{cl}(\mathcal{S})$. ∎