Similarly, for every $\textbf{a}\in\textbf{a}_{2}(u)$, we get the following

$\displaystyle{}\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|+\eta)=\mathfrak{h}\left(\min\limits_{a\in\texttt{Set}(\textbf{a})}(|u-a|+\eta)\right)$
$\displaystyle\overset{(b)}{\leq}\mathfrak{h}\left(\min\limits_{a\in\texttt{Set}(\textbf{a})}|u-a|\right)\cdot
e^{M\eta}$
$\displaystyle=\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\cdot
e^{M\eta}$ (45)

$(b)$ follows since, $\log\mathfrak{h}(z)$ is Lipschitz-continous in
$[\mathcal{B},\infty)$, thus
$\mathfrak{h}(z+\eta)\leq\mathfrak{h}(z)e^{M\eta}$ for $z\geq\mathcal{B}$.

Combining equations (B.2.3) and (B.2.3) coupled with the fact that
$\textbf{a}_{1}(u)\cup\textbf{a}_{2}(u)=\mathbb{R}^{k}$, we get the following
result for every $\textbf{a}\in\mathbb{R}^{k}$

$\displaystyle\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|+\eta)$
$\displaystyle\leq\max\left(\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\cdot
e^{M\eta},\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)+\kappa(\eta)\right)$
(46)
$\displaystyle\leq\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\cdot
e^{M\eta}+\kappa(\eta)$ (47)

With this, we now observe that

$\displaystyle\sup_{u\in\mathbb{R}}\left(\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|+\eta)\right]\right)\leq\sup_{u\in\mathbb{R}}\left(\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]\right)e^{M\eta}+\kappa(\eta)$
$\displaystyle\overset{(c)}{\implies}$ $\displaystyle\lim\limits_{\eta\to
0}\left(\sup_{u\in\mathbb{R}}\left(\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|+\eta)\right]\right)\right)\leq\sup_{u\in\mathbb{R}}\left(\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]\right)$
(48)

$(c)$ follows since $\lim_{\eta\to 0}\kappa(\eta)=0$

Using a very similar approach, we can show that

$\displaystyle{}\lim\limits_{\eta\to
0}\left(\sup_{u\in\mathbb{R}}\left(\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(\left[|u-a|-\eta\right]_{+}\right]\right)\right)\geq\sup_{u\in\mathbb{R}}\left(\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]\right)$
(49)

Now, combining equations (B.2.3), (49) and bounds in equation (42) and (34),
we obtain

${}\lim_{\eta\to
0}\sup_{u\in\mathbb{R}}\left(\mathbb{E}_{\textbf{a}\sim{P}^{(\eta)}_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]\right)=\sup_{u\in\mathbb{R}}\left(\mathbb{E}_{\textbf{a}\sim
P_{u}}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]\right)$
(50)

Thus, we show that the distributions
$\textbf{P}^{(\eta)}\in\mathcal{P}^{(\epsilon)}_{\mathbb{R}^{k}}$ with a valid
probability density function defined by $\rho_{V}(u,.)$ arbitrarily
approximates P for every distribution
$\textbf{P}\in\mathcal{P}^{(\epsilon)}_{\mathbb{R}^{k}}$.

We now construct the DILP $\mathcal{O}$ in (13) where
$g(u,.):\mathbb{R}^{k}\rightarrow\mathbb{R}$ denotes the probability density
corresponding to ${P}^{(\eta)}_{u}$ for every $u\in\mathbb{R}$. The last 2
conditions in DILP $\mathcal{O}$ follow as a consequence of Lemma 2.6.

∎

###  B.3 Dual fitting: Proof of Lemma 2.10

######  Lemma (detailed proof of Lemma 2.10).

$\hat{\textbf{P}}^{\mathcal{L}_{\epsilon}}$ satisfies $\epsilon$-geographic
differential-privacy constraints i.e.
$\hat{P}^{\mathcal{L}_{\epsilon}}\in\mathcal{P}^{(\epsilon)}_{\mathbb{R}^{k}}$
and thus, we have
$f(\epsilon,k)\leq\text{cost}(\hat{\textbf{P}}^{\mathcal{L}_{\epsilon}})=\hat{f}(\epsilon,k)$

###### Proof.

We denote $\textbf{a}+z$ as $\textbf{a}+z\mathbbm{1}_{k}$ (i.e.) adding $z\in
U$ to every component of $\textbf{a}\in U^{k}$

$\displaystyle f(\epsilon,k)$
$\displaystyle\overset{(a)}{\leq}\sup_{u\in\mathbb{R}}\underset{\textbf{a}\sim\hat{P}^{\mathcal{L}_{\epsilon}}_{u}}{\mathbb{E}}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|u-a|)\right]$
$\displaystyle\overset{(b)}{=}\sup_{u\in\mathbb{R}}\underset{S_{u}\sim\mathcal{L}_{\epsilon}(u)}{\mathbb{E}}\left(\left[\min_{a\in\texttt{Set}(\hat{\textbf{a}})}\mathfrak{h}(|u-a|)\right]\Biggl{|}_{\hat{\textbf{a}}=\operatorname*{arg\,min}\limits_{\textbf{a}\in\mathbb{R}^{k}}\mathbb{E}_{y\sim\mathcal{L}_{\epsilon}(0)}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|y-a|)\right]+S_{u}}\right)$
$\displaystyle\overset{(c)}{=}\sup_{u\in\mathbb{R}}\underset{S_{u}\sim\mathcal{L}_{\epsilon}(u)}{\mathbb{E}}\left(\left[\min_{a\in\texttt{Set}(\hat{\textbf{b}})}\mathfrak{h}(|(u-S_{u})-a|)\right]\Biggl{|}_{\hat{\textbf{b}}=\operatorname*{arg\,min}\limits_{\textbf{a}\in\mathbb{R}^{k}}\mathbb{E}_{y\sim\mathcal{L}_{\epsilon}(0)}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|y-a|)\right]}\right)$
$\displaystyle\overset{(d)}{=}\sup_{u\in\mathbb{R}}\underset{y\sim\mathcal{L}_{\epsilon}(0)}{\mathbb{E}}\left[\min_{a\in\texttt{Set}(\hat{\textbf{b}})}\mathfrak{h}(|y-a|)\right]\Biggl{|}_{\hat{\textbf{b}}=\operatorname*{arg\,min}\limits_{\textbf{a}\in\mathbb{R}^{k}}\mathbb{E}_{y\sim\mathcal{L}_{\epsilon}(0)}\left[\min\limits_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|y-a|)\right]}$
$\displaystyle\overset{(e)}{=}\min_{\textbf{a}\in\mathbb{R}^{k}}\mathbb{E}_{y\sim\mathcal{L}_{\epsilon}(0)}\left[\min_{a\in\texttt{Set}(\textbf{a})}\mathfrak{h}(|y-a|)\right]=\hat{f}(\epsilon,k)$

$(a)$ follows from the fact that
$\hat{P}^{\mathcal{L}_{\epsilon}}\in\mathcal{P}^{(\epsilon)}_{\mathbb{R}^{k}}$
from the post processing theorem, refer to [27] since
$S_{u}\sim\mathcal{L}_{\epsilon}(u)$ satisfies $\epsilon$-geographic
differential privacy constraints.202020Post processing theorem can be proven
even for $\epsilon$-geographic differential privacy similarly. $(b)$ follows
from the definition in Equation (15) and $(c)$ follows on substituting
$\hat{\textbf{b}}=\hat{\textbf{a}}-S_{u}$ and $(d)$ follows on substituting
$u-S_{u}$ by $y$ and the fact that $\hat{\textbf{b}}$ is independent of
$S_{u}$ and $(e)$ follows since $\hat{\textbf{b}}$ is minimised over the same
objective function and independent of $u$.

∎

###  B.4 Dual fitting: Proofs of Lemmas 2.11 and Lemma 2.12

Recall from Section 2.3 the following assignment to functions
$\delta^{(c)}(.)$ and $\lambda^{(c)}(.)$

$\delta^{(c)}(r)=(\zeta/2)e^{-\zeta|r|}\text{ and
}\lambda^{(c)}(r)=\hat{\lambda}\cdot(\zeta/2)e^{-\zeta|r|}\text{ }\forall
r\in\mathbb{R}$

Recall that we considered the following Differential Equation (19) in
$\hat{\nu}(.)$.

$-\left[\min_{a\in\texttt{Set}(\textbf{v})}\mathfrak{h}(|r-a|)\right]\delta^{(c)}(r)+\lambda^{(c)}(r)+\frac{d\hat{\nu}(r)}{dr}+\epsilon|\hat{\nu}(r)|=0;\text{
with $\hat{\nu}(v_{med})=0$}$

We show that there always exists a solution $\hat{\nu}(.)$ to (19) such that
$\hat{\nu}(r)$ is non-negative for sufficiently large $u$ and non-positive for
sufficiently small $r$ 212121We may still need to prove continuity of the
bounds $U(.)$ and $L(.)$ which we discuss in Lemma 2.12 to satisfy the last
two constraints of DILP $\mathcal{E}$ in Section below. Observe that the
solution could depend on v. In the next subsection, we prove two technical
lemmas which is used in the proof of Lemmas and Claims in Section B.4.2.

####  B.4.1 Technical lemmas used

######  Lemma B.1.

Consider any vector $\textbf{q}\in\mathbb{R}^{k}$ and consider any
$v_{med}\in\mathbb{R}$ satisfying
$v_{med}\geq\text{Median}(\texttt{Set}(\textbf{q}))$. Then the following holds
true (recall the definition of $\hat{f}(\epsilon,k)$ from Equation (15))

$2\int_{v_{med}}^{\infty}\left[\min_{a\in\texttt{Set}(\textbf{q})}\mathfrak{h}(|t-a|)\right]\left(\epsilon/2\right)e^{-\epsilon(t-v_{med})}dt\geq\hat{f}(\epsilon,k).$
(51)

Notation: In this proof we use $q_{[j:k]}$ to denote a vector in
$\mathbb{R}^{k-j+1}$ constructed from all coordinates of q starting from
$j^{th}$ coordinate to the $k^{th}$ coordinate of q.

###### Proof.

Suppose the median of $\texttt{Set}(\textbf{q})$ is denoted by $q_{med}$ and
construct $\textbf{v}=\textbf{q}+(v_{med}-q_{med})\mathbbm{1}_{k}$
222222$\mathbbm{1}_{k}$ is a vector in $\mathbb{R}^{k}$ with all elements
unity. W.L.O.G, we assume that components in q are sorted in ascending order.
Consider the smallest index $j$ in $[k]$ s.t. $q_{j}>v_{med}$. Clearly,
$j>\frac{k+1}{2}$ if $k$ is odd and $j>\frac{k}{2}$ if $k$ is even.

We construct a vector $\tilde{\textbf{q}}\in\mathbb{R}^{k}$ by defining
$\tilde{q}_{[j:k]}=q_{[j:k]}$ and
$\tilde{q}_{[1:k-j+1]}=2v_{med}\mathbbm{1}-q_{[j:k]}$. For all other entries
of $\tilde{\textbf{q}}$, define it to be $v_{med}$. Observe that we choose a
points from $q_{[j:k]}$ and choose other points by symmetrizing around
$v_{med}$ and $j>\frac{k}{2}+1$ implies
$v_{med}\in\texttt{Set}(\tilde{\textbf{q}})$ as $2(k-j+1)<k$. Now consider the
following two exhaustive cases.

Case - 1: $j>\frac{k}{2}+1$.

$\displaystyle
2\int_{v_{med}}^{\infty}\left[\min_{a\in\texttt{Set}(\textbf{q})}\mathfrak{h}(|t-a|)\right]$
$\displaystyle\left(\epsilon/2\right)e^{-\epsilon(t-v_{med})}dt$ (52)
$\displaystyle\overset{(a)}{\geq}2\int_{v_{med}}^{\infty}\left[\min_{a\in\texttt{Set}(q_{[j:k]})\cup\\{v_{med}\\}}\mathfrak{h}(|t-a|)\right]\left(\epsilon/2\right)e^{-\epsilon(t-v_{med})}dt$
(53)
$\displaystyle\overset{(b)}{=}\int_{-\infty}^{\infty}\left[\min_{a\in\texttt{Set}(\tilde{\textbf{q}})}\mathfrak{h}(|t-a|)\right]\left(\epsilon/2\right)e^{-\epsilon|t-v_{med}|}dt$
(54)
$\displaystyle=\mathbb{E}_{y\sim\mathcal{L}_{\epsilon}(v_{med})}\left[\min_{a\in\texttt{Set}(\tilde{\textbf{q}})}\mathfrak{h}(|y-a|)\right]\overset{(c)}{\geq}\hat{f}(\epsilon,k).$
(55)

