# The Minimizer of the Sum of Two Strongly Convex Functions

Kananart Kuwaranancharoen
School of Electrical and Computer Engineering
Purdue University
West Lafayette, IN 47907
<EMAIL_ADDRESS>
& Shreyas Sundaram
School of Electrical and Computer Engineering
Purdue University
West Lafayette, IN 47907
<EMAIL_ADDRESS>

###### Abstract

The problem of finding the minimizer of a sum of convex functions is central
to the field of optimization. In cases where the functions themselves are not
fully known (other than their individual minimizers and convexity parameters),
it is of interest to understand the region containing the potential minimizers
of the sum based only on those known quantities. Characterizing this region in
the case of multivariate strongly convex functions is far more complicated
than the univariate case. In this paper, we provide both outer and inner
approximations for the region containing the minimizer of the sum of two
strongly convex functions, subject to a constraint on the norm of the gradient
at the minimizer of the sum. In particular, we explicitly characterize the
boundary and interior of both outer and inner approximations. Interestingly,
the boundaries as well as the interiors turn out to be identical and we show
that the boundary of the region containing the potential minimizers is also
identical to that of the outer and inner approximations.

_Keywords_ Convex Optimization $\cdot$ Distributed Optimization $\cdot$
Minimizer Analysis $\cdot$ Quadratic Functions $\cdot$ Strongly Convex
Functions

##  1 Introduction

The problem of optimizing a sum of functions arises in a variety of
applications, including machine learning (Shalev-Shwartz, 2011; Boyd et al.,
2011; Sayed, 2014), control of large-scale systems (Molzahn et al., 2017; Li
et al., 2011), and cooperative robotic systems (Zavlanos et al., 2012; Tron et
al., 2016). In these settings, each node in a network is assumed to possess a
convex function. There are many proposed algorithms to find the minimizer of
the sum of these functions (Nedić et al., 2010; Johansson et al., 2009; Zhu
and Martínez, 2012; Gharesifard and Cortés, 2014; Nedic and Olshevsky, 2015),
under some common assumptions such as the functions being strongly convex and
the gradients being bounded.

In some cases, the exact functions themselves may not be fully known, and only
certain characteristics (such as minimizer and convexity parameters) may be
known. In this case, it is of interest to understand the potential set of
minimizers of the sum of functions, despite this limited knowledge of the
individual functions. For example, in resilient distributed optimization
settings (Sundaram and Gharesifard, 2018; Kuwaranancharoen et al., 2020), the
network contains malicious nodes that do not follow the distributed
optimization algorithm and one cannot guarantee that all nodes calculate the
true minimizer. Instead, one must settle for algorithms that allow the non-
malicious nodes to converge to a certain region (Sundaram and Gharesifard,
2016; Su and Vaidya, 2015). In such situations, knowing the region where the
minimizer can lie would allow us to evaluate the efficacy of such resilient
distributed optimization algorithms. Another example involves the scenario
where two similar machine learning models trained on similar data are combined
to achieve a common goal. However, due to privacy concerns (Shokri and
Shmatikov, 2015), the datasets used to train these models may not available
directly, which means we know the minimizer of each function for inference but
not the function itself. In this case, it is of interest to obtain a potential
new minimizer, i.e., a combined machine learning model, which could offer
enhanced performance for the original inference task. More specifically,
consider a federated learning setup (Konevcnỳ et al., 2016; Kairouz et al.,
2021) with two clients, each with access to local data. Each client, denoted
by $i$, obtains a local optimal parameter $\boldsymbol{x}_{i}^{*}$ that
minimizes its own loss function $f_{i}$. Now, if each client only reports
$\boldsymbol{x}_{i}^{*}$ to a server, can the server determine the set of
potential optimal parameters for the combined loss function $f_{1}+f_{2}$,
based solely on the information it has (i.e., $\boldsymbol{x}_{1}^{*}$,
$\boldsymbol{x}_{2}^{*}$, and knowledge of the convexity properties of $f_{1}$
and $f_{2}$)?

When the local functions $f_{i}$ at each node $v_{i}$ are univariate (i.e.,
$f_{i}:\mathbb{R}\rightarrow\mathbb{R}$), and strongly convex, it is easy to
argue that the minimizer of the sum must lie in the interval bracketed by the
smallest and largest minimizers of the functions (Sundaram and Gharesifard,
2018). This is because the gradients of all the functions will have the same
sign outside that region, and thus cannot sum to zero. However, a similar
characterization of the region containing the minimizer of multivariate
functions is lacking in the literature, and is significantly more challenging
to obtain. For example, the conjecture that the minimizer of a sum of convex
functions is in the convex hull of their local minimizers can be easily
disproved via simple examples; consider $f_{1}(x,y)=x^{2}-xy+\frac{1}{2}y^{2}$
and $f_{2}(x,y)=x^{2}+xy+\frac{1}{2}y^{2}-4x-2y$ with minimizers $(0,0)$ and
$(2,0)$ respectively, whose sum has minimizer $(1,1)$. In our recent work
(Kuwaranancharoen and Sundaram, 2018, 2020), we studied this problem and
provided an outer approximation on the region containing the minimizer of two
strongly convex functions in a specific case; this region is determined by the
minimizers of the individual functions, their strong convexity parameters, and
the specified bound on the norms of the gradients of the functions at the
location of the minimizer.

In this paper, our goal is to characterize an outer approximation (i.e., a
region containing all valid minimizers) as well as an inner approximation
(i.e., a region where every point is a valid minimizer) for the sum of two
unknown strongly convex functions. More specifically, we provide an outer
approximation that is more general than the one given in (Kuwaranancharoen and
Sundaram, 2018). As we will see, the inner approximation essentially almost
coincides with the outer approximation. More precisely, the boundary of both
outer and inner approximations are the same under the assumption that the
gradients of the two original functions are bounded by a finite number at the
potential minimizer of the sum. Thus, our analysis in this paper complements
and completes the analysis in (Kuwaranancharoen and Sundaram, 2018) by fully
characterizing the region containing the minimizer of the sum of two strongly
convex functions. While the analysis is complicated even for this scenario
involving two functions, our analysis provides insights that could be
leveraged in future work to tackle the sum of multiple functions.

The paper is organized as follows. The notations used throughout the paper and
preliminaries are provided in Section 2. The problem formulation is in Section
3. Our main results regarding the outer approximation are in Section 4, our
analysis of the inner approximation and potential solution region is in
Section 5, and the conclusions follow in Section 7.

##  2 Preliminaries

###  2.1 Sets

Let $\mathbb{R}$ denotes the set of real numbers. We denote by
$\mathbb{R}^{n}$ the $n$-dimensional Euclidean space. For a subset
$\mathcal{E}$ of a topological space, we denote the complement, closure and
interior of a set $\mathcal{E}$ by $\mathcal{E}^{c}$, $\overline{\mathcal{E}}$
and ${\mathcal{E}}^{\circ}$, respectively. The boundary of $\mathcal{E}$ is
defined as
$\partial\mathcal{E}=\overline{\mathcal{E}}\setminus{\mathcal{E}}^{\circ}$. We
also use $\textbf{dom}(f)$ to denote the domain of function $f$. In addition,
we use $\sqcup$ to denote the disjoint union operation. We will use this
simple lemma later in the paper.

######  Lemma 2.1.

Let $\mathcal{G}$ and $\mathcal{H}$ be subsets of a topological space $X$ such
that $\mathcal{G}\subseteq\mathcal{H}$. Let $\mathfrak{P}$ be a partition of
$\mathcal{H}$. Then,

$\mathcal{G}^{\circ}=\bigsqcup_{\mathcal{Z}\in\mathfrak{P}}\big{(}(\mathcal{G}\cap\mathcal{Z})\setminus(\partial\mathcal{G}\cap\mathcal{Z})\big{)}.$

###### Proof.

For $\mathcal{Z}\in\mathfrak{P}$, since
$\mathcal{G}\cap\mathcal{Z}\cap\mathcal{Z}^{c}=\emptyset$, we have

$\mathcal{G}^{\circ}\cap\mathcal{Z}=(\mathcal{G}\cap(\partial\mathcal{G})^{c}\cap\mathcal{Z})\cup(\mathcal{G}\cap\mathcal{Z}\cap\mathcal{Z}^{c})=(\mathcal{G}\cap\mathcal{Z})\cap(\partial\mathcal{G}\cap\mathcal{Z})^{c}=(\mathcal{G}\cap\mathcal{Z})\setminus(\partial\mathcal{G}\cap\mathcal{Z}).$

Using the above equation, we can write

$\displaystyle\mathcal{G}^{\circ}=\bigsqcup_{\mathcal{Z}\in\mathfrak{P}}(\mathcal{G}^{\circ}\cap\mathcal{Z})=\bigsqcup_{\mathcal{Z}\in\mathfrak{P}}\big{(}(\mathcal{G}\cap\mathcal{Z})\setminus(\partial\mathcal{G}\cap\mathcal{Z})\big{)}.$

∎

###  2.2 Linear Algebra

For simplicity, we often use $(x_{1},\ldots,x_{n})$ to represent the column
vector
$\boldsymbol{x}=\begin{bmatrix}x_{1}&x_{2}&\cdots&x_{n}\end{bmatrix}^{\intercal}$.
We use $\boldsymbol{0}$ to denote the all-zero vector with appropriate
dimension and $\boldsymbol{e}_{i}$ to denote the $i$-th basis vector (the
vector of all zeros except for a one in the $i$-th position). We denote by
$\langle\boldsymbol{u},\boldsymbol{v}\rangle$ the Euclidean inner product of
vectors $\boldsymbol{u}$ and $\boldsymbol{v}$, i.e.,
$\langle\boldsymbol{u},\boldsymbol{v}\rangle\triangleq\boldsymbol{u}^{\intercal}\boldsymbol{v}$,
by $\|\boldsymbol{u}\|$ the Euclidean norm of $\boldsymbol{u}$, i.e.,
$\|\boldsymbol{u}\|\triangleq\sqrt{\langle\boldsymbol{u},\boldsymbol{u}\rangle}=(\sum_{i}u_{i}^{2})^{1/2}$.
We define the functions
$\angle:(\mathbb{R}^{n}\setminus\\{\mathbf{0}\\})\times(\mathbb{R}^{n}\setminus\\{\mathbf{0}\\})\to[0,\pi]$
and
$\measuredangle:(\mathbb{R}^{2}\setminus\\{\mathbf{0}\\})\times(\mathbb{R}^{2}\setminus\\{\mathbf{0}\\})\to\big{[}-\frac{\pi}{2},\frac{\pi}{2}\big{]}$
as

$\angle(\boldsymbol{u},\boldsymbol{v})\triangleq\arccos\bigg{(}\frac{\langle\boldsymbol{u},\boldsymbol{v}\rangle}{\|\boldsymbol{u}\|\|\boldsymbol{v}\|}\bigg{)}\quad\text{and}\quad\measuredangle(\boldsymbol{u},\boldsymbol{v})\triangleq\arcsin\bigg{(}\frac{u_{2}v_{1}-u_{1}v_{2}}{\|\boldsymbol{u}\|\|\boldsymbol{v}\|}\bigg{)},$
(1)

respectively. Note that
$\angle(\boldsymbol{u},\boldsymbol{v})=\angle(\boldsymbol{v},\boldsymbol{u})$
but
$\measuredangle(\boldsymbol{u},\boldsymbol{v})=-\measuredangle(\boldsymbol{v},\boldsymbol{u})$.
We use

$\mathcal{B}(\boldsymbol{x}_{0},r_{0})\triangleq\\{\boldsymbol{x}\in\mathbb{R}^{n}:\|\boldsymbol{x}-\boldsymbol{x}_{0}\|<r_{0}\\}$
(2)

and $\overline{\mathcal{B}}(\boldsymbol{x}_{0},r_{0})$ to denote the open and
closed balls, respectively, in $\mathbb{R}^{n}$ centered at
$\boldsymbol{x}_{0}\in\mathbb{R}^{n}$ and with radius
$r_{0}\in\mathbb{R}_{>0}$. We use $\boldsymbol{I}$ to denote the identity
matrix of appropriate dimension. For square matrix
$\boldsymbol{A}\in\mathbb{R}^{n\times n}$, we use $\lambda(\boldsymbol{A})$,
$\lambda_{\text{min}}(\boldsymbol{A})$ and $\text{Tr}(\boldsymbol{A})$ to
denote an eigenvalue, the minimum eigenvalue and the trace of matrix
$\boldsymbol{A}$, respectively. For $\boldsymbol{A}\in\mathbb{R}^{m\times n}$,
we use $\mathcal{R}(\boldsymbol{A})$ and $\mathcal{N}(\boldsymbol{A})$ to
denote the column space and null space of matrix $\boldsymbol{A}$,
respectively.

###  2.3 Convex Sets and Functions

A set $\mathcal{C}\subseteq\mathbb{R}^{n}$ is said to be convex if, for all
$\boldsymbol{x}$ and $\boldsymbol{y}$ in $\mathcal{C}$ and all $t$ in the
interval $(0,1)$, the point $(1-t)\boldsymbol{x}+t\boldsymbol{y}$ also belongs
to $\mathcal{C}$. A differentiable function $f$ is called strongly convex with
parameter $\sigma\in\mathbb{R}_{>0}$ (or $\sigma$-strongly convex) if

$\langle\nabla f(\boldsymbol{x})-\nabla
f(\boldsymbol{y}),\;\boldsymbol{x}-\boldsymbol{y}\rangle\geq\sigma\|\boldsymbol{x}-\boldsymbol{y}\|^{2}$
(3)

holds for all points $\boldsymbol{x},\boldsymbol{y}$ in its domain. We use
$\mathcal{S}(\boldsymbol{x}^{*},\sigma)$ to denote the set of all
differentiable and $\sigma$-strongly convex functions that have their
minimizer at $\boldsymbol{x}^{*}\in\mathbb{R}^{n}$. Define $\mathsf{S}^{n}$ to
be the set of symmetric matrices in $\mathbb{R}^{n\times n}$, and
$\mathsf{Q}^{n}$ to be the set of all quadratic functions that map
$\mathbb{R}^{n}$ to $\mathbb{R}$. A quadratic function $f\in\mathsf{Q}^{n}$
parameterized by $\boldsymbol{Q}\in\mathsf{S}^{n}$,
$\boldsymbol{b}\in\mathbb{R}^{n}$, and $c\in\mathbb{R}$ is given by

$f(x;\boldsymbol{Q},\boldsymbol{b},c)=\frac{1}{2}\boldsymbol{x}^{\intercal}\boldsymbol{Q}\boldsymbol{x}+\boldsymbol{b}^{\intercal}\boldsymbol{x}+c.$

For $\boldsymbol{x}^{*}\in\mathbb{R}^{n}$ and $\sigma\in\mathbb{R}_{>0}$,
define

$\mathcal{Q}^{(n)}(\boldsymbol{x}^{*},\sigma)\triangleq\big{\\{}f(x;\boldsymbol{Q},\boldsymbol{b},c)\in\mathsf{Q}^{n}:\lambda_{\text{min}}(\boldsymbol{Q})=\sigma,\;\;\boldsymbol{Q}\boldsymbol{x}^{*}=-\boldsymbol{b}\big{\\}}.$
(4)

We will omit the superscript $(n)$ of $\mathcal{Q}^{(n)}$ when it is clear
from contexts. Note that every function in
$\mathcal{Q}(\boldsymbol{x}^{*},\sigma)$ is $\sigma$-strongly convex quadratic
and has the minimizer at $\boldsymbol{x}^{*}$, and

$\mathcal{Q}(\boldsymbol{x}^{*},\sigma)\subset\bigcup_{\tilde{\sigma}\geq\sigma}\mathcal{Q}(\boldsymbol{x}^{*},\tilde{\sigma})\subset\mathcal{S}(\boldsymbol{x}^{*},\sigma).$
(5)

The following lemma shows that the strong convexity of functions is invariant
under some particular affine transformations. This property will help us to
simplify the analysis throughout the paper.

######  Lemma 2.2.

Let $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ be an orthogonal matrix and
$\boldsymbol{b}\in\mathbb{R}^{n}$. Suppose $f:\mathbb{R}^{n}\to\mathbb{R}$ is
a differentiable function and define
$h(\boldsymbol{x})=f(\boldsymbol{Ax}+\boldsymbol{b})$. Then, $f$ is
$\sigma$-strongly convex if and only if $h$ is $\sigma$-strongly convex.

###### Proof.

By the definition of strongly convex functions in (3), we have that

$\langle\nabla f(\boldsymbol{x})-\nabla
f(\boldsymbol{y}),\;\boldsymbol{x}-\boldsymbol{y}\rangle\geq\sigma\|\boldsymbol{x}-\boldsymbol{y}\|^{2}\quad\text{for
all}\quad\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{n}.$

Since $\boldsymbol{A}$ is invertible, we can replace $\boldsymbol{x}$ and
$\boldsymbol{y}$ by $\boldsymbol{Ax}+\boldsymbol{b}$ and
$\boldsymbol{Ay}+\boldsymbol{b}$, respectively, and the above inequality is
equivalent to

$\big{\langle}\nabla f(\boldsymbol{Ax}+\boldsymbol{b})-\nabla
f(\boldsymbol{Ay}+\boldsymbol{b}),\;\boldsymbol{A}(\boldsymbol{x}-\boldsymbol{y})\big{\rangle}\geq\sigma\|\boldsymbol{A}(\boldsymbol{x}-\boldsymbol{y})\|^{2}\;\;\text{for
all}\;\;\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{n}.$ (6)

Since $\nabla h(\boldsymbol{x})=\boldsymbol{A}^{\intercal}\nabla
f(\boldsymbol{Ax}+\boldsymbol{b})$, we can rewrite the LHS of (6) as
$\big{\langle}\boldsymbol{A}^{\intercal}\big{(}\nabla
f(\boldsymbol{Ax}+\boldsymbol{b})-\nabla
f(\boldsymbol{Ay}+\boldsymbol{b})\big{)},\;\boldsymbol{x}-\boldsymbol{y}\big{\rangle}=\langle\nabla
h(\boldsymbol{x})-\nabla
h(\boldsymbol{y}),\;\boldsymbol{x}-\boldsymbol{y}\rangle$. On the other hand,
since $\boldsymbol{A}$ is an orthogonal matrix, the RHS of (6) becomes
$\sigma\|\boldsymbol{x}-\boldsymbol{y}\|^{2}$. ∎

##  3 Problem Formulation

Consider two (unknown) functions $f_{1}$ and $f_{2}$. In order to investigate
the minimizer of the sum of two unknown functions $f_{1}+f_{2}$, we will
impose the following assumptions on the structure of both functions.

  1. 1.

Given $\sigma_{1},\sigma_{2}\in\mathbb{R}_{>0}$, the functions
$f_{1}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and
$f_{2}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ are differentiable and strongly
convex with parameters $\sigma_{1}$ and $\sigma_{2}$, respectively.

  2. 2.

Given $\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\in\mathbb{R}^{n}$, the
minimizers of $f_{1}$ and $f_{2}$ are at $\boldsymbol{x}_{1}^{*}$ and
$\boldsymbol{x}_{2}^{*}$, respectively.

  3. 3.

Suppose $\boldsymbol{x}^{*}\in\mathbb{R}^{n}$ is the minimizer of
$f_{1}+f_{2}$. There is a finite (given) number $L\in\mathbb{R}_{>0}$ such
that the norm of gradient of $f_{1}$ and $f_{2}$ evaluated at
$\boldsymbol{x}^{*}$ is less than $L$.

Assumption 1 and 2 will be captured using the notations introduced earlier:
$f_{1}\in\mathcal{S}(\boldsymbol{x}_{1}^{*},\sigma_{1})$ and
$f_{2}\in\mathcal{S}(\boldsymbol{x}_{2}^{*},\sigma_{2})$. For Assumption 3,
since $\boldsymbol{x}^{*}$ is the minimizer of $f_{1}+f_{2}$, we have that
$\nabla f_{1}(\boldsymbol{x}^{*})=-\nabla f_{2}(\boldsymbol{x}^{*})$. In
addition, we can rewrite the bounded gradient at $\boldsymbol{x}^{*}$
condition as $\|\nabla f_{1}(\boldsymbol{x}^{*})\|=$ $\|\nabla
f_{2}(\boldsymbol{x}^{*})\|\leq L$. Essentially, our goal is to estimate the
region $\mathcal{M}$ containing all possible values $\boldsymbol{x}^{*}$
satisfying the above conditions. More specifically, given
$\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\in\mathbb{R}^{n}$,
$\sigma_{1},\sigma_{2}\in\mathbb{R}_{>0}$, and $L\in\mathbb{R}_{>0}$, we wish
to estimate the potential solution region

