condition for strongly convex function

Question

Given a convex set $C$. The distance function is defined for any $C$ as $$ \textrm{dist}_{C} \left( x \right) = \inf\limits_{z \in C} \left\lVert x - z \right\rVert . $$ Then the function $$ d \left( x \right) = \dfrac{1}{2} \left[ \textrm{dist}_{C} \left( x \right) \right] ^{2} . $$ is convex and continuously differentiable.

My question is can we impose some condition on $C$ so that the function $d$ is not only convex but strongly convex?

Answer 1

The function $d$ is locally strongly convex on the complement of $C$, provided that $C$ satisfies the following condition:

For every point $x\in \partial C$ there is a closed ball $B$ such that $C\subset B$ and $x\in \partial B$.

Uniformity of radius is not required, because we are not going to have a uniform constant of strong convexity anyway: it generates near $C$. In this post, "locally strongly convex" means: for every point $x\in\mathbb{R}^n\setminus C$ there exist a neighborhood $U$ and a constant $\lambda>0$ such that $d(x)-\lambda \|x\|^2$ is convex in $U$. The constant $\lambda$ may depend on $x$.

Proof: Fix $x_0\in \mathbb{R}^n\setminus C$. Let $y\in C$ be the closest point of $C$ to $x_0$. By assumption there is a ball $B$ as above; let $R$ be its radius. Also let $r=\frac12 \operatorname{dist}(x,C)$ and $U=\{z:\|z-x_0\|<r\}$.

Let $\rho(x) = (\operatorname{dist}(x, B))^2$. Without loss of generality $B$ is centered at $0$, so we can write $$\rho(x) = (\|x\|-R)^2 = \|x\|^2 - 2R\|x\| + R^2$$ Using a known formula for the Hessian of $\|x\|$, see this post, we get $$ D^2 \rho(x) = 2I - 2R\frac{\|x\|^2I - x\otimes x}{\|x\|^3} = 2\left(1-\frac{R}{\|x||} \right)I + 2R \frac{x\otimes x}{\|x\|^3} $$ The term with $x\otimes x$ is positive semidefinite. The coefficient $1-R/\|x\|$ is at least $1-R/(R-r)= r/(R+r)$ within $U$. Thus, the function $\rho$ is strongly convex in $U$ with $\lambda = r/(R+r)$.

Since $d(x_0)=\rho(x_0)$ and $d(x)\ge \rho(x)$ everywhere, we conclude that $$ d(x) \ge d(x_0) + \langle \nabla \rho(x_0), x-x_0\rangle + \lambda \|x-x_0\|^2 $$ for $x$ in $U$, which proves strong convexity (it shows that $d(x)-\lambda\|x\|^2$ has a supporting hyperplane at every point).

Answer 2

Your $d$ is strongly convex if and only if $C$ is a singleton.

The “if” part is trivial. For the “only if” part, consider a convex set $C$ which is not a singleton, and take two distinct points $a, b \in C$ to show that $d$ violates the definition of strong convexity (hint: use the fact that $d(a)=d(b)=0$, just like for any convex combination of $a$ and $b$).