$(a)$ follows from the fact that $q_{j}$ is the smallest element in list
larger than $v_{med}$. $(b)$ follows from the fact that $\tilde{\textbf{q}}$
is constructed from a symmetric extension of $q_{[j:k]}$ about $v_{med}$ and
$v_{med}\in\texttt{Set}(\tilde{\textbf{q}})$. $(c)$ follows from the fact that
it is minimised over all collection of $k$ points as defined in Equation (15).

Case -2: $j=\frac{k}{2}+1$. And thus,

$\displaystyle
2\int_{v_{med}}^{\infty}\left[\min_{a\in\texttt{Set}(\textbf{q})}\mathfrak{h}(|t-a|)\right]$
$\displaystyle\left(\epsilon/2\right)e^{-\epsilon(t-v_{med})}dt$ (56)
$\displaystyle\overset{(a)}{\geq}2\int_{v_{med}}^{\infty}\left[\min_{a\in\texttt{Set}(q_{[j:k]})}\mathfrak{h}(|t-a|)\right]\left(\epsilon/2\right)e^{-\epsilon(t-v_{med})}dt$
(57)
$\displaystyle\overset{(b)}{=}\int_{-\infty}^{\infty}\left[\min_{a\in\texttt{Set}(\tilde{\textbf{q}})}\mathfrak{h}(|t-a|)\right]\left(\epsilon/2\right)e^{-\epsilon|t-v_{med}|}dt$
(58)
$\displaystyle=\mathbb{E}_{y\sim\mathcal{L}_{\epsilon}(v_{med})}\left[\min_{a\in\texttt{Set}(\tilde{\textbf{q}})}\mathfrak{h}(|y-a|)\right]\overset{(c)}{\geq}\hat{f}(\epsilon,k).$
(59)

Note that $(a)$ follows from the fact that $q_{j}+q_{j-1}>2v_{med}$ as
$\text{Median}(\texttt{Set}(\textbf{q}))>v_{med}$ and
$\text{Median}(\texttt{Set}(\textbf{q}))=\frac{q_{j}+q_{j-1}}{2}$. $(b)$
follows from the fact that $\tilde{\textbf{q}}$ is constructed from a
symmetric extension of $q_{[j:k]}$ about $v_{med}$. $(c)$ follows from the
fact that it is minimised over all collection of $k$ points as defined in
Equation (15).

∎

We now state the next lemma which say that we says that there exists a
solution to Equation (19). This lemma states that zeros of the solution to
Equation (19) with negative derivative is upper bounded and states that zeros
with positive derivative is lower bounded.

######  Lemma B.2.

Choose any
$0<\hat{\lambda}\leq\frac{\epsilon-\zeta}{\epsilon+\zeta}\hat{f}(\epsilon+\zeta,k)$
for some $0<\zeta<\epsilon$. Then for every $\textbf{v}\in\mathbbm{R}^{k}$, a
unique $\mathcal{C}^{1}$ solution $\nu^{(c)}(.)$ exists to Differential
Equation (19) satisfying the following two constraints for some constant $C$
independent of $\textbf{v}\in\mathbb{R}^{k}$. Note that $v_{\lfloor i\rfloor}$
denotes the $i^{th}$ largest component of v for every $i\in[k]$.

  * •

$\Big{\\{}\mathfrak{r}\in\mathbb{R}:\nu^{(c)}(\mathfrak{r})=0\text{ and
}\frac{d\nu^{(c)}(\mathfrak{r})}{d\mathfrak{r}}<0\Big{\\}}\text{ is upper
bounded}$ by $C+v_{\lfloor k\rfloor}$.

  * •

$\Big{\\{}\mathfrak{r}\in\mathbb{R}:\nu^{(c)}(\mathfrak{r})=0\text{ and
}\frac{d\nu^{(c)}(\mathfrak{r})}{d\mathfrak{r}}>0\Big{\\}}\text{ is lower
bounded}$ by $-C+v_{\lfloor 1\rfloor}$.

###### Proof.

Recall Differential Equation from Equation (19), restate it below as follows.

$-\left[\min_{a\in\texttt{Set}(\textbf{v})}\mathfrak{h}(|r-a|)\right]\delta^{(c)}(r)+\lambda^{(c)}(r)+\frac{d\hat{\nu}(r)}{dr}+\epsilon|\hat{\nu}(r)|=0$

Also recall from Equation (18) that we defined

$\delta^{(c)}(r)=(\zeta/2)e^{-\zeta|r|}\text{ and
}\lambda^{(c)}(r)=\hat{\lambda}\cdot(\zeta/2)e^{-\zeta|r|}\text{ }\forall
r\in\mathbb{R}$

From global uniqueness and existence condition of Cauchy-Lipschitz theorem in
[44, Theorem 2], we can show that there is a unique solution
$\hat{\nu}^{(c)}(.)$ of Equation (19) satisfying this initial value condition
as Lipschitz conditions as described in [44, Theorem 2] is satisfied in
Equation (19). Also, observe that this function is continuously
differentiable.

We now prove the first point in the lemma..

We first prove that $\lim_{u\to\infty}\mathfrak{h}(u)>\hat{\lambda}$. First
observe from Claim B.1) (substituting $\epsilon$ by $\epsilon+\zeta$) that

$\displaystyle\int_{v_{med}}^{\infty}\left[\min_{a\in\texttt{Set}(\textbf{q})}\mathfrak{h}(|t-a|)\right]\left(\epsilon+\zeta\right)e^{-(\epsilon+\zeta)(t-v_{med})}dt\geq\hat{f}(\epsilon+\zeta,k).$
$\displaystyle\implies$
$\displaystyle\int_{v_{med}}^{\infty}\left[\min_{a\in\texttt{Set}(\textbf{q})}\mathfrak{h}(|t-a|)-\hat{f}(\epsilon+\zeta,k)\right](\epsilon+\zeta)e^{-(\epsilon+\zeta)(t-v_{med})}dt\geq
0$

This, implies that for some $t>v_{med}$ s.t.
$\left[\min_{a\in\texttt{Set}(\textbf{q})}\mathfrak{h}(|t-a|)-\hat{f}(\epsilon+\zeta,k)\right]>0$
and since, we know $\mathfrak{h}(.)$ is monotonic, we can argue that
$\lim_{r\to\infty}\mathfrak{h}(r)>\hat{f}(\epsilon+\zeta,k)>\hat{\lambda}$.232323The
limits are defined over extended reals $\mathbb{R}\cup\\{-\infty,+\infty\\}$
Let us denote the the smallest $r$ s.t. $\mathfrak{h}(r)>\hat{\lambda}$ by
$\mathfrak{u}^{s}$. Now observe for $r>(v_{\lfloor
k\rfloor}+\mathfrak{r}^{s})$,
$\left[\min_{a\in\texttt{Set}(\textbf{v})}\mathfrak{h}(|r-a|)\right]\delta^{(c)}(r)-\lambda^{(c)}(r)$
is non-negative.

Suppose there exists $r_{0}\in[v_{\lfloor k\rfloor}+\mathfrak{r}^{s},\infty)$
satisfying, $\nu^{(c)}(r_{0})=0$ and $\nu^{(c)^{\prime}}(r_{0})<0$ thus,
$\nu^{(c)^{\prime}}(r_{0})+\nu^{(c)}(r_{0})<0$ , thus contradicting the fact
that
$\left[\min_{a\in\texttt{Set}(\textbf{v})}\mathfrak{h}(|r-a|)\right]\delta^{(c)}(r)-\lambda^{(c)}(r)>0$
is non-negative in $r\in[v_{\lfloor k\rfloor}+\mathfrak{u}^{s},\infty)$. Thus,
we show that there does not exist $r_{0}>v_{\lfloor
k\rfloor}+\mathfrak{r}^{s}$ satisfying $\nu^{(c)}(u_{0})=0$ and
$\nu^{(c)^{\prime}}(r_{0})<0$ thus proving the desired statement, since
$\mathfrak{r}^{s}$ is a constant independent of v.

The second statement follows from a very similar argument.

∎

With these lemmas, we now prove the following lemma 2.11 which shows that
$\nu^{(c)}(.)$ is positive for sufficiently large $u$ and negative for
sufficiently small $u$.

####  B.4.2 Obtaining a feasible solution to DILP $\mathcal{E}$: Proof of
Lemma 2.11

######  Lemma (detailed proof of Lemma 2.11).

Choose $\zeta<\epsilon$ and
$0<\hat{\lambda}\leq\frac{\epsilon-\zeta}{\epsilon+\zeta}\hat{f}(\epsilon+\zeta,k)$,
then equation $\eqref{eqn:diff_eqn_nu}$ has a unique $\mathcal{C}^{1}$
solution $\nu^{(c)}(.)$ and there exists $U,L\in\mathbb{R}$ satisfying
$\nu^{(c)}(r)\geq 0\text{ }\forall r\geq U$ and $\nu^{(c)}(r)\leq 0\text{
}\forall r\leq L$.

###### Proof.

Recall from lemma B.2, that there exists a unique $\mathcal{C}^{1}$ solution
(denoted by $\nu^{(c)}(.)$) to (19). Uniqueness and existence of the solution
can be shown from global uniqueness and existence condition of Cauchy-
Lipschitz theorem in [44, Theorem 2] as Lipschitz conditions as described in
[44, Theorem 2] is satisfied in Equation (19).

We first prove the following Equation (60) in fnum@pfpartsiPart - 1. which
states that there cannot be an unbounded interval in $[v_{med},\infty)$ where
$\nu^{(c)}(.)$ is non-positive. Next, we use this statement to prove the main
lemma in fnum@pfpartsiPart - 2..

${}\Big{\\{}\mathfrak{r}\in[v_{med},\infty)\;\Big{|}\;\nu^{(c)}(r)\leq 0\text{
}\forall r\geq\mathfrak{r}\Big{\\}}=\phi$ (60)

fnum@pfpartsiPart - 1.

We now assume the contradictory statement that there exists
$r^{0}\in\mathbbm{R}$ s.t. ${\nu}^{(c)}(r)\leq 0$ for all $r>r^{0}$ and define
$r^{\max}=\inf\Big{\\{}\mathfrak{r}\in[v_{med},\infty)\;\Big{|}\;\nu^{(c)}(r)\leq
0\text{ }\forall r\geq\mathfrak{r}\Big{\\}}$. Since, $\nu^{(c)}(.)$ is
continuous and $\nu^{(c)}(v_{med})=0$, we have $\nu^{(c)}(r^{max})=0$. Thus,
the differential equation (19) can be rewritten in $[r^{\max},\infty)$ as
follows (replacing $|\hat{\nu}(u)|$ by $-\hat{\nu}(u)$)

$-\left[\min_{a\in\texttt{Set}(\textbf{v})}\mathfrak{h}(|r-a|)\right]\delta^{(c)}(r)+\lambda^{(c)}(r)+\frac{d\hat{\nu}(r)}{dr}-\epsilon\hat{\nu}(r)=0$

Now, multiplying both sides by $e^{-\epsilon r}$ and applying the initial
value condition of $\nu^{(c)}(v_{med})=0$, we have the solution to the
Differential Equation in $[r^{\max},\infty)$ is given by ν^(c)(r) = (∫_r^max^r
[-λ^(c)(t) +[min_a ∈Set(v) h(—t-a—) ]δ^(c)(t) ] e^-ϵt dt)e^ϵr

However, since $\hat{\nu}^{(c)}(r)$ is non-positive in $[r^{\max},\infty)$, we
have242424Observe that a strict inequality follows since a contrary assumption
would imply that $\nu^{(c)}(r)$ is identically zero in $[r^{med},\infty)$.
This would imply that
$-\lambda^{(c)}(t)+\left[\min\limits_{a\in\texttt{Set}(\textbf{v})}\mathfrak{h}(|t-a|)\right]\delta^{(c)}(t)$
is zero in $[r_{max},\infty)$ implying, $\mathfrak{h}(|t-a|)=\hat{\lambda}$
which is a contradiction since,
$\lim_{r\to\infty}\mathfrak{h}(r)>\hat{\lambda}$ as shown in proof of Claim
B.2