$\mathcal{M}(\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*},\sigma_{1},\sigma_{2},L)\triangleq\big{\\{}\boldsymbol{x}\in\mathbb{R}^{n}:\exists
f_{1}\in\mathcal{S}(\boldsymbol{x}_{1}^{*},\sigma_{1}),\quad\exists
f_{2}\in\mathcal{S}(\boldsymbol{x}_{2}^{*},\sigma_{2}),\\\ \nabla
f_{1}(\boldsymbol{x})=-\nabla f_{2}(\boldsymbol{x}),\quad\|\nabla
f_{1}(\boldsymbol{x})\|=\|\nabla f_{2}(\boldsymbol{x})\|\leq L\big{\\}}.$ (7)

For simplicity of notation, we will omit the argument of the set
$\mathcal{M}(\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*},\sigma_{1},\sigma_{2},L)$
and write it as $\mathcal{M}$.

###  3.1 Discussion of Assumptions

Functions that satisfy both differentiable and strongly convex conditions
(Assumption 1) are common in many applications. In machine learning
applications, for example, linear regression and logistic regression models
with $L_{2}$-regularization are commonly used when only a small amount of
training data is available (Hastie et al., 2009).

Assumption 2 can be generalized by assuming that for $i\in\\{1,2\\}$, the
minimizer $\boldsymbol{x}_{i}^{*}$ of the function $f_{i}$ is not available
but instead $\boldsymbol{x}_{i}^{*}$ is located in a known compact set
$\mathcal{A}_{i}\subset\mathbb{R}^{n}$ as in (Kuwaranancharoen and Sundaram,
2020). However, the analysis will be more involved, so we defer these
assumptions to our future works.

Assumption 3 is a technical assumption. Given
$\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\in\mathbb{R}^{n}$ such that
$\boldsymbol{x}_{1}^{*}\neq\boldsymbol{x}_{2}^{*}$, let

$\mathcal{L}=\big{\\{}\boldsymbol{x}\in\mathbb{R}^{n}:\text{there
exists}\;k\in\mathbb{R}\setminus(-1,1)\;\;\text{such
that}\;\;\boldsymbol{x}-\boldsymbol{x}_{1}^{*}=k(\boldsymbol{x}_{2}^{*}-\boldsymbol{x}_{1}^{*})\big{\\}}.$

Without Assumption 3, i.e., the norm of the gradient of each function at the
minimizer of the sum can be arbitrarily large, one can use the result from
Proposition 5.1 to show that $\mathcal{M}=\mathbb{R}^{n}\setminus\mathcal{L}$.
We can see that for $n\in\mathbb{N}\setminus\\{1\\}$, the set $\mathcal{L}$
has measure zero and hence, $\mathcal{M}$ covers almost the entire space. In
other words, almost all points can be minimizers. One can think of imposing
the bound on the gradients as one of the ways to implicitly limit the
functions that we can choose from
$\mathcal{S}(\boldsymbol{x}_{1}^{*},\sigma_{1})$ and
$\mathcal{S}(\boldsymbol{x}_{2}^{*},\sigma_{2})$. However, there might be
other ways to restrict the class of functions that we can select, for example,
considering the functions that have Lipschitz continuous gradients in addition
to Assumptions 1 and 2. For now, we restrict ourselves to the simpler
assumption, Assumption 3, and leave such alternative assumptions for future
work.

###  3.2 A Preview of the Solution

Recall the definition of the potential solution region $\mathcal{M}$ from (7).
One way to characterize the set $\mathcal{M}$ is to provide an explicit
formula for the boundary $\partial\mathcal{M}$ in terms of
$\boldsymbol{x}_{1}^{*}$, $\boldsymbol{x}_{2}^{*}$, $\sigma_{1}$, $\sigma_{2}$
and $L$. In Fig. 1, we provide a preview of the boundary $\partial\mathcal{M}$
in $\mathbb{R}^{2}$ given fixed parameters $\sigma_{1}=1.5$, $\sigma_{2}=1$,
and $L=10$, and a variable parameter $r\in\mathbb{R}_{>0}$. Suppose
$\boldsymbol{x}_{1}^{*}=(-r,0)$ and $\boldsymbol{x}_{2}^{*}=(r,0)$. We
illustrate $\partial\mathcal{M}$ for the case where $r=2,4$, and $6$ in Fig.
1a, Fig. 1b and Fig. 1c, respectively. The different colors in the figures
indicate different equations that combine together to yield the boundary (as
we will explicitly characterize in the rest of the paper).

(a) For $r=2$, $\partial\mathcal{M}$ consists of $1$ curve (blue curve) and
$\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.

(b) For $r=4$, $\partial\mathcal{M}$ consists of $2$ curves (blue and cyan
curves) and $\\{\boldsymbol{x}_{1}^{*}\\}$.

(c) For $r=6$, $\partial\mathcal{M}$ consists of $3$ curves (blue, cyan and
magenta curves).

Figure 1: The boundary $\partial\mathcal{M}$ in $\mathbb{R}^{2}$ is plotted
given minimizers $\boldsymbol{x}_{1}^{*}=(-r,0)$ and
$\boldsymbol{x}_{2}^{*}=(r,0)$ and fixed parameters $\sigma_{1}=1.5$,
$\sigma_{2}=1$, and $L=10$. Different colors denote different equations that
combine together to yield the boundary $\partial\mathcal{M}$.

###  3.3 Solution Approach

Since the analysis of the case $\boldsymbol{x}_{1}^{*}=\boldsymbol{x}_{2}^{*}$
is trivial (i.e., the potential solution region is
$\mathcal{M}=\\{\boldsymbol{x}_{1}^{*}\\}$), without loss of generality, we
assume that $\boldsymbol{x}_{1}^{*}=(-r,0,\ldots,0)\in\mathbb{R}^{n}$ and
$\boldsymbol{x}_{2}^{*}=(r,0,\ldots,0)\in\mathbb{R}^{n}$ with
$r=\frac{1}{2}\|\boldsymbol{x}_{2}^{*}-\boldsymbol{x}_{1}^{*}\|>0$.

To show this, given general
$\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\in\mathbb{R}^{n}$ with
$\boldsymbol{x}_{1}^{*}\neq\boldsymbol{x}_{2}^{*}$, let the set of new bases
$\mathcal{J}=\\{\boldsymbol{e}^{\prime}_{1},\boldsymbol{e}^{\prime}_{2},\ldots,\boldsymbol{e}^{\prime}_{n}\\}$
be such that
$\boldsymbol{e}^{\prime}_{1}=\frac{\boldsymbol{x}_{2}^{*}-\boldsymbol{x}_{1}^{*}}{\|\boldsymbol{x}_{2}^{*}-\boldsymbol{x}_{1}^{*}\|}$
and
$\\{\boldsymbol{e}^{\prime}_{2},\boldsymbol{e}^{\prime}_{3},\ldots,\boldsymbol{e}^{\prime}_{n}\\}$
is obtained by Gram-Schmidt orthogonalization. Let

$\boldsymbol{e}=\begin{bmatrix}\boldsymbol{e}_{1}^{\prime}&\boldsymbol{e}_{2}^{\prime}&\cdots&\boldsymbol{e}_{n}^{\prime}\end{bmatrix}\quad\text{and}\quad\boldsymbol{b}=\frac{1}{2}(\boldsymbol{x}_{1}^{*}+\boldsymbol{x}_{2}^{*}).$

We let
$\boldsymbol{x}_{\mathcal{J}}=\boldsymbol{e}^{\intercal}(\boldsymbol{x}-\boldsymbol{b})$
be the coordinate transformation. One can verify that if
$\boldsymbol{x}=\boldsymbol{x}_{1}^{*}$ then
$\boldsymbol{x}_{\mathcal{J}}=\big{(}-\frac{1}{2}\|\boldsymbol{x}_{2}^{*}-\boldsymbol{x}_{1}^{*}\|,\;\mathbf{0}\big{)}=(-r,\mathbf{0})$
and if $\boldsymbol{x}=\boldsymbol{x}_{2}^{*}$ then
$\boldsymbol{x}_{\mathcal{J}}=\big{(}\frac{1}{2}\|\boldsymbol{x}_{2}^{*}-\boldsymbol{x}_{1}^{*}\|,\;\mathbf{0}\big{)}=(r,\mathbf{0})$.
For $i\in\\{1,2\\}$, let $\tilde{f}_{i}:\mathbb{R}^{n}\to\mathbb{R}$ be the
function such that
$\tilde{f}_{i}(\boldsymbol{x}_{\mathcal{J}})=f_{i}(\boldsymbol{x})$ for all
$\boldsymbol{x}\in\mathbb{R}^{n}$, i.e., $\tilde{f}_{i}$’s value at the
coordinate of point $\boldsymbol{x}$ on the new bases $\mathcal{J}$ is the
same as $f_{i}$ at point $\boldsymbol{x}$. We can write
$\tilde{f}_{i}(\boldsymbol{x})=f_{i}(\boldsymbol{Ex}+\boldsymbol{b})$ for
$i\in\\{1,2\\}$. Applying Lemma 2.2, we have that $\tilde{f}_{i}$ is
$\sigma_{i}$-strongly convex for $i\in\\{1,2\\}$. Once we attain the potential
solution region $\mathcal{M}$ in terms of $\boldsymbol{x}_{\mathcal{J}}$, we
can always use the transformation to obtain the region in terms of
$\boldsymbol{x}$, i.e., the original coordinate system.

For convenience, we introduce the shorthand notation of sets that will be
encountered throughout the paper. Recall the definition of $\mathcal{B}$ from
(2). For $i\in\\{1,2\\}$, define

$\mathcal{B}_{i}\triangleq\mathcal{B}\Big{(}\boldsymbol{x}_{i}^{*},\frac{L}{\sigma_{i}}\Big{)}.$
(8)

Now, we introduce the functions that will be used to define the outer and
inner approximations of $\mathcal{M}$. For $i\in\\{1,2\\}$, define the
functions
$\tilde{\phi}_{i}:\;\overline{\mathcal{B}}_{i}\to\big{[}0,\frac{\pi}{2}\big{]}$
to be such that

$\tilde{\phi}_{i}(\boldsymbol{x})\triangleq\arccos{\Big{(}\frac{\sigma_{i}}{L}\|\boldsymbol{x}-\boldsymbol{x}_{i}^{*}\|\Big{)}},$
(9)

and the functions
$\alpha_{i}:\;\mathbb{R}^{n}\setminus\\{\boldsymbol{x}_{i}^{*}\\}\to[0,\pi]$
to be such that

$\alpha_{i}(\boldsymbol{x})\triangleq\angle(\boldsymbol{x}-\boldsymbol{x}_{i}^{*},\;\boldsymbol{x}_{2}^{*}-\boldsymbol{x}_{1}^{*}),$
(10)

i.e., the angle between vectors $\boldsymbol{x}-\boldsymbol{x}_{i}^{*}$ and
$\boldsymbol{x}_{2}^{*}-\boldsymbol{x}_{1}^{*}$. Note that
$\alpha_{2}(\boldsymbol{x})\geq\alpha_{1}(\boldsymbol{x})$ for all
$\boldsymbol{x}\in\mathbb{R}^{n}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$
due to the assumption that $\boldsymbol{x}_{1}^{*}=(-r,\mathbf{0})$ and
$\boldsymbol{x}_{2}^{*}=(r,\mathbf{0})$. We define
$\psi:\mathbb{R}^{n}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}\to[0,\pi]$
to be the function such that

$\psi(\boldsymbol{x})\triangleq\pi-\big{(}\alpha_{2}(\boldsymbol{x})-\alpha_{1}(\boldsymbol{x})\big{)}.$
(11)

The interpretation of the angles $\tilde{\phi}_{i}(\boldsymbol{x})$ and
$\psi(\boldsymbol{x})$ will be clarified later (in Fig. 2). In addition, given
$\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\in\mathbb{R}^{n}$,
$\sigma_{1},\sigma_{2}\in\mathbb{R}_{>0}$, and $L\in\mathbb{R}_{>0}$, we
define

$\mathcal{X}\triangleq\begin{cases}\Big{\\{}\boldsymbol{x}\in\mathbb{R}^{n}:\|\boldsymbol{x}-\boldsymbol{x}_{i}^{*}\|=\frac{L}{\sigma_{i}}\;\;\text{for
all}\;i\in\\{1,2\\}\Big{\\}}\;&\text{if}\;\|\boldsymbol{x}_{2}^{*}-\boldsymbol{x}_{1}^{*}\|=L\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)},\\\
\emptyset&\text{otherwise}.\end{cases}$ (12)

Due to the assumption that $\boldsymbol{x}_{1}^{*}=(-r,\mathbf{0})$ and
$\boldsymbol{x}_{2}^{*}=(r,\mathbf{0})$, for
$\|\boldsymbol{x}_{2}^{*}-\boldsymbol{x}_{1}^{*}\|=L\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}$,
we have
$\mathcal{X}=\big{\\{}\big{(}-r+\frac{L}{\sigma_{1}},\;\mathbf{0}\big{)}\big{\\}}$.

With these definitions in place, given
$\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\in\mathbb{R}^{n}$,
$\sigma_{1},\sigma_{2}\in\mathbb{R}_{>0}$, and $L\in\mathbb{R}_{>0}$, we
define the outer and inner approximations of $\mathcal{M}$ as

$\mathcal{M}^{\uparrow}(\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*},\sigma_{1},\sigma_{2},L)\triangleq\big{\\{}\boldsymbol{x}\in\mathbb{R}^{n}:\;\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\geq\psi(\boldsymbol{x})\big{\\}}$
(13)

and

$\mathcal{M}_{\downarrow}(\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*},\sigma_{1},\sigma_{2},L)\triangleq\big{\\{}\boldsymbol{x}\in\mathbb{R}^{n}:\;\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})>\psi(\boldsymbol{x})\big{\\}}\cup\mathcal{X},$
(14)

respectively. As before, we will omit the argument of the sets
$\mathcal{M}^{\uparrow}(\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*},\sigma_{1},\sigma_{2},L)$
and
$\mathcal{M}_{\downarrow}(\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*},\sigma_{1},\sigma_{2},L)$,
and write them as $\mathcal{M}^{\uparrow}$ and $\mathcal{M}_{\downarrow}$,
respectively.

######  Remark 1.

Recall the definition of $\tilde{\phi}_{i}$ for $i\in\\{1,2\\}$ and $\psi$
from (9) and (11), respectively. Since $\mathcal{M}^{\uparrow}$ and
$\mathcal{M}_{\downarrow}$ are defined using $\tilde{\phi}_{1}$,
$\tilde{\phi}_{2}$ and $\psi$, implicitly, they must be subsets of
$\textbf{dom}(\tilde{\phi}_{1})\cap\textbf{dom}(\tilde{\phi}_{2})\cap\textbf{dom}(\psi)$.
In other words, the sets
$\mathcal{M}^{\uparrow}\subseteq(\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$
and
$\mathcal{M}_{\downarrow}\subseteq(\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$
where $\mathcal{B}_{i}$ for $i\in\\{1,2\\}$ are defined in (8).

In order to characterize the potential solution region $\mathcal{M}$, we
proceed as follows. First, in Proposition 4.1, we show that
$\mathcal{M}\subseteq\mathcal{M}^{\uparrow}$ by considering a property of
strongly convex functions. Then, we characterize the boundary and interior of
the outer approximation ($\partial\mathcal{M}^{\uparrow}$ and
$(\mathcal{M}^{\uparrow})^{\circ}$) for each value of $r$ in Theorem 4.10. In
Proposition 5.1, we consider quadratic functions and show that
$\mathcal{M}_{\downarrow}\subseteq\mathcal{M}$ in Proposition 5.3. We use a
similar approach as in Theorem 4.10 to characterize the boundary and interior
of the inner approximation ($\partial\mathcal{M}_{\downarrow}$ and
$(\mathcal{M}_{\downarrow})^{\circ}$) for each value of $r$ which is presented
in Theorem 5.4. Finally, by observing that
$\partial\mathcal{M}^{\uparrow}=\partial\mathcal{M}_{\downarrow}$ and
$(\mathcal{M}^{\uparrow})^{\circ}=(\mathcal{M}_{\downarrow})^{\circ}$ from
Theorem 4.10 and Theorem 5.4, we conclude the paper by showing that, in fact,
the boundary of the potential solution region, outer approximation, and inner
approximation are identical, i.e.,
$\partial\mathcal{M}=\partial\mathcal{M}^{\uparrow}=\partial\mathcal{M}_{\downarrow}$,
in Theorem 6.2.

##  4 Outer Approximation

In this section, we derive necessary conditions for a point to be in the
potential solution region $\mathcal{M}$ and show that
$\mathcal{M}\subseteq\mathcal{M}^{\uparrow}$ in Proposition 4.1. Then, we
explicitly characterize an important part of $\partial\mathcal{M}^{\uparrow}$
(and also $\partial\mathcal{M}_{\downarrow}$) in Proposition 4.2. In Theorem
4.10, which is the main result of this section, we identify
$\partial\mathcal{M}^{\uparrow}$ and $(\mathcal{M}^{\uparrow})^{\circ}$, and
also provide a property of $\mathcal{M}^{\uparrow}$. Other lemmas in this
section are presented as tools that will be utilized in the proof of Theorem
4.10 (and also Theorem 5.4).

We will be using the following functions throughout our analysis. For
$i\in\\{1,2\\}$, define
$\boldsymbol{u}_{i}:\;\mathbb{R}^{n}\setminus\\{\boldsymbol{x}_{i}^{*}\\}\to\mathbb{R}^{n}$
to be the function such that

$\boldsymbol{u}_{i}(\boldsymbol{x})\triangleq\frac{\boldsymbol{x}-\boldsymbol{x}_{i}^{*}}{\|\boldsymbol{x}-\boldsymbol{x}_{i}^{*}\|},$
(15)

i.e., the unit vector in the direction of
$\boldsymbol{x}-\boldsymbol{x}_{i}^{*}$. Recall the definition of
$\angle(\cdot,\cdot)$ from (1). For $i\in\\{1,2\\}$, we define
$\phi_{i}:\mathbb{R}^{n}\setminus\\{\boldsymbol{x}_{i}^{*}\\}\to\big{[}0,\frac{\pi}{2}\big{]}$
to be the function such that

$\phi_{i}(\boldsymbol{x})\triangleq\angle\big{(}\nabla
f_{i}(\boldsymbol{x}),\;\boldsymbol{u}_{i}(\boldsymbol{x})\big{)},$ (16)

and $\underline{L}_{i}:\mathbb{R}^{n}\to\mathbb{R}$ to be the function such
that

$\underline{L}_{i}(\boldsymbol{x})\triangleq\sigma_{i}\|\boldsymbol{x}-\boldsymbol{x}_{i}^{*}\|.$
(17)

Note that for $i\in\\{1,2\\}$, the quantity
$\underline{L}_{i}(\boldsymbol{x})$ is a lower bound on the norm of the
gradient of $f_{i}$ at $\boldsymbol{x}\in\mathbb{R}^{n}$ if
$f_{i}\in\mathcal{S}(\boldsymbol{x}_{i}^{*},\sigma_{i})$.

In Fig. 2, we illustrate the definition of $\boldsymbol{u}_{i}$, $\phi_{i}$,
$\tilde{\phi}_{i}$, $\alpha_{i}$ for $i\in\\{1,2\\}$, and $\psi$. Moreover, we
illustrate the inequality
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\geq\psi(\boldsymbol{x})$
which is used to describe the outer approximation $\mathcal{M}^{\uparrow}$ in
(13).

In the following proposition, we show a crucial result that the set
$\mathcal{M}^{\uparrow}$ covers the set that we want to characterize,
$\mathcal{M}$. In other words, the points in the set $\mathcal{M}^{\uparrow}$
satisfy necessary conditions of a point to be a minimizer of the sum
$f_{1}+f_{2}$.

######  Proposition 4.1.

Suppose the sets $\mathcal{M}$ and $\mathcal{M}^{\uparrow}$ are defined as in
(7) and (13), respectively. Then,
$\mathcal{M}\subseteq\mathcal{M}^{\uparrow}$.

###### Proof.

Recall the definition of the sets $\mathcal{B}_{i}$ for $i\in\\{1,2\\}$, the
angles $\tilde{\phi}_{i}$ for $i\in\\{1,2\\}$, and the angle $\psi$ from (8),
(9), and (11), respectively. First, we want to show that the necessary
conditions for a point
$\boldsymbol{x}\in\mathbb{R}^{n}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$
to be in $\mathcal{M}$ are

  1. (i)

$\boldsymbol{x}\in\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2}$,
and

  2. (ii)

$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\geq\psi(\boldsymbol{x})$.

From the definition of strongly convex functions in (3), we have

$\big{\langle}\nabla f_{i}(\boldsymbol{x})-\nabla
f_{i}(\boldsymbol{y}),\;\boldsymbol{x}-\boldsymbol{y}\big{\rangle}\geq\sigma_{i}\|\boldsymbol{x}-\boldsymbol{y}\|^{2}$

for all $\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{n}$ and for
$i\in\\{1,2\\}$. For $i\in\\{1,2\\}$, recall the definition of
$\boldsymbol{u}_{i}(\boldsymbol{x})$ and $\phi_{i}(\boldsymbol{x})$ from (15)
and (16), respectively. Since $\boldsymbol{x}_{1}^{*}$ and
$\boldsymbol{x}_{2}^{*}$ are the minimizers of $f_{1}$ and $f_{2}$,
respectively, for
$\boldsymbol{x}\notin\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$, we
get

$\displaystyle\big{\langle}\nabla f_{i}(\boldsymbol{x})-\nabla
f_{i}(\boldsymbol{x}_{i}^{*}),\;\boldsymbol{x}-\boldsymbol{x}_{i}^{*}\big{\rangle}$
$\displaystyle\geq\sigma_{i}\|\boldsymbol{x}-\boldsymbol{x}_{i}^{*}\|^{2},$
$\displaystyle\Leftrightarrow\quad\|\nabla
f_{i}(\boldsymbol{x})\|\cos(\phi_{i}(\boldsymbol{x}))=\langle\nabla
f_{i}(\boldsymbol{x}),\;\boldsymbol{u}_{i}(\boldsymbol{x})\rangle$
$\displaystyle\geq\sigma_{i}\|\boldsymbol{x}-\boldsymbol{x}_{i}^{*}\|>0.$ (18)

Suppose $\boldsymbol{x}$ is a candidate minimizer. Then, we have that
$\|\nabla f_{i}(\boldsymbol{x})\|\leq L$ for $i\in\\{1,2\\}$ by our
assumption. Recall the definition of $\underline{L}_{i}$ for $i\in\\{1,2\\}$
from (17). Inequality (18) becomes

$\cos(\phi_{i}(\boldsymbol{x}))\geq\frac{\sigma_{i}}{L}\|\boldsymbol{x}-\boldsymbol{x}_{i}^{*}\|=\frac{\underline{L}_{i}(\boldsymbol{x})}{L}.$
(19)

If $\underline{L}_{1}(\boldsymbol{x})>L$ or
$\underline{L}_{2}(\boldsymbol{x})>L$, we have that $\boldsymbol{x}$ cannot be
the minimizer of the function $f_{1}+f_{2}$ since there is no
$\phi_{i}(\boldsymbol{x})$ that can satisfy inequality (19). Thus, a necessary
condition for
$\boldsymbol{x}\in\mathbb{R}^{n}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$
to be a minimizer of $f_{1}+f_{2}$ is that
$\underline{L}_{i}(\boldsymbol{x})\leq L$ for $i\in\\{1,2\\}$ or equivalently,
$\boldsymbol{x}\in\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2}$,
yielding part (i) of the claim. We now prove part (ii).

