Homotopy with non piece-wise linear boundary

Question

in the middle of a long proof I encounter the following problem.

Let $E$ be a closed and convex set in $\mathbb R^n$ such that for all $\vec x\in E$ it holds that $\sum_ix_i=1$. (We can understand $E$ as a set of probability functions.)

Let $x^\dagger$ be the probability function in $E$ which has maximum Shannon entropy: i.e. $\{x^\dagger\}=\arg\sup_{\vec x\in E}-\sum_{i=1}^nx_i\cdot \log(x_i)$. This function is well-known to be unique. In the case I am interested in, I can assume that $x^\dagger_i>0$ for all $i$.

For all $k\in\mathbb N$ let $c_k(i)$ be an $n$-tuple of numbers such that for all $1\leq i\leq n$ it holds that $\lim_k c_k(i)=\log(x_i)$.

I need to show the following: there exists a sequence $(q_k)_{k\in\mathbb N}$ with $q_k\in E$ such that

1. $q_k \in \arg \sup_{\vec x\in E}-\sum_{i=1}^n x_i c_k(i)$ and
2. $\lim_k q_k = x^\dagger$.

The main problem is that $\arg \sup_{\vec x\in E}-\sum_{i=1}^n x_i c_k(i)$ may contain more than one element.

So, if I replace $E$ by a closed, convex set with an open (i.e. non-empty) interior $U_\epsilon(E)\subset\mathbb R^n$ with a boundary which is nowhere piece-wise linear, then $\arg \sup_{\vec x\in U_\epsilon(E)}-\sum_{i=1}^n x_i c_k(i)$ has a unique solution in $U_\epsilon(E)$. (This is a general fact about linear optimisation problems; or so I hope :))

These maxima will then obtain, in general, not for probability functions. But I think I can handle this.

What I need for my proof is the following: Given a fixed closed and convex set $E$ as above I need to construct sets $U_\epsilon(E)$ such that

1. $U_\epsilon(E)$ is closed,
2. $U_\epsilon(E)$ varies continuously with $\epsilon>0$,
3. the interior of $U_\epsilon(E)$ is open for $\epsilon>0$,
4. $\{(1+\epsilon) x^\dagger\} = \arg \sup_{\vec x\in U_\epsilon(E)} -\sum_{i=1}^n ,x_i\log(x^\dagger_i)$,
5. the boundary of $U_\epsilon(E)$ is nowhere piece-wise linear and
6. $\lim_{\epsilon\rightarrow 0}U_\epsilon(E)=E$.

The last limit is taken over all strictly positive $\epsilon$.

@4: It is well-known that $\{ x^\dagger\} = \arg \sup_{\vec x\in E} -\sum_{i=1}^n ,x_i\log(x^\dagger_i)$.

So, I can simply assume that there exists a homotopy which gives me what I need or do I have to/can I prove the existence of such a homotopy.

All help much appreciated.

Answer 1

I believe I can answer your question for the case where $E=\Delta_n:=\{x\geq 0:\,\,\sum_i x_i = 1\}$ is the standard $n$-dimensional simplex.

My first thought when I saw your question was to consider the level sets of the entropy itself $$ U_{\varepsilon} = \{x\in \Delta_n : \,\, -\sum_{i=1}^n x_i \ln(x_i) > \varepsilon\}.$$ However, these level sets have some piece-wise linear boundaries for $\varepsilon<n-1$ (they start touching the facets of the simplex, see the level curves of $H$ in http://blog.quantitations.com/static/2012-12-10-method-of-types/Q1.png).

For this reason, I tried to use a standard tool from convex analysis: Moreau regularization. I will perturb the function above with a strongly concave one (in fact, the squared distance to the simplex center), so its level sets will not have boundaries with linear pieces anymore, and I will adjust the perturbation parameter to converge to 0 as $\varepsilon\to 0$. So let $$ U_{\varepsilon}=\{x\in \Delta_n : \,-\sum_{i=1}^n x_i \ln(x_i) -\varepsilon \|x-\mathbb{1}/n\|_2^2 > \varepsilon \}, $$ where $\mathbb{1}$ is an $n$-dimensional vector with every component equal to 1. In fact, for the perturbation term you can use any function of $\varepsilon$ that goes to zero as $\varepsilon\to 0$ (I used here $\varepsilon$ just for simplicity).

For $\varepsilon$ small enough the sets $U_{\varepsilon}$ are nonempty and bounded. Since the function we are taking level sets is strongly convex its level sets are 'rounded' (no linear pieces on the boundary) and it converges to the simplex as $\varepsilon\to 0$.

Hopefully you can adapt this construction for arbitrary closed $E$, since the Moreau technique is fairly general.