$\displaystyle\int_{r^{\max}}^{\infty}\left[-\lambda^{(c)}(t)+\left[\min_{a\in\texttt{Set}(\textbf{v})}\mathfrak{h}(|t-a|)\right]\delta^{(c)}(t)\right]e^{-\epsilon
t}dt<0$ (61) $\displaystyle\implies$
$\displaystyle\int_{r^{\max}}^{\infty}\left[\min_{a\in\texttt{Set}(\textbf{v})}\mathfrak{h}(|t-a|)\right]\left(\frac{{\zeta}}{2}\right)e^{-{\zeta}|t|}(\epsilon/2)e^{-\epsilon
t}dt<\int_{r^{\max}}^{\infty}\lambda^{(c)}(t)(\epsilon/2)e^{-\epsilon t}dt$
(62)

We now consider two exhaustive cases and treat them separately $r^{\max}>0$
and $r^{\max}<0$. We denote $q_{i}=v_{i}+v_{med}-r^{\max}\forall i\in[k]$ and
$\textbf{q}=[q_{1},q_{2},\ldots,q_{k}]$

Case a: Let us first consider the case where $r^{\max}>0$. We thus get from
Equation (62)

$\displaystyle\overset{(a)}{\implies}$ $\displaystyle
e^{-(\epsilon+{\zeta})(r^{\max}-v_{med})}.\int_{v_{med}}^{\infty}\left[\min_{\begin{subarray}{c}a\in\texttt{Set}(\textbf{q})\end{subarray}}\mathfrak{h}(|t-a|)\right]\left(\frac{{\zeta}}{2}\right)e^{-{\zeta}t}(\epsilon/2)e^{-\epsilon
t}dt<(1/4)\hat{\lambda}e^{-(\epsilon+{\zeta})r^{\max}}\left(\frac{\epsilon{\zeta}}{\epsilon+{\zeta}}\right)$
(63) $\displaystyle\implies$ $\displaystyle
2\int_{v_{med}}^{\infty}\left[\min_{\begin{subarray}{c}a\in\texttt{Set}(\textbf{q})\end{subarray}}\mathfrak{h}(|t-a|)\right]((\epsilon+{\zeta})/2)e^{-(\epsilon+{\zeta})t}dt<\hat{\lambda}e^{-(\epsilon+{\zeta})v_{med}}$
(64) $\displaystyle{\implies}$ $\displaystyle
2\int_{v_{med}}^{\infty}\left[\min_{\begin{subarray}{c}a\in\texttt{Set}(\textbf{q})\end{subarray}}\mathfrak{h}(|t-a|)\right]((\epsilon+{\zeta})/2)e^{-(\epsilon+{\zeta})(t-v_{med})}dt<\hat{\lambda}$
(65) $\displaystyle\overset{(b)}{\implies}$
$\displaystyle\hat{f}(\epsilon+{\zeta},k)<\hat{\lambda}$ (66)

which is a contradiction.

$(a)$ follows from the fact that $r^{\max}>0$, thus $|t|=t$ and applying
change of variables. The argument for $(b)$ follows from Lemma B.1.

Case b: Consider the case when $r^{\max}<0$. We can thus write Equation (62)

$\displaystyle{\implies}$
$\displaystyle\int_{r^{\max}}^{0}\left[\min_{a\in\texttt{Set}(\textbf{v})}\mathfrak{h}(|t-a|)\right]\left(\frac{\epsilon{\zeta}}{4}\right)e^{{\zeta}t}e^{-\epsilon
t}dt+\int_{0}^{\infty}\left[\min_{a\in\texttt{Set}(\textbf{v})}\mathfrak{h}(|t-a|)\right]\left(\frac{{\zeta}\epsilon}{4}\right)e^{-{\zeta}t}e^{-\epsilon
t}dt$ (67)
$\displaystyle<\int_{r^{\max}}^{0}\hat{\lambda}\left(\epsilon{\zeta}/4\right)e^{{\zeta}t}e^{-{\epsilon}t}dt+\int_{0}^{\infty}\hat{\lambda}\left(\epsilon{\zeta}/4\right)e^{-{\zeta}t}e^{-{\epsilon}t}dt$
(68) $\displaystyle\overset{(a)}{\implies}$ $\displaystyle
e^{-(\epsilon-{\zeta})r^{\max}}\int_{v_{med}}^{v_{med}-r^{\max}}\left[\min_{a\in\texttt{Set}(\textbf{q})}\mathfrak{h}(|t-a|)\right]e^{-(\epsilon-{\zeta})(t-v_{med})}dt$
(69) $\displaystyle+$ $\displaystyle
e^{-(\epsilon+{\zeta})r^{\max}}\int_{v_{med}-r^{\max}}^{0}\left[\min_{a\in\texttt{Set}(\textbf{q})}\mathfrak{h}(|t-a|)\right]e^{-(\epsilon+{\zeta})(t-v_{med})}dt<\hat{\lambda}\left[\frac{1}{(\epsilon+{\zeta})}+\frac{e^{-(\epsilon-{\zeta})r^{\max}}-1}{(\epsilon-{\zeta})}\right]$
(70) $\displaystyle\overset{(b)}{\implies}$ $\displaystyle
e^{-(\epsilon-{\zeta})r^{\max}}\int_{v_{med}}^{\infty}\left[\min_{a\in\texttt{Set}(\textbf{q})}\mathfrak{h}(|t-a|)\right]e^{-(\epsilon+{\zeta})(t-v_{med})}dt<\hat{\lambda}\left[\frac{1}{(\epsilon+{\zeta})}+\frac{e^{-(\epsilon-{\zeta})r^{\max}}-1}{(\epsilon-{\zeta})}\right]$
(71) $\displaystyle{\implies}$ $\displaystyle
2e^{-(\epsilon-{\zeta})r^{\max}}\int_{v_{med}}^{\infty}\left[\min_{a\in\texttt{Set}(\textbf{q})}\mathfrak{h}(|t-a|)\right]\left(\frac{\epsilon+{\zeta}}{2}\right)e^{-(\epsilon+{\zeta})(t-v_{med})}dt<\hat{\lambda}\left[1+\frac{(\epsilon+{\zeta})}{(\epsilon-{\zeta})}(e^{-(\epsilon-{\zeta})r^{\max}}-1)\right]$
(72) $\displaystyle{\implies}$
$\displaystyle\frac{e^{-(\epsilon-{\zeta})r^{\max}}2}{\left[1+\frac{(\epsilon+{\zeta})}{(\epsilon-{\zeta})}(e^{-(\epsilon-{\zeta})r^{\max}}-1)\right]}\int_{v_{med}}^{\infty}\left[\min_{a\in\texttt{Set}(\textbf{q})}\mathfrak{h}(|t-a|)\right]\left(\frac{\epsilon+{\zeta}}{2}\right)e^{-(\epsilon+{\zeta})(t-v_{med})}dt<\hat{\lambda}$
(73) $\displaystyle\overset{(c)}{\implies}$
$\displaystyle\left(\frac{\epsilon-{\zeta}}{\epsilon+{\zeta}}\right)2\int_{v_{med}}^{\infty}\left[\min_{a\in\texttt{Set}(\textbf{q})}\mathfrak{h}(|t-a|)\right]\left(\frac{\epsilon+{\zeta}}{2}\right)e^{-(\epsilon+{\zeta})(t-v_{med})}dt<\hat{\lambda}$
(74)
$\displaystyle\overset{(d)}{\implies}\left(\frac{\epsilon-{\zeta}}{\epsilon+{\zeta}}\right)\hat{f}(\epsilon+{\zeta},k)<\hat{\lambda}$
(75)

which is a contradiction.

$(b)$ follows from the fact that $\epsilon-{\zeta}<\epsilon+{\zeta}$ and thus,
$-(\epsilon-{\zeta})r^{\max}<-(\epsilon+{\zeta})r^{\max}$ since $r^{\max}<0$.
Also, $-(\epsilon+{\zeta})(t-v_{med})<-(\epsilon-{\zeta})(t-v_{med})$ for
$t>v_{med}$. $(c)$ follows from by infimising
$\frac{e^{-(\epsilon-{\zeta})r^{\max}}}{\left[1+\frac{(\epsilon+{\zeta})}{(\epsilon-{\zeta})}(e^{-(\epsilon-{\zeta})r^{\max}}-1)\right]}$
over all $r^{\max}<0$ (happens as $r^{\max}\to-\infty$) and $(d)$ follows from
Lemma B.1.

We thus prove Equation (60) by showing contradiction under both cases.

fnum@pfpartsiPart - 2.

Observe that Equation (76) follows from Claim B.2 and Equation (60) (restated
below) which has been shown above.

${}\Big{\\{}\mathfrak{r}\in\mathbb{R}:\nu^{(c)}(\mathfrak{r})=0\text{ and
}\frac{d\nu^{(c)}(\mathfrak{r})}{d\mathfrak{r}}<0\Big{\\}}\text{ is upper
bounded by $C+v_{\lfloor k\rfloor}$}.$ (76)

.

$\Big{\\{}\mathfrak{r}\in\mathbbm{R}\;\Big{|}\;\nu^{(c)}(r)\leq 0\text{
}\forall r>\mathfrak{r}\Big{\\}}=\phi$

Let us denote the set of all the closed intervals in $[v_{med},\infty)$, where
$\nu^{(c)}(.)$ is non-negative by $\mathcal{I}^{pos}$252525We can construct
such intervals as $\nu^{(c)}$ is continuously differentiable and there does
not exist an interval where $\nu^{(c)}$ is identically zero.. Now observe,
that the Equation (76) implies that upper bound of every interval in
$\mathcal{I}^{pos}$ must be upper bounded by $C+v_{\lfloor k\rfloor}$. This
implies the existence of an unbounded interval where $\nu^{(c)}(.)$ is non-
negative or an unbounded interval where $\nu^{(c)}(.)$ is non-positive.
However Equation (60) implies that there can not exist an unbounded interval
where $\nu^{(c)}(.)$ is non-positive and thus, we show that there exists an
unbounded interval where $\nu^{(c)}(.)$ is non-negative. This proves the
statement in Claim 2.11 that there exists $U\in\mathbbm{R}$ s.t.
$\nu^{(c)}(u)\geq 0\forall u\geq U$.

Using a very similar approach, we can prove that $\nu^{(c)}(u)\leq 0$ for
$u\leq L$ for some $L\in\mathbbm{R}$.

∎

We now prove the main lemma 2.12 which shows that the objective value of
$\hat{f}(\epsilon,k)$ is achievable by some solution in the DILP
$\mathcal{E}$. Observe that this feasible solution is constructed using
$\delta^{(c)}(.),\lambda^{(c)}(.)$ and $\nu^{(c)}(.)$ that we defined to
satisfy Equation (19) and ensured positivity and negativity of $\nu^{(c)}(.)$
for “sufficiently” large and small $u$ respectively for every
$\textbf{v}\in\mathbb{R}^{k}$. However, we also require a technical claim 1 to
prove the existence of continuous bounds $U(.)$ and $L(.)$. For sake of
brevity, we state and prove it in Appendix B.7.

######  Lemma (detailed proof of Lemma 2.12).

$\text{opt}(\mathcal{E})\geq\hat{f}(\epsilon,k)$

###### Proof.

Recall the functions $\lambda^{(c)}(.),\delta^{(c)}(.)$ defined in (18). Also
for every $\textbf{v}\in\mathbb{R}^{k}$, we obtain a function
$\nu^{(c)}(.,\textbf{v})$ [solution of Equation (19)] with bounds
$U(\textbf{v})$ and $L(\textbf{v})$ satisfying $\nu^{(c)}(r,\textbf{v})\geq
0\forall u\geq U(\textbf{v})$ and $\nu^{(c)}(r,\textbf{v})\leq 0\forall u\leq
L(\textbf{v})$. Now, we argue that this solution is feasible attaining an
objective value of $\hat{\lambda}$ which we argue below.

  * •

Observe that $\int_{u\in\mathbb{R}}\lambda^{(c)}(u)=\hat{\lambda}$ and
$\int_{u\in\mathbb{R}}\delta^{(c)}(u)=1$

  * •

The second constraint is satisfied as $\nu^{(c)}(\textbf{v},.)$ is a solution
of Equation (19).

  * •

Bounds $U(\textbf{v})$ and $L(\textbf{v})$ exist from statement in Lemma 2.11.
The proof of continuity of $U(.)$ and $L(.)$ is slightly technical and we
formally prove this in Claim 1. Observe that all the assumptions in Claim 1 is
satisfied due to results from Lemma 2.11 and Lemma B.2.