From the definition of $\psi(\boldsymbol{x})$ in (11) and that
$\angle(-\boldsymbol{u}_{1}(\boldsymbol{x}),-\boldsymbol{u}_{2}(\boldsymbol{x}))$,
$\alpha_{1}(\boldsymbol{x})$ and $\pi-\alpha_{2}(\boldsymbol{x})$ are the
angles of the triangle formed by the points $\boldsymbol{x}$,
$\boldsymbol{x}_{1}^{*}$ and $\boldsymbol{x}_{2}^{*}$, we can write that for
all
$\boldsymbol{x}\in\mathbb{R}^{n}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$,

$\psi(\boldsymbol{x})=(\pi-\alpha_{2}(\boldsymbol{x}))+\alpha_{1}(\boldsymbol{x})=\pi-\angle(-\boldsymbol{u}_{1}(\boldsymbol{x}),-\boldsymbol{u}_{2}(\boldsymbol{x}))=\angle(\boldsymbol{u}_{1}(\boldsymbol{x}),-\boldsymbol{u}_{2}(\boldsymbol{x})).$
(20)

Suppose that
$\boldsymbol{x}\in\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2}$.
Recall the definition of $\tilde{\phi}_{i}$ for $i\in\\{1,2\\}$ from (9). From
inequality (19), we have
$\phi_{i}(\boldsymbol{x})\leq\tilde{\phi}_{i}(\boldsymbol{x})$ for
$i\in\\{1,2\\}$. If
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})<\psi(\boldsymbol{x})$,
then using (16) and (20), we have

$\angle(\nabla
f_{1}(\boldsymbol{x}),\boldsymbol{u}_{1}(\boldsymbol{x}))+\angle(-\nabla
f_{2}(\boldsymbol{x}),-\boldsymbol{u}_{2}(\boldsymbol{x}))<\angle(\boldsymbol{u}_{1}(\boldsymbol{x}),-\boldsymbol{u}_{2}(\boldsymbol{x})).$

However, using (Castano et al., 2016, Corollary 12), we can write
$\angle(\boldsymbol{u}_{1}(\boldsymbol{x}),-\boldsymbol{u}_{2}(\boldsymbol{x}))\leq$
$\angle(\nabla f_{1}(\boldsymbol{x}),\boldsymbol{u}_{1}(\boldsymbol{x}))$
$+\angle(\nabla f_{1}(\boldsymbol{x}),-\boldsymbol{u}_{2}(\boldsymbol{x}))$.
Therefore, if
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})<\psi(\boldsymbol{x})$,
we have that $\nabla f_{1}(\boldsymbol{x})\neq-\nabla f_{2}(\boldsymbol{x})$
which implies that $\boldsymbol{x}$ is not the minimizer of $f_{1}+f_{2}$.
This means that one of the necessary conditions is that
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\geq\psi(\boldsymbol{x})$
which completes the proof of the claim.

In the above analysis, we considered the case when
$\boldsymbol{x}\in\mathbb{R}^{n}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.
We are left with the case when
$\boldsymbol{x}\in\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$. From
the definition of strongly convex functions, for all
$\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{n}$,

$\big{\langle}\nabla f_{2}(\boldsymbol{x})-\nabla
f_{2}(\boldsymbol{y}),\;\boldsymbol{x}-\boldsymbol{y}\big{\rangle}\geq\sigma_{2}\|\boldsymbol{x}-\boldsymbol{y}\|^{2}.$

Since $\boldsymbol{x}_{2}^{*}$ is the minimizer of $f_{2}$ and
$\boldsymbol{x}_{1}^{*}\neq\boldsymbol{x}_{2}^{*}$, we get

$\big{\langle}\nabla
f_{2}(\boldsymbol{x}_{1}^{*}),\;\boldsymbol{x}_{1}^{*}-\boldsymbol{x}_{2}^{*}\big{\rangle}=\big{\langle}\nabla
f_{2}(\boldsymbol{x}_{1}^{*})-\nabla
f_{2}(\boldsymbol{x}_{2}^{*}),\;\boldsymbol{x}_{1}^{*}-\boldsymbol{x}_{2}^{*}\big{\rangle}\geq\sigma_{2}\|\boldsymbol{x}_{1}^{*}-\boldsymbol{x}_{2}^{*}\|^{2}>0,$

and thus, $\nabla f_{2}(\boldsymbol{x}_{1}^{*})\neq\boldsymbol{0}$. This
implies that $\nabla f_{2}(\boldsymbol{x}_{1}^{*})+\nabla
f_{1}(\boldsymbol{x}_{1}^{*})\neq\boldsymbol{0}$ and $\boldsymbol{x}_{1}^{*}$
is not the minimizer of $f_{1}+f_{2}$. By using similar approach, we can also
conclude that $\boldsymbol{x}_{2}^{*}$ is not the minimizer of $f_{1}+f_{2}$.
∎

(a)

(b)

Figure 2: (a) The figure illustrates the definition of $\boldsymbol{u}_{i}$,
$\phi_{i}$, and $\tilde{\phi}_{i}$ for $i\in\\{1,2\\}$. In particular,
inequality (19) implies that
$\phi_{i}(\boldsymbol{x})\in[0,\tilde{\phi}_{i}(\boldsymbol{x})]$ for
$i\in\\{1,2\\}$, i.e., the gradient vectors $\nabla f_{1}(\boldsymbol{x})$ and
$\nabla f_{2}(\boldsymbol{x})$ must lie in the corresponding shaded regions.
(b) The figure illustrates the definition of $\alpha_{i}$ for $i\in\\{1,2\\}$
and $\psi$. In addition, the inequality
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\geq\psi(\boldsymbol{x})$
in $\mathcal{M}^{\uparrow}$ means that there is an overlapping region (light
green region in the figure) caused by one shaded region and the mirror of the
other shaded region.

######  Remark 2.

The angle functions $\tilde{\phi}_{i}$ and $\alpha_{i}$ for $i\in\\{1,2\\}$
defined in (16) and (10), respectively, can be expressed as functions of the
distances $\|\boldsymbol{x}_{1}^{*}-\boldsymbol{x}_{2}^{*}\|$,
$\|\boldsymbol{x}-\boldsymbol{x}_{1}^{*}\|$, and
$\|\boldsymbol{x}-\boldsymbol{x}_{2}^{*}\|$. This means that the inequality
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\geq\psi(\boldsymbol{x})$
depends only on the distance among three points $\boldsymbol{x}$,
$\boldsymbol{x}_{1}^{*}$ and $\boldsymbol{x}_{2}^{*}$. Since
$\boldsymbol{x}_{1}^{*}=(-r,\mathbf{0})$ and
$\boldsymbol{x}_{2}^{*}=(r,\mathbf{0})$, we conclude that the shape of
$\mathcal{M}^{\uparrow}$ (and $\mathcal{M}_{\downarrow}$) is symmetric around
$x_{1}$-axis.

From this point, we will denote
$\boldsymbol{x}=(x_{1},\tilde{\mathbf{x}})\in\mathbb{R}^{n}$ where
$x_{1}\in\mathbb{R}$ and
$\tilde{\mathbf{x}}=(x_{2},x_{3},\ldots,x_{n})\in\mathbb{R}^{n-1}$. Next, we
will provide an algebraic expression for a certain portion of
$\partial\mathcal{M}^{\uparrow}$ (and $\partial\mathcal{M}_{\downarrow}$)
based on the geometric equation
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})=\psi(\boldsymbol{x})$,
where $\tilde{\phi}_{i}$ for $i\in\\{1,2\\}$ and $\psi$ are defined in (9) and
(11), respectively. For convenience, we define

$\displaystyle d_{1}(\boldsymbol{x})$
$\displaystyle\triangleq\|\boldsymbol{x}-\boldsymbol{x}_{1}^{*}\|=\sqrt{(x_{1}+r)^{2}+\|\tilde{\mathbf{x}}\|^{2}}\quad\text{and}$
(21) $\displaystyle d_{2}(\boldsymbol{x})$
$\displaystyle\triangleq\|\boldsymbol{x}-\boldsymbol{x}_{2}^{*}\|=\sqrt{(x_{1}-r)^{2}+\|\tilde{\mathbf{x}}\|^{2}}.$

Define the set of points

$\mathcal{T}\triangleq\bigg{\\{}\boldsymbol{x}\in\mathbb{R}^{n}:\;\frac{\|\boldsymbol{x}\|^{2}-r^{2}}{d_{1}^{2}(\boldsymbol{x})\cdot
d_{2}^{2}(\boldsymbol{x})}+\frac{\sigma_{1}\sigma_{2}}{L^{2}}=\sqrt{\frac{1}{d_{1}^{2}(\boldsymbol{x})}-\frac{\sigma_{1}^{2}}{L^{2}}}\cdot\sqrt{\frac{1}{d_{2}^{2}(\boldsymbol{x})}-\frac{\sigma_{2}^{2}}{L^{2}}}\bigg{\\}}.$
(22)

######  Proposition 4.2.

The set $\mathcal{T}$ defined in (22) can equivalently be written as
$\mathcal{T}=\big{\\{}\boldsymbol{x}\in\mathbb{R}^{n}:\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})=\psi(\boldsymbol{x})\big{\\}}$.

###### Proof.

Based on the definition of $\alpha_{i}(\boldsymbol{x})$ for $i\in\\{1,2\\}$ in
(10), for any point
$\boldsymbol{x}\in\mathbb{R}^{n}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$,
we have

$\displaystyle x_{1}=d_{1}(\boldsymbol{x})\cos(\alpha_{1}(\boldsymbol{x}))-r=$
$\displaystyle\;d_{2}(\boldsymbol{x})\cos(\alpha_{2}(\boldsymbol{x}))+r,$
$\displaystyle\Leftrightarrow\quad\cos(\alpha_{1}(\boldsymbol{x}))=\frac{x_{1}+r}{d_{1}(\boldsymbol{x})}\quad\text{and}$
$\displaystyle\quad\cos(\alpha_{2}(\boldsymbol{x}))=\frac{x_{1}-r}{d_{2}(\boldsymbol{x})}.$
(23)

Similarly,

$\displaystyle\|\tilde{\mathbf{x}}\|=d_{1}(\boldsymbol{x})\sin(\alpha_{1}(\boldsymbol{x}))=$
$\displaystyle\;d_{2}(\boldsymbol{x})\sin(\alpha_{2}(\boldsymbol{x})),$
$\displaystyle\Leftrightarrow\quad\sin(\alpha_{1}(\boldsymbol{x}))=\frac{\|\tilde{\mathbf{x}}\|}{d_{1}(\boldsymbol{x})}\quad\text{and}$
$\displaystyle\quad\sin(\alpha_{2}(\boldsymbol{x}))=\frac{\|\tilde{\mathbf{x}}\|}{d_{2}(\boldsymbol{x})}.$
(24)

Since $\tilde{\phi}_{i}(\boldsymbol{x})\in\big{[}0,\frac{\pi}{2}\big{]}$ for
$i\in\\{1,2\\}$, we get
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\in[0,\pi]$.
Recall from (11) that $\psi(\boldsymbol{x})\in[0,\pi]$. Since the cosine
function is one-to-one for this range of angles, equation
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})=\psi(\boldsymbol{x})$
is equivalent to

$\cos\big{(}\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\big{)}=\cos\big{(}\pi-(\alpha_{2}(\boldsymbol{x})-\alpha_{1}(\boldsymbol{x}))\big{)}=-\cos\big{(}\alpha_{2}(\boldsymbol{x})-\alpha_{1}(\boldsymbol{x})\big{)}.$

Expanding this equation and substituting (23), (24), and
$\cos(\tilde{\phi}_{i}(\boldsymbol{x}))=\frac{\sigma_{i}}{L}d_{i}(\boldsymbol{x})$
for $i\in\\{1,2\\}$, we get

$\frac{\sigma_{1}}{L}d_{1}(\boldsymbol{x})\cdot\frac{\sigma_{2}}{L}d_{2}(\boldsymbol{x})-\sqrt{1-\Big{(}\frac{\sigma_{1}}{L}d_{1}(\boldsymbol{x})\Big{)}^{2}}\cdot\sqrt{1-\Big{(}\frac{\sigma_{2}}{L}d_{2}(\boldsymbol{x})\Big{)}^{2}}=-\frac{x_{1}-r}{d_{2}(\boldsymbol{x})}\cdot\frac{x_{1}+r}{d_{1}(\boldsymbol{x})}-\frac{\|\tilde{\mathbf{x}}\|}{d_{2}(\boldsymbol{x})}\cdot\frac{\|\tilde{\mathbf{x}}\|}{d_{1}(\boldsymbol{x})}.$

Dividing the above equation by $d_{1}(\boldsymbol{x})\cdot
d_{2}(\boldsymbol{x})$ and rearranging it yields the result. ∎

The subsequent lemmas (Lemma 4.3 \- 4.9) are useful ingredients for proving
the characterization of the outer approximation $\mathcal{M}^{\uparrow}$
(defined in (13)) given in Theorem 4.10, and their proofs are provided in
Appendix A.

The following lemma provides a sufficient condition for the minimizers
$\boldsymbol{x}_{1}^{*}$ and $\boldsymbol{x}_{2}^{*}$ to be on the boundary of
the outer approximation $\mathcal{M}^{\uparrow}$ and the inner approximation
$\mathcal{M}_{\downarrow}$.

######  Lemma 4.3.

Let $\mathcal{M}^{\uparrow}$ and $\mathcal{M}_{\downarrow}$ be as defined in
(13) and (14), respectively.

  1. (i)

If $r\in\big{(}0,\;\frac{L}{2\sigma_{2}}\big{]}$ then
$\boldsymbol{x}_{1}^{*}\in\partial\mathcal{M}^{\uparrow}$ and
$\boldsymbol{x}_{1}^{*}\in\partial\mathcal{M}_{\downarrow}$.

  2. (ii)

If $r\in\big{(}0,\;\frac{L}{2\sigma_{1}}\big{]}$ then
$\boldsymbol{x}_{2}^{*}\in\partial\mathcal{M}^{\uparrow}$ and
$\boldsymbol{x}_{2}^{*}\in\partial\mathcal{M}_{\downarrow}$.

In the next lemma, we provide a property of points in a particular set which
will be used to characterize the sets $\mathcal{M}^{\uparrow}$ and
$\mathcal{M}_{\downarrow}$ defined in (13) and (14), respectively. Roughly
speaking, if $\boldsymbol{x}\in\mathcal{M}^{\uparrow}$ and $x_{1}\in[-r,r]$,
then each point that has the same first component and is closer to the
$x_{1}$-axis is also in $\mathcal{M}^{\uparrow}$.

######  Lemma 4.4.

Consider two points $\boldsymbol{x}=(x_{1},\tilde{\mathbf{x}})$ and
$\boldsymbol{y}=(y_{1},\tilde{\mathbf{y}})$. Suppose $-r\leq x_{1}=y_{1}\leq
r$ and $\|\tilde{\mathbf{x}}\|>\|\tilde{\mathbf{y}}\|$. If
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\geq\psi(\boldsymbol{x})$
then either
$\tilde{\phi}_{1}(\boldsymbol{y})+\tilde{\phi}_{2}(\boldsymbol{y})>\psi(\boldsymbol{y})$
or $\boldsymbol{y}\in\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.

Recall the definition of $\mathcal{B}$ from (8). Since
$\boldsymbol{x}_{1}^{*}=(-r,\mathbf{0})$ and
$\boldsymbol{x}_{2}^{*}=(r,\mathbf{0})$ by our assumption, we can explicitly
write $\partial\mathcal{B}_{i}$ for $i\in\\{1,2\\}$ as follows:

$\displaystyle\partial\mathcal{B}_{1}=\partial\mathcal{B}\Big{(}\boldsymbol{x}_{1}^{*},\frac{L}{\sigma_{1}}\Big{)}$
$\displaystyle=\bigg{\\{}\boldsymbol{x}\in\mathbb{R}^{n}:(x_{1}+r)^{2}+\|\tilde{\mathbf{x}}\|^{2}=\frac{L^{2}}{\sigma_{1}^{2}}\bigg{\\}},$
(25)
$\displaystyle\partial\mathcal{B}_{2}=\partial\mathcal{B}\Big{(}\boldsymbol{x}_{2}^{*},\frac{L}{\sigma_{2}}\Big{)}$
$\displaystyle=\bigg{\\{}\boldsymbol{x}\in\mathbb{R}^{n}:(x_{1}-r)^{2}+\|\tilde{\mathbf{x}}\|^{2}=\frac{L^{2}}{\sigma_{2}^{2}}\bigg{\\}}.$

For convenience, we define

$\gamma_{i}\triangleq\frac{L^{2}}{\sigma_{i}^{2}}\;\;\text{for}\;\;i\in\\{1,2\\}\quad\text{and}\quad\beta\triangleq\frac{\sigma_{2}}{\sigma_{1}}.$
(26)

By using the definitions above, we define

$\lambda_{1}\triangleq\Big{(}\frac{1+\beta}{1+2\beta}\Big{)}\frac{\gamma_{1}}{2r}-\frac{r}{1+2\beta}\quad\text{and}\quad\lambda_{2}\triangleq-\Big{(}\frac{1+\beta}{2+\beta}\Big{)}\frac{\gamma_{2}}{2r}+\frac{\beta
r}{2+\beta}.$ (27)

In the following lemma, we will show that if
$\boldsymbol{x}\in\\{\partial\mathcal{B}_{1},\partial\mathcal{B}_{2}\\}$, the
value of the first component $x_{1}$ is necessary and sufficient to determine
whether $\boldsymbol{x}$ is in $\mathcal{M}^{\uparrow}$ and
$\mathcal{M}_{\downarrow}$, which are defined in (13) and (14), respectively.
In other words, the angle condition
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\lessgtr\psi(\boldsymbol{x})$
can be simplified if we consider a point in $\partial\mathcal{B}_{1}$ or
$\partial\mathcal{B}_{2}$.

