# On the Set of Possible Minimizers of a Sum of Convex Functions

Moslem Zamani1, François Glineur1,2, and Julien M. Hendrickx1 1 ICTEAM/INMA /
2 CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium.
{moslem.zamani, francois.glineur<EMAIL_ADDRESS>
###### Abstract

Consider a sum of convex functions, where the only information known about
each individual summand is the location of a minimizer. In this work, we give
an exact characterization of the set of possible minimizers of the sum.

Our results cover several types of assumptions on the summands, such as
smoothness or strong convexity. Our main tool is the use of necessary and
sufficient conditions for interpolating the considered function classes, which
leads to shorter and more direct proofs in comparison with previous work.

We also address the setting where each summand minimizer is assumed to lie in
a unit ball, and prove a tight bound on the norm of any minimizer of the sum.

##  I Introduction

Consider the following optimization problem

$\textstyle\min_{x\in\mathbb{R}^{n}}\ f(x):=\textstyle\sum_{i\in[m]}f_{i}(x),$
(1)

where $f_{i}:\mathbb{R}^{n}\to(-\infty,\infty]$, $i\in[m]$, are convex
functions. Problem (1) appears naturally in a variety of settings, including
distributed optimization; see [1, 2] and references therein. In some
situations including resilient distributed optimization [3] and some federated
learning setups [4], functions $f_{i}$’s are unknown and the only knowledge
about each summand is the location of a minimizer $x_{i}^{\star}$, that is,

$x_{i}^{\star}\in\operatorname*{argmin}_{x\in\mathbb{R}^{n}}f_{i}(x),\ \ \ \
i\in[m].$

The problem we consider is to determine the set of potential minimizers of
problem (1) using only those known individual summand minimizers
$x_{i}^{\star}$ and some additional properties of the functions $f_{i}$, such
as smoothness or strong convexity.

In a recent line of work, Kuwaranancharoen and Sundaram [5, 6, 7] study this
problem for $m=2$ differentiable and strongly convex functions, with the
additional knowledge of an upper bound on the norm of the gradient of each
summand at the minimizer $x^{\star}$ (see Proposition (III.3) for our result
in a similar setting). Using a geometric approach, they provide a near-exact
characterization of the set of possible minimizers, using _ad hoc_ coordinates
(more precisely, [7, Theorem 6.2] characterizes the boundary of the region of
potential minimizers, which coincides with its interior). Assuming that the
summands are smooth (i.e. that their gradient is Lipschitz) is also mentioned
in [7] as a possibility for further work.

Hendrickx and Rabbat consider a sum of smooth strongly convex functions in the
context of open multi-agent systems [8]. They assume all summand minimizers
lie in a ball centered at the origin, and derive an upper bond for the norm of
a potential minimizer of the sum, expressed in terms of the condition number
of the summands [8, Theorem 1].

In this paper, we show how the use of the interpolation conditions [9, 10]
described in Section II, provides a more direct and algebraic approach to
tackle these problems. We give in Section III an exact characterization of the
set of potential minimizers of a sum of two smooth strongly convex functions,
and we provide an alternative, simpler characterization of set of possible
minimizers of a sum of two strongly convex functions in the setting of [7].

In Section IV, we extend our results in a straightforward way to sums
involving arbitrary numbers of functions, and to a variation of the problem
where all but one function is smooth. Finally we provide in Section V a tight
bound for the setting where each summand minimizer lies in a ball.

##  II Preliminaries and Interpolation Conditions

###  II-A Notations and Definitions

Throughout the paper, $\|\cdot\|$ and $\langle\cdot,\cdot\rangle$ denote the
Euclidean norm and the dot product, respectively. We also use iff as an
abbreviation for if and only if. The set of the first $m$ natural numbers is
denoted by $[m]$, and $[\ell,m]$ denotes $[m]\setminus[\ell-1]$.

Let $f:\mathbb{R}^{n}\to(-\infty,\infty]$ be an extended real valued convex
function. Function $f$ is proper if its effective domain, defined as
$\mathrm{dom}\ f=\\{x:f(x)<\infty\\}$, is non-empty. It is closed if its
epigraph $\\{(x,r):f(x)\leq r\\}$ is a closed subset of $\mathbb{R}^{n+1}$.
The set of subgradients at $x\in\mathrm{dom}\ f$ (subdifferential) is

$\partial f(x)=\\{g:f(y)\geq f(x)+\langle g,y-x\rangle,\forall
y\in\mathbb{R}^{n}\\}.$

Let $L\in(0,\infty]$ and $\mu\in[0,\infty)$. A convex function
$f:\mathbb{R}^{n}\to(-\infty,\infty]$ is said to be $L$-smooth if for any
$x_{1},x_{2}\in\mathbb{R}^{n}$,

$\|g_{1}-g_{2}\|\leq L\|x_{1}-x_{2}\|\ \ \forall g_{1}\in\partial f(x_{1}),\
g_{2}\in\partial f(x_{2}).$

If $L<\infty$, then $f$ must be differentiable on $\mathbb{R}^{n}$. In
addition, any convex function is $\infty$-smooth. Furthermore, a function
$f:\mathbb{R}^{n}\to(-\infty,\infty]$ is said to be $\mu$-strongly convex if
the function $x\mapsto f(x)-\tfrac{\mu}{2}\|x\|^{2}$ is convex. Note that any
convex function is $0$-strongly convex. We denote the set of closed proper
convex functions that are $L$-smooth and $\mu$-strongly convex by
$\mathcal{F}_{\mu,L}(\mathbb{R}^{n})$. In addition,
$\mathcal{M}_{\mu,L}(x^{\star})$ stands for the set of functions in
$\mathcal{F}_{\mu,L}(\mathbb{R}^{n})$ for which $x^{\star}$ is a minimizer. We
make the convention $\tfrac{a}{\infty}=0$ for $a\in\mathbb{R}$.

###  II-B Interpolation Results

Interpolation constraints are necessary and sufficient conditions for a finite
set of vectors and values to be consistent with an actual function in a given
function class. For example, we will heavily rely on the following
interpolation result for the class of smooth strongly convex functions.

###### Theorem II.1

(see [9, Theorem 4]) Consider the class of functions
$\mathcal{F}_{\mu,L}(\mathbb{R}^{n})$ with $0\leq\mu<L\leq\infty$. Given a set
of triplets $\\{(x_{i};g_{i};f_{i})\\}_{i\in[m]}$ with
$x_{i},g_{i}\in\mathbb{R}^{n}$ and $f_{i}\in\mathbb{R}$, there exists a
function $f\in\mathcal{F}_{\mu,L}(\mathbb{R}^{n})$ satisfying

$f(x_{i})=f_{i},\ \ g_{i}\in\partial f(x_{i}),\ i\in[m],$

i.e. a function that interpolates the function and (sub)gradient values as
prescribed in $(x_{i};g_{i};f_{i})$, if and only if the following set of
interpolating conditions is satisfied:

$\displaystyle f_{i}-f_{j}-\langle
g_{j},x_{i}-x_{j}\rangle\geq(1-\tfrac{\mu}{L})^{-1}\big{(}\tfrac{1}{2L}\|g_{i}-g_{j}\|^{2}+$
$\displaystyle\ \ \tfrac{\mu}{2}\|x_{i}-x_{j}\|^{2}-\tfrac{\mu}{L}\langle
g_{i}-g_{j},x_{i}-x_{j}\rangle\big{)},\ \ \ \forall i,j\in[m].$ (2)

Interpolation conditions provide an exact characterization of the triplets
$\\{(x_{i};g_{i};f_{i})\\}_{i\in[m]}$ that are consistent with actual
functions, and as such, are instrumental in the automated tight analysis of
black-box optimization algorithm [9].

Our analysis will rely on the following central Lemma, which provides an
interpolation condition for a minimizer $x^{\star}$ and an arbitrary point
$x$, only involving those two points and their gradients, but not their
function values.

###### Lemma II.2

Consider the function class $\mathcal{F}_{\mu,L}(\mathbb{R}^{n})$ with
$0\leq\mu<L\leq\infty$. Given two points $x,x^{\star}\in\mathbb{R}^{n}$ and a
(sub)gradient $g\in\mathbb{R}^{n}$, there exists a function
$f\in\mathcal{M}_{\mu,L}(x^{\star})$ with $g\in\partial f(x)$ if and only if

$\displaystyle\langle
g,x-x^{\star}\rangle\geq({1+\tfrac{\mu}{L}})^{-1}\left(\tfrac{1}{L}\left\|g\right\|^{2}+\mu\|x-x^{\star}\|^{2}\right).$
(3)

###### Proof:

The existence of a function $f$ satisfying the assumptions in the Lemma is
equivalent to asking that the two triplets
$\\{(x;g;f_{x}),(x^{\star};0;f^{\star})\\}$ are interpolable by a function in
$\mathcal{F}_{\mu,L}(\mathbb{R}^{n})$ for some values of $f_{x}$ and
$f^{\star}$. Indeed, we have $f_{x}=f(x)$, $f^{\star}=f(x^{\star})$ and the
optimality condition for a minimizer of a convex function gives
$g^{\star}=0\in\partial f(x^{\star})$. Theorem II.1 states that it is
equivalent to the following pair of conditions (II.1), first for
$(x_{i},x_{j})=(x,x^{\star})$ then for $(x^{\star},x)$:

$\displaystyle f_{x}-f^{\star}$
$\displaystyle\geq(1-\tfrac{\mu}{L})^{-1}E(x,g,x^{\star})$ $\displaystyle
f^{\star}-f_{x}-\langle g,x^{\star}-x\rangle$
$\displaystyle\geq(1-\tfrac{\mu}{L})^{-1}E(x,g,x^{\star})$

where
$E(x,g,x^{\star})=\tfrac{1}{2L}\|g\|^{2}+\tfrac{\mu}{2}\|x-x^{\star}\|^{2}-\tfrac{\mu}{L}\langle
g,x-x^{\star}\rangle$. Hence we need to show that these two conditions holds
for some $f_{x}$ and $f^{\star}$ if and only if inequality (3) is satisfied.

We first establish the only if part. Summing the above two conditions leads to
$-\langle g,x^{\star}-x\rangle\geq 2(1-\tfrac{\mu}{L})^{-1}E(x,g,x^{\star})$
which is equivalent to

$(1-\tfrac{\mu}{L})\langle
g,x-x^{\star}\rangle\geq\tfrac{1}{L}\|g\|^{2}+\mu\|x-x^{\star}\|^{2}-\tfrac{2\mu}{L}\langle
g,x-x^{\star}\rangle$

and can be rearranged as inequality (3) in the Lemma.

To prove the if part, we assume inequality (3) holds and show that the above
two conditions are satisfied with the following

$f_{x}=(1-\tfrac{\mu}{L})^{-1}E(x,g,x^{\star}),\quad f^{\star}=0$

It is easy to check that this choice of $f_{x}$ and $f^{\star}$ leads to an
equality in the first condition. Furthermore, as the sum of the two
inequalities was shown above to be equivalent to condition (3), we can
conclude that the second inequality is also satisfied. This concludes the
proof of the equivalence.

Note that condition (3) can be equivalently rewritten as

$\big{\|}g-\tfrac{L+\mu}{2}(x^{\star}-x)\big{\|}\leq\tfrac{L-\mu}{2}\big{\|}x^{\star}-x\big{\|}$
(4)

when $L<\infty$, which is easier to interpret geometrically: it states that
$g$ must belong to a ball centered at $\tfrac{L+\mu}{2}(x^{\star}-x)$ with
radius equal to $\tfrac{L-\mu}{2}\big{\|}x^{\star}-x\big{\|}$ (to verify the
equivalence, square both sides and distribute the left-hand side). ∎

##  III Minimizers of a sum of two convex functions

We first study the case of a sum of two smooth (strongly) convex functions.
More precisely, given two points $x_{1}^{\star},x^{\star}_{2}$, we want to
characterize the set of potential minimizers of a sum $f_{1}(x)+f_{2}(x)$
where $f_{1}$ and $f_{2}$ are smooth and strongly convex and have a minimizer
at $x_{1}^{\star}$ and $x_{2}^{\star}$ respectively.

###### Proposition III.1

Let $0\leq\mu_{1}<L_{1}<\infty$ and $0\leq\mu_{2}<L_{2}<\infty$. Given two
points $x_{1}^{\star},x^{\star}_{2}\in\mathbb{R}^{n}$, a point
$x^{\star}\in\mathbb{R}^{n}$ is a minimizer of the sum $f_{1}(x)+f_{2}(x)$ for
some functions $f_{1}\in\mathcal{M}_{\mu_{1},L_{1}}(x^{\star}_{1})$ and
$f_{2}\in\mathcal{M}_{\mu_{2},L_{2}}(x^{\star}_{2})$ if and only if

$\displaystyle\left\|(L_{1}+\mu_{1})(x^{\star}-x_{1}^{\star})+(L_{2}+\mu_{2})(x^{\star}-x_{2}^{\star})\right\|\leq$
$\displaystyle(L_{1}-\mu_{1})\|x^{\star}-x^{\star}_{1}\|+(L_{2}-\mu_{2})\|x^{\star}-x^{\star}_{2}\|.$
(5)

###### Proof:

Optimality conditions imply that $x^{\star}$ is a minimizer of the sum
$f_{1}(x)+f_{2}(x)$ if and only if there exists subgradients of $f_{1}$ and
$f_{2}$ at $x^{\star}$ that sum to zero, i.e. if and only if there exists
$g_{1}$ and $g_{2}$ such that

$g_{1}\in\partial f_{1}(x^{\star}),g_{2}\in\partial
f_{2}(x^{\star}),g_{1}+g_{2}=0.$

Lemma II.2 with the geometrical inequality (4) applied to each function
$f_{1}$ and $f_{2}$ implies that $x^{\star}$ is a potential minimizer iff the
following system has a solution,

$\displaystyle\big{\|}g_{1}-\tfrac{L_{1}+\mu_{1}}{2}(x^{\star}-x_{1}^{\star})\big{\|}\leq\tfrac{L_{1}-\mu_{1}}{2}\|x^{\star}-x^{\star}_{1}\|,$
$\displaystyle\big{\|}g_{2}-\tfrac{L_{2}+\mu_{2}}{2}(x^{\star}-x_{2}^{\star})\big{\|}\leq\tfrac{L_{2}-\mu_{2}}{2}\|x^{\star}-x^{\star}_{2}\|,$
$\displaystyle g_{1}+g_{2}=0.$

By replacing $g_{2}$ by $-g_{1}$, this system is equivalent to

$\displaystyle\big{\|}g_{1}-\tfrac{L_{1}+\mu_{1}}{2}(x^{\star}-x_{1}^{\star})\big{\|}\leq\tfrac{L_{1}-\mu_{1}}{2}\|x^{\star}-x^{\star}_{1}\|,$
$\displaystyle\big{\|}g_{1}+\tfrac{L_{2}+\mu_{2}}{2}(x^{\star}-x_{2}^{\star})\big{\|}\leq\tfrac{L_{2}-\mu_{2}}{2}\|x^{\star}-x^{\star}_{2}\|.$

Geometrically, this system is asking for $g_{1}$ to belong to the intersection
of two balls. This is possible if and only if the distance between the centers
of the two balls is less than or equal to the sum of their radii, which gives
the desired inequality. ∎

One can verify that this set is always bounded provided $\mu_{1}>0$ or
$\mu_{2}>0$. Indeed, as the norm of $x^{\star}$ tends to infinity,
$x_{1}^{\star}$ and $x_{2}^{\star}$ become negligible in (III.1), leading in
the limit to condition
$(L_{1}+\mu_{1}+L_{2}+\mu_{2})\|x^{\star}\|\leq(L_{1}-\mu_{1}+L_{2}-\mu_{2})\|x^{\star}\|$
which cannot be satisfied unless $\mu_{1}+\mu_{2}=0$. On the other hand, when
$\mu_{1}=\mu_{2}=0$, condition (III.1) becomes

$\left\|L_{1}(x^{\star}-x_{1}^{\star})+L_{2}(x^{\star}-x_{2}^{\star})\right\|\leq
L_{1}\|x^{\star}-x^{\star}_{1}\|+L_{2}\|x^{\star}-x^{\star}_{2}\|$

which is the triangle inequality. This implies that any point
$x^{\star}\in\mathbb{R}^{n}$ can be a minimizer (which can also be derived
from the choice $f_{1}(x)=f_{2}(x)=0$).

Observe that the following point

$x^{\star}=\tfrac{L_{1}+\mu_{1}}{L_{1}+\mu_{1}+L_{2}+\mu_{2}}x^{\star}_{1}+\tfrac{L_{2}+\mu_{2}}{L_{1}+\mu_{1}+L_{2}+\mu_{2}}x^{\star}_{2}$

satisfies inequality (III.1) strictly when $x^{\star}_{1}\neq x^{\star}_{2}$,
from which one can infer that the set of potential minimizers has a nonempty
interior. Figure LABEL:fig.P1 shows the set of potential minimizer $x^{\star}$
from Proposition III.1 for two different sets of parameters in
$\mathbb{R}^{2}$.

We now consider a situation where one of the functions is not smooth, assuming
without loss of generality $L_{2}=\infty$.

###### Proposition III.2

Let $0\leq\mu_{1}<L_{1}<\infty$ and $0\leq\mu_{2}$. Given two points
$x_{1}^{\star},x^{\star}_{2}\in\mathbb{R}^{n}$, a point
$x^{\star}\in\mathbb{R}^{n}$ is a minimizer of the sum $f_{1}(x)+f_{2}(x)$ for
some functions $f_{1}\in\mathcal{M}_{\mu,L}(x^{\star}_{1})$ and
$f_{2}\in\mathcal{M}_{\mu,L}(x^{\star}_{2})$ if and only if the following
holds

$\displaystyle\mu_{2}\|x^{\star}-x_{2}^{\star}\|^{2}+\tfrac{L_{1}+\mu_{1}}{2}\langle
x^{\star}-x_{1}^{\star},x^{\star}-x^{\star}_{2}\rangle\leq$
$\displaystyle\tfrac{L_{1}-\mu_{1}}{2}\|x^{\star}-x^{\star}_{1}\|\|x^{\star}-x^{\star}_{2}\|.$
(6)

###### Proof:

Due to Lemma II.2 and the optimality conditions for the sum
$f_{1}(x)+f_{2}(x)$, $x^{\star}$ is a potential minimizer iff the following
system has a solution (using both (3) and (4))

$\displaystyle\big{\|}g_{1}-\tfrac{L_{1}+\mu_{1}}{2}(x^{\star}-x_{1}^{\star})\big{\|}\leq\tfrac{L_{1}-\mu_{1}}{2}\|x^{\star}-x^{\star}_{1}\|,$
$\displaystyle\langle
g_{2},x^{\star}-x_{2}^{\star}\rangle\geq\mu_{2}\|x^{\star}-x^{\star}_{2}\|^{2},$
$\displaystyle g_{1}+g_{2}=0.$

Replacing $g_{2}$ by $-g_{1}$, the above system becomes

$\displaystyle\big{\|}g_{1}-\tfrac{L_{1}+\mu_{1}}{2}(x^{\star}-x_{1}^{\star})\big{\|}\leq\tfrac{L_{1}-\mu_{1}}{2}\|x^{\star}-x^{\star}_{1}\|,$
$\displaystyle\langle-
g_{1},x^{\star}-x_{2}^{\star}\rangle\geq\mu_{2}\|x^{\star}-x^{\star}_{2}\|^{2}.$

The desired inequality follows from the necessary and sufficient condition for
the intersection between a ball and a half-space to be nonempty. ∎

Proposition III.2 also corresponds to Proposition III.1 in the limit when
$L_{2}$ tends to infinity; see the discussion before Corollary IV.2. Figure
LABEL:fig.P2 shows the set of potential minimizer $x^{\star}$ from Proposition
III.2 for two different sets of parameters in $\mathbb{R}^{2}$. As before,
this set is bounded when $\mu_{1}+\mu_{2}>0$.

When none of the functions is smooth, i.e. when $L_{1}=L_{2}=\infty$, the
situation becomes qualitatively different. Indeed, as shown in [7], the set of
potential minimizers becomes unbounded and its closure is equal to the whole
$\mathbb{R}^{n}$ when $n\geq 2$. Hence, similarly to [7], we consider an
additional condition on the minimizer: we assume that the subgradients of
$f_{1}$ and $f_{2}$ at the minimizer $x^{\star}$ have their norm bounded by a
constant $B$ (note that since those subgradients sum to zero, they have the
same norm).

Since the case $\mu_{1}=\mu_{2}=0$ is uninteresting (all points can be
minimizers in that case), we assume from here that $\mu_{1}+\mu_{2}>0$, i.e.
that function $f$ is strongly convex. Using condition (3) from Lemma II.2, we
have that the subgradient $g_{1}$ at a potential minimizer $x^{\star}$ must
satisfy $\|g_{1}\|\geq\mu_{1}\|x_{1}^{\star}-x^{\star}\|$, hence the upper
bound $B$ on its norm must satisfy $B\geq\mu_{1}\|x_{1}^{\star}-x^{\star}\|$.
Similarly, we must have $B\geq\mu_{2}\|x_{2}^{\star}-x^{\star}\|$ (also
showing that the set of potential minimizers is bounded). Combining with
$\|x_{1}^{\star}-x^{\star}\|+\|x_{2}^{\star}-x^{\star}\|\geq\|x_{1}^{\star}-x_{2}^{\star}\|$
(triangle inequality), these two inequalities imply that

$B\geq\tfrac{\mu_{1}\mu_{2}}{\mu_{1}+\mu_{2}}\|x_{1}^{\star}-x_{2}^{\star}\|.$
(7)

Define the focal point
$x_{f}=\tfrac{\mu_{1}}{\mu_{1}+\mu_{2}}x^{\star}_{1}+\tfrac{\mu_{1}}{\mu_{1}+\mu_{2}}x^{\star}_{2}$,
easily seen to be the minimizer of the sum of
$f_{1}(x)=\tfrac{\mu_{1}}{2}\|x-x_{1}^{\star}\|^{2}$ and
$f_{2}(x)=\tfrac{\mu_{2}}{2}\|x-x_{2}^{\star}\|^{2}$. Since we also have
$\|\nabla
f_{1}(x_{f})\|=\tfrac{\mu_{1}\mu_{2}}{\mu_{1}+\mu_{2}}\|x_{1}^{\star}-x_{2}^{\star}\|$,
the bound (7) is necessary and sufficient for the set of minimizers to be
nonempty.

We believe the following characterization is easier to state and slightly more
complete than the one proposed in [7].

###### Proposition III.3

Let $\mu_{1},\mu_{2}\geq 0$ such that $\mu_{1}+\mu_{2}>0$. Given two points
$x_{1}^{\star}\neq x^{\star}_{2}\in\mathbb{R}^{n}$ and a bound $B$ satisfying
(7), a point $x^{\star}\in\mathbb{R}^{n}$ is a minimizer of the sum
$f_{1}(x)+f_{2}(x)$ for some functions
$f_{1}\in\mathcal{M}_{\mu_{1},\infty}(x^{\star}_{1})$,
$f_{2}\in\mathcal{M}_{\mu_{2},\infty}(x^{\star}_{2})$ with $\|g\|\leq B$ for
some $g\in\partial f_{1}(x^{\star})$ if and only if it satisfies

$\mu_{1}\|x^{\star}-x^{\star}_{1}\|\leq B\text{ and
}\mu_{2}\|x^{\star}-x^{\star}_{2}\|\leq B$

and at least an additional inequality among the following:

$\displaystyle(i)\ \mu_{1}\langle
x_{1}^{\star}-x^{\star},x^{\star}-x^{\star}_{2}\rangle\geq\mu_{2}\|x^{\star}-x^{\star}_{2}\|^{2}$
$\displaystyle(ii)\ \mu_{2}\langle
x_{2}^{\star}-x^{\star},x^{\star}-x^{\star}_{1}\rangle\geq\mu_{1}\|x^{\star}-x^{\star}_{1}\|^{2}$
$\displaystyle(iii)\
\det\left(M(x^{\star},x^{\star}_{1},x^{\star}_{2},B^{2})\right)\geq 0.$

where matrix $M(x^{\star},x^{\star}_{1},x^{\star}_{2},\alpha)$ be given as
follows

$\begin{pmatrix}1&\tfrac{\langle
x^{\star}-x_{1}^{\star},x^{\star}-x^{\star}_{2}\rangle}{\|x^{\star}-x^{\star}_{1}\|\|x^{\star}-x^{\star}_{2}\|}&\mu_{1}\|x^{\star}-x^{\star}_{1}\|\\\
\tfrac{\langle
x^{\star}-x_{1}^{\star},x^{\star}-x^{\star}_{2}\rangle}{\|x^{\star}-x^{\star}_{1}\|\|x^{\star}-x^{\star}_{2}\|}&1&-\mu_{2}\|x^{\star}-x^{\star}_{2}\|\\\
\mu_{1}\|x^{\star}-x^{\star}_{1}\|&-\mu_{2}\|x^{\star}-x^{\star}_{2}\|&\alpha\end{pmatrix}.$

###### Proof:

Using Lemma II.2, we see that $x^{\star}$ is a potential minimizer if and only
if the optimal value of the following convex problem is less than or equal to
$B^{2}$,

$\displaystyle\min\ \|g\|^{2}\ \operatorname*{s.t.}\ $ $\displaystyle\ \langle
g,x^{\star}_{1}-x^{\star}\rangle\leq-\mu_{1}\|x^{\star}-x^{\star}_{1}\|^{2}$
(8) $\displaystyle\ \langle
g,x^{\star}-x^{\star}_{2}\rangle\leq-\mu_{2}\|x^{\star}-x^{\star}_{2}\|^{2}$

It is seen that the problem has a unique solution. Due to the optimality
condition, the feasible point $g$ is the optimal solution of problem (8) iff
there exist $\lambda_{1},\lambda_{2}\geq 0$ with

$\displaystyle
g=\lambda_{1}(x^{\star}-x^{\star}_{1})+\lambda_{2}(x_{2}^{\star}-x^{\star}),$
$\displaystyle\lambda_{1}\left(\langle
g,x^{\star}_{1}-x^{\star}\rangle+\mu_{1}\|x^{\star}-x^{\star}_{1}\|^{2}\right)=0$
$\displaystyle\lambda_{2}\left(\langle
g,x^{\star}-x^{\star}_{2}\rangle+\mu_{2}\|x^{\star}-x^{\star}_{2}\|^{2}\right)=0.$

As $x_{1}^{\star}\neq x^{\star}_{2}$, the optimal value cannot be zero, and at
least one constraint is active at the optimal solution. If the first
constraint is active, the optimal value is less that or equal to $B^{2}$ iff

$\mu_{1}\|x^{\star}-x^{\star}_{1}\|\leq B,\mu_{1}\langle
x_{1}^{\star}-x^{\star},x^{\star}-x^{\star}_{2}\rangle\geq\mu_{2}\|x^{\star}-x^{\star}_{2}\|^{2}.$

The case that the second is active is shown analogously. Now, we consider the
case that both constraints are active. Without loss of generality, we assume
that $x^{\star}-x^{\star}_{1}$ and $x^{\star}-x^{\star}_{2}$ are not parallel.
The case that these vectors are parallel is covered by the former cases.
Consider the Gram matrix composed of $x^{\star}-x^{\star}_{1}$,
$x^{\star}-x^{\star}_{2}$ and $g$. In this case, problem (8) and the following
semi-definite program share the same optimal value,

$\min\ \alpha\ \operatorname*{s.t.}\
M(x^{\star},x^{\star}_{1},x^{\star}_{2},\alpha)\succeq 0.$ (9)

Note that we factor $\|x^{\star}-x^{\star}_{1}\|^{2}$ and
$\|x^{\star}-x^{\star}_{2}\|^{2}$ in problem (9) as $x^{\star}\neq
x_{1}^{\star},x_{2}^{\star}$. The optimal value of semi-definite program (9)
is less than or equal to $B^{2}$ iff
$\det\left(M(x^{\star},x^{\star}_{1},x^{\star}_{2},B^{2})\right)\geq 0$. This
follows from the fact that a symmetric matrix is positive definite iff its
leading principal minors are positive. To complete the proof, we need to show
that if $x^{\star}-x^{\star}_{1}$ and $x^{\star}-x^{\star}_{2}$ are parallel
and $\det(M(x^{\star},x^{\star}_{1},x^{\star}_{2},B^{2})\geq 0$, then
$x^{\star}$ is a potential minimizer. In this case, we have

$\det\left(M(x^{\star},x^{\star}_{1},x^{\star}_{2},\alpha)\right)=-\|\mu_{1}(x^{\star}-x^{\star}_{1})+\mu_{2}(x^{\star}-x^{\star}_{2})\|^{2},$

which implies $x^{\star}=x_{f}$ and the proof is complete. ∎

Closedness of the potential set of minimizers under the assumptions of
Proposition III.3 follows from closedness of the intersection of the feasible
region of (8) and $\|g\|\leq B$. Figure LABEL:fig.P3 shows the set of
potential minimizer $x^{\star}$ from Proposition III.3 for two different sets
of parameters in $\mathbb{R}^{2}$ (colors green and red correspond to the
first two inequalities, color blue corresponds to the third determinant
condition). Note that a potential minimizer may satisfy more than one system
among the three systems given in Proposition III.3.

Our last theorem bounds the distance between any minimizer in Proposition
III.3 and the focal point $x_{f}$.

###### Theorem III.4

Any minimizer $x^{*}$ verifying the assumptions of Proposition III.3 must
satisfy

$\displaystyle\left\|x^{\star}-x_{f}\right\|^{2}\leq\min\big{(}\tfrac{B}{\mu_{1}+\mu_{2}}\left\|x_{1}^{\star}-x_{2}^{\star}\right\|-\tfrac{\mu_{1}\mu_{2}}{(\mu_{1}+\mu_{2})^{2}}$
$\displaystyle\hskip
85.35826pt\left\|x_{1}^{\star}-x_{2}^{\star}\right\|^{2},\tfrac{B^{2}}{(\mu_{1}+\mu_{2})^{2}}\big{)}.$

###### Proof:

We may assume w.l.o.g. that
$x^{\star}_{1}=\tfrac{\mu_{2}\left\|x_{1}^{\star}-x_{2}^{\star}\right\|}{\mu_{1}+\mu_{2}}e_{1}$
and
$x^{\star}_{2}=-\tfrac{\mu_{1}\left\|x_{1}^{\star}-x_{2}^{\star}\right\|}{\mu_{1}+\mu_{2}}e_{1}$,
which implies that $x_{f}=0$ and

$\displaystyle\mu_{1}\left\|x_{1}^{\star}\right\|^{2}+\mu_{2}\left\|x_{2}^{\star}\right\|^{2}=\tfrac{\mu_{1}\mu_{2}}{\mu_{1}+\mu_{2}}\left\|x_{1}^{\star}-x_{2}^{\star}\right\|^{2}.$
(10)

First, we establish

$\left\|x^{\star}-x_{f}\right\|^{2}\leq\tfrac{B}{\mu_{1}+\mu_{2}}\left\|x_{1}^{\star}-x_{2}^{\star}\right\|-\tfrac{\mu_{1}\mu_{2}}{(\mu_{1}+\mu_{2})^{2}}\left\|x_{1}^{\star}-x_{2}^{\star}\right\|^{2}.$

By (3), we have

$\displaystyle\langle
g,x^{\star}-x^{\star}_{1}\rangle\geq\mu_{1}\left\|x^{\star}-x^{\star}_{1}\right\|^{2},$
$\displaystyle\langle-g,x^{\star}-x^{\star}_{2}\rangle\geq\mu_{2}\left\|x^{\star}-x^{\star}_{2}\right\|^{2}.$

By summing these inequalities, we get

$\displaystyle\langle
g,x^{\star}_{2}-x^{\star}_{1}\rangle\geq\mu_{1}\left\|x_{1}^{\star}\right\|^{2}+\mu_{2}\left\|x_{2}^{\star}\right\|^{2}+(\mu_{1}+\mu_{2})\left\|x^{\star}\right\|^{2}.$

and we conclude with Cauchy–Schwarz inequality and (10)

$(\mu_{1}+\mu_{2})\left\|x^{\star}\right\|^{2}\leq{B}\left\|x_{1}^{\star}-x_{2}^{\star}\right\|-\tfrac{\mu_{1}\mu_{2}}{\mu_{1}+\mu_{2}}\left\|x_{1}^{\star}-x_{2}^{\star}\right\|^{2}.$

Now, we prove that
$\|x^{\star}-x_{f}\|^{2}\leq\tfrac{B^{2}}{(\mu_{1}+\mu_{2})^{2}}$. Suppose
that $\gamma=\tfrac{1}{(\mu_{1}+\mu_{2})^{2}}$. Consider the following
inequalities,

$\displaystyle\gamma\left(B^{2}-\|g\|^{2}\right)\geq 0,$ $\displaystyle
2\mu_{1}\gamma\left(\langle
g,x^{\star}-x^{\star}_{1}\rangle-\mu_{1}\left\|x^{\star}-x^{\star}_{1}\right\|^{2}\right)\geq
0,$ $\displaystyle
2\mu_{2}\gamma\left(\langle-g,x^{\star}-x^{\star}_{2}\rangle-\mu_{2}\left\|x^{\star}-x^{\star}_{2}\right\|^{2}\right)\geq
0.$

By summing these inequalities, we get

$\gamma
B^{2}-\left\|x^{\star}\right\|^{2}-\gamma\left\|\mu_{1}x_{1}^{\star}-\mu_{2}x_{2}^{\star}+(\mu_{2}-\mu_{1})x^{\star}+g\right\|^{2}\geq
0,$

which implies the desired inequality. ∎

##  IV Minimizers of a sum of $m$ convex functions

We now extend the results of Section III to sums of more than two functions,
and start with the smooth case.

###### Theorem IV.1

Let $0\leq\mu_{i}<L_{i}<\infty$ for all $i\in[m]$. Given $m$ points
$x_{i}^{\star}\in\mathbb{R}^{n}$, $i\in[m]$, a point
$x^{\star}\in\mathbb{R}^{n}$ is a minimizer of the sum
$\sum_{i=1}^{m}f_{i}(x)$ for some functions
$f_{i}\in\mathcal{M}_{\mu_{i},L_{i}}(x^{\star}_{i})$, $i\in[m]$ if and only if

$\big{\|}\sum_{i\in[m]}(L_{i}+\mu_{i})(x^{\star}-x_{i}^{\star})\big{\|}\leq\sum_{i\in[m]}(L_{i}-\mu_{i})\|x^{\star}-x^{\star}_{i}\|.$
(11)

###### Proof:

The proof is analogous to that of Proposition III.1. Due to the optimality
conditions, $x^{\star}$ is a minimizer of $\sum_{i\in[m]}f_{i}(x)$ iff there
exist $g_{i}\in\partial f_{i}(x^{\star})$, $i\in[m]$ such that
$\sum_{i\in[m]}g_{i}=0$. Hence, by Lemma II.2,
$x^{\star}\in\operatorname*{argmin}\sum_{i\in[m]}f_{i}$ with
$f_{i}\in\mathcal{M}_{\mu_{i},L_{i}}(x^{\star}_{i})$ for $i\in[m]$ iff there
exists $g_{i},i\in[m]$ satisfying $\sum_{i\in[m]}g_{i}=0$ and

$\big{\|}g_{i}-\tfrac{L_{i}+\mu_{i}}{2}(x^{\star}-x_{i}^{\star})\big{\|}\leq\tfrac{L_{i}-\mu_{i}}{2}\|x^{\star}-x^{\star}_{i}\|,\
i\in[m]$

Below we use $L^{+}_{i}=\frac{L_{i}+\mu_{i}}{2}$ and
$L^{-}_{i}=\frac{L_{i}-\mu_{i}}{2}$ for convenience. Replacing $g_{m}$ with
$-\sum_{i\in[m-1]}g_{i}$, we obtain

$\displaystyle\big{\|}g_{i}-L^{+}_{i}(x^{\star}-x_{i}^{\star})\big{\|}\leq
L^{-}_{i}\|x^{\star}-x^{\star}_{1}\|,\ i\in[m-1]$
$\displaystyle\big{\|}\textstyle\sum_{i\in[m-1]}g_{i}+L^{+}_{m}(x^{\star}-x_{m}^{\star})\big{\|}\leq
L^{-}_{m}\|x^{\star}-x^{\star}_{m}\|.$

We check the consistency of this system by an elimination method. We first
investigate the solvability with respect to $g_{m-1}$ while
$g_{1},\dots,g_{m-2}$ are fixed. As $g_{m-1}$ only appears in the following
two inequalities, defining two balls

$\displaystyle\big{\|}g_{m-1}-L^{+}_{m-1}(x^{\star}-x_{m-1}^{\star})\big{\|}\leq
L^{-}_{m-1}\|x^{\star}-x^{\star}_{m-1}\|$ $\displaystyle\big{\|}\textstyle
g_{m-1}+\sum_{i\in[m-2]}g_{i}+L^{+}_{m}(x^{\star}-x_{m}^{\star})\big{\|}\leq
L^{-}_{m}\|x^{\star}-x^{\star}_{m}\|,$

the system has a solution in terms of $g_{m-1}$ iff distance between the two
ball centers is not greater than the sum of the two radii, leading to the
inequality

$\displaystyle\big{\|}\textstyle\sum_{i\in[m-2]}g_{i}+L^{+}_{m}(x^{\star}-x_{m}^{\star})+L^{+}_{m-1}(x^{\star}-x_{m-1}^{\star})\big{\|}$
$\displaystyle\leq$ $\displaystyle\
L^{-}_{m}\|x^{\star}-x^{\star}_{m}\|+L^{-}_{m-1}\|x^{\star}-x^{\star}_{m-1}\|.$

Consider now at $g_{m-2}$, which must again lie in the intersection of two
balls: applying the same principle leads to an inequality of the same form as
above, with one more term with $L^{+}_{m-2}$ inside of the left-hand side
norm, and one more norm term with $L^{-}_{m-2}$ on the right-hand side. A
simple induction argument then completes the proof. ∎

The potential minimizer set in Theorem IV.1 is closed and bounded set if
$\sum_{i\in[m]}\mu_{i}>0$. If $x^{\star}_{i}$’s are distinct, inequality (11)
is satisfied strictly for the focal point
$x_{f}=\tfrac{1}{\sum_{i\in[m]}L_{i}+\mu_{i}}\sum_{i\in[m]}(L_{i}+\mu_{i})x^{\star}_{i}$,
and the interior of the minimizer set is non-empty.

We now consider the case where (exactly) one summand is not smooth, using a
limiting argument. Rewriting (11) as

$\displaystyle\textstyle\frac{1}{2}\sum_{i\in[m]}\mu_{i}L_{i}\|x^{\star}-x_{i}^{\star}\|^{2}+\sum_{\begin{subarray}{c}i<j\end{subarray}}L^{+}_{i}L^{+}_{j}\langle
x^{\star}-x_{i}^{\star},x^{\star}-x_{j}^{\star}\rangle$
$\displaystyle\textstyle\leq\textstyle\sum_{\begin{subarray}{c}i<j,i,j\in[m]\end{subarray}}L^{-}_{i}L^{-}_{j}\|x^{\star}-x^{\star}_{i}\|\|x^{\star}-x^{\star}_{j}\|$
(12)

dividing both sides by $L_{m}$ and taking the limit as $L_{m}\to\infty$, we
obtain the inequality of the following Corollary.

###### Corollary IV.2

Let $0\leq\mu_{i}<L_{i}<\infty$ for all $i\in[m-1]$ and
$0\leq\mu_{m}<L_{m}=\infty$. Given $m$ points
$x_{i}^{\star}\in\mathbb{R}^{n}$, a point $x^{\star}\in\mathbb{R}^{n}$ is a
minimizer of the sum $\sum_{i=1}^{m}f_{i}(x)$ for some functions
$f_{i}\in\mathcal{M}_{\mu_{i},L_{i}}(x^{\star}_{i})$, $i\in[m]$ if and only if

$\displaystyle\sum_{i\in[m-1]}\tfrac{L_{i}+\mu_{i}}{2}\langle
x^{\star}-x_{i}^{\star},x^{\star}-x_{m}^{\star}\rangle+\mu_{m}\|x^{\star}-x_{m}^{\star}\|^{2}$
$\displaystyle\leq$
$\displaystyle\sum_{i\in[m-1]}\tfrac{L_{i}-\mu_{i}}{2}\|x^{\star}-x^{\star}_{i}\|\|x^{\star}-x^{\star}_{m}\|.$

Observe that if more than one summand is not smooth, the set of potential
minimizers may become very large set, as its closure may be whole space [7].

In some cases, some functions are only unknown. The following proposition
addresses this situation. For the simplicity of the presentation, we assume
that the known functions $f_{i}$, $i\in[\ell]$, are differentiable.

###### Proposition IV.3

Let $f_{i}\in\mathcal{F}_{0,\infty}$, $i\in[\ell]$ be $l$ known differentiable
convex functions. Let $0\leq\mu_{i}<L_{i}<\infty$ for all $i\in[\ell,m]$.
Given $m-l$ points $x_{i}^{\star}\in\mathbb{R}^{n}$, $i\in[\ell+1,m]$, a point
$x^{\star}\in\mathbb{R}^{n}$ is a minimizer of the sum
$\sum_{i=1}^{m}f_{i}(x)$ for some functions
$f_{i}\in\mathcal{M}_{\mu_{i},L_{i}}(x^{\star}_{i})$, $i\in[\ell+1,m]$ if and
only if

$\displaystyle\big{\|}2\sum_{i\in[\ell]}\nabla
f_{i}(x^{\star})+\sum_{i\in[\ell+1,m]}(L_{i}+\mu_{i})(x^{\star}-x_{i}^{\star})\big{\|}\leq$
$\displaystyle\ \ \
\sum_{i\in[\ell+1,m]}(L_{i}-\mu_{i})\|x^{\star}-x^{\star}_{i}\|.$

###### Proof:

By Lemma II.2, $x^{\star}$ a potential minimizer iff the following system has
a solution,

$\displaystyle\big{\|}g_{i}-\tfrac{L_{i}+\mu_{i}}{2}(x^{\star}-x_{i}^{\star})\big{\|}\leq\tfrac{L_{i}-\mu_{i}}{2}\|x^{\star}-x^{\star}_{1}\|,i\in[\ell+1,m]$
$\displaystyle\big{\|}\sum_{i\in[\ell+1,m-1]}g_{i}+\sum_{i\in[\ell]}\nabla
f_{i}(x^{\star})+\tfrac{L_{m}+\mu_{m}}{2}(x^{\star}-x_{m}^{\star})\big{\|}\leq$
$\displaystyle\ \tfrac{L_{m}-\mu_{m}}{2}\|x^{\star}-x^{\star}_{m}\|.$

Analogous to the proof of Theorem IV.1, one can infer the desired inequality
and the proof is complete. ∎

Similar to Corollary IV, we can characterize the potential set when
$L_{m}=\infty$ by using Proposition IV.3. The following corollary states this
point.

###### Corollary IV.4

Let $f_{i}\in\mathcal{F}_{0,\infty}$, $i\in[\ell]$, be known and
differentiable convex functions. Assume that $L_{i}<\infty$ for
$i\in[\ell+1,m-1]$ and $\mu_{i}$ and $x^{\star}_{i}$ for $i\in[\ell+1,m]$ are
given. The point $x^{\star}\in\operatorname*{argmin}\sum_{i\in[m]}f_{i}(x)$
for some $f_{i}\in\mathcal{M}_{\mu_{i},L_{i}}(x^{\star}_{i})$,
$i\in[\ell+1,m-1]$, and $f_{m}\in\mathcal{M}_{\mu_{m},\infty}(x_{m}^{\star})$
iff

$\displaystyle\mu_{m}\|x^{\star}-x_{m}^{\star}\|^{2}+\sum_{i\in[\ell]}\langle\nabla
f(x^{\star}),x^{\star}-x_{m}^{\star}\rangle+$
$\displaystyle\sum_{i\in[\ell+1,m-1]}\tfrac{L_{i}+\mu_{i}}{2}\langle
x^{\star}-x_{i}^{\star},x^{\star}-x_{m}^{\star}\rangle\leq$ $\displaystyle\ \
\
\sum_{i\in[\ell+1,m-1]}\tfrac{L_{i}-\mu_{i}}{2}\|x^{\star}-x^{\star}_{i}\|\|x^{\star}-x^{\star}_{m}\|.$

##  V Bounds when summand minimizers lie in a ball

Hendrickx et al. [8] consider a sum of smooth strongly convex functions
$f_{i}\in\mathcal{F}_{\mu,L}(\mathbb{R}^{n})$ in the case that all summand
minimizers $x_{i}^{\star}$ lie in a unit ball centered at the origin, i.e.
$\|x^{\star}_{i}\|\leq 1$ for all $i\in[m]$. In [8, Theorem 1] they prove the
following bound on the norm of a potential minimizer $x^{\star}$

$\|x^{\star}\|\leq 1+\sqrt{\kappa},\quad\text{where $\kappa=\tfrac{L}{\mu}$.}$

The following theorem gives a tighter bound.

###### Theorem V.1

Let $f_{i}\in\mathcal{M}_{\mu,L}(x^{\star}_{i})$ with $0<\mu<L<\infty$,
$i\in[m]$, and $\|x^{\star}_{i}-\bar{x}\|\leq 1$. If
$x^{\star}\in\operatorname*{argmin}\sum_{i=1}^{m}f_{i}(x)$ then

$\|x^{\star}-\bar{x}\|\leq\tfrac{1}{2}\left(\sqrt{\kappa}+\tfrac{1}{\sqrt{\kappa}}\right),\quad\text{where
$\kappa=\tfrac{L}{\mu}$.}$

###### Proof:

Without loss of generality, we may assume that $\bar{x}=0$. Since
$2\|x^{\star}-x^{\star}_{i}\|\|x^{\star}-x^{\star}_{j}\|\leq\|x^{\star}-x^{\star}_{i}\|^{2}+\|x^{\star}-x^{\star}_{j}\|^{2}$,
inequality (IV) may be written as

$\displaystyle
4\kappa\sum_{i\in[m]}\|x^{\star}-x_{i}^{\star}\|^{2}+2(\kappa+1)^{2}\sum_{\begin{subarray}{c}i<j\\\
i,j\in[m]\end{subarray}}\langle
x^{\star}-x_{i}^{\star},x^{\star}-x_{j}^{\star}\rangle$
$\displaystyle-(\kappa-1)^{2}\sum_{\begin{subarray}{c}i<j\\\
i,j\in[m]\end{subarray}}\left(\|x^{\star}-x^{\star}_{i}\|^{2}+\|x^{\star}-x^{\star}_{j}\|^{2}\right)=$
(13)
$\displaystyle\kappa\left((\sqrt{\kappa}+\tfrac{1}{\sqrt{\kappa}})^{2}-m(\sqrt{\kappa}-\tfrac{1}{\sqrt{\kappa}})^{2}\right)\sum_{i\in[m]}\|x^{\star}-x_{i}^{\star}\|^{2}+$
$\displaystyle
2\kappa\left(\sqrt{\kappa}+\tfrac{1}{\sqrt{\kappa}}\right)^{2}\sum_{\begin{subarray}{c}i<j\\\
i,j\in[m]\end{subarray}}\langle
x^{\star}-x_{i}^{\star},x^{\star}-x_{j}^{\star}\rangle\leq 0.$

By the assumptions, we have for $i\in\\{1,\dots,m\\}$

$\displaystyle\|x^{\star}-x^{\star}_{i}\|^{2}+\|x^{\star}\|^{2}+2\langle
x^{\star}-x^{\star}_{i},x^{\star}\rangle-1\leq 0.$ (14)

Suppose that
$\alpha=\big{(}\tfrac{1}{2m\sqrt{\kappa}(\sqrt{\kappa}-\tfrac{1}{\sqrt{\kappa}})}\big{(}\sqrt{\kappa}+\tfrac{1}{\sqrt{\kappa}}\big{)}\big{)}^{2}$.
By multiplying inequalities (V) and (14) by $\alpha$ and
$\tfrac{1}{4m}\big{(}\sqrt{\kappa}+\tfrac{1}{\sqrt{\kappa}}\big{)}^{2}$,
respectively, and summing these $m+1$ inequalities we get

$\displaystyle\|x^{\star}\|^{2}-\tfrac{1}{4}\big{(}\sqrt{\kappa}+\tfrac{1}{\sqrt{\kappa}}\big{)}^{2}+\big{\|}\tfrac{1}{2}(\sqrt{\kappa}-\tfrac{1}{\sqrt{\kappa}})x^{\star}+\sqrt{\alpha}(\kappa+1)$
$\displaystyle\ \ \sum_{i\in[m]}(x^{\star}-x^{\star}_{i})\big{\|}^{2}\leq 0.$

The above inequality implies the desired bound and the proof is complete. ∎

We now addresses the setting where one of the functions (w.l.o.g. $f_{m}$) is
an arbitrary closed proper convex function.

###### Theorem V.2

Let $f_{i}\in\mathcal{M}_{\mu,L}(x_{i}^{\star})$, $i\in[m-1]$, with
$0<\mu<L<\infty$ and let $f_{m}\in\mathcal{M}_{0,\infty}(x_{m}^{\star})$.
Assume that $\|x^{\star}_{i}-\bar{x}\|\leq 1$ for $i\in[m]$. If
$x^{\star}\in\operatorname*{argmin}\sum_{i=1}^{m}f_{i}(x)$ then

$\|x^{\star}-\bar{x}\|\leq\sqrt{\kappa+1},\ \ \text{where
$\kappa=\tfrac{L}{\mu}$.}$

###### Proof:

The proof is analogous to that of Theorem V.1. We assume that $\bar{x}=0$. By
Corollary IV.2, we have

$\displaystyle(\kappa+1)\sum_{i\in[m-1]}\langle
x^{\star}-x_{i}^{\star},x^{\star}-x_{m}^{\star}\rangle-\tfrac{1}{2}(\kappa-1)$
$\displaystyle\sum_{i\in[m-1]}\left(\|x^{\star}-x^{\star}_{i}\|^{2}+\|x^{\star}-x^{\star}_{m}\|^{2}\right)\leq
0.$ (15)

By the assumptions, we have for $i\in[m-1]$

$\displaystyle\|x^{\star}-x^{\star}_{i}\|^{2}+\|x^{\star}\|^{2}+2\langle
x^{\star}-x^{\star}_{i},x^{\star}\rangle-1\leq 0,$ (16)

and

$\displaystyle\|x^{\star}-x^{\star}_{m}\|^{2}+\|x^{\star}\|^{2}+2\langle
x^{\star}-x^{\star}_{m},x^{\star}\rangle-1\leq 0.$ (17)

By multiplying inequalities (V), (16) and (17) by
$\tfrac{1}{2m-2}(1+\tfrac{1}{\kappa})$, $\tfrac{1}{2m-2}(\kappa+1)$ and
$\tfrac{1}{2}(\kappa+1)$, respectively, and summing them we obtain

$\displaystyle\|x^{\star}\|^{2}-(\kappa+1)+\tfrac{1}{4\kappa(m-1)}\sum_{i\in[m-1]}\big{\|}2\kappa
x^{\star}+(\kappa+1)(x^{\star}-$ $\displaystyle\
x^{\star}_{m})+(\kappa+1)(x^{\star}-x^{\star}_{i})\big{\|}^{2}\leq 0.$

The above inequality implies the desired bound and the proof is complete. ∎

##  VI Conclusions

This work has demonstrated how the use of interpolation constraints simplifies
the analysis of questions about convex functions and their minimizers. This
framework can in principle allow for even more accurate descriptions of those
sets of potential minimizers if additional information on the summands is
provided, such as the bounds or exact values of the summands or their gradient
at some remarkable points.

## References

  * [1] A. Nedić and J. Liu, “Distributed optimization for control,” _Annual Review of Control, Robotics, and Autonomous Systems_ , vol. 1, pp. 77–103, 2018.
  * [2] T. Yang, X. Yi, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin, and K. H. Johansson, “A survey of distributed optimization,” _Annual Reviews in Control_ , vol. 47, pp. 278–305, 2019.
  * [3] S. Sundaram and B. Gharesifard, “Distributed optimization under adversarial nodes,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 3, pp. 1063–1076, 2018.
  * [4] J. Konečnỳ, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” _arXiv preprint arXiv:1610.05492_ , 2016.
  * [5] K. Kuwaranancharoen and S. Sundaram, “On the location of the minimizer of the sum of two strongly convex functions,” in _2018 IEEE Conference on Decision and Control (CDC)_. IEEE, 2018, pp. 1769–1774.
  * [6] ——, “On the set of possible minimizers of a sum of known and unknown functions,” in _2020 American Control Conference (ACC)_. IEEE, 2020, pp. 106–111.
  * [7] ——, “The minimizer of the sum of two strongly convex functions,” _arXiv preprint arXiv:2305.13134_ , 2023.
  * [8] J. M. Hendrickx and M. G. Rabbat, “Stability of decentralized gradient descent in open multi-agent systems,” in _2020 59th IEEE Conference on Decision and Control (CDC)_. IEEE, 2020, pp. 4885–4890.
  * [9] A. B. Taylor, J. M. Hendrickx, and F. Glineur, “Smooth strongly convex interpolation and exact worst-case performance of first-order methods,” _Mathematical Programming_ , vol. 161, pp. 307–345, 2017.
  * [10] A. Rubbens, N. Bousselmi, S. Colla, and J. M. Hendrickx, “Interpolation constraints for computing worst-case bounds in performance estimation problems,” in _2023 62nd IEEE Conference on Decision and Control (CDC)_. IEEE, 2023, pp. 3015–3022.