Now observe that the objective value of this feasible solution in
$\hat{\lambda}$ and the constructed solution is feasible for any
$\hat{\lambda}\leq\frac{\epsilon-\zeta}{\epsilon+\zeta}\hat{f}(\epsilon+\zeta,k)$
and $\zeta>0$. Now, since $\hat{f}(\epsilon,k)$ is continuous in $\epsilon$,
choosing $\zeta$ to be arbitrarily small enables us to get obtain the
objective value of the solution arbitrarily close to $\hat{f}(\epsilon,k)$ and
thus, $\text{opt}(\mathcal{E})\geq\hat{f}(\epsilon,k)$.

∎

###  B.5 Optimal Result Selection given Laplace noise when $\mathfrak{h}(.)$
is an identity function

######  Theorem B.3 (corresponds to Theorem 1.4).

Recall the definition of $\hat{f}(\epsilon,k)$ from Equation (15) and suppose
$A^{*}=\\{x_{1},x_{2},\dots,x_{k}\\}$ where $x_{1}\leq x_{2}\leq\dots\leq
x_{k}$ minimises the same.262626Here, we denote $A^{*}$ by a set instead of a
vector. Then, we have

  1. 1.

When $k$ is odd, $x_{(k+1)/2}=0$. For $i\in[(k-1)/2]$,
$x_{i}=-2\log((k+3)/2-i)/\epsilon$. For $i\in[k]\setminus[(k+1)/2]$,
$x_{i}=-x_{k+1-i}$. That is, if $t:=(k-1)/2$, then

$\displaystyle\\{x_{1},\dots,x_{k}\\}=\left\\{0,\pm\frac{2\log\left(\frac{t+1}{t}\right)}{\epsilon},\pm\frac{2\log\left(\frac{t+1}{t-1}\right)}{\epsilon},\dots,\pm\frac{2\log\left(\frac{t+1}{2}\right)}{\epsilon},\pm\frac{2\log\left(t+1\right)}{\epsilon}\right\\}.$

  2. 2.

When $k$ is even, $x_{k/2}=-\log(1+2/k)/\epsilon$. For $i\in[k/2-1]$,
$x_{i}=x_{i+1}-(2\log(1+1/i))/\epsilon$. For $i\in[k]\setminus[k/2]$,
$x_{i}=-x_{k+1-i}$. That is, if $t:=k/2$, then

$\displaystyle\\{x_{1},\dots,x_{k}\\}=\left\\{\pm\frac{\log\left(\frac{t+1}{t}\right)}{\epsilon},\pm\frac{\log\left(\frac{t(t+1)}{(t-1)^{2}}\right)}{\epsilon},\pm\frac{\log\left(\frac{t(t+1)}{(t-2)^{2}}\right)}{\epsilon},\dots,\pm\frac{\log\left(\frac{t(t+1)}{2^{2}}\right)}{\epsilon},\pm\frac{\log\left(t(t+1)\right)}{\epsilon}\right\\}.$

We prove this theorem using the following lemmas.

######  Lemma B.4.

If
$\min\limits_{A\in\mathcal{A}}\mathop{\operatorname{\mathbb{E}}}\limits_{x\sim\mathcal{L}_{\epsilon}(0)}\left[\min\limits_{a\in
A}\left|a-x\right|\right]=\mathop{\operatorname{\mathbb{E}}}\limits_{x\sim\mathcal{L}_{\epsilon}(0)}\left[\min\limits_{a\in
A^{*}}\left|a-x\right|\right]$ and $A^{*}=\\{x_{1},x_{2},\dots,x_{k}\\}$ where
$x_{1}\leq x_{2}\leq\dots\leq x_{k}$, we define $y_{i}:=(x_{i}+x_{i+1})/2$ for
$i\in[k-1]$, $y_{0}:=-\infty$, and $y_{k}:=+\infty$. Then,

$\displaystyle\operatorname{\mathbb{P}}_{z\sim\mathcal{L}_{\epsilon}(0)}\left(y_{i-1}<z<x_{i}\right)=\operatorname{\mathbb{P}}_{z\sim\mathcal{L}_{\epsilon}(0)}\left(x_{i}<z<y_{i}\right),\quad\forall~{}~{}i\in[k].$
(77)

###### Proof.

Note that for any $i\in[k]$, for any $z\in(y_{i-1},y_{i})$, $\min_{a\in
A^{*}}\left|a-x\right|=\left|x_{i}-x\right|$. Then we have

$\displaystyle\operatorname{\mathbb{E}}_{x\sim\mathcal{L}_{\epsilon}(0)}\left[\min_{a\in
A^{*}}\left|a-x\right|\right]=\sum_{i=1}^{k}\operatorname{\mathbb{P}}_{z\sim\mathcal{L}_{\epsilon}(0)}\left(y_{i-1}<z<y_{i}\right)\operatorname{\mathbb{E}}_{z\sim\mathcal{L}_{\epsilon}(0)}\left[\left|x_{i}-z\right||y_{i-1}<z<y_{i}\right].$

If
$x_{i}\neq\operatorname{\mathbb{E}}_{z\sim\mathcal{L}_{\epsilon}(0)}\left[z|y_{i-1}<z<y_{i}\right]$
for a certain $i\in[k]$, we can change the value of $x_{i}$ so that Equation
77 holds, in which $x_{i}$ is somehow a median of $\mathcal{L}_{\epsilon}(0)$
inside the interval $(y_{i-1},y_{i})$, and then
$\operatorname{\mathbb{E}}_{z\sim\mathcal{L}_{\epsilon}(0)}\left[\left|x_{i}-z\right||y_{i-1}<z<y_{i}\right]$
strictly decreases, which implies
$\operatorname{\mathbb{E}}_{x\sim\mathcal{L}_{\epsilon}(0)}\left[\min_{a\in
A^{*}}\left|a-x\right|\right]$ decreases. However, $A^{*}$ is the optimal
point, so it is a contradiction. As a result, for $i\in[k]$, we have Equations
77.

∎

######  Lemma B.5.

Using the same definition of $x_{i}$ and $y_{i}$ as Lemma B.4, we have

  1. 1.

for $i\in[k-1]$, if $y_{i}\leq 0$, we have
$x_{i}=y_{i}-\frac{\log(1+1/i)}{\epsilon}$,

  2. 2.

for $i\in[k]\setminus\\{1\\}$, if $y_{i-1}\geq 0$, we have
$x_{i}=y_{i-1}+\frac{\log(1+1/(k-i+1))}{\epsilon}$.

###### Proof.

We first show $x_{i}=y_{i}-\frac{\log(1+1/i)}{\epsilon}$ when $y_{i}\leq 0$.
We prove it by induction. When $i=1$, by Equation 77, we have
$\operatorname{\mathbb{P}}_{z\sim\mathcal{L}_{\epsilon}(0)}\left(z<x_{1}\right)=\operatorname{\mathbb{P}}_{z\sim\mathcal{L}_{\epsilon}(0)}\left(x_{1}<z<y_{1}\right)$.
If $y_{1}\leq 0$, we have

$\displaystyle\int_{-\infty}^{x_{1}}e^{\epsilon
z}dz=\int_{x_{1}}^{y_{1}}e^{\epsilon z}dz,$

which is equivalent to

$\displaystyle e^{\epsilon x_{1}}=e^{\epsilon y_{1}}-e^{\epsilon x_{1}},$

so $y_{1}=x_{1}+\log(2)/\epsilon$.

If $y_{i}\leq 0$, assuming $x_{i-1}=y_{i-1}-\frac{\log(1+1/(i-1))}{\epsilon}$,
then $x_{i}=y_{i-1}+\frac{\log(1+1/(i-1))}{\epsilon}$. By Equation 77, we have

$\displaystyle\int_{y_{i-1}}^{x_{i}}e^{\epsilon
z}dz=\int_{x_{i}}^{y_{i}}e^{\epsilon z}dz,$

which is equivalent to

$\displaystyle\exp{(\epsilon x_{i})}-\exp{\left(\epsilon
x_{i}-\frac{\log(1+1/(i-1))}{\epsilon}\right)}=\exp{(\epsilon
y_{i})}-\exp{(\epsilon x_{i})},$

so $y_{i}=x_{i}+\frac{\log(1+1/i)}{\epsilon}$.

As a result, for $i\in[k-1]$, if $y_{i}\leq 0$, we have
$x_{i}=y_{i}-\frac{\log(1+1/i)}{\epsilon}$.

By symmetry, using similar arguments, we know that for
$i\in[k]\setminus\\{1\\}$, if $y_{i-1}\geq 0$, then
$x_{i}=y_{i-1}+\frac{\log(1+1/(k-i+1))}{\epsilon}$.

∎

######  Lemma B.6.

Using the same definition of $x_{i}$ and $y_{i}$ as Lemma B.4, if $y_{i}\leq
0\leq y_{i+1}$ where $i\in[k-2]$, then $|i-(k-i)|\leq 1$.

###### Proof.

By Lemma B.5, we have

$\displaystyle\begin{cases}x_{i}=y_{i}-\frac{\log(1+1/i)}{\epsilon},\\\
x_{i+2}=y_{i+1}+\frac{\log(1+1/(k-i-1))}{\epsilon},\end{cases}$

which implies

$\displaystyle
y_{i}+\frac{\log(1+1/i)}{\epsilon}=x_{i+1}=y_{i+1}-\frac{\log(1+1/(k-i-1))}{\epsilon}.$

Since $y_{i}\leq 0\leq y_{i+1}$, we have
$x_{i+1}\in\left[\beta_{1},\beta_{2}\right]$, where

$\displaystyle\beta_{1}:=-\frac{\log(1+1/(k-i-1))}{\epsilon},\quad\beta_{2}:=\frac{\log(1+1/i)}{\epsilon}.$

Define

$\displaystyle
g_{1}(x):=\int_{x-\frac{\log(1+1/i)}{\epsilon}}^{x}e^{-\epsilon|z|}dz,~{}~{}\text{and}~{}~{}g_{2}(x):=\int_{x}^{x+\frac{\log(1+1/(k-i-1))}{\epsilon}}e^{-\epsilon|z|}dz,$

and define $h(x):=g_{1}(x)/g_{2}(x)$. By Lemma B.4, we have
$g_{1}(x_{i+1})=g_{2}(x_{i+1})$, which implies $h(x_{i+1})=1$.

For $\beta_{1}\leq y_{1}<y_{2}\leq 0$, we have
$g_{1}(y_{1})=e^{y_{1}-y_{2}}g_{1}(y_{2})$, and
$g_{2}(y_{1})>e^{y_{1}-y_{2}}g_{2}(y_{2})$, so $h(y_{1})<h(y_{2})$. Similarly,
for $0\leq y_{1}<y_{2}\leq\beta_{2}$, we have
$g_{1}(y_{1})<e^{y_{2}-y_{1}}g_{1}(y_{2})$, and
$g_{2}(y_{1})=e^{y_{2}-y_{1}}g_{2}(y_{2})$, so $h(y_{1})<h(y_{2})$. As a
result, $h(x)$ is strictly increasing on $[\beta_{1},\beta_{2}]$.

If $i>k-i+1$, $h(\beta_{2})<1$. If $i+1<k-i$, $h(\beta_{1})>1$. In both cases,
for any $x\in[\beta_{1},\beta_{2}]$, $h(x)\neq 1$. It contradicts to
$h(x_{i+1})=1$ and $x_{i+1}\in[\beta_{1},\beta_{2}]$. As a result, we have
$|i-(k-i)|\leq 1$.

∎

Combining Lemmas B.5 and B.6, we have the following corollary B.3.

And thus, Theorem A.1 is proved.

###  B.6 Proof of weak duality as stated in Theorem 2.8

We now restate the weak duality theorem from Theorem 2.8.

######  Theorem (proof of Theorem 2.8).

$\text{opt}(\mathcal{O})\geq\text{opt}(\mathcal{E})$.

To prove this lemma, we now redefine the optimization problems $\mathcal{O}$
and $\mathcal{E}$ in (13) and (14).

$\text{ $\mathcal{O}$ =}\left\\{\begin{aligned}
\inf_{g(.,.):\mathcal{I}^{B}(\mathbb{R}\times\mathbb{R}^{k}\rightarrow\mathbb{R}^{+}),\kappa\in\mathbb{R}}\quad&\kappa\\\
\textrm{s.t.}\quad&\kappa-\int\limits_{\textbf{x}\in\mathbb{R}^{k}}\left[\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right]g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)\geq
0\text{ }\forall u\in\mathbb{R}\\\
&\int\limits_{\textbf{x}\in\mathbb{R}^{k}}g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)=1\text{
}\forall u\in\mathbb{R}\\\ &\epsilon
g(u,\textbf{x})+\underline{g}_{u}(u,\textbf{x})\geq 0;\text{ }\forall
u\in\mathbb{R};\textbf{x}\in\mathbb{R}^{k}\\\ &\epsilon
g(u,\textbf{x})-\overline{g}_{u}(u,\textbf{x})\geq 0;\text{ }\forall
u\in\mathbb{R};\textbf{x}\in\mathbb{R}^{k}\end{aligned}\right.$ (78)