######  Lemma 4.5.

Let $\lambda_{1}$ and $\lambda_{2}$ be as defined in (27). Consider
$\boldsymbol{x}=(x_{1},\tilde{\mathbf{x}})\in(\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.

  1. (i)

If $\boldsymbol{x}\in\partial\mathcal{B}_{1}$ then
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\lessgtr\psi(\boldsymbol{x})$
if and only if $x_{1}\lessgtr\lambda_{1}$.

  2. (ii)

If $\boldsymbol{x}\in\partial\mathcal{B}_{2}$ then
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\lessgtr\psi(\boldsymbol{x})$
if and only if $x_{1}\gtrless\lambda_{2}$.

In the following lemma, we will show that the points in the set of
intersection between $\mathcal{T}$ and $\partial\mathcal{B}_{1}$ (resp.
$\mathcal{T}$ and $\partial\mathcal{B}_{2}$) have the same first component, if
the intersection is non-empty. Moreover, the first component of these points
is $\lambda_{1}$ (resp. $\lambda_{2}$) where $\lambda_{i}$ for $i\in\\{1,2\\}$
are defined in (27). By using the definition of $\gamma_{1}$, $\gamma_{2}$ and
$\beta$ in (26), define

$\displaystyle\nu_{1}$
$\displaystyle\triangleq\frac{r}{2(1+2\beta)}\sqrt{-\Big{(}\frac{\gamma_{1}}{r^{2}}-4\Big{)}\Big{(}(1+\beta)^{2}\frac{\gamma_{1}}{r^{2}}-4\beta^{2}\Big{)}}\quad\text{and}$
(28) $\displaystyle\nu_{2}$
$\displaystyle\triangleq\frac{r}{2(2+\beta)}\sqrt{-\Big{(}\frac{\gamma_{2}}{r^{2}}-4\Big{)}\Big{(}(1+\beta)^{2}\frac{\gamma_{2}}{r^{2}}-4\Big{)}}.$

######  Lemma 4.6.

Consider the sets of points $\mathcal{T}$ and $\partial\mathcal{B}_{i}$ for
$i\in\\{1,2\\}$ defined in (22) and (25), respectively. Let $\lambda_{i}$ and
$\nu_{i}$ for $i\in\\{1,2\\}$ be as defined in (27) and (28), respectively.

  1. (i)

For $i\in\\{1,2\\}$, if $r\in\big{(}0,\frac{L}{2\sigma_{i}}\big{]}$, then
$\mathcal{T}\cap\partial\mathcal{B}_{i}=\emptyset$.

  2. (ii)

For $i\in\\{1,2\\}$, if
$r\in\big{(}\frac{L}{2\sigma_{i}},\frac{L}{2}(\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}})\big{]}$,
then
$\mathcal{T}\cap\partial\mathcal{B}_{i}=\big{\\{}\boldsymbol{x}\in\mathbb{R}^{n}:x_{1}=\lambda_{i},\;\;\|\tilde{\mathbf{x}}\|=\nu_{i}\big{\\}}$.

Recall that $\lambda_{1}$ and $\lambda_{2}$ are defined in (27). In the
following lemma, for $i\in\\{1,2\\}$, we consider a relationship between
$\frac{L}{\sigma_{i}r}$ and $\frac{\lambda_{i}}{r}$. In particular, for
$r\in\big{(}0,\frac{L}{2}(\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}})\big{]}$,
recall from Lemma 4.6 that if
$\mathcal{T}\cap\partial\mathcal{B}_{1}\neq\emptyset$ (resp.
$\mathcal{T}\cap\partial\mathcal{B}_{2}\neq\emptyset$), then every point in
the intersection has the first component equal to $\lambda_{1}$ (resp.
$\lambda_{2}$). The next lemma compares $\lambda_{1}$ to the maximum value of
the first component over all points of $\partial\mathcal{B}_{1}$ (which is
$-r+\frac{L}{\sigma_{1}}$), and compares $\lambda_{2}$ to the minimum value of
the first component over all points of $\partial\mathcal{B}_{2}$ (which is
$r-\frac{L}{\sigma_{1}}$), respectively.

######  Lemma 4.7.

Let $\lambda_{i}$ for $i\in\\{1,2\\}$ be as defined in (27).

  1. (i)

If $r\in\big{(}0,\;\frac{L}{2\sigma_{1}}\big{]}$ then
$\lambda_{1}\geq\frac{L}{\sigma_{1}}-r$, with equality only if
$r=\frac{L}{2\sigma_{1}}$.

  2. (ii)

$r\in\big{(}\frac{L}{2\sigma_{1}},\;\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}\big{)}$
if and only if $\lambda_{1}<\frac{L}{\sigma_{1}}-r$.

  3. (iii)

If $r\in\big{(}0,\;\frac{L}{2\sigma_{2}}\big{]}$ then $\lambda_{2}\leq
r-\frac{L}{\sigma_{2}}$, with equality only if $r=\frac{L}{2\sigma_{2}}$.

  4. (iv)

$r\in\big{(}\frac{L}{2\sigma_{2}},\;\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}\big{)}$
if and only if $\lambda_{2}>r-\frac{L}{\sigma_{2}}$.

In the next lemma, we will consider a relationship between $\mathcal{T}$ and
$\partial\mathcal{M}^{\uparrow}$ (the boundary of the outer approximation),
and $\mathcal{T}$ and $\partial\mathcal{M}_{\downarrow}$ (the boundary of the
inner approximation). In particular, we will show that
$\mathcal{T}\subseteq\partial\mathcal{M}^{\uparrow}$ and
$\mathcal{T}\subseteq\partial\mathcal{M}_{\downarrow}$ for a particular range
of $r$.

######  Lemma 4.8.

Let $\mathcal{M}^{\uparrow}$, $\mathcal{M}_{\downarrow}$ and $\mathcal{T}$ be
defined as in (13), (14) and (22), respectively. If
$r\in\Big{(}0,\;\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}\Big{)}$,
then $\mathcal{T}\subseteq\partial\mathcal{M}^{\uparrow}$ and
$\mathcal{T}\subseteq\partial\mathcal{M}_{\downarrow}$.

For $i\in\\{1,2\\}$, define half-planes

$\mathcal{H}_{i}^{+}\triangleq\\{\boldsymbol{x}\in\mathbb{R}^{n}:x_{1}\geq\lambda_{i}\\}\quad\text{and}\quad\mathcal{H}_{i}^{-}\triangleq\\{\boldsymbol{x}\in\mathbb{R}^{n}:x_{1}\leq\lambda_{i}\\},$
(29)

where $\lambda_{i}$ for $i\in\\{1,2\\}$ are defined in (27). In the lemma
below, we examine properties of points
$\boldsymbol{x}\in\partial\mathcal{B}_{1}\cap\mathcal{H}_{1}^{+}$ (resp.
$\boldsymbol{x}\in\partial\mathcal{B}_{2}\cap\mathcal{H}_{2}^{-}$).

######  Lemma 4.9.

Let the sets $\mathcal{B}_{i}$ for $i\in\\{1,2\\}$, and $\mathcal{H}_{1}^{+}$
and $\mathcal{H}_{2}^{-}$ be defined as in (8) and (29), respectively.

  1. (i)

If
$r\in\Big{(}\frac{L}{2\sigma_{1}},\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}\Big{)}$
then $\big{[}\lambda_{1},\;-r+\frac{L}{\sigma_{1}}\big{]}\subseteq(-r,r)$ and
$\partial\mathcal{B}_{1}\cap\mathcal{H}_{1}^{+}\subseteq(\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.

  2. (ii)

If
$r\in\Big{(}\frac{L}{2\sigma_{2}},\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}\Big{)}$
then $\big{[}r-\frac{L}{\sigma_{2}},\;\lambda_{2}\big{]}\subseteq(-r,r)$ and
$\partial\mathcal{B}_{2}\cap\mathcal{H}_{2}^{-}\subseteq(\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.

In the theorem below, we give the characterization of the boundary
$\partial\mathcal{M}^{\uparrow}$ and interior
$(\mathcal{M}^{\uparrow})^{\circ}$, and also a property of the set
$\mathcal{M}^{\uparrow}$ for each range of $r$. Define the set

$\widetilde{\mathcal{T}}\triangleq\\{\boldsymbol{x}\in\mathbb{R}^{n}:\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})>\psi(\boldsymbol{x})\\},$
(30)

which will be used especially in Theorem 4.10 and Theorem 5.4.

######  Theorem 4.10.

Assume $\sigma_{1}\geq\sigma_{2}$. Let the sets $\mathcal{M}^{\uparrow}$,
$\mathcal{T}$, $\widetilde{\mathcal{T}}$, and $\mathcal{B}_{i}$ for
$i\in\\{1,2\\}$ be defined as in (13), (22), (30), and (8), respectively.
Also, let the sets $\mathcal{H}_{i}^{+}$ and $\mathcal{H}_{i}^{-}$ for
$i\in\\{1,2\\}$ be defined as in (29).

  1. (i)

If $r\in\big{(}0,\;\frac{L}{2\sigma_{1}}\big{]}$ then
$\mathcal{M}^{\uparrow}\sqcup\\{\boldsymbol{x}^{*}_{1},\boldsymbol{x}^{*}_{2}\\}$
is closed,

$\partial\mathcal{M}^{\uparrow}=\mathcal{T}\sqcup\\{\boldsymbol{x}^{*}_{1},\boldsymbol{x}^{*}_{2}\\}\quad\text{and}\quad(\mathcal{M}^{\uparrow})^{\circ}=\widetilde{\mathcal{T}}.$

  2. (ii)

If $r\in\big{(}\frac{L}{2\sigma_{1}},\;\frac{L}{2\sigma_{2}}\big{]}$ then
$\mathcal{M}^{\uparrow}\sqcup\\{\boldsymbol{x}^{*}_{1}\\}$ is closed,

$\displaystyle\partial\mathcal{M}^{\uparrow}$
$\displaystyle=\big{[}\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\mathcal{T}\sqcup\\{\boldsymbol{x}^{*}_{1}\\}\quad\text{and}$
$\displaystyle(\mathcal{M}^{\uparrow})^{\circ}$
$\displaystyle=\big{[}\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\big{[}\widetilde{\mathcal{T}}\cap\mathcal{H}_{1}^{-}\big{]}.$

  3. (iii)

If
$r\in\Big{(}\frac{L}{2\sigma_{2}},\;\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}\Big{)}$
then $\mathcal{M}^{\uparrow}$ is closed,

$\displaystyle\partial\mathcal{M}^{\uparrow}$
$\displaystyle=\big{[}\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\big{[}\partial\mathcal{B}_{2}\cap(\mathcal{H}_{2}^{+})^{c}\big{]}\sqcup\mathcal{T}\quad\text{and}$
$\displaystyle(\mathcal{M}^{\uparrow})^{\circ}$
$\displaystyle=\big{[}\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\big{[}\mathcal{B}_{2}\cap(\mathcal{H}_{2}^{+})^{c}\big{]}\sqcup\big{[}\widetilde{\mathcal{T}}\cap(\mathcal{H}_{1}^{-}\cap\mathcal{H}_{2}^{+})\big{]}.$

  4. (iv)

If $r=\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}$ then
$\mathcal{M}^{\uparrow}=\Big{\\{}\Big{(}\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}-\frac{1}{\sigma_{2}}\big{)},\;\mathbf{0}\Big{)}\Big{\\}}$.

  5. (v)

If
$r\in\Big{(}\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)},\;\infty\Big{)}$
then $\mathcal{M}^{\uparrow}=\emptyset$.

###### Proof.

For convenience, we define function
$\varphi:(\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}\to[-\pi,\pi]$
to be such that

$\varphi(\boldsymbol{x})\triangleq\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})-\psi(\boldsymbol{x}),$
(31)

where $\tilde{\phi}_{i}$ for $i\in\\{1,2\\}$ and $\psi$ are defined in (9) and
$\eqref{def: psi}$, respectively.

Part (i): $r\in\big{(}0,\;\frac{L}{2\sigma_{1}}\big{]}$. First, we want to
show that

$\text{if}\quad\boldsymbol{x}\in\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})\quad\text{then}\quad\boldsymbol{x}\in\\{\boldsymbol{z}\in\mathbb{R}^{n}:\varphi(\boldsymbol{z})<0\\}\cup\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}.$
(32)

Suppose $\boldsymbol{x}\in\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})$ and
$\boldsymbol{x}\in\partial\mathcal{B}_{1}$. Since $\overline{\mathcal{B}}_{1}$
is closed and
$x_{1}\in\big{[}-r-\frac{L}{\sigma_{1}},-r+\frac{L}{\sigma_{1}}\big{]}$, from
Lemma 4.7 part (i), we get $x_{1}\leq\frac{L}{\sigma_{1}}-r\leq\lambda_{1}$.
If $x_{1}<\lambda_{1}$, from Lemma 4.5 part (i), we obtain
$\varphi(\boldsymbol{x})<0$. On the other hand, if $x_{1}=\lambda_{1}$ (i.e.,
$\frac{L}{\sigma_{1}}-r=\lambda_{1}$), from Lemma 4.7 part (i), we get
$r=\frac{L}{2\sigma_{1}}$. Substituting into $x_{1}=\frac{L}{\sigma_{1}}-r$,
we obtain that $x_{1}=\frac{L}{2\sigma_{1}}=r$. Since
$\boldsymbol{x}\in\partial\mathcal{B}(\boldsymbol{x}_{1}^{*},2r)$ and
$x_{1}=r$, we conclude that
$\boldsymbol{x}=\boldsymbol{x}_{2}^{*}=(r,\mathbf{0})$.

From the assumption $\sigma_{1}\geq\sigma_{2}$ and the inequality
$r\leq\frac{L}{2\sigma_{1}}$, we get $r\leq\frac{L}{2\sigma_{2}}$. We can
similarly show that if
$\boldsymbol{x}\in\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})$ and
$\boldsymbol{x}\in\partial\mathcal{B}_{2}$ then either
$\varphi(\boldsymbol{x})<0$ or
$\boldsymbol{x}=\boldsymbol{x}_{1}^{*}=(-r,\mathbf{0})$ by using Lemma 4.7
part (iii) and Lemma 4.5 part (ii). Since
$\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})\subseteq\partial\mathcal{B}_{1}\cup\partial\mathcal{B}_{2}$,
we have proved our claim.

Since
$\mathcal{M}^{\uparrow}\subseteq\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2}$
from the definition of $\mathcal{M}^{\uparrow}$ in (13) and
$\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})\subset(\mathcal{M}^{\uparrow})^{c}$
from (32), we have
$\mathcal{M}^{\uparrow}\subseteq\mathcal{B}_{1}\cap\mathcal{B}_{2}$. Recall
the definition of $\varphi$ in (31). Let
$\mathcal{R}=(\mathcal{B}_{1}\cap\mathcal{B}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.
We then partition the set $\mathcal{R}$ into 3 parts as follows:

$\mathcal{R}_{1}=\big{\\{}\boldsymbol{z}\in\mathcal{R}:\varphi(\boldsymbol{z})>0\big{\\}},\;\;\mathcal{R}_{2}=\big{\\{}\boldsymbol{z}\in\mathcal{R}:\varphi(\boldsymbol{z})<0\big{\\}},\quad\text{and}\quad\mathcal{R}_{3}=\big{\\{}\boldsymbol{z}\in\mathcal{R}:\varphi(\boldsymbol{z})=0\big{\\}}=\mathcal{T},$

where the last equality comes from Proposition 4.2. We will show that

$\begin{cases}\mathcal{R}_{1}\subset(\partial\mathcal{M}^{\uparrow})^{c},\\\
\mathcal{R}_{2}\subset(\partial\mathcal{M}^{\uparrow})^{c},\\\
\mathcal{R}_{3}\subseteq\partial\mathcal{M}^{\uparrow},\\\
\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}\subset(\partial\mathcal{M}^{\uparrow})^{c},\\\
(\operatorname*{\textbf{dom}}(\varphi))^{c}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}\subset(\partial\mathcal{M}^{\uparrow})^{c}.\end{cases}$
(33)

Suppose $\boldsymbol{x}\in\mathcal{R}_{1}$. Since $\varphi$ is continuous,
there exists $\epsilon>0$ such that for all
$\boldsymbol{x}_{0}\in\mathcal{B}(\boldsymbol{x},\epsilon)$, we have
$\boldsymbol{x}_{0}\in\mathcal{R}_{1}$ and $\varphi(\boldsymbol{x}_{0})>0$.
Since $\mathcal{R}_{1}\subseteq\mathcal{M}^{\uparrow}$ and is open, we have
$\mathcal{R}_{1}\subseteq(\mathcal{M}^{\uparrow})^{\circ}$. Similarly, we have
$\mathcal{R}_{2}\subseteq(\mathcal{R}\setminus\mathcal{M}^{\uparrow})^{\circ}$.
Suppose $\boldsymbol{x}\in\mathcal{R}_{3}=\mathcal{T}$. Using Lemma 4.8, we
have that $\mathcal{R}_{3}\subseteq\partial\mathcal{M}^{\uparrow}$. Since
$(\mathcal{M}^{\uparrow})^{\circ}$,
$(\mathcal{R}\setminus\mathcal{M}^{\uparrow})^{\circ}$, and
$\partial\mathcal{M}^{\uparrow}$ are disjoint, we conclude that
$\mathcal{R}_{1}\subset(\partial\mathcal{M}^{\uparrow})^{c}$ and
$\mathcal{R}_{2}\subset(\partial\mathcal{M}^{\uparrow})^{c}$.

Consider
$\boldsymbol{x}\in\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.
From (32), we have
$\boldsymbol{x}\in\\{\boldsymbol{z}\in\mathbb{R}^{n}:\varphi(\boldsymbol{z})<0\\}$.
Since
$\textbf{dom}(\varphi)=(\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$
and $\varphi$ is continuous, there exists $\epsilon>0$ such that for all
$\boldsymbol{x}_{0}\in\mathcal{B}(\boldsymbol{x},\epsilon)\cap\textbf{dom}(\varphi)$,
we have $\varphi(\boldsymbol{x}_{0})<0$. Thus,
$\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}\subset((\mathcal{M}^{\uparrow})^{c})^{\circ}$
which implies that
$\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}\subset(\partial\mathcal{M}^{\uparrow})^{c}$.
In addition, we have
$(\textbf{dom}(\varphi))^{c}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}\subseteq((\mathcal{M}^{\uparrow})^{c})^{\circ}$
(since
$(\textbf{dom}(\varphi))^{c}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}\subseteq(\mathcal{M}^{\uparrow})^{c}$
and is open) which implies
$(\textbf{dom}(\varphi))^{c}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}\subset(\partial\mathcal{M}^{\uparrow})^{c}$.
Therefore, we have proved the claim (33).

Since we can partition $\mathbb{R}^{n}$ into $\mathcal{R}$,
$\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$,
$(\textbf{dom}(\varphi))^{c}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$
and $\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$, using (33), we
obtain that
$\partial\mathcal{M}^{\uparrow}\subseteq\mathcal{R}_{3}\sqcup\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.
However, we know that $\mathcal{R}_{3}\subseteq\partial\mathcal{M}^{\uparrow}$
from the above analysis and
$\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}\subseteq\partial\mathcal{M}^{\uparrow}$
from Lemma 4.3. Thus, we have
$\partial\mathcal{M}^{\uparrow}=\mathcal{R}_{3}\sqcup\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}=\mathcal{T}\sqcup\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$
by Proposition 4.2.

From Proposition 4.2, we have
$\mathcal{T}=\\{\boldsymbol{z}\in\mathbb{R}^{n}:\varphi(\boldsymbol{z})=0\\}$.
Using the definition of $\mathcal{M}^{\uparrow}$ in (13) and
$\partial\mathcal{M}^{\uparrow}=\mathcal{T}\sqcup\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$,
we can write
$(\mathcal{M}^{\uparrow})^{\circ}=\mathcal{M}^{\uparrow}\setminus\partial\mathcal{M}^{\uparrow}=\widetilde{\mathcal{T}}$
where $\widetilde{\mathcal{T}}$ is defined in (30). Since
$\mathcal{T}\subseteq\mathcal{M}^{\uparrow}$, this implies that
$\partial\mathcal{M}^{\uparrow}=\mathcal{T}\sqcup\\{\boldsymbol{x}^{*}_{1},\boldsymbol{x}^{*}_{2}\\}\subseteq\mathcal{M}^{\uparrow}\sqcup\\{\boldsymbol{x}^{*}_{1},\boldsymbol{x}^{*}_{2}\\}$.
Thus, the set
$\mathcal{M}^{\uparrow}\sqcup\\{\boldsymbol{x}^{*}_{1},\boldsymbol{x}^{*}_{2}\\}$
is closed.

