Vtyjkyuk

I have a lower semi-continuous (l.s.c) extended-valued function $f: mathbbR^3 to mathbbR cup +infty$. I know the following properties:

• $operatornamedom(f)$ is compact, and we have its bounding box $B$,


• $f$ is bounded,


• $f$ is piecewise-continuous - there exists a finite partition $operatornamedom(f) = bigcup_i=1^m D_i$ such that $f$ is continuous on each $D_i$, and $operatornamecl(D_i) = operatornamecl (operatornameint (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 mathbbN $ of extended-valued functions, denoted by $f = operatornameepi-lim_nu to infty f_nu$, if

• for any sequence $ mathbfx_nu : nu in mathbbN$ convering to $mathbfx$, we have $liminf_nu to infty f_nu(mathbfx_nu) geq f(mathbfx)$, and,


• there exists is a sequence $ mathbfx_nu : nu in mathbfN $ converging to $mathbfx$ such that $limsup_nu to infty f_nu(mathbfx_nu) leq f(mathbfx)$.

The proof that $operatornameepi-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 $operatornameepi-lim$ hold.

1. 
   

   Let $ mathbfx_nu : nu in mathbbN $ be a sequence converging to $mathbfx$.

   
   
   

   Suppose that $mathbfx notin B$. Then, for some $nu_0$ we have $mathbfx_nu notin B$ for all $nu geq nu_0$, meaning that $f_nu(mathbfx_nu) = +infty$ for all $nu geq nu_0$. Thus, in this case,
   $$liminf_nu to infty f_nu(mathbfx_nu) = +infty geq f(x_nu).$$

   
   
   

   Suppose that $mathbfx in B$, and let $ nu_k $ be the sequence of indices satisfying $mathbfx_nu_k in B$. If the sequence above is finite, then
   $$liminf_nu to infty f_nu(mathbfx_nu) = +infty geq f(mathbfx).$$
   If the sequence above is infinite, let $mathbfy_k$ be the nearest neighbor of $mathbfx_nu_k$ satisfying $f(mathbfy_k) = f_nu(mathbfx_nu_k)$. Since $|mathbfx_nu_k - mathbfy_k| leq frac12nu$ and $mathbfnu_k to mathbfx$, we have $mathbfy_k to mathbfx$. Combining with the closedness of $f$ we obtain,
   $$
   liminf_nu to infty f_nu(mathbfx_nu) = liminf_k to infty f_nu_k(mathbfx_nu_k) = liminf_k to infty f(mathbfy_k) geq f(mathbfx).
   $$

   
   
   

   In all cases, we obtained
   $$
   liminf_nu to infty f_nu(mathbfx_nu) geq f(mathbfx).
   $$

   
   


2. 
   

   Let $mathbfx in mathbbR^3$.

   
   
   

   Suppose that $mathbfx notin B$. Take the sequence $mathbfx_nu = mathbfx$, which clearly converges to $mathbfx$. By definition of $f_nu$, we have $f_nu(mathbfx_nu) = +infty$, and hence
   $$
   limsup_nu to infty f_nu(mathbfx) = +infty = f(mathbfx).
   $$

   
   
   

   Suppose that $mathbfx in B$. We have three cases:

   
   
   

   • Suppose that $x notin operatornamedom(f)$. Take $mathbfx_nu$ be the nearest neighbor of $mathbfx$ selected when evaluating $f_nu(mathbfx)$. Since $operatornamedom(f)$ is closed $mathbbR^3 setminus operatornamedom(f)$ is open, and there is a neighborhood (ball) $U$ of $mathbfx$ such that $U cap operatornamedom(f) = emptyset$. On the other hand, there exists $nu_0$ such that for all $nu geq nu_0$ we have $mathbfy_nu in U$, and therefore for all $nu geq nu_0$ we have $f_nu(mathbfx_nu) = f(mathbfx_nu) = +infty$. Hence,
     $$
     limsup_nu to infty f_nu(mathbfx_nu) = +infty = f(mathbfx).
     $$

   
   

   • Suppose that $mathbfx in operatornamedom(f)$, and let $U(r) = mathbfy : $. Since the sets $D_1, dots, D_n$ form a partition of $operatornamedom(f)$, there is a unique $j$ for which $mathbfx in D_j$, and hence $mathbfx in operatornamecl(D_j)$. Since $operatornamecl(D_j) = operatornamecl(operatornameint(D_j))$, there exists $nu_0$ such that for all $nu geq nu_0$ we have $U_nu equiv U(1/nu) cap operatornameint(D_j) neq emptyset$. Since $U_nu$ is open, there exists $k_nu$ such that there is a grid point $mathbfy_nu$ in the grid of density $k_nu$ which is also in $U_nu$, meaning that $mathbfy_nu in operatornameint(D_j)$. For any $nu < nu_0$, let $mathbfy_nu = mathbfy_nu_0$. By construction, $|mathbfx - mathbfy_nu| < frac1nu$ for all $nu geq nu_0$, and hence the sequence $mathbfy_nu : nu in mathbbN $ converges to $mathbfx$. By continuity of $f$ on $D_j$, we have
     $$
     limsup_nu to inftyf_nu(mathbfy_nu) = limsup_nu to inftyf(mathbfy_nu) = f(mathbfx).
     $$