$\text{ {$\mathcal{E}$ =}}\left\\{\begin{aligned}
\sup_{\begin{subarray}{c}{\nu}(.,.):\mathcal{C}^{1}(\mathbb{R}\times\mathbb{R}^{k}\rightarrow\mathbb{R})\\\
\lambda(.):\mathcal{C}^{0}(\mathbb{R}\rightarrow\mathbb{R}^{+})\\\
\delta(.):\mathcal{C}^{0}(\mathbb{R}\rightarrow\mathbb{R}^{+})\end{subarray}}&\int_{u\in\mathbb{R}}{\lambda}(u)du\\\
\textrm{ s.t. }\quad&\int_{u\in\mathbb{R}}{\delta}(u)du\leq 1\\\
&-\left[\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right]{\delta}(u)+{\lambda}(u)+\epsilon|{\nu}(u,\textbf{x})|+{\nu}_{u}(u,\textbf{x})\leq
0\text{ }\forall u\in\mathbb{R},\forall\textbf{x}\in\mathbb{R}^{k}\\\ &\exists
U:\mathcal{C}^{0}(\mathbb{R}^{k}\rightarrow\mathbb{R})\textrm{ s.t.
}\nu(u,\textbf{x})\geq 0\text{ }\forall u\geq U(\textbf{x})\text{
}\forall\textbf{x}\in(\mathbb{R})^{k}\\\ &\exists
L:\mathcal{C}^{0}(\mathbb{R}^{k}\rightarrow\mathbb{R})\textrm{ s.t.
}\nu(u,\textbf{x})\leq 0\text{ }\forall u\leq L(\textbf{x})\text{
}\forall\textbf{x}\in(\mathbb{R})^{k}\\\ \end{aligned}\right.$ (79)

We now define a DILP $\mathcal{E}^{int}$ which effectively splits the function
$\nu(.,.)$ into a negative and a positive part and prove a lemma B.7 bounding
the optimal value of $\mathcal{E}$ by $\mathcal{E}^{int}$.

$\text{ {$\mathcal{E}^{int}$ =}}\left\\{\begin{aligned}
\sup_{\begin{subarray}{c}\delta(.):\mathcal{C}^{0}(\mathbb{R}\rightarrow\mathbb{R}^{+}),{\nu^{(1)}}(.,.):\mathcal{C}^{1}(\mathbb{R}\times\mathbb{R}^{k}\rightarrow\mathbb{R}^{+})\\\
{\nu^{(2)}}(.,.):\mathcal{C}^{1}(\mathbb{R}\times\mathbb{R}^{k}\rightarrow\mathbb{R}^{+}),\lambda(.):\mathcal{C}^{0}(\mathbb{R}\rightarrow\mathbb{R}^{+})\end{subarray}}&\int_{u\in\mathbb{R}}{\lambda}(u)du\\\
\textrm{ s.t. }\quad&\int_{u\in\mathbb{R}}{\delta}(u)du\leq 1\\\
&-\left[\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right]{\delta}(u)+{\lambda}(u)+\epsilon\left(-{\nu}^{(1)}(u,\textbf{x})+{\nu}^{(2)}(u,\textbf{x})\right)\\\
&\hskip
50.00008pt+{\nu}^{(1)}_{u}(u,\textbf{x})+{\nu}^{(2)}_{u}(u,\textbf{x})\leq
0\text{ }\forall u\in\mathbb{R},\forall\textbf{x}\in\mathbb{R}^{k}\\\ &\exists
U:\mathcal{C}^{0}(\mathbb{R}^{k}\rightarrow\mathbb{R})\textrm{ s.t.
}-\nu^{(1)}(u,\textbf{x})+\nu^{(2)}(u,\textbf{x})\geq 0\text{ }\forall u\geq
U(\textbf{x})\text{ }\forall\textbf{x}\in(\mathbb{R})^{k}\\\ &\exists
L:\mathcal{C}^{0}(\mathbb{R}^{k}\rightarrow\mathbb{R})\textrm{ s.t.
}-\nu^{(1)}(u,\textbf{x})+\nu^{(2)}(u,\textbf{x})\leq 0\text{ }\forall u\leq
L(\textbf{x})\text{ }\forall\textbf{x}\in(\mathbb{R})^{k}\end{aligned}\right.$
(80)

We now prove the following set of lemmas and denote the optimal value of DILP
given by $\mathcal{O}$ as $\text{opt}(\mathcal{O})$

######  Lemma B.7.

$\text{opt}(\mathcal{E}^{int})\geq\text{opt}(\mathcal{E})$

###### Proof.

This proof follows by restricting exactly one of the values
$\nu^{(1)}(u,\textbf{x})$ or $\nu^{(2)}(u,\textbf{x})$ = 0. In this case, we
may define
$\nu(u,\textbf{x})=-\nu^{(1)}(u,\textbf{x})+\nu^{(2)}(u,\textbf{x})$ and thus,
$|\nu(u,\textbf{x})|=\nu^{(1)}(u,\textbf{x})+\nu^{(2)}(u,\textbf{x})$. Since,
we restrict the optimization variables i.e. add an extra constraint, we get
$\text{opt}(\mathcal{E}^{int})\geq\text{opt}(\mathcal{E})$ ∎

######  Lemma B.8.

$\text{opt}(\mathcal{O})\geq\text{opt}(\mathcal{E}^{int})$.

Before we start the proof, we give some key observations which allow us to
prove the weak duality. Observe that the constraint of DILP $\mathcal{O}$
involves a linear constraint of derivative of $g(.,.)$. We use integration by
parts in this proof to convert this into a constraint on the derivative of the
dual variable $\nu(.)$ in the dual DILP $\mathcal{E}$. We state the equation
for this below. 272727For sake of brevity, we give the inequality using
derivatives and not upper and lower derivatives. A formal version of this is
given in equation (98).

$\displaystyle\int_{u\in\mathbb{R}}(\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x}))g_{u}(u,\textbf{x})du$
(81) $\displaystyle=$
$\displaystyle\left[(\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x}))g(u,\textbf{x})\right]_{u=-\infty}^{+\infty}-\int_{u\in\mathbb{R}}(\nu^{(1)}_{u}(u,\textbf{x})-\nu^{(2)}_{u}(u,\textbf{x}))g(u,\textbf{x})du$
(82) $\displaystyle\leq$
$\displaystyle-\int_{u\in\mathbb{R}}(\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x}))g(u,\textbf{x})$
(83)

The last step follows from the last two constraints in DILP $\mathcal{E}$ i.e.
$\lim_{u\to\infty}\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})\leq 0$ and
$\lim_{u\to-\infty}\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})\geq 0$

We now move to the proof of the weak duality. Notice that this proof B.6.2
bears resemblance to the weak duality proof, albeit with a clever utilization
of integration by parts, Fatou’s lemma, and the monotone convergence theorem.
This approach allows for the exchange of limits and integrals in a strategic
manner.

To get an intuition on the proof steps, we first present an informal proof
B.6.1 where we assume functions are always integrable and exchange limits and
integrals without giving explicit reasons. To look into its formal treatment
refer to Section B.6.2

####  B.6.1 Informal proof to Theorem 2.8

As discussed above, in this proof we just give an intuition for the steps to
gain an understanding without giving formal reasons for exchange of integrals
and limits. We further assume that the lower and upper derivatives are
integrable in this part. To look into its formal treatment refer to Proof in
Section B.6.2.

###### Informal proof.

Now consider any feasible solution $g(.,.)$ and $\kappa$ in the primal DILP
$\mathcal{O}$ and feasible solution
$\nu^{(1)}(.,.),\nu^{(2)}(.,.),\lambda(.)\text{ and }\delta(.)$ in the dual
DILP $\mathcal{E}^{int}$.

Now pre-multiply the first constraint in DILP $\mathcal{O}$ by $\delta(u)$
second constraint in DILP by $\lambda(u)$, the third constraint in DILP by
$\nu^{(1)}(u,\textbf{x})$ and fourth constraint in DILP $\mathcal{O}$ by
$\nu^{(2)}(u,\textbf{x})$

$\displaystyle\int\limits_{u\in\mathbb{R}}\delta(u)\left[\kappa-\int\limits_{\textbf{x}\in\mathbb{R}^{k}}\left(\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right)g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)\right]du+\int\limits_{u\in\mathbb{R}}\int\limits_{\textbf{x}\in\mathbb{R}^{k}}g(u,\textbf{x})\lambda(u)d\left(\prod_{i=1}^{k}x_{i}\right)du$
$\displaystyle+\int\limits_{u\in\mathbb{R}}\int\limits_{\textbf{x}\in\mathbb{R}^{k}}(\epsilon
g(u,\textbf{x})+\underline{g}_{u}(u,\textbf{x}))\nu^{(1)}(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)du+\int\limits_{u\in\mathbb{R}}\int\limits_{\textbf{x}\in\mathbb{R}^{k}}(\epsilon
g(u,\textbf{x})-\overline{g}_{u}(u,\textbf{x}))\nu^{(2)}(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)du\geq\int\limits_{u\in\mathbb{R}}\lambda(u)du$
(84) $\displaystyle\overset{(e)}{\implies}$
$\displaystyle\kappa+\int\limits_{\textbf{x}\in\mathbb{R}^{k}}\left[\int\limits_{u\in\mathbb{R}}\left(-\left[\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right]\delta(u)+\lambda(u)+\epsilon\nu^{(2)}(u,\textbf{x})+\epsilon\nu^{(1)}(u,\textbf{x})\right)du\right]g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)$
$\displaystyle+\int_{\textbf{x}\in\mathbb{R}^{k}}\left[\int_{u\in\mathbb{R}}\left(\nu^{(1)}(u,\textbf{x})(u,\textbf{x})\underline{g}_{u}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})\overline{g}_{u}(u,\textbf{x})\right)du\right]d\left(\prod_{i=1}^{k}x_{i}\right)\geq\int\limits_{u\in\mathbb{R}}\lambda(u)du$
(85)

$(e)$ follows by exchanging integrals since each term is positive and the
constraint$\int_{u}\delta(u)\leq 1$.

Now, we solve the for the term
$\int_{u\in\mathbb{R}}\left[\nu^{(1)}(u,\textbf{x})\underline{g}_{u}(u,\textbf{x})du-\nu^{(2)}(u,\textbf{x})\overline{g}_{u}(u,\textbf{x})\right]du$

$\displaystyle\int_{u\in\mathbb{R}}\left[\nu^{(1)}(u,\textbf{x})\underline{g}_{u}(u,\textbf{x})du-\nu^{(2)}(u,\textbf{x})\overline{g}_{u}(u,\textbf{x})\right]du$
(86)
$\displaystyle\overset{(a)}{\leq}\left[\left(\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})\right)g(u,\textbf{x})\right]_{u=-\infty}^{+\infty}-\left[\int\limits_{u\in\mathbb{R}}(\nu^{(1)}_{u}(u,\textbf{x})-\nu^{(2)}_{u}(u,\textbf{x})){g}(u,\textbf{x})du\right]$
(87)
$\displaystyle\overset{(b)}{\leq}-\left[\int\limits_{u\in\mathbb{R}}\left(\nu^{(1)}_{u}(u,\textbf{x})-\nu^{(2)}_{u}(u,\textbf{x})\right){g}(u,\textbf{x})du\right]$
(88)

$(a)$ follows from integration of parts and the inequality from the fact that
we take lower derivative and upper derivative of $g(.)$ respectively. $(b)$
follows from the third and fourth constraints in the LP $D^{int}$ on
$\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})$ as $u\to\infty$ or
$u\to-\infty$.

Combining the inequalities in (97) and (98), we get,

