6

I find the following link Gradient of squared distance to a convex set. But I don't understand how prove that the function is convex.

My attempt was use the $$\langle f^{\prime}(y)-f^{\prime}(x), y-x\rangle \geq 0$$ and try use that $\|,\|^{2}$ is convex but I don't know if when set $\|x-P_{D}(x)\|^{2}$ this property continue.

Thanks! in advance.

Zacarias89.
  • 173

2 Answers2

5
  1. Let your ambient space be Banach $X$; if you haven't heard of Banach spaces, this is weaker than assuming (say) $X=\mathbb{R}^n$.
  2. Likewise, call your convex set $K$; since the distance to $K$ is also the distance to $\overline{K}$, we may assume that $K$ is closed.
  3. If $f$ is convex and $g$ is convex and increasing, then $g\circ f$ is also convex. $x\mapsto x^2$ is increasing and convex; it turns out that $d(x,K)$ is too.
  4. The latter claim is easiest to prove without messing around with (a.e.) gradients. Just work from the definition of convexity directly.
  5. The distance to $K$ is $d(x,K)=\inf_{z\in K}{\|x-z\|}$; this infimum is always attained, since the infimand is convex in $z$.
  6. For each $x\in X$, let $z(x)\in K$ minimize $\|x-z(x)\|$. Then for $(\mu,\nu)\in\Delta^1$, \begin{align*} \mu d(x,K)+\nu d(y,K)&=\mu\|x-z(x)\|+\nu\|y-z(y)\| \\ &\geq\|\mu x+\nu y-(\mu z(x)+\nu z(y))\| \end{align*} by triangle inequality.
  7. Since $K$ is convex, $\mu z(x)+\nu z(y)\in K$. Thus \begin{align*} \|\mu x+\nu y-(\mu z(x)+\nu z(y))\|&\geq\inf_{z\in K}{\|\mu x+\nu y-z\|} \\ &=d(\mu x+\nu y,K) \end{align*}
Jacob Manaker
  • 9,937
3

The result is straightforward to prove since $x \mapsto \|x\|^2$ is convex.

Let $s(x) = \inf_{c\in C} \|x-c\|^2$, where $C$ is convex and non empty. Let $\epsilon>0$, choose $x_1,x_2$ and choose $c_1,c_2 \in C$ such that $\|x_k-c_k\|^2 < s(x_k)+ \epsilon$. Let $t \in (0,1)$. \begin{eqnarray} s(tx_1+(1-t)x_2) &\le& \|tx_1+(1-t)x_2 - (tc_1+(1-t)c_2) \|^2 \\ &\le& t \|x_1-c_1\|^2 +(1-t) \|x_2-c_2\|^2 \\ &\le&t s(x_1)+(1-t)s(x_2)+ 2 \epsilon \end{eqnarray} Since $\epsilon>0$ was arbitrary, we have the desired result.

copper.hat
  • 172,524