Part (ii): $r\in\big{(}\frac{L}{2\sigma_{1}},\frac{L}{2\sigma_{2}}\big{]}$. We
separately consider three disjoint regions: $(\mathcal{H}_{1}^{-})^{c}$,
$\mathcal{H}_{1}^{+}\cap\mathcal{H}_{1}^{-}$, $(\mathcal{H}_{1}^{+})^{c}$. For
the first region, we want to show that

$\mathcal{T}\cap(\mathcal{H}_{1}^{-})^{c}=\emptyset\quad\text{and}\quad\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{-})^{c}=\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}.$
(34)

From Lemma 4.9 part (i), we have
$\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\subseteq\partial\mathcal{B}_{1}\cap\mathcal{H}_{1}^{+}\subseteq\textbf{dom}(\varphi)$.
Consider
$\boldsymbol{x}\in\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}$ and
note that $x_{1}\in\big{(}\lambda_{1},\;-r+\frac{L}{\sigma_{1}}\big{]}$. From
Lemma 4.5 part (i), we have $\varphi(\boldsymbol{x})>0$. Since
$\big{[}\lambda_{1},\;-r+\frac{L}{\sigma_{1}}\big{]}\subseteq(-r,r)$ from
Lemma 4.9 part (i), we can apply Lemma 4.4 to get that for all
$\boldsymbol{x}\in\overline{\mathcal{B}}_{1}\cap(\mathcal{H}_{1}^{-})^{c}$, we
have $\varphi(\boldsymbol{x})>0$. This implies that

$\overline{\mathcal{B}}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\subseteq\mathcal{T}^{c}\quad\text{and}\quad\overline{\mathcal{B}}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\subseteq\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{-})^{c},$
(35)

by Proposition 4.2 and the definition of $\mathcal{M}^{\uparrow}$ in (13),
respectively. Since $\mathcal{T}\subseteq\textbf{dom}(\varphi)$, we have
$(\overline{\mathcal{B}}_{1})^{c}\cap(\mathcal{H}_{1}^{-})^{c}\subseteq\mathcal{T}^{c}$.
Using this inclusion and the first inclusion in (35), we can write

$\emptyset=\big{[}\mathcal{T}\cap\big{(}\overline{\mathcal{B}}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{)}\big{]}\cup\big{[}\mathcal{T}\cap\big{(}(\overline{\mathcal{B}}_{1})^{c}\cap(\mathcal{H}_{1}^{-})^{c}\big{)}\big{]}=\mathcal{T}\cap(\mathcal{H}_{1}^{-})^{c},$
(36)

which completes the first part of claim (34). Next, note that since
$-r+\frac{L}{\sigma_{1}}<r$, we have
$\boldsymbol{x}_{2}^{*}\in\mathcal{H}_{1}^{+}$. However, we have
$\mathcal{M}^{\uparrow}\subseteq\overline{\mathcal{B}}_{1}$ from the
definition of $\mathcal{M}^{\uparrow}$ in (13). Combine this argument with the
second inclusion in (35) yields

$\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{-})^{c}=\overline{\mathcal{B}}_{1}\cap(\mathcal{H}_{1}^{-})^{c}.$
(37)

Since $(\mathcal{H}_{1}^{-})^{c}$ is open, (37) implies that
$(\mathcal{M}^{\uparrow})^{\circ}\cap(\mathcal{H}_{1}^{-})^{c}=\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}$.
Then, subtracting this equation from (37), we obtain that
$\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{-})^{c}=\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}$,
which completes the second part of claim (34).

Next, consider the second region
$\mathcal{H}_{1}^{+}\cap\mathcal{H}_{1}^{-}=\\{\boldsymbol{z}\in\mathbb{R}^{n}:z_{1}=\lambda_{1}\\}$.
Recall the definition of $\nu_{1}$ in (28). Consider the following three
cases.

  * •

Suppose
$\boldsymbol{x}\in\\{\boldsymbol{z}\in\mathbb{R}^{n}:z_{1}=\lambda_{1},\;\|\tilde{\mathbf{z}}\|>\nu_{1}\\}$.
Then,
$\boldsymbol{x}\in(\textbf{dom}(\varphi))^{c}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$
which implies that $\boldsymbol{x}\notin\mathcal{T}$. Since
$(\textbf{dom}(\varphi))^{c}\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}\subseteq(\mathcal{M}^{\uparrow})^{c}$
and is open, we also have
$\boldsymbol{x}\notin\partial\mathcal{M}^{\uparrow}$.

  * •

Suppose
$\boldsymbol{x}\in\\{\boldsymbol{z}\in\mathbb{R}^{n}:z_{1}=\lambda_{1},\;\|\tilde{\mathbf{z}}\|=\nu_{1}\\}$.
From Lemma 4.6 part (ii), we have $\boldsymbol{x}\in\mathcal{T}$. Using Lemma
4.8, we obtain that $\boldsymbol{x}\in\partial\mathcal{M}^{\uparrow}$.

  * •

Suppose
$\boldsymbol{x}\in\\{\boldsymbol{z}\in\mathbb{R}^{n}:z_{1}=\lambda_{1},\;\|\tilde{\mathbf{z}}\|<\nu_{1}\\}$.
Since
$\\{\boldsymbol{z}\in\mathbb{R}^{n}:z_{1}=\lambda_{1},\;\|\tilde{\mathbf{z}}\|=\nu_{1}\\}\subseteq\mathcal{T}$,
from Lemma 4.4, we have
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})>\psi(\boldsymbol{x})$
which implies that $\boldsymbol{x}\notin\mathcal{T}$. Since
$\boldsymbol{x}\in(\mathcal{B}_{1}\cap\mathcal{B}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$
and $\varphi$ is continuous, there exists $\epsilon\in\mathbb{R}_{>0}$ such
that for all $\boldsymbol{x}_{0}\in\mathcal{B}(\boldsymbol{x},\epsilon)$, we
have $\boldsymbol{x}_{0}\in\mathcal{M}^{\uparrow}$ by the definition of
$\mathcal{M}^{\uparrow}$ in (13). This means that
$\boldsymbol{x}\in(\mathcal{M}^{\uparrow})^{\circ}$ and thus,
$\boldsymbol{x}\notin\partial\mathcal{M}^{\uparrow}$.

Combining the analysis of these three cases, we have that

$\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{+}\cap\mathcal{H}_{1}^{-})=\\{\boldsymbol{z}\in\mathbb{R}^{n}:z_{1}=\lambda_{1},\;\|\tilde{\mathbf{z}}\|=\nu_{1}\\}=\mathcal{T}\cap(\mathcal{H}_{1}^{+}\cap\mathcal{H}_{1}^{-}).$
(38)

Next, consider the third region
$(\mathcal{H}_{1}^{+})^{c}=\mathbb{R}^{n}\setminus\mathcal{H}_{1}^{+}$. First,
we want to show that

$\text{if}\quad\boldsymbol{x}\in\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})\cap(\mathcal{H}_{1}^{+})^{c}\quad\text{then}\quad\boldsymbol{x}\in\\{\boldsymbol{z}\in\mathbb{R}^{n}:\varphi(\boldsymbol{z})<0\\}\cup\\{\boldsymbol{x}_{1}^{*}\\}.$
(39)

Suppose $\boldsymbol{x}\in\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})$ and
$\boldsymbol{x}\in\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{+})^{c}$. Since
$x_{1}<\lambda_{1}$, from Lemma 4.5 part (i), we obtain
$\varphi(\boldsymbol{x})<0$. By using the result from the proof of part (i),
we have that if
$\boldsymbol{x}\in\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})$ and
$\boldsymbol{x}\in\partial\mathcal{B}_{2}$ then either
$\varphi(\boldsymbol{x})<0$ or $\boldsymbol{x}=\boldsymbol{x}_{1}^{*}$.
Combining the two results, we have proved the claim.

Since
$\mathcal{M}^{\uparrow}\subseteq\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2}$
from the definition of $\mathcal{M}^{\uparrow}$ in (13) and
$\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})\cap(\mathcal{H}_{1}^{+})^{c}\subset(\mathcal{M}^{\uparrow})^{c}$
from (39), we have
$\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{+})^{c}\subseteq(\mathcal{B}_{1}\cap\mathcal{B}_{2})\cap(\mathcal{H}_{1}^{+})^{c}$.
Let $\mathcal{R}^{\prime}=\mathcal{R}\cap(\mathcal{H}_{1}^{+})^{c}$. We then
partition the set $\mathcal{R}^{\prime}$ into $\mathcal{R}_{1}^{\prime}$,
$\mathcal{R}_{2}^{\prime}$, and $\mathcal{R}_{3}^{\prime}$ where
$\mathcal{R}_{i}^{\prime}=\mathcal{R}_{i}\cap(\mathcal{H}_{1}^{+})^{c}$ for
$i\in\\{1,2,3\\}$. We can use a similar argument as in the proof of (33) to
show that

$\begin{cases}\mathcal{R}_{1}^{\prime}\subset(\partial\mathcal{M}^{\uparrow})^{c}\cap(\mathcal{H}_{1}^{+})^{c},\\\
\mathcal{R}_{2}^{\prime}\subset(\partial\mathcal{M}^{\uparrow})^{c}\cap(\mathcal{H}_{1}^{+})^{c},\\\
\mathcal{R}_{3}^{\prime}\subseteq\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{+})^{c},\\\
(\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})\setminus\\{\boldsymbol{x}_{1}^{*}\\})\cap(\mathcal{H}_{1}^{+})^{c}\subset(\partial\mathcal{M}^{\uparrow})^{c}\cap(\mathcal{H}_{1}^{+})^{c},\\\
\big{(}(\operatorname*{\textbf{dom}}(\varphi))^{c}\setminus\\{\boldsymbol{x}_{1}^{*}\\}\big{)}\cap(\mathcal{H}_{1}^{+})^{c}\subset(\partial\mathcal{M}^{\uparrow})^{c}\cap(\mathcal{H}_{1}^{+})^{c}.\end{cases}$
(40)

Since we can partition $(\mathcal{H}_{1}^{+})^{c}$ into
$\mathcal{R}^{\prime}$,
$(\partial(\mathcal{B}_{1}\cap\mathcal{B}_{2})\setminus\\{\boldsymbol{x}_{1}^{*}\\})\cap(\mathcal{H}_{1}^{+})^{c}$,
$\big{(}(\textbf{dom}(\varphi))^{c}\setminus\\{\boldsymbol{x}_{1}^{*}\\}\big{)}\cap(\mathcal{H}_{1}^{+})^{c}$
and $\\{\boldsymbol{x}_{1}^{*}\\}$, using (40), we obtain that
$\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{+})^{c}\subseteq\mathcal{R}_{3}^{\prime}\sqcup\\{\boldsymbol{x}_{1}^{*}\\}$.
However, we know that
$\mathcal{R}_{3}^{\prime}\subseteq\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{+})^{c}$
from (40) and
$\\{\boldsymbol{x}_{1}^{*}\\}\subseteq\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{+})^{c}$
from Lemma 4.3. Thus, using
$\mathcal{R}_{3}^{\prime}=\mathcal{R}_{3}\cap(\mathcal{H}_{1}^{+})^{c}$ and
Proposition 4.2 we have

$\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{+})^{c}=\mathcal{R}_{3}^{\prime}\sqcup\\{\boldsymbol{x}_{1}^{*}\\}=\big{[}\mathcal{T}\cap(\mathcal{H}_{1}^{+})^{c}\big{]}\sqcup\\{\boldsymbol{x}^{*}_{1}\\}.$
(41)

Since
$\mathbb{R}^{n}=(\mathcal{H}_{1}^{-})^{c}\sqcup(\mathcal{H}_{1}^{+}\cap\mathcal{H}_{1}^{-})\sqcup(\mathcal{H}_{1}^{+})^{c}$,
using (34), (38) and (41), we obtain that

$\partial\mathcal{M}^{\uparrow}=\big{[}\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\big{[}\mathcal{T}\cap(\mathcal{H}_{1}^{+}\cap\mathcal{H}_{1}^{-})\big{]}\sqcup\big{[}\mathcal{T}\cap(\mathcal{H}_{1}^{+})^{c}\big{]}\sqcup\\{\boldsymbol{x}^{*}_{1}\\}.$
(42)

However, from (36), we can write
$\mathcal{T}=\big{[}\mathcal{T}\cap(\mathcal{H}_{1}^{+}\cap\mathcal{H}_{1}^{-})\big{]}\sqcup\big{[}\mathcal{T}\cap(\mathcal{H}_{1}^{+})^{c}\big{]}$
which means that we can rewrite (42) as

$\partial\mathcal{M}^{\uparrow}=\big{[}\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\mathcal{T}\sqcup\\{\boldsymbol{x}^{*}_{1}\\}.$
(43)

From (37) and (43), we can write
$\big{[}\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\setminus\big{[}\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}=\big{[}\overline{\mathcal{B}}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\setminus\big{[}\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}=\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}$.
From the definition of $\mathcal{M}^{\uparrow}$ in (13) and equation (38), we
can write
$\big{[}\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{+}\cap\mathcal{H}_{1}^{-})\big{]}\setminus\big{[}\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{+}\cap\mathcal{H}_{1}^{-})\big{]}=\widetilde{\mathcal{T}}\cap(\mathcal{H}_{1}^{+}\cap\mathcal{H}_{1}^{-})$.
From the definition of $\mathcal{M}^{\uparrow}$ in (13) and equation (41), we
can write
$(\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{+})^{c})\setminus(\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{+})^{c})=\widetilde{\mathcal{T}}\cap(\mathcal{H}_{1}^{+})^{c}$.
Applying the above three equations to Lemma 2.1, we obtain the result of
$(\mathcal{M}^{\uparrow})^{\circ}$. Consider the characterization of
$\partial\mathcal{M}^{\uparrow}$ in (43). Since
$\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\subseteq\mathcal{M}^{\uparrow}$
from (37), and $\mathcal{T}\subseteq\mathcal{M}^{\uparrow}$ from Proposition
4.2 and the definition of $\mathcal{M}^{\uparrow}$, we can write
$\partial\mathcal{M}^{\uparrow}\subseteq\mathcal{M}^{\uparrow}\sqcup\\{\boldsymbol{x}^{*}_{1}\\}$
and thus, $\mathcal{M}^{\uparrow}\sqcup\\{\boldsymbol{x}^{*}_{1}\\}$ is
closed.

Part (iii):
$r\in\Big{(}\frac{L}{2\sigma_{2}},\;\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}\Big{)}$.
We can use a similar argument as in the proof of part (ii) to show that

$\begin{cases}\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{-})^{c}=\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\subseteq\mathcal{M}^{\uparrow},\quad\text{(similar
to proving \eqref{eqn: nc thm part2.1})}\\\
\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{2}^{+})^{c}=\partial\mathcal{B}_{2}\cap(\mathcal{H}_{2}^{+})^{c}\subseteq\mathcal{M}^{\uparrow},\quad\text{(similar
to proving \eqref{eqn: nc thm part2.1})}\\\
\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{+}\cap\mathcal{H}_{1}^{-})=\mathcal{T}\cap(\mathcal{H}_{1}^{+}\cap\mathcal{H}_{1}^{-})\subseteq\mathcal{M}^{\uparrow},\quad\text{(similar
to proving \eqref{eqn: nc thm part2.2})}\\\
\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{2}^{+}\cap\mathcal{H}_{2}^{-})=\mathcal{T}\cap(\mathcal{H}_{2}^{+}\cap\mathcal{H}_{2}^{-})\subseteq\mathcal{M}^{\uparrow},\quad\text{(similar
to proving \eqref{eqn: nc thm part2.2})}\\\
\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{+}\cup\mathcal{H}_{2}^{-})^{c}=\mathcal{T}\cap(\mathcal{H}_{1}^{+}\cup\mathcal{H}_{2}^{-})^{c}\subseteq\mathcal{M}^{\uparrow}.\quad\text{(similar
to proving \eqref{eqn: nc thm part2.3})}\\\ \end{cases}$

Similar to (36), in this case, we have that
$\mathcal{T}\cap(\mathcal{H}_{1}^{-})^{c}=\emptyset$ and
$\mathcal{T}\cap(\mathcal{H}_{2}^{+})^{c}=\emptyset$. This means that the last
three equations regarding $\partial\mathcal{M}^{\uparrow}$ above can be
combined into
$\partial\mathcal{M}^{\uparrow}\cap(\mathcal{H}_{1}^{-}\cap\mathcal{H}_{2}^{+})=\mathcal{T}$.
Combining this equation with the first two equations regarding
$\partial\mathcal{M}^{\uparrow}$ above, we obtain the characterization of
$\partial\mathcal{M}^{\uparrow}$. For the characterization of
$(\mathcal{M}^{\uparrow})^{\circ}$, we can use the same technique as shown in
the analysis of part (ii) to obtain the result. From the five inclusions
regarding $\partial\mathcal{M}^{\uparrow}$ above, we can write
$\partial\mathcal{M}^{\uparrow}\subseteq\mathcal{M}^{\uparrow}$ and we
conclude that $\mathcal{M}^{\uparrow}$ is closed.

Part (iv):
$r=\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}$. In
this case, we have
$\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2}=\Big{\\{}\Big{(}\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}-\frac{1}{\sigma_{2}}\big{)},\;\mathbf{0}\Big{)}\Big{\\}}$.
Suppose
$\boldsymbol{x}=\Big{(}\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}-\frac{1}{\sigma_{2}}\big{)},\;\mathbf{0}\Big{)}$.
Since
$\mathcal{M}^{\uparrow}\subseteq\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2}$,
we only need to check point $\boldsymbol{x}$. At this point, we get
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})=\psi(\boldsymbol{x})=0$
(since $d_{1}(\boldsymbol{x})=\frac{L}{\sigma_{1}}$,
$d_{2}(\boldsymbol{x})=\frac{L}{\sigma_{2}}$, $\alpha_{1}(\boldsymbol{x})=0$
and $\alpha_{2}(\boldsymbol{x})=\pi$). So, we conclude that
$\mathcal{M}^{\uparrow}=\Big{\\{}\Big{(}\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}-\frac{1}{\sigma_{2}}\big{)},\;\mathbf{0}\Big{)}\Big{\\}}$.

Part (v):
$r\in\Big{(}\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)},\;\infty\Big{)}$.
Since $r>\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}$,
we have $\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2}=\emptyset$.
Since
$\mathcal{M}^{\uparrow}\subseteq\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2}$,
we conclude that $\mathcal{M}^{\uparrow}=\emptyset$. ∎

