I have a lower semi-continuous (l.s.c) extended-valued function $f: \mathbb{R}^3 \to \mathbb{R} \cup \{+\infty\}$. I know the following properties:
- $\operatorname{dom}(f)$ is compact, and we have its bounding box $B$,
- $f$ is bounded,
- $f$ is piecewise-continuous - there exists a finite partition $\operatorname{dom}(f) = \bigcup_{i=1}^m D_i$ such that $f$ is continuous on each $D_i$, and $\operatorname{cl}(D_i) = \operatorname{cl} (\operatorname{int} (D_i))$.
For my purposes, I would like to approximate $f$ by partitioning $B$ into a regular grid of $\nu$ points along each axis, and defining my approximation $f_\nu$ to be constant in each grid box.
My objective is to obtain convergence of $f_\nu$ to $f$ in some sense. My best-case scenario is having epi-graphical convergence, since I want to use the approximation in an optimization context.
My question is: what value should my approximation have in each grid cell? I tried the function value at the center of each cell, but I was not able to prove epigraphical convergence.
Restrictions:
- Computationally, I have an oracle which can evaluate $f$ at any given point. In particular, it is not possible to compute the infimum of $f$ on each grid cell. Just evaluate it at a finite number of points.
- I do not have any information about the discontinuity set, except for the knowledge that the finite partition above exists.
Update I posted a proof, which is hopefully correct. Answers providing a simpler proof, or a reference to an existing article which already shows such a result are very welcome, and will receive the bounty.
It turns out that the idea of the function value at the center of the box is OK, and I was able to prove epi-convergence, as defined below.
The extended-valued function $f$ is the epigraphical limit of the sequence $\{f_\nu : \nu \in \mathbb{N} \}$ of extended-valued functions, denoted by $f = \operatorname{epi-lim}_{\nu \to \infty} f_\nu$, if
The proof that $\operatorname{epi-lim}_{\nu \to \infty} f_\nu = f$ follows from the fact that such an approximation is actually a nearest-neighbor interpolant of $f$ on the grid centers in $\ell_\infty$ norm, and here it is. Hopefully, there are no errors.
Proof
We show the result by showing that both parts of the definition of $\operatorname{epi-lim}$ hold.
Let $\{ \mathbf{x}_\nu : \nu \in \mathbb{N} \}$ be a sequence converging to $\mathbf{x}$.
Suppose that $\mathbf{x} \notin B$. Then, for some $\nu_0$ we have $\mathbf{x}_\nu \notin B$ for all $\nu \geq \nu_0$, meaning that $f_\nu(\mathbf{x}_\nu) = +\infty$ for all $\nu \geq \nu_0$. Thus, in this case, $$\liminf_{\nu \to \infty} f_\nu(\mathbf{x}_\nu) = +\infty \geq f(x_\nu).$$
Suppose that $\mathbf{x} \in B$, and let $\{ \nu_k \}$ be the sequence of indices satisfying $\mathbf{x}_{\nu_k} \in B$. If the sequence above is finite, then $$\liminf_{\nu \to \infty} f_\nu(\mathbf{x}_\nu) = +\infty \geq f(\mathbf{x}).$$ If the sequence above is infinite, let $\mathbf{y}_k$ be the nearest neighbor of $\mathbf{x}_{\nu_k}$ satisfying $f(\mathbf{y}_k) = f_\nu(\mathbf{x}_{\nu_k})$. Since $\|\mathbf{x}_{\nu_k} - \mathbf{y}_k\| \leq \frac{1}{2\nu}$ and $\mathbf{\nu_k} \to \mathbf{x}$, we have $\mathbf{y}_k \to \mathbf{x}$. Combining with the closedness of $f$ we obtain, $$ \liminf_{\nu \to \infty} f_\nu(\mathbf{x}_{\nu}) = \liminf_{k \to \infty} f_{\nu_k}(\mathbf{x}_{\nu_k}) = \liminf_{k \to \infty} f(\mathbf{y}_k) \geq f(\mathbf{x}). $$
In all cases, we obtained $$ \liminf_{\nu \to \infty} f_\nu(\mathbf{x}_{\nu}) \geq f(\mathbf{x}). $$
Let $\mathbf{x} \in \mathbb{R}^3$.
Suppose that $\mathbf{x} \notin B$. Take the sequence $\mathbf{x}_\nu = \mathbf{x}$, which clearly converges to $\mathbf{x}$. By definition of $f_\nu$, we have $f_\nu(\mathbf{x}_\nu) = +\infty$, and hence $$ \limsup_{\nu \to \infty} f_\nu(\mathbf{x}) = +\infty = f(\mathbf{x}). $$
Suppose that $\mathbf{x} \in B$. We have three cases:
Suppose that $x \notin \operatorname{dom}(f)$. Take $\mathbf{x}_\nu$ be the nearest neighbor of $\mathbf{x}$ selected when evaluating $f_\nu(\mathbf{x})$. Since $\operatorname{dom}(f)$ is closed $\mathbb{R}^3 \setminus \operatorname{dom}(f)$ is open, and there is a neighborhood (ball) $U$ of $\mathbf{x}$ such that $U \cap \operatorname{dom}(f) = \emptyset$. On the other hand, there exists $\nu_0$ such that for all $\nu \geq \nu_0$ we have $\mathbf{y}_\nu \in U$, and therefore for all $\nu \geq \nu_0$ we have $f_\nu(\mathbf{x}_\nu) = f(\mathbf{x}_\nu) = +\infty$. Hence, $$ \limsup_{\nu \to \infty} f_\nu(\mathbf{x}_\nu) = +\infty = f(\mathbf{x}). $$
Suppose that $\mathbf{x} \in \operatorname{dom}(f)$, and let $U(r) = \{ \mathbf{y} : \|\mathbf{y} - \mathbf{x}\| < r \}$. Since the sets $D_1, \dots, D_n$ form a partition of $\operatorname{dom}(f)$, there is a unique $j$ for which $\mathbf{x} \in D_j$, and hence $\mathbf{x} \in \operatorname{cl}(D_j)$. Since $\operatorname{cl}(D_j) = \operatorname{cl}(\operatorname{int}(D_j))$, there exists $\nu_0$ such that for all $\nu \geq \nu_0$ we have $U_\nu \equiv U(1/\nu) \cap \operatorname{int}(D_j) \neq \emptyset$. Since $U_\nu$ is open, there exists $k_\nu$ such that there is a grid point $\mathbf{y}_{\nu}$ in the grid of density $k_\nu$ which is also in $U_\nu$, meaning that $\mathbf{y}_\nu \in \operatorname{int}(D_j)$. For any $\nu < \nu_0$, let $\mathbf{y}_\nu = \mathbf{y}_{\nu_0}$. By construction, $\|\mathbf{x} - \mathbf{y}_\nu\| < \frac{1}{\nu}$ for all $\nu \geq \nu_0$, and hence the sequence $\{\mathbf{y}_\nu : \nu \in \mathbb{N} \}$ converges to $\mathbf{x}$. By continuity of $f$ on $D_j$, we have $$ \limsup_{\nu \to \infty}f_\nu(\mathbf{y}_\nu) = \limsup_{\nu \to \infty}f(\mathbf{y}_\nu) = f(\mathbf{x}). $$