$\displaystyle\implies$
$\displaystyle\kappa+\int\limits_{\textbf{x}\in\mathbb{R}^{k}}\left[\int\limits_{u\in\mathbb{R}}\left(\left[\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right]\delta(u)+\lambda(u)+\epsilon\nu^{(2)}(u,\textbf{x})+\epsilon\nu^{(1)}(u,\textbf{x})\right)du\right]g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)$
$\displaystyle-\int_{\textbf{x}\in\mathbb{R}^{k}}\left[\int\limits_{u\in\mathbb{R}}\left(\nu^{(1)}_{u}(u,\textbf{x})-\nu^{(2)}_{u}(u,\textbf{x})\right){g}(u,\textbf{x})du\right]d\left(\prod_{i=1}^{k}x_{i}\right)\geq\int\limits_{u\in\mathbb{R}}\lambda(u)du$
(89) $\displaystyle\implies$
$\displaystyle\kappa+\int_{\textbf{x}\in\mathbb{R}^{k}}\Biggl{[}\int\limits_{u\in\mathbb{R}}\Biggl{(}\left(\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right)\delta(u)+\lambda(u)+\epsilon\nu^{(2)}(u,\textbf{x})+\epsilon\nu^{(1)}(u,\textbf{x})$
(90) $\displaystyle\hskip
100.00015pt-\left(\nu^{(1)}_{u}(u,\textbf{x})-\nu^{(2)}_{u}(u,\textbf{x})\right)\Biggr{)}du\Biggr{]}g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)\geq\int\limits_{u\in\mathbb{R}}\lambda(u)du$
(91)
$\displaystyle\overset{(c)}{\implies}\kappa\geq\int\limits_{u\in\mathbb{R}}\lambda(u)du$
(92)

$(c)$ follows from the first and second constraint in LP $\mathcal{E}^{int}$.
Since this inequality is true for every feasible solution in the primal
$\mathcal{O}$ and dual $\mathcal{E}^{int}$, we have the proof in the theorem.

∎

####  B.6.2 A formal proof of Theorem 2.8

###### Proof.

Now consider any feasible solution $g(.,.)$ and $\kappa$ in the primal DILP
$\mathcal{O}$ and feasible solution
$\nu^{(1)}(.,.),\nu^{(2)}(.,.),\lambda(.)\text{ and }\delta(.)$ in the dual
DILP $\mathcal{E}^{int}$.

Now pre-multiply the first constraint in DILP $\mathcal{O}$ by $\delta(u)$
second constraint in DILP by $\lambda(u)$, the third constraint in DILP by
$\nu^{(1)}(u,\textbf{x})$ and fourth constraint in DILP $\mathcal{O}$ by
$\nu^{(2)}(u,\textbf{x})$ and take the lower Riemann-Darboux integrals for the
last two terms and the integral for the first two terms. 282828The integral
may not be defined as $\underline{g}_{u}$ and $\overline{g}_{u}$ may not be
Riemann integrable, however the first and second terms are integrable which
follows since the product of integrable functions is integrable. . This
approach is very similar to the use of Lagrange multiplier in weak duality
proof in linear programming. Also observe that some limits may take values in
the extended reals i.e. $\mathbbm{R}\cup\\{-\infty,\infty\\}$ and thus, we
define the limits in extended reals.

.

Observe that
$d^{l},d^{u}\in\mathbb{R}$,$\textbf{c}^{l},\textbf{c}^{u}\in\mathbb{R}^{k}$
and $c^{l}_{i},c^{u}_{i}$ refers to its $i^{th}$ component of $\textbf{c}^{l}$
and $\textbf{c}^{u}\in\mathbb{R}^{k}$ respectively.

Thus, we get292929$\mkern 3.0mu\underline{\vphantom{\intop}\mkern
7.0mu}\mkern-10.0mu\int f(x)dx$ and $\mathchoice{\mkern
13.0mu\overline{\vphantom{\intop}\mkern 7.0mu}\mkern-20.0mu}{\mkern
7.0mu\overline{\vphantom{\intop}\mkern 7.0mu}\mkern-14.0mu}{\mkern
7.0mu\overline{\vphantom{\intop}\mkern 7.0mu}\mkern-14.0mu}{\mkern
7.0mu\overline{\vphantom{\intop}\mkern 7.0mu}\mkern-14.0mu}\int f(x)dx$
denotes the lower and upper integral respectively.

$\displaystyle\lim_{\begin{subarray}{c}d^{l}\to-\infty\\\
d^{u}\to\infty\end{subarray}}\int\limits_{u=d^{l}}^{d^{u}}\delta(u)\left[\kappa-\int\limits_{\textbf{x}\in\mathbb{R}^{k}}\left(\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right)g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)\right]du$
(93) $\displaystyle\hskip
180.00027pt+\lim_{\begin{subarray}{c}d^{l}\to-\infty\\\
d^{u}\to\infty\end{subarray}}\int\limits_{u=d^{l}}^{d^{u}}\left(\int\limits_{\textbf{x}\in\mathbb{R}^{k}}g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)\right)\lambda(u)du$
$\displaystyle+\liminf_{d,\textbf{c}\to\infty}\mkern
3.0mu\underline{\vphantom{\intop}\mkern
7.0mu}\mkern-10.0mu\int_{\begin{subarray}{c}u\in[d^{l},d^{u}]\\\
\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]\end{subarray}}\left((\epsilon
g(u,\textbf{x})+\underline{g}_{u}(u,\textbf{x}))\nu^{(1)}(u,\textbf{x})+(\epsilon
g(u,\textbf{x})-\overline{g}_{u}(u,\textbf{x}))\nu^{(2)}(u,\textbf{x})\right)d\left(\prod_{i=1}^{k}x_{i}\right)du\geq\int\limits_{u\in\mathbb{R}}\lambda(u)du$
(94) $\displaystyle\text{ }\implies\lim_{\begin{subarray}{c}d^{l}\to-\infty\\\
d^{u}\to\infty\end{subarray}}\int\limits_{u=d^{l}}^{d^{u}}\delta(u)\lim_{\begin{subarray}{c}\textbf{c}^{u}\to\infty\\\
\textbf{c}^{l}\to-\infty\end{subarray}}\left[\kappa-\int\limits_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left(\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right)g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)\right]du$
$\displaystyle\hskip 200.0003pt+\lim_{\begin{subarray}{c}d^{l}\to-\infty\\\
d^{u}\to\infty\end{subarray}}\int\limits_{u=d^{l}}^{d^{u}}\lim_{\begin{subarray}{c}\textbf{c}^{u}\to\infty\\\
\textbf{c}^{l}\to-\infty\end{subarray}}\left[\int\limits_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}g(u,\textbf{x})\lambda(u)d\left(\prod_{i=1}^{k}x_{i}\right)\right]du$
$\displaystyle+\liminf_{d,\textbf{c}\to\infty}\mkern
3.0mu\underline{\vphantom{\intop}\mkern
7.0mu}\mkern-10.0mu\int_{\begin{subarray}{c}u\in[d^{l},d^{u}]\\\
\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]\end{subarray}}\left((\epsilon
g(u,\textbf{x})+\underline{g}_{u}(u,\textbf{x}))\nu^{(1)}(u,\textbf{x})+(\epsilon
g(u,\textbf{x})-\overline{g}_{u}(u,\textbf{x}))\nu^{(2)}(u,\textbf{x})\right)d\left(\prod_{i=1}^{k}x_{i}\right)du\geq\int\limits_{u\in\mathbb{R}}\lambda(u)du$
(95) $\displaystyle\text{
}\overset{(c)}{\implies}\lim_{d\to\infty}\lim_{\textbf{c}\to\infty}\int\limits_{u=d^{l}}^{d^{u}}\left(\kappa\delta(u)+\int\limits_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left(\left(-\delta(u)\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)+\lambda(u)\right)g(u,\textbf{x})\right)d\left(\prod_{i=1}^{k}x_{i}\right)\right)du$
$\displaystyle\hskip
40.00006pt+\liminf_{d,\textbf{c}\to\infty}\Biggl{(}\int_{\begin{subarray}{c}u\in[d^{l},d^{u}]\\\
\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]\end{subarray}}\left(\epsilon
g(u,\textbf{x})\left(\nu^{(1)}(u,\textbf{x})+\nu^{(2)}(u,\textbf{x})\right)\right)d\left(\prod_{i=1}^{k}x_{i}\right)du$
$\displaystyle\hskip 60.00009pt+\mkern 3.0mu\underline{\vphantom{\intop}\mkern
7.0mu}\mkern-10.0mu\int_{\begin{subarray}{c}u\in[d^{l},d^{u}]\\\
\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]\end{subarray}}\left(\underline{g}_{u}(u,\textbf{x})\nu^{(1)}(u,\textbf{x})-\overline{g}_{u}(u,\textbf{x})\nu^{(2)}(u,\textbf{x})\right)d\left(\prod_{i=1}^{k}x_{i}\right)du\Biggr{)}\geq\int\limits_{u\in\mathbb{R}}\lambda(u)du$
(96)
$\displaystyle\overset{(d)}{\implies}\kappa+\limsup_{{d},\textbf{c}\to\infty}\Biggl{(}\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left[\int\limits_{u=d^{l}}^{d^{u}}\left(-\left[\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right]\delta(u)+\lambda(u)\right)du\right]g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)\Biggr{)}$
$\displaystyle+\liminf_{d,\textbf{c}\to\infty}\Biggl{(}\int_{\begin{subarray}{c}u\in[d^{l},d^{u}]\\\
\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]\end{subarray}}\left(\epsilon
g(u,\textbf{x})\left(\nu^{(1)}(u,\textbf{x})+\nu^{(2)}(u,\textbf{x})\right)\right)d\left(\prod_{i=1}^{k}x_{i}\right)du$
$\displaystyle\hskip 45.00006pt+\mkern 3.0mu\underline{\vphantom{\intop}\mkern
7.0mu}\mkern-10.0mu\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left[\mkern
3.0mu\underline{\vphantom{\intop}\mkern
7.0mu}\mkern-10.0mu\int_{u=d^{l}}^{d^{u}}\left(\nu^{(1)}(u,\textbf{x})\underline{g}_{u}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})\overline{g}_{u}(u,\textbf{x})\right)du\right]d\left(\prod_{i=1}^{k}x_{i}\right)\Biggr{)}\geq\int\limits_{u\in\mathbb{R}}\lambda(u)du$
(97)

$(c)$ 303030$d,\to\infty$ is a shorthand notation for $d^{u}\to\infty$,
$d^{l}\to-\infty$ and $\textbf{c}\to\infty$ is a shorthand for
$\textbf{c}^{u}\to\infty$ and $\textbf{c}^{l}\to-\infty$ follows from the
following observations.

  * •

For the first two integrals, apply monotone convergence theorem (MCT) which
allows us to exchange limit and integral. This is possible since the
expression in $[.]$ is positive and non-decreasing as
$\textbf{c}^{u}\to\infty$ and $\textbf{c}^{l}\to-\infty$ due to first
constraint of DILP $\mathcal{O}$ and the fact that the $g(.,.)$ is non-
negative.

$(d)$ follows from the following steps.

  * •

Apply the interated integral inequality [54, Proposition 3.9] that $\mkern
3.0mu\underline{\vphantom{\intop}\mkern 7.0mu}\mkern-10.0mu\int_{A\times
B}g(A,B)dAdB\leq\mkern 3.0mu\underline{\vphantom{\intop}\mkern
7.0mu}\mkern-10.0mu\int_{A}\left[\mkern
3.0mu\underline{\vphantom{\intop}\mkern
7.0mu}\mkern-10.0mu\int_{B}g(A,B)dB\right]dA$ for the last integral.

  * •

We exchange integrals for the first term using Fubini’s theorem [54, Theorem
3.10] as the functions are Riemann integrable and use the fact that
$\int_{u\in\mathbbm{R}}\delta(u)\leq 1$.

  * •

We upper bound the iterated limits by a limsup as
$\limsup_{m,n}a_{m,n}\geq\lim_{m}\lim_{n}a_{m,n}$.

Now, we bound the term $\mkern 3.0mu\underline{\vphantom{\intop}\mkern
7.0mu}\mkern-10.0mu\int_{u\in[d^{l},d^{u}]}\left[\nu^{(1)}(u,\textbf{x})\underline{g}_{u}(u,\textbf{x})du-\nu^{(2)}(u,\textbf{x})\overline{g}_{u}(u,\textbf{x})\right]du$.313131Note
that the second integral is defined as the product of Riemann integrable
functions is also integrable. Observe that,