Examples of the boundary $\partial\mathcal{M}^{\uparrow}$ in $\mathbb{R}^{2}$
for the first three cases of Theorem 4.10 are shown in Fig. 3. We consider
parameters $\sigma_{1}=1.5$, $\sigma_{2}=1$ and $L=10$. For $r=2$, as we can
see from Fig. 3a, we have
$\partial\mathcal{M}^{\uparrow}=\mathcal{T}\sqcup\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$
(i.e., solid blue line + two red dots) consistent with part (i) of Theorem
4.10. For $r=4$, as we can see from Fig. 3b, we have
$\partial\mathcal{M}^{\uparrow}=\big{[}\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\mathcal{T}\sqcup\\{\boldsymbol{x}^{*}_{1}\\}$
(i.e., solid cyan line + solid blue line + left red dot) consistent with part
(ii) of Theorem 4.10. For $r=6$, as we can see from Fig. 3c, we have
$\partial\mathcal{M}^{\uparrow}=\big{[}\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\big{[}\partial\mathcal{B}_{2}\cap(\mathcal{H}_{2}^{+})^{c}\big{]}\sqcup\mathcal{T}$
(i.e., solid cyan line + solid magenta line + solid blue line) consistent with
part (iii) of Theorem 4.10. Note that the solid blue line, solid cyan line and
solid magenta line in the figures indicate that the corresponding sets of
points are subsets of the outer approximation $\mathcal{M}^{\uparrow}$, i.e.,
$\mathcal{T}\subseteq\mathcal{M}^{\uparrow}$,
$\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\subseteq\mathcal{M}^{\uparrow}$
and
$\partial\mathcal{B}_{2}\cap(\mathcal{H}_{2}^{+})^{c}\subseteq\mathcal{M}^{\uparrow}$,
respectively.

(a) For $r=2$, the characterization of boundary
$\partial\mathcal{M}^{\uparrow}$ corresponds to Theorem 4.10 part (i).

(b) For $r=4$, the characterization of boundary
$\partial\mathcal{M}^{\uparrow}$ corresponds to Theorem 4.10 part (ii).

(c) For $r=6$, the characterization of boundary
$\partial\mathcal{M}^{\uparrow}$ corresponds to Theorem 4.10 part (iii).

Figure 3: The boundary $\partial\mathcal{M}^{\uparrow}$ in $\mathbb{R}^{2}$
with different values of $r$ for two original minimizers $x_{1}^{*}=(-r,0)$
and $x_{2}^{*}=(r,0)$ is plotted given fixed parameters $\sigma_{1}=1.5$,
$\sigma_{2}=1$, and $L=10$. The sets $\mathcal{T}$,
$\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}$ and
$\partial\mathcal{B}_{2}\cap(\mathcal{H}_{2}^{+})^{c}$ are shown by solid
blue, cyan and magenta lines, respectively. The vertical dotted lines
represent the equations $x_{1}=\lambda_{1}$ and $x_{1}=\lambda_{2}$ and note
that the value of $\lambda_{1}$ and $\lambda_{2}$ depends on $r$.

##  5 Inner Approximation and Potential Solution Region

In the previous section, we showed that the set $\mathcal{M}^{\uparrow}$
defined in (13) is an outer approximation for the desired set $\mathcal{M}$
defined in (7), in that $\mathcal{M}\subseteq\mathcal{M}^{\uparrow}$. We now
turn our attention to the set $\mathcal{M}_{\downarrow}$ defined in (14). We
will show that $\mathcal{M}_{\downarrow}\subseteq\mathcal{M}$, and
consequently, provide a tight characterization of $\mathcal{M}$.

Since we have
$\bigcup_{\tilde{\sigma}\geq\sigma}\mathcal{Q}(\boldsymbol{x}^{*},\tilde{\sigma})\subset\mathcal{S}(\boldsymbol{x}^{*},\sigma)$
for all $\boldsymbol{x}^{*}\in\mathbb{R}^{n}$ and $\sigma\in\mathbb{R}_{>0}$
from (5), we can provide a region contained in the potential solution region
$\mathcal{M}$ by restricting our consideration to only some classes of
quadratic functions. In Section 5.1, we analyze a sufficient and necessary
condition for constructing a quadratic function with a given minimizer,
gradient and curvature. Then, using the result from Section 5.1, in Section
5.2, we prove a relationship between the potential solution region
$\mathcal{M}$ and the inner approximation $\mathcal{M}_{\downarrow}$, and also
provide a characterization of $\mathcal{M}_{\downarrow}$.

###  5.1 Quadratic Functions Analysis

In this subsection, first we consider an equivalent condition for the
existence of a quadratic function with a given minimizer, gradient at a
specific point and the smallest eigenvalue associated to the quadratic term in
$n$-dimensional space (i.e., in $\mathbb{R}^{n}$) which is presented in
Proposition 5.1. Then, we present Corollary 5.2 in which we provide a similar
equivalent condition for the class
$\bigcup_{\tilde{\sigma}\geq\sigma}\mathcal{Q}(\boldsymbol{x}^{*},\tilde{\sigma})$
for a given $\boldsymbol{x}^{*}\in\mathbb{R}^{n}$ and
$\sigma\in\mathbb{R}_{>0}$.

In the following proposition (whose proof is provided in Appendix B.1), we
consider an equivalent condition for the existence of a quadratic function
with more than one independent variable satisfying certain properties.

######  Proposition 5.1.

Let $\mathcal{Q}$ be defined as in (4). For $n\in\mathbb{N}\setminus\\{1\\}$,
suppose we are given points $\boldsymbol{x}^{*}\in\mathbb{R}^{n}$ and
$\boldsymbol{x}_{0}\in\mathbb{R}^{n}$ such that
$\boldsymbol{x}_{0}\neq\boldsymbol{x}^{*}$, vector
$\boldsymbol{g}\in\mathbb{R}^{n}$, and scalar $\sigma\in\mathbb{R}_{>0}$.
Then, there exists a function
$f\in\mathcal{Q}^{(n)}(\boldsymbol{x}^{*},\sigma)$ with a gradient $\nabla
f(\boldsymbol{x}_{0})=\boldsymbol{g}$ if and only if

  1. (i)

$\boldsymbol{x}_{0}\in\overline{\mathcal{B}}\big{(}\boldsymbol{x}^{*},\frac{\|\boldsymbol{g}\|}{\sigma}\big{)}$
and

  2. (ii)

$\angle(\boldsymbol{g},\boldsymbol{x}_{0}-\boldsymbol{x}^{*})\in\\{0\\}\cup\Big{[}0,\;\arccos\big{(}\frac{\sigma}{\|\boldsymbol{g}\|}\|\boldsymbol{x}_{0}-\boldsymbol{x}^{*}\|\big{)}\Big{)}$.

Note that if
$\sigma\|\boldsymbol{x}_{0}-\boldsymbol{x}^{*}\|=\|\boldsymbol{g}\|$, then
$\Big{[}0,\;\arccos(\frac{\sigma}{\|\boldsymbol{g}\|}\|\boldsymbol{x}_{0}-\boldsymbol{x}^{*}\|)\Big{)}=\emptyset$.

Recall from (5) that
$\bigcup_{\hat{\sigma}\geq\sigma}\mathcal{Q}(\boldsymbol{x}^{*},\hat{\sigma})\subset\mathcal{S}(\boldsymbol{x}^{*},\sigma)$
for all $\boldsymbol{x}^{*}\in\mathbb{R}^{n}$ and $\sigma\in\mathbb{R}_{>0}$.
One way to characterize the inner approximation $\mathcal{M}_{\downarrow}$ is
to utilize sufficient conditions for the construction of a function
$f\in\bigcup_{\hat{\sigma}\geq\sigma}\mathcal{Q}(\boldsymbol{x}^{*},\hat{\sigma})$.
More generally, the following corollary presents necessary and sufficient
conditions for such construction.

######  Corollary 5.2.

Let $\mathcal{Q}$ be defined as in (4). For $n\in\mathbb{N}\setminus\\{1\\}$,
suppose we are given points $\boldsymbol{x}^{*}\in\mathbb{R}^{n}$ and
$\boldsymbol{x}_{0}\in\mathbb{R}^{n}$ such that
$\boldsymbol{x}_{0}\neq\boldsymbol{x}^{*}$, a vector
$\boldsymbol{g}\in\mathbb{R}^{n}$, scalar $L\in\mathbb{R}_{>0}$ such that
$\|\boldsymbol{g}\|=L$, and a scalar $\sigma\in\mathbb{R}_{>0}$. Then, there
exists a function
$f\in\bigcup_{\hat{\sigma}\geq\sigma}\mathcal{Q}(\boldsymbol{x}^{*},\hat{\sigma})$
with $\nabla f(\boldsymbol{x}_{0})=\boldsymbol{g}$ if and only if

  1. (i)

$\boldsymbol{x}_{0}\in\overline{\mathcal{B}}\big{(}\boldsymbol{x}^{*},\frac{L}{\sigma}\big{)}$
and

  2. (ii)

$\angle(\boldsymbol{g},\;\boldsymbol{x}_{0}-\boldsymbol{x}^{*})\in\\{0\\}\cup\Big{[}0,\;\arccos\big{(}\frac{\sigma}{L}\|\boldsymbol{x}_{0}-\boldsymbol{x}^{*}\|\big{)}\Big{)}$.

Note that if $\sigma\|\boldsymbol{x}_{0}-\boldsymbol{x}^{*}\|=L$, then
$\Big{[}0,\;\arccos(\frac{\sigma}{L}\|\boldsymbol{x}_{0}-\boldsymbol{x}^{*}\|)\Big{)}=\emptyset$.

###### Proof.

From Proposition 5.1, we can write that there exists a function
$f\in\bigcup_{\hat{\sigma}\geq\sigma}\mathcal{Q}(\boldsymbol{x}^{*},\hat{\sigma})$
with a gradient $\nabla f(\boldsymbol{x}_{0})=\boldsymbol{g}$ and $\|\nabla
f(\boldsymbol{x}_{0})\|=L$ if and only if

$\boldsymbol{x}_{0}\in\bigcup_{\hat{\sigma}\geq\sigma}\overline{\mathcal{B}}\Big{(}\boldsymbol{x}^{*},\frac{\|\boldsymbol{g}\|}{\hat{\sigma}}\Big{)}=\overline{\mathcal{B}}\Big{(}\boldsymbol{x}^{*},\frac{L}{\sigma}\Big{)},$

and

$\displaystyle\angle(\boldsymbol{g},\;\boldsymbol{x}_{0}-\boldsymbol{x}^{*})$
$\displaystyle\in\\{0\\}\cup\bigcup_{\hat{\sigma}\geq\sigma}\bigg{[}0,\;\arccos\Big{(}\frac{\hat{\sigma}}{\|\boldsymbol{g}\|}\|\boldsymbol{x}_{0}-\boldsymbol{x}^{*}\|\Big{)}\bigg{)}$
$\displaystyle=\\{0\\}\cup\bigg{[}0,\;\arccos\Big{(}\frac{\sigma}{L}\|\boldsymbol{x}_{0}-\boldsymbol{x}^{*}\|\Big{)}\bigg{)}.$

∎

###  5.2 Inner Approximation Characterization

In this subsection, we use results from Section 5.1 to derive a sufficient
condition for a point to be in the potential solution region $\mathcal{M}$,
defined in (7). In fact, the sufficient condition is encapsulated in the
description of the inner approximation $\mathcal{M}_{\downarrow}$; therefore,
$\mathcal{M}_{\downarrow}\subseteq\mathcal{M}$ which is presented in
Proposition 5.3. Then, in Theorem 5.4, we characterize the boundary
$\partial\mathcal{M}_{\downarrow}$ and interior
$(\mathcal{M}_{\downarrow})^{\circ}$, and provide a property of
$\mathcal{M}_{\downarrow}$ similar to Theorem 4.10.

Recall the definition of $\underline{L}_{i}$ for $i\in\\{1,2\\}$ from (17).
Given $i\in\\{1,2\\}$, $\boldsymbol{x}_{i}^{*}\in\mathbb{R}^{n}$,
$\sigma_{i}\in\mathbb{R}_{>0}$, and $L\in\mathbb{R}_{>0}$, from Corollary 5.2,
we define the set of gradient angles $\angle(\nabla
f_{i}(\boldsymbol{x}),\;\boldsymbol{x}-\boldsymbol{x}_{i}^{*})$ that we can
choose to construct a quadratic function
$f_{i}\in\bigcup_{\hat{\sigma}_{i}\geq\sigma_{i}}\mathcal{Q}(\boldsymbol{x}_{i}^{*},\hat{\sigma}_{i})$
with $\|\nabla f_{i}(\boldsymbol{x})\|\leq L$ as
$\Phi_{i}:\overline{\mathcal{B}}\big{(}\boldsymbol{x}^{*}_{i},\frac{L}{\sigma_{i}}\big{)}\to
2^{[0,\frac{\pi}{2})}$ with

$\displaystyle\Phi_{i}(\boldsymbol{x})\triangleq\begin{cases}\Big{[}0,\;\arccos\big{(}\frac{\underline{L}_{i}(\boldsymbol{x})}{L}\big{)}\Big{)}\quad&\text{if}\quad\underline{L}_{i}(\boldsymbol{x})<L,\\\
\\{0\\}\quad&\text{if}\quad\underline{L}_{i}(\boldsymbol{x})=L.\end{cases}$
(44)

Notice that the supremum of the set of angles $\Phi_{i}(\boldsymbol{x})$ is
equal to $\tilde{\phi}_{i}(\boldsymbol{x})$ which is defined in (9). That is,
for $i\in\\{1,2\\}$, for all
$\boldsymbol{x}\in\overline{\mathcal{B}}\big{(}\boldsymbol{x}_{i}^{*},\frac{L}{\sigma_{i}}\big{)}$,
we have

$\displaystyle\sup\Phi_{i}(\boldsymbol{x})=\arccos\Big{(}\frac{\underline{L}_{i}(\boldsymbol{x})}{L}\Big{)}=\tilde{\phi}_{i}(\boldsymbol{x}).$

In two-dimensional space, for a given
$\boldsymbol{x}\in\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2}$,
for $i\in\\{1,2\\}$, the set of admissible angles $\Phi_{i}(\boldsymbol{x})$
and the quantity $\tilde{\phi}_{i}(\boldsymbol{x})$ are shown in Fig. 4a. In
the next proposition, using Corollary 5.2, we show that the inner
approximation $\mathcal{M}_{\downarrow}$ is contained in the potential
solution region $\mathcal{M}$.

######  Proposition 5.3.

Suppose the sets $\mathcal{M}$ and $\mathcal{M}_{\downarrow}$ are defined as
in (7) and (14), respectively. Then,
$\mathcal{M}\supseteq\mathcal{M}_{\downarrow}$.

###### Proof.

Suppose
$\boldsymbol{x}\in(\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.
Recall the definition of $\mathcal{X}$ from (12). We want to show that if
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})>\psi(\boldsymbol{x})$
or $\boldsymbol{x}\in\mathcal{X}$, then $\boldsymbol{x}\in\mathcal{M}$. Recall
the definition of $\boldsymbol{u}_{i}(\boldsymbol{x})$ for $i\in\\{1,2\\}$
from (15). Consider the following two cases.

  * •

Suppose
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})>\psi(\boldsymbol{x})$.
Since
$\psi(\boldsymbol{x})=\angle(\boldsymbol{u}_{1}(\boldsymbol{x}),-\boldsymbol{u}_{2}(\boldsymbol{x}))$
from (20), there exists a vector $\boldsymbol{g}\in\mathbb{R}^{n}$ with
$\|\boldsymbol{g}\|=L$ such that
$\angle(\boldsymbol{g},\boldsymbol{u}_{1}(\boldsymbol{x}))<\tilde{\phi}_{1}(\boldsymbol{x})$
and
$\angle(\boldsymbol{g},-\boldsymbol{u}_{2}(\boldsymbol{x}))<\tilde{\phi}_{2}(\boldsymbol{x})$.
By the definition of $\Phi_{i}$ in (44), this means that
$\angle(\boldsymbol{g},\boldsymbol{u}_{1}(\boldsymbol{x}))\in\Phi_{1}(\boldsymbol{x})$
and
$\angle(-\boldsymbol{g},\boldsymbol{u}_{2}(\boldsymbol{x}))\in\Phi_{2}(\boldsymbol{x})$.

  * •

Suppose $\boldsymbol{x}\in\mathcal{X}$. Then, the point
$\boldsymbol{x}=\big{(}-r+\frac{L}{\sigma_{1}},\mathbf{0}\big{)}$ and
$-r+\frac{L}{\sigma_{1}}\in(-r,r)$ as discussed below (12). In this case, we
choose $\boldsymbol{g}=L\boldsymbol{e}^{\prime}_{1}$ where
$\boldsymbol{e}^{\prime}_{1}=\frac{\boldsymbol{x}_{2}^{*}-\boldsymbol{x}_{1}^{*}}{\|\boldsymbol{x}_{2}^{*}-\boldsymbol{x}_{1}^{*}\|}$.
This implies that
$\angle(\boldsymbol{g},\boldsymbol{u}_{1}(\boldsymbol{x}))=0\in\Phi_{1}(\boldsymbol{x})$
and
$\angle(-\boldsymbol{g},\boldsymbol{u}_{2}(\boldsymbol{x}))=0\in\Phi_{2}(\boldsymbol{x})$
by the definition of $\Phi_{i}$ in (44).

Using Corollary 5.2, for both cases, we have that for $i\in\\{1,2\\}$, there
exist functions
$f_{i}\in\bigcup_{\hat{\sigma}>\sigma}\mathcal{Q}(\boldsymbol{x}_{i}^{*},\hat{\sigma})$
such that $\boldsymbol{g}=\nabla f_{1}(\boldsymbol{x})=-\nabla
f_{2}(\boldsymbol{x})$ and $\|\nabla f_{1}(\boldsymbol{x})\|=\|\nabla
f_{2}(\boldsymbol{x})\|=L$. Using (5), we have that there exist
$f_{i}\in\mathcal{S}(\boldsymbol{x}_{i}^{*},\sigma)$ with $\|\nabla
f_{i}(\boldsymbol{x})\|\leq L$ for $i\in\\{1,2\\}$ and $\boldsymbol{x}$ is the
minimizer of $f_{1}+f_{2}$. Therefore, $\boldsymbol{x}\in\mathcal{M}$. Since
$\mathcal{M}_{\downarrow}\subseteq(\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$,
we conclude that $\mathcal{M}\supseteq\mathcal{M}_{\downarrow}$. ∎

(a)

(b)

Figure 4: (a) For given $\boldsymbol{x}$, $\boldsymbol{x}^{*}$ and $\sigma$,
the figure illustrates the regions where the vectors $\boldsymbol{g}_{1}$ and
$\boldsymbol{g}_{2}$ with $\|\boldsymbol{g}_{1}\|=\|\boldsymbol{g}_{2}\|=L$
must lie, so that we can construct quadratic functions
$f_{i}\in\bigcup_{\hat{\sigma}\geq\sigma}\mathcal{Q}(\boldsymbol{x}^{*},\hat{\sigma})$
with $\nabla f_{i}(\boldsymbol{x})=\boldsymbol{g}_{i}$ for $i\in\\{1,2\\}$.
Recall the definition of $\phi_{i}$ and $\Phi_{i}$ from (16) and (44),
respectively. In particular, for $i\in\\{1,2\\}$, it is sufficient to have
$\phi_{i}(\boldsymbol{x})\in\Phi_{i}(\boldsymbol{x})$ from Corollary 5.2,
i.e., pictorially, the vectors $\boldsymbol{g}_{1}$ and $\boldsymbol{g}_{2}$
must strictly lie in the corresponding shaded regions. (b) The figure
illustrates the inequality
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})>\psi(\boldsymbol{x})$
in the description of $\mathcal{M}_{\downarrow}$ which means that there is an
overlapping region (light green region in the figure) caused by one shaded
region and the mirror of the other shaded region.

In two-dimensional space, for a given
$\boldsymbol{x}\in(\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$,
the geometrical interpretation of the inequality
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})>\psi(\boldsymbol{x})$,
which is used to describe the inner approximation $\mathcal{M}_{\downarrow}$,
is represented in Fig. 4b.

Before characterizing the set $\mathcal{M}_{\downarrow}$, recall the
definition of $\lambda_{i}$ and $\nu_{i}$ in (27) and (28), respectively. For
$i\in\\{1,2\\}$, we define

$\mathcal{C}_{i}\triangleq\big{\\{}\boldsymbol{x}\in\mathbb{R}^{n}:x_{1}=\lambda_{i},\;\;\|\tilde{\mathbf{x}}\|=\nu_{i}\big{\\}}.$
(45)

Comparing the definition of $\mathcal{M}^{\uparrow}$ in (13) to that of
$\mathcal{M}_{\downarrow}$ in (14), we see that the description of
$\mathcal{M}_{\downarrow}$ involves a strict inequality while it is not for
$\mathcal{M}^{\uparrow}$. Since the only difference is the inequality sign, we
could expect to see similar results as in Theorem 4.10. Specifically, the
following theorem provides a characterization of
$\partial\mathcal{M}_{\downarrow}$ and $(\mathcal{M}_{\downarrow})^{\circ}$
explicitly, and also a property of $\mathcal{M}_{\downarrow}$. Since most
parts of the proof are similar to that of Theorem 4.10, we defer the proof to
Appendix B.2.

######  Theorem 5.4.

Assume $\sigma_{1}\geq\sigma_{2}$. Let the sets $\mathcal{M}_{\downarrow}$,
$\mathcal{T}$, $\widetilde{\mathcal{T}}$, and $\mathcal{B}_{i}$ for
$i\in\\{1,2\\}$ be defined as in (13), (22), (30), and (8), respectively.
Also, let the sets $\mathcal{H}_{i}^{+}$ and $\mathcal{H}_{i}^{-}$ for
$i\in\\{1,2\\}$ be defined as in (29), and the sets $\mathcal{C}_{i}$ for
$i\in\\{1,2\\}$ be defined as in (45).

  1. (i)

If $r\in\big{(}0,\;\frac{L}{2\sigma_{1}}\big{]}$ then
$\mathcal{M}_{\downarrow}$ is open and

$\partial\mathcal{M}_{\downarrow}=\mathcal{T}\sqcup\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}\quad\text{and}\quad(\mathcal{M}_{\downarrow})^{\circ}=\widetilde{\mathcal{T}}.$

  2. (ii)

If $r\in\big{(}\frac{L}{2\sigma_{1}},\;\frac{L}{2\sigma_{2}}\big{]}$ then
$(\mathcal{M}_{\downarrow}\cup\mathcal{C}_{1})\cap\mathcal{H}_{1}^{+}$ is
closed while $\mathcal{M}_{\downarrow}\cap(\mathcal{H}_{1}^{+})^{c}$ is open,
and

$\displaystyle\partial\mathcal{M}_{\downarrow}$
$\displaystyle=\big{[}\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\mathcal{T}\sqcup\\{\boldsymbol{x}^{*}_{1}\\}\quad\text{and}$
$\displaystyle(\mathcal{M}_{\downarrow})^{\circ}$
$\displaystyle=\big{[}\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\big{[}\widetilde{\mathcal{T}}\cap\mathcal{H}_{1}^{-}\big{]}.$

  3. (iii)

If
$r\in\Big{(}\frac{L}{2\sigma_{2}},\;\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}\Big{)}$
then $(\mathcal{M}_{\downarrow}\cup\mathcal{C}_{1})\cap\mathcal{H}_{1}^{+}$
and $(\mathcal{M}_{\downarrow}\cup\mathcal{C}_{2})\cap\mathcal{H}_{2}^{-}$ are
closed while
$\mathcal{M}_{\downarrow}\cap(\mathcal{H}_{1}^{+}\cup\mathcal{H}_{2}^{-})^{c}$
is open, and

$\displaystyle\partial\mathcal{M}_{\downarrow}$
$\displaystyle=\big{[}\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\big{[}\partial\mathcal{B}_{2}\cap(\mathcal{H}_{2}^{+})^{c}\big{]}\sqcup\mathcal{T}\quad\text{and}$
$\displaystyle(\mathcal{M}_{\downarrow})^{\circ}$
$\displaystyle=\big{[}\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\big{[}\mathcal{B}_{2}\cap(\mathcal{H}_{2}^{+})^{c}\big{]}\sqcup\big{[}\widetilde{\mathcal{T}}\cap(\mathcal{H}_{1}^{-}\cap\mathcal{H}_{2}^{+})\big{]}.$

  4. (iv)

If $r=\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}$ then
$\mathcal{M}_{\downarrow}=\Big{\\{}\Big{(}\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}-\frac{1}{\sigma_{2}}\big{)},\;\mathbf{0}\Big{)}\Big{\\}}$.

  5. (v)

If
$r\in\Big{(}\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)},\;\infty\Big{)}$
then $\mathcal{M}_{\downarrow}=\emptyset$.

Examples of the boundary $\partial\mathcal{M}_{\downarrow}$ in
$\mathbb{R}^{2}$ for the first three cases of Theorem 5.4 are shown in Fig. 5.
Again, we consider parameters $\sigma_{1}=1.5$, $\sigma_{2}=1$ and $L=10$. For
$r=2$, as we can see from Fig. 5a, we have
$\partial\mathcal{M}_{\downarrow}=\mathcal{T}\sqcup\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$
(i.e., dotted blue line + two red dots) consistent with part (i) of Theorem
5.4. For $r=4$, as we can see from Fig. 5b, we have
$\partial\mathcal{M}_{\downarrow}=\big{[}\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\mathcal{T}\sqcup\\{\boldsymbol{x}^{*}_{1}\\}$
(i.e., solid cyan line + dotted blue line + left red dot) consistent with part
(ii) of Theorem 5.4. For $r=6$, as we can see from Fig. 5c, we have
$\partial\mathcal{M}_{\downarrow}=\big{[}\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\big{[}\partial\mathcal{B}_{2}\cap(\mathcal{H}_{2}^{+})^{c}\big{]}\sqcup\mathcal{T}$
(i.e., solid cyan line + solid magenta line + dotted blue line) consistent
with part (iii) of Theorem 5.4. Note that the dotted blue line in the figures
indicates that the corresponding set of points is not a subset of the inner
approximation $\mathcal{M}_{\downarrow}$, i.e.,
$\mathcal{T}\not\subseteq\mathcal{M}_{\downarrow}$ whereas the solid cyan line
and solid magenta line indicate that
$\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\subseteq\mathcal{M}_{\downarrow}$
and
$\partial\mathcal{B}_{2}\cap(\mathcal{H}_{2}^{+})^{c}\subseteq\mathcal{M}_{\downarrow}$,
respectively.

(a) For $r=2$, the characterization of boundary
$\partial\mathcal{M}_{\downarrow}$ corresponds to Theorem 5.4 part (i).

(b) For $r=4$, the characterization of boundary
$\partial\mathcal{M}_{\downarrow}$ corresponds to Theorem 5.4 part (ii).

(c) For $r=6$, the characterization of boundary
$\partial\mathcal{M}_{\downarrow}$ corresponds to Theorem 5.4 part (iii).

Figure 5: The boundary $\partial\mathcal{M}_{\downarrow}$ in $\mathbb{R}^{2}$
with different values of $r$ for two original minimizers $x_{1}^{*}=(-r,0)$
and $x_{2}^{*}=(r,0)$ is plotted given fixed parameters $\sigma_{1}=1.5$,
$\sigma_{2}=1$, and $L=10$. The set $\mathcal{T}$ is represented by blue
dashed lines since $\mathcal{T}\subseteq(\mathcal{M}_{\downarrow})^{c}$, while
the sets $\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}$ and
$\partial\mathcal{B}_{2}\cap(\mathcal{H}_{2}^{+})^{c}$ are represented by cyan
and magenta solid lines, respectively since they are both subsets of
$\mathcal{M}_{\downarrow}$. The vertical dotted lines represent the equations
$x_{1}=\lambda_{1}$ and $x_{1}=\lambda_{2}$ and note that the value of
$\lambda_{1}$ and $\lambda_{2}$ depends on $r$.

##  6 Potential Solution Region

In this section, using results from analyzing the outer approximation
$\mathcal{M}^{\uparrow}$ in Section 4 and the inner approximation
$\mathcal{M}_{\downarrow}$ in Section 5.2, we derive relationships among the
potential solution region $\mathcal{M}$ (which is the set that we want to
identify), outer approximation $\mathcal{M}^{\uparrow}$ and inner
approximation $\mathcal{M}_{\downarrow}$.

Before stating the main theorem, we summarize the inclusions among the three
sets. Specifically, based on Proposition 4.1 and Proposition 5.3, we get
$\mathcal{M}\subseteq\mathcal{M}^{\uparrow}$ and
$\mathcal{M}_{\downarrow}\subseteq\mathcal{M}$, respectively, and we can state
the following proposition.

######  Proposition 6.1.

Suppose the sets $\mathcal{M}$, $\mathcal{M}^{\uparrow}$ and
$\mathcal{M}_{\downarrow}$ are defined as in (7), (13) and (14), respectively.
Then,
$\mathcal{M}_{\downarrow}\subseteq\mathcal{M}\subseteq\mathcal{M}^{\uparrow}$.

Since Theorem 4.10 and Theorem 5.4 are similar, we will see that, in fact, the
boundary of the outer approximation $\partial\mathcal{M}^{\uparrow}$ and inner
approximation $\partial\mathcal{M}_{\downarrow}$ are equal to the boundary of
the potential solution region $\partial\mathcal{M}$ for all values of $r$.
This means that we obtain the explicit characterization of
$\partial\mathcal{M}$ from Theorem 4.10 or Theorem 5.4. We present this result
in the following theorem.

######  Theorem 6.2.

Suppose $\mathcal{M}$, $\mathcal{M}^{\uparrow}$ and $\mathcal{M}_{\downarrow}$
are defined as in (7), (13) and (14), respectively. Then,
$\partial\mathcal{M}=\partial\mathcal{M}^{\uparrow}=\partial\mathcal{M}_{\downarrow}$.

###### Proof.

Recall from Proposition 6.1 that
$\mathcal{M}_{\downarrow}\subseteq\mathcal{M}\subseteq\mathcal{M}^{\uparrow}$.
This entails that
$(\mathcal{M}_{\downarrow})^{\circ}\subseteq(\mathcal{M})^{\circ}\subseteq(\mathcal{M}^{\uparrow})^{\circ}$
and
$\overline{\mathcal{M}_{\downarrow}}\subseteq\overline{\mathcal{M}}\subseteq\overline{\mathcal{M}^{\uparrow}}$.
On the other hand, we have
$(\mathcal{M}_{\downarrow})^{\circ}=(\mathcal{M}^{\uparrow})^{\circ}$ and
$\partial\mathcal{M}_{\downarrow}=\partial\mathcal{M}^{\uparrow}$ from Theorem
4.10 and Theorem 5.4. Combine the facts regarding the interiors to obtain that
$(\mathcal{M}_{\downarrow})^{\circ}=(\mathcal{M})^{\circ}=(\mathcal{M}^{\uparrow})^{\circ}$.
Then, we can write

$\overline{\mathcal{M}_{\downarrow}}=(\mathcal{M}_{\downarrow})^{\circ}\sqcup\partial\mathcal{M}_{\downarrow}=(\mathcal{M}^{\uparrow})^{\circ}\sqcup\partial\mathcal{M}^{\uparrow}=\overline{\mathcal{M}^{\uparrow}}.$

Combining the above equation with
$\overline{\mathcal{M}_{\downarrow}}\subseteq\overline{\mathcal{M}}\subseteq\overline{\mathcal{M}^{\uparrow}}$,
we can write
$\overline{\mathcal{M}_{\downarrow}}=\overline{\mathcal{M}}=\overline{\mathcal{M}^{\uparrow}}$.
Since $\partial\mathcal{E}=\overline{\mathcal{E}}\setminus\mathcal{E}^{\circ}$
for any subset $\mathcal{E}$ in a topological space, we conclude that
$\partial\mathcal{M}=\partial\mathcal{M}^{\uparrow}=\partial\mathcal{M}_{\downarrow}$.
∎

Recall the definition of $\mathcal{M}$, $\mathcal{T}$,
$\\{\partial\mathcal{B}_{i}\;\text{for}\;i\in\\{1,2\\}\\}$ and
$\\{\mathcal{H}_{1}^{-},\mathcal{H}_{2}^{+}\\}$ from (7), (22), (25), and
(29), respectively. Assuming that $\sigma_{1}\geq\sigma_{2}$, we summarize a
characterization of the potential solution region $\mathcal{M}$ as follows:

$\begin{cases}\partial\mathcal{M}=\mathcal{T}\sqcup\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}&\text{if}\quad
r\in\big{(}0,\;\frac{L}{2\sigma_{1}}\big{]},\\\
\partial\mathcal{M}=\big{[}\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\mathcal{T}\sqcup\\{\boldsymbol{x}^{*}_{1}\\}&\text{if}\quad
r\in\big{(}\frac{L}{2\sigma_{1}},\;\frac{L}{2\sigma_{2}}\big{]},\\\
\partial\mathcal{M}=\big{[}\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}\big{]}\sqcup\big{[}\partial\mathcal{B}_{2}\cap(\mathcal{H}_{2}^{+})^{c}\big{]}\sqcup\mathcal{T}&\text{if}\quad
r\in\Big{(}\frac{L}{2\sigma_{2}},\;\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}\Big{)},\\\
\mathcal{M}=\Big{\\{}\Big{(}\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}-\frac{1}{\sigma_{2}}\big{)},\;\mathbf{0}\Big{)}\Big{\\}}&\text{if}\quad
r\in\Big{(}\frac{L}{2\sigma_{2}},\;\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}\Big{)},\\\
\mathcal{M}=\emptyset&\text{if}\quad
r\in\Big{(}\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)},\;\infty\Big{)},\end{cases}$

where the first three equations are obtained by applying Theorem 4.10 and
Theorem 5.4 to Theorem 6.2, and the last two equations are obtained by
applying Theorem 4.10 and Theorem 5.4 to Proposition 6.1. Examples of the
boundary $\partial\mathcal{M}$ in $\mathbb{R}^{2}$ with different values of
$r$ are shown in Fig. 1. In particular, the solid blue, cyan and magenta
curves in the figure correspond to the sets $\mathcal{T}$,
$\partial\mathcal{B}_{1}\cap(\mathcal{H}_{1}^{-})^{c}$ and
$\partial\mathcal{B}_{2}\cap(\mathcal{H}_{2}^{+})^{c}$, respectively.

##  7 Discussion and Conclusions

In this work, we studied the possible locations of the minimizer of the sum of
two strongly convex functions. Based on the location of the two minimizers of
the individual functions, strong convexity parameters and a bound on the
gradients at the minimizer of the sum, we established a necessary condition
and a sufficient condition for a given point to be a minimizer, and called the
set of points that satisfies the conditions as the outer approximation
$\mathcal{M}^{\uparrow}$ and inner approximation $\mathcal{M}_{\downarrow}$,
respectively. We then explicitly characterized the boundary and interior of
the outer and inner approximations. The characterization of these boundaries
and interiors turned out to be identical. Subsequently, we showed that the
boundary of the potential solution region $\partial\mathcal{M}$ is also
identical to those boundaries. In particular, we showed that it is sufficient
to consider quadratic functions to establish (almost) the entire set of
potential minimizers. To visualize the boundary of the potential solution
region $\partial\mathcal{M}$, we provided examples with different distances
between the two original minimizers in Fig. 1.

Our work in this paper focused on the case of two functions. Future work could
include identifying the region that the minimizer of the sum can lie for the
case of multiple strongly convex functions. One can also modify some
assumptions, for example by considering strongly convex functions with
Lipschitz continuous gradient condition.

## References

  * Shalev-Shwartz [2011] Shai Shalev-Shwartz.  Online learning and online convex optimization.  _Foundations and Trends in Machine Learning_ , 4(2):107–194, 2011.
  * Boyd et al. [2011] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  _Foundations and Trends in Machine Learning_ , 3(1), 2011\.
  * Sayed [2014] Ali H Sayed.  Adaptive networks.  _Proceedings of the IEEE_ , 102(4):460–497, 2014\.
  * Molzahn et al. [2017] Daniel K Molzahn, Florian Dörfler, Henrik Sandberg, Steven H Low, Sambuddha Chakrabarti, Ross Baldick, and Javad Lavaei.  A survey of distributed optimization and control algorithms for electric power systems.  _IEEE Transactions on Smart Grid_ , 8(6):2941–2962, 2017.
  * Li et al. [2011] Na Li, Lijun Chen, and Steven H Low.  Optimal demand response based on utility maximization in power networks.  In _IEEE Power and Energy Society General Meeting_ , pages 1–8, 2011\.
  * Zavlanos et al. [2012] Michael M Zavlanos, Alejandro Ribeiro, and George J Pappas.  Network integrity in mobile robotic networks.  _IEEE Transactions on Automatic Control_ , 58(1):3–18, 2012.
  * Tron et al. [2016] Roberto Tron, Justin Thomas, Giuseppe Loianno, Kostas Daniilidis, and Vijay Kumar.  A distributed optimization framework for localization and formation control: Applications to vision-based measurements.  _IEEE Control Systems Magazine_ , 36(4):22–44, 2016.
  * Nedić et al. [2010] Angelia Nedić, Asuman Ozdaglar, and Pablo Parrilo.  Constrained consensus and optimization in multi-agent networks.  _IEEE Transactions on Automatic Control_ , 55(4):922–938, 2010.
  * Johansson et al. [2009] B. Johansson, M. Rabi, and M. Johansson.  A randomized incremental subgradient method for distributed optimization in networked systems.  _SIAM Journal on Optimization_ , 20(3):1157–1170, 2009.
  * Zhu and Martínez [2012] M. Zhu and S. Martínez.  On distributed convex optimization under inequality and equality constraints.  _IEEE Transactions on Automatic Control_ , 57(1):151–164, 2012.
  * Gharesifard and Cortés [2014] B. Gharesifard and J. Cortés.  Distributed continuous-time convex optimization on weight-balanced digraphs.  _IEEE Transactions on Automatic Control_ , 59(3):781–786, 2014.
  * Nedic and Olshevsky [2015] A. Nedic and A. Olshevsky.  Distributed optimization over time-varying directed graphs.  _IEEE Transactions on Automatic Control_ , 60(3):601–615, 2015.
  * Sundaram and Gharesifard [2018] Shreyas Sundaram and Bahman Gharesifard.  Distributed optimization under adversarial nodes.  _IEEE Transactions on Automatic Control_ , 64(3):1063–1076, 2018.
  * Kuwaranancharoen et al. [2020] Kananart Kuwaranancharoen, Lei Xin, and Shreyas Sundaram.  Byzantine-resilient distributed optimization of multi-dimensional functions.  _arXiv preprint arXiv:2003.09038_ , 2020.
  * Sundaram and Gharesifard [2016] Shreyas Sundaram and Bahman Gharesifard.  Secure local filtering algorithms for distributed optimization.  In _Decision and Control (CDC), 2016 IEEE 55th Conference on_ , pages 1871–1876. IEEE, 2016.
  * Su and Vaidya [2015] Lili Su and Nitin Vaidya.  Byzantine multi-agent optimization.  _arXiv preprint arXiv:1506.04681_ , 2015.
  * Shokri and Shmatikov [2015] Reza Shokri and Vitaly Shmatikov.  Privacy-preserving deep learning.  In _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_ , pages 1310–1321, 2015.
  * Konevcnỳ et al. [2016] Jakub Konevcnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon.  Federated learning: Strategies for improving communication efficiency.  _arXiv preprint arXiv:1610.05492_ , 2016.
  * Kairouz et al. [2021] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.  Advances and open problems in federated learning.  _Foundations and Trends® in Machine Learning_ , 14(1–2):1–210, 2021.
  * Kuwaranancharoen and Sundaram [2018] Kananart Kuwaranancharoen and Shreyas Sundaram.  On the location of the minimizer of the sum of two strongly convex functions.  In _2018 IEEE Conference on Decision and Control (CDC)_ , pages 1769–1774. IEEE, 2018.
  * Kuwaranancharoen and Sundaram [2020] Kananart Kuwaranancharoen and Shreyas Sundaram.  On the set of possible minimizers of a sum of known and unknown functions.  _arXiv preprint arXiv:2003.09035_ , 2020.
  * Hastie et al. [2009] Trevor Hastie, Robert Tibshirani, and Jerome Friedman.  _The elements of statistical learning: data mining, inference, and prediction_.  Springer Science & Business Media, 2009.
  * Castano et al. [2016] Diego Castano, Vehbi E Paksoy, and Fuzhen Zhang.  Angles, triangle inequalities, correlation matrices and metric-preserving and subadditive functions.  _Linear Algebra and its Applications_ , 491:15–29, 2016\.

##  Appendix A Proofs of Theoretical Results for Outer Approximation

###  A.1 Proof of Lemma 4.3

###### Proof of Lemma 4.3.

Consider part (i) of the lemma. Suppose
$\boldsymbol{x}_{\epsilon}=\boldsymbol{x}_{1}^{*}+\epsilon\boldsymbol{e}_{1}$
for $\epsilon\in\mathbb{R}$. We want to show that

  1. (a)

If $r\in\big{(}0,\;\frac{L}{2\sigma_{2}}\big{]}$ then for all
$\epsilon\in\Big{(}0,\;\min\big{\\{}\frac{L}{\sigma_{1}},2r\big{\\}}\Big{)}$,
we have
$\tilde{\phi}_{1}(\boldsymbol{x}_{\epsilon})+\tilde{\phi}_{2}(\boldsymbol{x}_{\epsilon})>\psi(\boldsymbol{x}_{\epsilon})$.

  2. (b)

If $r\in\big{(}0,\;\frac{L}{2\sigma_{2}}\big{)}$ then for all
$\epsilon\in\Big{(}-\min\big{\\{}\frac{L}{\sigma_{1}},\frac{L}{\sigma_{2}}-2r\big{\\}},\;0\Big{)}$,
we have
$\tilde{\phi}_{1}(\boldsymbol{x}_{\epsilon})+\tilde{\phi}_{2}(\boldsymbol{x}_{\epsilon})<\psi(\boldsymbol{x}_{\epsilon})$.

  3. (c)