$\displaystyle\mkern 3.0mu\underline{\vphantom{\intop}\mkern
7.0mu}\mkern-10.0mu\int_{u\in[d^{l},d^{u}]}\left[\nu^{(1)}(u,\textbf{x})\underline{g}_{u}(u,\textbf{x})du-\nu^{(2)}(u,\textbf{x})\overline{g}_{u}(u,\textbf{x})\right]du+\int_{u\in[d^{l},d^{u}]}\left(\nu^{(1)}_{u}(u,\textbf{x})-\nu^{(2)}_{u}(u,\textbf{x})\right){g}(u,\textbf{x})du$
$\displaystyle\overset{(f)}{\leq}$
$\displaystyle\left[\left(\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})\right)g(u,\textbf{x})\right]_{u=d^{l}}^{d^{u}}$
(98)

$(f)$ follows from the chain rule of differentiation and the inequality from
the fact that we take lower derivative of $-g(.)$ is upper derivative of
$g(.)$

Now consider (observe we take the -ve of the last term in Equation (98)).

$\displaystyle\limsup_{d,\textbf{c}\to\infty}\left[\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}-\left[\left(\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})\right)g(u,\textbf{x})\right]_{u=d^{l}}^{d^{u}}d\left(\prod_{i=1}^{k}x_{i}\right)\right]$
$\displaystyle\overset{(i)}{\geq}$
$\displaystyle\limsup_{\textbf{c}\to\infty}\liminf_{d\to\infty}\left[\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left(-\left[\left(\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})\right)g(u,\textbf{x})\right]_{u=d^{l}}^{d^{u}}\right)d\left(\prod_{i=1}^{k}x_{i}\right)\right]$
$\displaystyle\overset{(g)}{\geq}$
$\displaystyle\limsup_{\textbf{c}\to\infty}\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\liminf_{\begin{subarray}{c}d^{u}\to\infty\\\
d^{l}\to-\infty\end{subarray}}\left[-\left(\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})\right)g(u,\textbf{x})\right]_{u=d^{l}}^{d^{u}}d\left(\prod_{i=1}^{k}x_{i}\right)$
$\displaystyle\overset{(h)}{\geq}$
$\displaystyle\limsup_{\textbf{c}\to\infty}\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\Bigl{(}\liminf_{d^{u}\to\infty}\left[\left(-\nu^{(1)}(d^{u},\textbf{x})+\nu^{(2)}(d^{u},\textbf{x})\right)g(d^{u},\textbf{x})\right]$
(99) $\displaystyle\hskip
120.00018pt+\liminf_{d^{l}\to-\infty}\left[\left(\nu^{(1)}(d^{l},\textbf{x})-\nu^{(2)}(d^{l},\textbf{x})\right)g(d^{l},\textbf{x})\right]\Bigr{)}d\left(\prod_{i=1}^{k}x_{i}\right)$
$\displaystyle\overset{(m)}{\geq}0$ (100)

$(i)$ follows from the fact that
$\limsup_{m,n}f(m,n)\geq\limsup_{m}\limsup_{n}f(m,n)\geq\limsup_{m}\liminf_{n}f(m,n)$.

$(g)$ follows from the following arguments.

  * •

Observe that
$\left[-\left(\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})\right)g(u,\textbf{x})\right]_{u=d^{l}}^{d^{u}}$
is non-negative for every
$\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]$ whenever,
$d_{u}>\sup\\{U(\textbf{x})|\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]\\}$
and
$d_{l}<\inf\\{L({\textbf{x}})|\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]\\}$
from third and fourth constraint of DILP $\mathcal{E}^{int}$. Note that value
is finite as supremeum and infimum of continuous functions is finite over a
compact set since $\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]$ is closed and
bounded.

  * •

Now apply Fatou’s lemma to conclude $(g)$.

$(h)$ follows from the fact that
$\liminf_{n}(A_{n}+B_{n})\geq\liminf_{n}A_{n}+\liminf_{n}B_{n}$ and the last
inequality $(m)$ follows from the following 2 statements.

  * •

$\liminf_{d^{u}\to\infty}\left(-\nu^{(1)}(d^{u},\textbf{x})+\nu^{(2)}(d^{u},\textbf{x})\right)\geq
0$ and
$\liminf_{d^{l}\to-\infty}\left(\nu^{(1)}(d^{l},\textbf{x})-\nu^{(2)}(d^{l},\textbf{x})\right)\geq
0$ follows from third and fourth constraint of DILP $\mathcal{E}^{int}$.

  * •

$g(.,.)$ is a bounded function follows from the constraint in DILP
$\mathcal{O}$.

Observe that (B.6.2) implies (follows from
$\limsup_{n}A_{n}=-\liminf_{n}-A_{n}$) that

${}\liminf_{d,\textbf{c}\to\infty}\left[\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left[\left(\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})\right)g(u,\textbf{x})\right]_{u=d^{l}}^{d^{u}}d\left(\prod_{i=1}^{k}x_{i}\right)\right]\leq
0$ (101)

Using inequality in (98) and the fact that
$\liminf_{n}(a_{n}+b_{n})\leq\liminf a_{n}+\limsup_{n}b_{n}$, we obtain

$\displaystyle\liminf_{d,\textbf{c}\to\infty}\Biggl{(}\mkern
3.0mu\underline{\vphantom{\intop}\mkern
7.0mu}\mkern-10.0mu\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left[\mkern
3.0mu\underline{\vphantom{\intop}\mkern
7.0mu}\mkern-10.0mu\int_{u=d^{l}}^{d^{u}}\left(\nu^{(1)}(u,\textbf{x})\underline{g}_{u}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})\overline{g}_{u}(u,\textbf{x})\right)du\right]d\left(\prod_{i=1}^{k}x_{i}\right)$
$\displaystyle\hskip 60.00009pt+\int_{\begin{subarray}{c}u\in[d^{l},d^{u}]\\\
\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]\end{subarray}}\left(\epsilon
g(u,\textbf{x})\left(\nu^{(1)}(u,\textbf{x})+\nu^{(2)}(u,\textbf{x})\right)\right)d\left(\prod_{i=1}^{k}x_{i}\right)\Biggr{)}du$
(102) $\displaystyle{\leq}$
$\displaystyle\liminf_{d,\textbf{c}\to\infty}\left[\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left[\left(\nu^{(1)}(u,\textbf{x})-\nu^{(2)}(u,\textbf{x})\right)g(u,\textbf{x})\right]_{u=d^{l}}^{d^{u}}d\left(\prod_{i=1}^{k}x_{i}\right)\right]$
$\displaystyle\hskip
60.00009pt+\limsup_{d,\textbf{c}\to\infty}\Biggr{(}\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left[-\int_{u\in[d^{l},d^{u}]}\left(\nu^{(1)}_{u}(u,\textbf{x})-\nu^{(2)}_{u}(u,\textbf{x})\right){g}(u,\textbf{x})du\right]d\left(\prod_{i=1}^{k}x_{i}\right)$
$\displaystyle\hskip 100.00015pt+\int_{\begin{subarray}{c}u\in[d^{l},d^{u}]\\\
\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]\end{subarray}}\left(\epsilon
g(u,\textbf{x})\left(\nu^{(1)}(u,\textbf{x})+\nu^{(2)}(u,\textbf{x})\right)\right)d\left(\prod_{i=1}^{k}x_{i}\right)du\Biggr{)}$
(103) $\displaystyle\overset{(k)}{\leq}$
$\displaystyle\limsup_{d,\textbf{c}\to\infty}\Biggr{(}\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left[-\int_{u\in[d^{l},d^{u}]}\left(\nu^{(1)}_{u}(u,\textbf{x})-\nu^{(2)}_{u}(u,\textbf{x})\right){g}(u,\textbf{x})du\right]d\left(\prod_{i=1}^{k}x_{i}\right)$
$\displaystyle\hskip 100.00015pt+\int_{\begin{subarray}{c}u\in[d^{l},d^{u}]\\\
\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]\end{subarray}}\left(\epsilon
g(u,\textbf{x})\left(\nu^{(1)}(u,\textbf{x})+\nu^{(2)}(u,\textbf{x})\right)\right)d\left(\prod_{i=1}^{k}x_{i}\right)du\Biggr{)}$
(104)

$(k)$ follows on applying Equation (101)

Now combining (104) and (97), we obtain

$\displaystyle\kappa+\limsup_{d,\textbf{c}\to\infty}\Biggl{(}\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left[\int_{u\in[d^{l},d^{u}]}\left(-\left[\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right]\delta(u)+\lambda(u)\right)du\right]g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)\Biggr{)}$
$\displaystyle+\limsup_{d,\textbf{c}\to\infty}\Biggr{(}\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left[-\int_{u\in[d^{l},d^{u}]}\left(\nu^{(1)}_{u}(u,\textbf{x})-\nu^{(2)}_{u}(u,\textbf{x})\right){g}(u,\textbf{x})du\right]d\left(\prod_{i=1}^{k}x_{i}\right)$
$\displaystyle\hskip 100.00015pt+\int_{\begin{subarray}{c}u\in[d^{l},d^{u}]\\\
\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]\end{subarray}}\left(\epsilon
g(u,\textbf{x})\left(\nu^{(1)}(u,\textbf{x})+\nu^{(2)}(u,\textbf{x})\right)\right)d\left(\prod_{i=1}^{k}x_{i}\right)du\Biggr{)}\geq\int\limits_{u\in\mathbbm{R}}\lambda(u)du$
(105)
$\displaystyle\overset{(i)}{\implies}\kappa+\lim_{d,\textbf{c}\to\infty}\Biggl{(}\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left[\int_{u\in[d^{l},d^{u}]}\left(-\left[\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right]\delta(u)+\lambda(u)\right)du\right]g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)\Biggr{)}$
$\displaystyle+\limsup_{d,\textbf{c}\to\infty}\Biggr{(}\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\left[-\int_{u\in[d^{l},d^{u}]}\left(\nu^{(1)}_{u}(u,\textbf{x})-\nu^{(2)}_{u}(u,\textbf{x})\right){g}(u,\textbf{x})du\right]d\left(\prod_{i=1}^{k}x_{i}\right)\Biggr{)}$
$\displaystyle\hskip
60.00009pt+\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\int_{u\in[d^{l},d^{u}]}\left(\epsilon
g(u,\textbf{x})\left(\nu^{(1)}(u,\textbf{x})+\nu^{(2)}(u,\textbf{x})\right)\right)d\left(\prod_{i=1}^{k}x_{i}\right)du\Biggr{)}\geq\int\limits_{u\in\mathbbm{R}}\lambda(u)du$
(106) $\displaystyle{\implies}$
$\displaystyle\kappa+\limsup_{d,\textbf{c}\to\infty}\Biggl{(}\int_{\textbf{x}\in\prod\limits_{i=1}^{k}[c^{l}_{i},c^{u}_{i}]}\Biggl{[}\int_{u\in[d^{l},d^{u}]}\Biggl{(}-\left(\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right)\delta(u)+\lambda(u)+\epsilon\nu^{(2)}(u,\textbf{x})+\epsilon\nu^{(1)}(u,\textbf{x})\Biggr{)}$
(107) $\displaystyle\hskip
100.00015pt-\left(\nu^{(1)}_{u}(u,\textbf{x})-\nu^{(2)}_{u}(u,\textbf{x})\right)\Biggr{)}du\Biggr{]}g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)\Biggr{)}\geq\int\limits_{u\in\mathbb{R}}\lambda(u)du$
(108)
$\displaystyle\overset{(j)}{\implies}\kappa\geq\int\limits_{u\in\mathbb{R}}\lambda(u)du$
(109)

The limsup in first term of $(i)$ can be replaced by a limit as integral (110)
is defined in extended reals ($\mathbb{R}\cup\\{\infty,-\infty\\}$) which
follows from the following reasons.323232Intuitively it shows that
$\infty-\infty$ scenario cannot arrive in this integral

$\displaystyle\Biggl{(}\int_{\textbf{x}\in\mathbb{R}^{k}}\left[\int_{u\in\mathbb{R}}\left(-\left[\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right]\delta(u)+\lambda(u)\right)du\right]g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)\Biggr{)}$
(110) $\displaystyle=$
$\displaystyle-\int_{\textbf{x}\in\mathbb{R}^{k}}\int_{u\in\mathbb{R}}\left[\min_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)\right]\delta(u)g(u,\textbf{x})du\text{
}d\left(\prod_{i=1}^{k}x_{i}\right)$ (111) $\displaystyle\hskip
180.00027pt+\int_{\textbf{x}\in\mathbb{R}^{k}}\int_{u\in\mathbb{R}}\lambda(u)g(u,\textbf{x})du\text{
}d\left(\prod_{i=1}^{k}x_{i}\right)$ (112)

  * •