If $r=\frac{L}{2\sigma_{2}}$ then for all $\epsilon\in(-\infty,0)$, we have
$\boldsymbol{x}_{\epsilon}\notin(\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.

First, consider case (a). Suppose
$\epsilon\in\big{(}0,\;\min\big{\\{}\frac{L}{\sigma_{1}},2r\big{\\}}\big{)}$.
Let $x_{\epsilon,1}$ be the first component of the point
$\boldsymbol{x}_{\epsilon}$. We have
$x_{\epsilon,1}\in\big{(}-r,\;\min\big{\\{}-r+\frac{L}{\sigma_{1}},\;r\big{\\}}\big{)}$.
Since $r\in\big{(}0,\;\frac{L}{2\sigma_{2}}\big{]}$, we have
$-r\in\big{[}r-\frac{L}{\sigma_{2}},r\big{)}$. Therefore,
$\boldsymbol{x}_{\epsilon}\in(\mathcal{B}_{1}\cap\mathcal{B}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.
By the location of $\boldsymbol{x}_{\epsilon}$, from (10), we get
$\alpha_{1}(\boldsymbol{x}_{\epsilon})=0$ and
$\alpha_{2}(\boldsymbol{x}_{\epsilon})=\pi$. Consequently, from (11), we
obtain $\psi(\boldsymbol{x}_{\epsilon})=0$. Since
$\boldsymbol{x}_{\epsilon}\notin\partial\mathcal{B}_{1}\cup\partial\mathcal{B}_{2}$,
from (9), we have that
$\tilde{\phi}_{i}(\boldsymbol{x}_{\epsilon})\in\big{(}0,\frac{\pi}{2}\big{]}$
for $i\in\\{1,2\\}$. This means that
$\tilde{\phi}_{1}(\boldsymbol{x}_{\epsilon})+\tilde{\phi}_{2}(\boldsymbol{x}_{\epsilon})>\psi(\boldsymbol{x}_{\epsilon})$.

Second, consider case (b). Suppose
$\epsilon\in\big{(}-\min\big{\\{}\frac{L}{\sigma_{1}},\frac{L}{\sigma_{2}}-2r\big{\\}},\;0\big{)}$.
We have
$x_{\epsilon,1}\in\big{(}\max\big{\\{}-r-\frac{L}{\sigma_{1}},\;r-\frac{L}{\sigma_{2}}\big{\\}},\;-r\big{)}$
which implies that
$\boldsymbol{x}_{\epsilon}\in(\mathcal{B}_{1}\cap\mathcal{B}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.
By the location of $\boldsymbol{x}_{\epsilon}$, from (10), we get
$\alpha_{1}(\boldsymbol{x}_{\epsilon})=\pi$ and
$\alpha_{2}(\boldsymbol{x}_{\epsilon})=\pi$. Consequently, from (11), we
obtain $\psi(\boldsymbol{x}_{\epsilon})=\pi$. Since
$\boldsymbol{x}_{\epsilon}\notin\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$,
from (9), we have that
$\tilde{\phi}_{i}(\boldsymbol{x}_{\epsilon})\in\big{[}0,\frac{\pi}{2}\big{)}$
for $i\in\\{1,2\\}$. This means that
$\tilde{\phi}_{1}(\boldsymbol{x}_{\epsilon})+\tilde{\phi}_{2}(\boldsymbol{x}_{\epsilon})<\psi(\boldsymbol{x}_{\epsilon})$.

Third, consider case (c). Suppose $\epsilon\in(-\infty,0)$. If
$\boldsymbol{x}\in\overline{\mathcal{B}}_{2}$ then
$x_{1}\in\big{[}r-\frac{L}{\sigma_{2}},r+\frac{L}{\sigma_{2}}\big{]}=[-r,3r]$.
However, we have $x_{\epsilon,1}\in(-\infty,-r)$. This means that
$\boldsymbol{x}_{\epsilon}\notin\overline{\mathcal{B}}_{2}$ which implies that
$\boldsymbol{x}_{\epsilon}\notin(\overline{\mathcal{B}}_{1}\cap\overline{\mathcal{B}}_{2})\setminus\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.
We complete the proof of our claim.

Recall the definition of $\mathcal{M}^{\uparrow}$ and
$\mathcal{M}_{\downarrow}$ in (13) and (14), respectively. From our claim, we
can see that if $r\in\big{(}0,\;\frac{L}{2\sigma_{2}}\big{]}$ then for all
$\delta\in\mathbb{R}_{>0}$, there exist
$\boldsymbol{x}_{\text{in}},\boldsymbol{x}_{\text{out}}\in\mathcal{B}(\boldsymbol{x}_{1}^{*},\delta)$
such that $\boldsymbol{x}_{\text{in}}\in\mathcal{M}^{\uparrow}$,
$\boldsymbol{x}_{\text{in}}\in\mathcal{M}_{\downarrow}$,
$\boldsymbol{x}_{\text{out}}\notin\mathcal{M}^{\uparrow}$ and
$\boldsymbol{x}_{\text{out}}\notin\mathcal{M}_{\downarrow}$. This implies that
$\boldsymbol{x}_{1}^{*}\in\partial\mathcal{M}^{\uparrow}$ and
$\boldsymbol{x}_{1}^{*}\in\partial\mathcal{M}_{\downarrow}$. The analysis for
part (ii) of the lemma follows in an identical manner. ∎

###  A.2 Proof of Lemma 4.4

###### Proof of Lemma 4.4.

Recall from (10) that
$\alpha_{i}(\boldsymbol{x})=\angle(\boldsymbol{x}-\boldsymbol{x}_{i}^{*},\;\boldsymbol{x}_{2}^{*}-\boldsymbol{x}_{1}^{*})$
for $i\in\\{1,2\\}$. Suppose
$\boldsymbol{y}\notin\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}$.
Since $-r\leq x_{1}=y_{1}\leq r$ and
$\|\tilde{\mathbf{x}}\|>\|\tilde{\mathbf{y}}\|$, we have
$\alpha_{1}(\boldsymbol{x})\geq\alpha_{1}(\boldsymbol{y})$ and
$\alpha_{2}(\boldsymbol{x})\leq\alpha_{2}(\boldsymbol{y})$, which implies that

$\psi(\boldsymbol{x})=\pi-(\alpha_{2}(\boldsymbol{x})-\alpha_{1}(\boldsymbol{x}))\geq\pi-(\alpha_{2}(\boldsymbol{y})-\alpha_{1}(\boldsymbol{y}))=\psi(\boldsymbol{y}).$
(SM.1)

On the other hand, since $x_{1}=y_{1}$ and
$\|\tilde{\mathbf{x}}\|>\|\tilde{\mathbf{y}}\|$, we get

$\|\boldsymbol{x}-\boldsymbol{x}_{1}^{*}\|>\|\boldsymbol{y}-\boldsymbol{x}_{1}^{*}\|>0\quad\text{and}\quad\|\boldsymbol{x}-\boldsymbol{x}_{2}^{*}\|>\|\boldsymbol{y}-\boldsymbol{x}_{2}^{*}\|>0.$

Using the above inequalities and the definition of (9), we get that
$\tilde{\phi}_{i}(\boldsymbol{x})<\tilde{\phi}_{i}(\boldsymbol{y})$ for
$i\in\\{1,2\\}$. Applying
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\geq\psi(\boldsymbol{x})$
and inequality (SM.1), we can write

$\psi(\boldsymbol{y})\leq\psi(\boldsymbol{x})\leq\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})<\tilde{\phi}_{1}(\boldsymbol{y})+\tilde{\phi}_{2}(\boldsymbol{y}),$

which completes the proof. ∎

###  A.3 Proof of Lemma 4.5

###### Proof of Lemma 4.5.

Consider part (i) of the lemma. Since
$\boldsymbol{x}\in\partial\mathcal{B}_{1}$, we get
$\|\boldsymbol{x}-\boldsymbol{x}_{1}^{*}\|=\frac{L}{\sigma_{1}}$ and thus
$\tilde{\phi}_{1}(\boldsymbol{x})=0$ from (9). Consider the inequality
$\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\lessgtr\psi(\boldsymbol{x})$.
Substitute $\tilde{\phi}_{1}(\boldsymbol{x})=0$ and
$\psi(\boldsymbol{x})=\pi-(\alpha_{2}(\boldsymbol{x})-\alpha_{1}(\boldsymbol{x}))$,
and take cosine of both sides of the inequality (and use
$\cos\tilde{\phi}_{2}(\boldsymbol{x})=\frac{\sigma_{2}}{L}d_{2}(\boldsymbol{x})$
from (9)) to get

$\frac{\sigma_{2}}{L}d_{2}(\boldsymbol{x})\gtrless-\cos\big{(}\alpha_{2}(\boldsymbol{x})-\alpha_{1}(\boldsymbol{x})\big{)}.$

Expand the cosine and substitute the equations (23) and (24) to obtain

$\frac{\sigma_{2}}{L}d_{2}(\boldsymbol{x})\gtrless-\frac{x_{1}^{2}+\|\tilde{\mathbf{x}}\|^{2}-r^{2}}{d_{1}(\boldsymbol{x})\cdot
d_{2}(\boldsymbol{x})}.$ (SM.2)

Since $\boldsymbol{x}\in\partial\mathcal{B}_{1}$, we have
$d_{1}(\boldsymbol{x})=\frac{L}{\sigma_{1}}$ and
$\|\tilde{\mathbf{x}}\|^{2}=\frac{L^{2}}{\sigma_{1}^{2}}-(x_{1}+r)^{2}$ from
(25). Also, from (21), we have

$d_{2}^{2}(\boldsymbol{x})=(x_{1}-r)^{2}+\|\tilde{\mathbf{x}}\|^{2}=(x_{1}-r)^{2}+\frac{L^{2}}{\sigma_{1}^{2}}-(x_{1}+r)^{2}=-4rx_{1}+\frac{L^{2}}{\sigma_{1}^{2}}.$
(SM.3)

Multiply inequality (SM.2) by $d_{1}(\boldsymbol{x})\cdot
d_{2}(\boldsymbol{x})$ and then substitute $d_{1}(\boldsymbol{x})$,
$\|\tilde{\mathbf{x}}\|^{2}$, and $d_{2}^{2}(\boldsymbol{x})$ to get

$\displaystyle\frac{\sigma_{2}}{\sigma_{1}}\Big{(}-4rx_{1}+\frac{L^{2}}{\sigma_{1}^{2}}\Big{)}\gtrless
2r^{2}+2rx_{1}-\frac{L^{2}}{\sigma_{1}^{2}},$
$\displaystyle\Leftrightarrow\quad$ $\displaystyle
x_{1}\Big{(}2r+4r\frac{\sigma_{2}}{\sigma_{1}}\Big{)}\lessgtr\frac{\sigma_{2}}{\sigma_{1}}\cdot\frac{L^{2}}{\sigma_{1}^{2}}+\frac{L^{2}}{\sigma_{1}^{2}}-2r^{2},$
$\displaystyle\Leftrightarrow\quad$ $\displaystyle
x_{1}\lessgtr\Big{(}\frac{1+\beta}{1+2\beta}\Big{)}\frac{\gamma_{1}}{2r}-\frac{r}{1+2\beta}=\lambda_{1},$

where $\gamma_{1}$ and $\beta$ are defined in (26). The proof of the second
part is similar to the first part. ∎

###  A.4 Proof of Lemma 4.6

###### Proof of Lemma 4.6.

We will prove the case that $i=1$; however, the proof of the case that $i=2$
can be obtained using the same approach. Suppose
$\boldsymbol{x}\in\partial\mathcal{B}_{1}$. Substituting
$\|\tilde{\mathbf{x}}\|^{2}=\frac{L^{2}}{\sigma_{1}^{2}}-(x_{1}+r)^{2}$,
$d_{1}(\boldsymbol{x})=\frac{L}{\sigma_{1}}$ and (SM.3) into the expression of
$\mathcal{T}$ in (22), we get

$\frac{x_{1}^{2}+\|\tilde{\mathbf{x}}\|^{2}-r^{2}}{d_{1}^{2}(\boldsymbol{x})\cdot
d_{2}^{2}(\boldsymbol{x})}+\frac{\sigma_{1}\sigma_{2}}{L^{2}}=\frac{\frac{L^{2}}{\sigma_{1}^{2}}-2rx_{1}-2r^{2}}{\frac{L^{2}}{\sigma_{1}^{2}}\big{(}-4rx_{1}+\frac{L^{2}}{\sigma_{1}^{2}}\big{)}}+\frac{\sigma_{1}\sigma_{2}}{L^{2}}=0.$
(SM.4)

Multiply both sides of the above equation by
$\frac{L^{2}}{\sigma_{1}^{2}}\big{(}-4rx_{1}+\frac{L^{2}}{\sigma_{1}^{2}}\big{)}$
and then use the definition of $\gamma_{1}$ and $\beta$ in (26) to get

$4\beta
rx_{1}-\beta\gamma_{1}=\gamma_{1}-2rx_{1}-2r^{2},\quad\Leftrightarrow\quad
x_{1}=\Big{(}\frac{1+\beta}{1+2\beta}\Big{)}\frac{\gamma_{1}}{2r}-\frac{r}{1+2\beta}=\lambda_{1}.$

Then, substituting
$x_{1}=\big{(}\frac{1+\beta}{1+2\beta}\big{)}\frac{\gamma_{1}}{2r}-\frac{r}{1+2\beta}$
back into the expression of $\partial\mathcal{B}_{1}$ in (25), we get

$\displaystyle\|\tilde{\mathbf{x}}\|^{2}$
$\displaystyle=\gamma_{1}-\bigg{[}\Big{(}\frac{1+\beta}{1+2\beta}\Big{)}\frac{\gamma_{1}}{2r}-\frac{r}{1+2\beta}+r\bigg{]}^{2}$
$\displaystyle=-\frac{1}{4r^{2}(1+2\beta)^{2}}\big{[}(\gamma_{1}-4r^{2})(\gamma_{1}(1+\beta)^{2}-4\beta^{2}r^{2})\big{]},$
$\displaystyle\Rightarrow\quad\|\tilde{\mathbf{x}}\|$
$\displaystyle=\frac{r}{2(1+2\beta)}\sqrt{-\Big{(}\frac{\gamma_{1}}{r^{2}}-4\Big{)}\Big{(}\frac{\gamma_{1}}{r^{2}}(1+\beta)^{2}-4\beta^{2}\Big{)}}=\nu_{1}.$

This equation is valid only when the term in the square root is a non-negative
real number. Equivalently,

$\frac{4\beta^{2}}{(1+\beta)^{2}}\leq\frac{\gamma_{1}}{r^{2}}\leq
4,\quad\Leftrightarrow\quad\frac{L}{2\sigma_{1}}\leq
r\leq\frac{L}{2\sigma_{1}}\Big{(}1+\frac{1}{\beta}\Big{)}=\frac{L}{2}\Big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\Big{)}.$

Since we multiplied (SM.4) by $d_{1}^{2}(\boldsymbol{x})\cdot
d_{2}^{2}(\boldsymbol{x})=\frac{L^{2}}{\sigma_{1}^{2}}\big{(}-4rx_{1}+\frac{L^{2}}{\sigma_{1}^{2}}\big{)}$
to obtain the result, $\boldsymbol{x}_{1}^{*}$ or $\boldsymbol{x}_{2}^{*}$
might appear in the intersection $\mathcal{T}\cap\partial\mathcal{B}_{1}$ even
if
$\\{\boldsymbol{x}_{1}^{*},\boldsymbol{x}_{2}^{*}\\}\not\subseteq\mathcal{T}$.
Therefore, we need to verify that the intersection points are not
$\boldsymbol{x}^{*}_{1}$ or $\boldsymbol{x}^{*}_{2}$. Considering the solution
of the equation $\|\tilde{\mathbf{x}}\|=\nu_{1}=0$ (i.e., $\boldsymbol{x}$ is
on the $x_{1}$-axis), we see that $r=\frac{L}{2\sigma_{1}}$ and
$r=\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}$ are the
candidates that we need to check. Substituting $r=\frac{L}{2\sigma_{1}}$ into
the equation $x_{1}=\lambda_{1}$, we get $x_{1}=\frac{L}{2\sigma_{1}}=r$ which
is $\boldsymbol{x}_{2}^{*}=(r,\mathbf{0})$ and therefore we conclude that
there are no intersection points when $r=\frac{L}{2\sigma_{1}}$. Next,
substituting
$r=\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}$ into
the equation $x_{1}=\lambda_{1}$, we get
$x_{1}=\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}-\frac{1}{\sigma_{2}}\big{)}$
which is a legitimate value of an intersection point. ∎

###  A.5 Proof of Lemma 4.7

###### Proof of Lemma 4.7.

To simplify notations in the proof, we define a new variable

$\chi_{1}\triangleq\frac{L}{\sigma_{1}r}=\frac{\sqrt{\gamma_{1}}}{r}.$ (SM.5)

First, consider part (ii) of the lemma. By the definition of $\lambda_{1}$ in
(27), we can rewrite the inequality $\lambda_{1}<\frac{L}{\sigma_{1}}-r$ as
$\big{(}\frac{1+\beta}{1+2\beta}\big{)}\frac{\gamma_{1}}{2r^{2}}-\frac{1}{1+2\beta}<\frac{L}{\sigma_{1}r}-1$.
Using $\chi_{1}$ defined in (SM.5), the inequality becomes

$\frac{1}{2}\Big{(}\frac{1+\beta}{1+2\beta}\Big{)}\chi_{1}^{2}-\frac{1}{1+2\beta}<\chi_{1}-1.$
(SM.6)

Multiplying both sides by $1+2\beta$ and then rearranging the resulting
inequality, we get

$(\chi_{1}-2)\Big{(}\frac{1}{2}(1+\beta)\chi_{1}-\beta\Big{)}<0,\quad\Leftrightarrow\quad\frac{2\beta}{1+\beta}<\chi_{1}<2.$

The last equivalence holds since $\frac{2\beta}{1+\beta}<2$. Substituting
$\chi_{1}=\frac{L}{\sigma_{1}r}$ and $\beta=\frac{\sigma_{2}}{\sigma_{1}}$,
the inequality $\frac{2\beta}{1+\beta}<\chi_{1}$ becomes
$r<\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}$ and the
inequality $\chi_{1}<2$ becomes $r>\frac{L}{2\sigma_{1}}$, which completes the
proof of part (ii).

Next, we can see that part (ii) of the lemma implies that if
$r\in\big{(}0,\;\frac{L}{2\sigma_{1}}\big{]}$ then
$\lambda_{1}\geq\frac{L}{\sigma_{1}}-r$. By proceeding the algebraic
simplification similar to (SM.6) except using equality instead, we can
conclude that given $r\in\big{(}0,\;\frac{L}{2\sigma_{1}}\big{]}$, we have
$\lambda_{1}=\frac{L}{\sigma_{1}}-r$ only when $r=\frac{L}{2\sigma_{1}}$. This
completes the proof of part (i).

The proof of part (iii) and part (iv) can be carried out using similar steps
as the proof given above. ∎

###  A.6 Proof of Lemma 4.8

###### Proof of Lemma 4.8.

Let $\boldsymbol{x}=(x_{1},\tilde{\mathbf{x}})\in\mathcal{T}$, and
$\boldsymbol{e}_{2}^{\prime}(\boldsymbol{x})=\frac{\boldsymbol{v}(\boldsymbol{x})}{\|\boldsymbol{v}(\boldsymbol{x})\|}$
where
$\boldsymbol{v}(\boldsymbol{x})=(\boldsymbol{x}-\boldsymbol{x}_{1}^{*})-\langle\boldsymbol{x}-\boldsymbol{x}_{1}^{*},\boldsymbol{e}_{1}\rangle\;\boldsymbol{e}_{1}$.
Suppose
$\theta(\boldsymbol{x})=\frac{1}{2}(\alpha_{1}(\boldsymbol{x})+\alpha_{2}(\boldsymbol{x}))$
where $\alpha_{i}(\boldsymbol{x})$ for $i\in\\{1,2\\}$ are defined in (10) and

$\boldsymbol{x}^{\prime}_{\epsilon}=\boldsymbol{x}+\epsilon\big{(}\cos(\theta(\boldsymbol{x}))\;\boldsymbol{e}_{1}+\sin(\theta(\boldsymbol{x}))\;\boldsymbol{e}_{2}^{\prime}(\boldsymbol{x})\big{)}\quad\text{for}\quad\epsilon\in\mathbb{R}.$
(SM.7)

Our claim is that if
$r\in\big{(}0,\;\frac{L}{2}\big{(}\frac{1}{\sigma_{1}}+\frac{1}{\sigma_{2}}\big{)}\big{)}$
then

  1. (i)

for all

$\epsilon\in\bigg{(}\max\Big{\\{}\max_{i=1,2}-2d_{i}(\boldsymbol{x})\sin\frac{1}{2}\big{(}\tilde{\phi}_{1}(\boldsymbol{x})+\tilde{\phi}_{2}(\boldsymbol{x})\big{)},\;-\|\tilde{\mathbf{x}}\|\csc(\theta(\boldsymbol{x}))\Big{\\}},\;0\bigg{)},$

it holds that
$\tilde{\phi}_{1}(\boldsymbol{x}^{\prime}_{\epsilon})+\tilde{\phi}_{2}(\boldsymbol{x}^{\prime}_{\epsilon})>\psi(\boldsymbol{x}^{\prime}_{\epsilon})$
(i.e., $\boldsymbol{x}^{\prime}_{\epsilon}\in\mathcal{M}^{\uparrow}$ and
$\boldsymbol{x}^{\prime}_{\epsilon}\in\mathcal{M}_{\downarrow}$), and

  2. (ii)

for all $\epsilon\in(0,\infty)$, either
$\tilde{\phi}_{1}(\boldsymbol{x}^{\prime}_{\epsilon})+\tilde{\phi}_{2}(\boldsymbol{x}^{\prime}_{\epsilon})<\psi(\boldsymbol{x}^{\prime}_{\epsilon})$,
or $\tilde{\phi}_{1}(\boldsymbol{x}^{\prime}_{\epsilon})$ or