Observe that $\int_{u}\delta(u)\leq 1$ and
$\int_{\textbf{x}\in\mathbb{R}^{k}}\min\limits_{a\in\texttt{Set}(\textbf{x})}\mathfrak{h}(|u-a|)g(u,\textbf{x})d\left(\prod_{i=1}^{k}x_{i}\right)\leq\kappa\text{
}\forall u\in\mathbb{R}$ (first constraint of DILP $\mathcal{O}$) implying
that term (111) is lower bounded by $-\kappa$.

  * •

Thus, we may conclude that the following integral (110) is defined in extended
reals as the first term (111) is lower bounded by $-\kappa$ and second term
(112) is lower bounded by 0.

$(j)$ follows from the first and second constraint in DILP
$\mathcal{E}^{int}$. Since this inequality is true for every feasible solution
in the primal $\mathcal{O}$ and dual $\mathcal{E}^{int}$, we have the proof in
the theorem. ∎

We now prove Theorem 2.8.

###### Proof.

Combining Claim B.7 and B.8, we obtain that
$\text{opt}(\mathcal{O})\geq\text{opt}(\mathcal{E})$. ∎

###  B.7 Claim to prove the existence of continuous bounds $U(\textbf{v})$ and
$L(\textbf{v})$ for the feasible solution in $\mathcal{E}$ in the proof of
Lemma 2.12

######  Claim 1.

Consider a function
$\nu(.,.):\mathcal{C}^{1}(\mathbbm{R}\times\mathbbm{R}^{k}\rightarrow\mathbbm{R})$
s.t. zeros of $\nu(.,\textbf{v})$ i.e.
$\\{\mathfrak{u}:\nu(\mathfrak{u},\textbf{v})=0\\}$ is a countable set for
every $\textbf{v}\in\mathbbm{R}^{k}$.

It also satisfies the following two conditions for some constant $C$
independent of v. Note that $v_{\lfloor i\rfloor}$ denotes the $i^{th}$
largest component of v for every $i\in[k]$.

  * •

$\Big{\\{}\mathfrak{u}\in\mathbb{R}:\nu(\mathfrak{u},\textbf{v})=0\text{ and
}\nu_{u}(\mathfrak{u},\textbf{v})<0\Big{\\}}$ is upper bounded by
$C+v_{\lfloor k\rfloor}$ for every $\textbf{v}\in\mathbbm{R}^{k}$.

  * •

$\forall\textbf{v}\in\mathbbm{R}^{k}\text{ }\exists\text{ }\mathcal{U}$ s.t
$\nu(u,\textbf{v})\geq 0\text{ }\forall u>\mathcal{U}$.

Then there exists $U:\mathcal{C}^{0}(\mathbbm{R}^{k}\rightarrow\mathbbm{R})$
s.t. $\nu(u,\textbf{v})\geq 0\text{ }\forall u\geq U(\textbf{v})\text{
}\forall\textbf{v}\in\mathbbm{R}^{k}$.

###### Proof.

We prove this statement as follows. For every $\textbf{v}\in\mathbbm{R}^{k}$,
denote the largest zero of $\nu(.,\textbf{v})$ by $p(\textbf{v})$. Now
construct $U(\textbf{v})=\max(p(\textbf{v}),C+v_{\lfloor k\rfloor})$. Observe
that $\nu(u,\textbf{v})\geq 0\text{ }\forall u\geq U(\textbf{v})\text{
}\forall\textbf{v}\in\mathbbm{R}^{k}$ follows from the second assumption.

To prove continuity at $\textbf{v}\in\mathbbm{R}^{k}$, we aim to show the
following statement.

${}\forall\epsilon>0\text{ }\exists\delta>0\text{ s.t.
}\forall\textbf{z}\in\mathbbm{R}^{k};\text{
}||\textbf{z}-\textbf{v}||_{1}\leq\delta\implies|U(\textbf{z})-U(\textbf{v})|\leq\epsilon.$
(113)

We now show $U(\textbf{v})$ is continuous for every
$\textbf{v}\in\mathbbm{R}^{k}$. We consider two exhaustive cases below.

Case 1: $p(\textbf{v})\geq C+v_{\lfloor k\rfloor}$ and thus,
$U(\textbf{v})=p(\textbf{v})$. Recall from the second assumption that
$\nu(u,\textbf{v})$ goes from negative to positive at $u=p(\textbf{v})$.

We now discuss the construction of $\delta$ below for a sufficiently small
$\epsilon$ as follows.

For some $\epsilon$ sufficiently small, we now discuss the construction of an
interval around $p_{\textbf{v}}$ as
$[\mathcal{A}_{\textbf{v}},\mathcal{B}_{\textbf{v}}]=[p_{\textbf{v}}-\frac{\epsilon}{2},p_{\textbf{v}}+\frac{\epsilon}{2}]$.
Since, $\epsilon$ is sufficiently small, observe that
$\nu(\mathcal{A}_{\textbf{v}},\textbf{v})=-\zeta_{1}$ and
$\nu(\mathcal{B}_{\textbf{v}},\textbf{v})=\zeta_{2}$ for some
$\zeta_{1},\zeta_{2}>0$.

Observe that $\nu(\mathcal{A}_{\textbf{v}},\textbf{v})$ must be continuous in
v and thus there must exist $\delta_{1}>0$ s.t.
$\forall\textbf{z}\in\mathbbm{R}^{k};\text{
}||\textbf{z}-\textbf{v}||\leq\delta_{1}\implies|\nu(\mathcal{A}_{\textbf{v}},\textbf{v})-\nu(\mathcal{A}_{\textbf{v}},\textbf{z})|\leq\frac{\zeta_{1}}{2}$
and similarly, choose $\delta_{2}>0$ s.t.
$\forall\textbf{z}\in\mathbbm{R}^{k};\text{
}||\textbf{z}-\textbf{v}_{1}||\leq\delta_{2}\implies|\nu(\mathcal{B}_{\textbf{v}},\textbf{v})-\nu(\mathcal{B}_{\textbf{v}},\textbf{z})|\leq\frac{\zeta_{2}}{2}$.333333Note
that we can do this since, the continuity result holds true for every
$\epsilon>0$ and we can choose any $\epsilon$ we want.

We choose $\delta=\min(\delta_{1},\delta_{2},\frac{\epsilon}{2})$ and consider
any $\textbf{z}\in\mathbbm{R}^{k}$ satisfying
$||\textbf{z}-\textbf{v}||_{1}<\delta$ and show (113)

This implies $\nu(\mathcal{A}_{\textbf{v}},\textbf{z})<-\frac{\zeta_{1}}{2}<0$
and $\nu(\mathcal{B}_{\textbf{v}},\textbf{z})>\frac{\zeta_{2}}{2}>0$ since,
$\nu(\mathcal{A}_{\textbf{v}},\textbf{v})=-\zeta_{1}$ and
$\nu(\mathcal{B}_{\textbf{v}},\textbf{v})=\zeta_{2}$. Thus, from intermediate
value and LMVT theorem, there must exist some zero of $\nu(.,\textbf{z})$
(call it $u_{0}$) with
$u_{0}\in[\mathcal{A}_{\textbf{v}},\mathcal{B}_{\textbf{v}}]$ with $\nu(.)$
going from negative to positive i.e. $\nu_{u}(u_{0},\textbf{z})\geq 0$ and
$\nu(u_{0},\textbf{z})=0$

Also observe that,

$\displaystyle{}\mathcal{B}_{\textbf{v}}$
$\displaystyle\overset{(a)}{\geq}C+v_{\lfloor k\rfloor}+\frac{\epsilon}{2}$
$\displaystyle\overset{(b)}{>}C+z_{\lfloor
k\rfloor}+\frac{\epsilon}{2}-\delta\geq C+z_{\lfloor k\rfloor}$ (114)

$(a)$ follows from $p(\textbf{v})\geq C+v_{\lfloor k\rfloor}$ and the
definition of $\mathcal{B}_{\textbf{v}}$. $(b)$ follows from the fact
$||\textbf{v}-\textbf{z}||\leq\delta$. Observe that the last inequality
follows from the fact that $\delta<\frac{\epsilon}{2}$.

Equation (B.7) and the first condition in Claim 1implies that
$U(u,\textbf{z})$ cannot have a zero in $u$ with $U(u,\textbf{z})$ going from
positive to negative on the right side of interval
$[\mathcal{A}_{\textbf{v}},\mathcal{B}_{\textbf{v}}]$. This implies that the
largest zero of $\nu(u,\textbf{z})$ in interval
$[\mathcal{A}_{\textbf{v}},\mathcal{B}_{\textbf{v}}]$ must be the largest zero
and thus, it must be $p(\textbf{z})$. Also,
$p(\textbf{z})>\mathcal{A}_{\textbf{v}}>C+z_{\lfloor k\rfloor}$ and thus,
$U(\textbf{z})=p(\textbf{z})$

We thus, have
$|U(\textbf{z})-U(\textbf{v})|=|p(\textbf{z})-p(\textbf{v})|\leq\epsilon$,
since
$\max(|\mathcal{A}_{\textbf{v}}-p(\textbf{v})|,|\mathcal{B}_{\textbf{v}}-p(\textbf{v})|)<\epsilon$
thus proving the desired result in (113)

Case 2: $p(\textbf{v})<C+v_{\lfloor k\rfloor}$, thus
$U(\textbf{v})=C+v_{\lfloor k\rfloor}$.

Since, $p(\textbf{v})$ was the largest zero of $\nu(.,\textbf{v})$ with
$\nu_{u}(p(\textbf{v}),\textbf{v})>0$, observe that $\nu(C+v_{\lfloor
k\rfloor},\textbf{v})=\zeta>0$. Now since $\nu(u,\textbf{v})$ is continuous,
there must exist $\delta_{1}>0$ s.t. $\forall\hat{u}\in\mathbbm{R}$ satisfying
$|\hat{u}-(C+v_{\lfloor k\rfloor})|<\delta_{1}$, we have
$|\nu(\hat{u},\textbf{v})-\nu(\hat{u},\textbf{v})|<\frac{\zeta}{4}$.
Similarly, there must exist $\delta_{2}>0$ s.t.
$\forall\textbf{z}\in\mathbb{R}$ satisfying
$||\textbf{v}-\textbf{z}||_{1}<\delta_{2}$, we have $|\nu(C+z_{\lfloor
k\rfloor},\textbf{v})-\nu(C+z_{\lfloor
k\rfloor},\textbf{z})|\leq\frac{\zeta}{4}$. 343434This holds since continuity
result holds for every $\epsilon>0$.

Now we choose $\delta=\min(\delta_{1},\delta_{2},\epsilon)$ and consider any
$\textbf{z}\in\mathbb{R}^{k}$ satisfying
$||\textbf{z}-\textbf{v}||_{1}\leq\delta$ to show (113).

Observe that, since, $|(C+v_{\lfloor k\rfloor})-(C+{z}_{\lfloor
k\rfloor})|\leq\delta\leq\delta_{1}$, we must have $\nu(C+z_{\lfloor
k\rfloor},\textbf{v})=\nu(C+v_{\lfloor k\rfloor},\textbf{v})+(\nu(C+z_{\lfloor
k\rfloor},\textbf{v})-\nu(C+{v}_{\lfloor
k\rfloor},\textbf{v}))\geq\zeta-\frac{\zeta}{4}=\frac{3\zeta}{4}$. Similarly,
since $||\textbf{v}-\textbf{z}||\leq\delta\leq\delta_{2}$, we must have
$\nu(C+z_{\lfloor k\rfloor},\textbf{z})=\nu(C+z_{\lfloor
k\rfloor},\textbf{v})+(\nu(C+z_{\lfloor k\rfloor},\textbf{v})-\nu(C+z_{\lfloor
k\rfloor},\textbf{v}))\geq\frac{3\zeta}{4}-\frac{\zeta}{4}=\frac{\zeta}{2}>0$.

Since, $\nu(C+z_{\lfloor k\rfloor},\textbf{z})>0$ and since the second
condition in lemma 1 says that there can be no zero of $\nu(u,\textbf{z})$ in
$u$ with $\nu(u,\textbf{z})$ going from positive to negative beyond
$C+z_{\lfloor k\rfloor}$ we have the largest zero of $\nu(.,\textbf{v})$
should be smaller than $C+z_{\lfloor k\rfloor}$ and thus
$U(\textbf{z})=C+z_{\lfloor k\rfloor}$.

Now observe that $|U(\textbf{z})-U(\textbf{y})|=|(C+z_{\lfloor
k\rfloor})-(C+y_{\lfloor k\rfloor})|\leq\delta\leq\epsilon$, thus proving the
desired statement in (113).

∎