# Moreau-Yosida regularization problem

Let $$F(x)=\min\limits_{y\in \mathbb R^n}\{f(y)+\|x-y\|^2\} ,$$ where $f(y)$ is convex and bounded below. How to show that

1. if $x^*\in \arg \min \{F(x)\}$, then $x^*$ is in the closure of the effective domain of $f$.

2. if $x^*$ is in the relative interior of the effective domain of $f$ and $x^*\in \arg \min \{F(x)\}$, then $x^*\in \arg \min \{f(x)\}$.

-

Here are a few hints and sketches of proofs. If the effective domain of $f$ is empty, then it is trivial, so assume it is nonempty.

For 1, if $x^*$ is not in the closure of the effective domain, then there exists an open ball $B$ containing $x^*$ such that $f(x)=\infty$ for all $x\in B$. Let $y$ be such that $F(x^*)=f(y) + \|x^*-y\|^2$. Note that $y\neq x^*$ as $y$ is in the effective domain of $f$. Then choose $x'\in B$ closer to $y$ than $x^*$. Then

$F(x') \leq f(y) + \|x'-y\|^2 < f(y) + \|x^*-y\|^2 = F(x^*)$

For 2, let $y$ be such that $F(x^*)=f(y)+\|x^*-y\|^2$. Since $F(x^*) \leq F(y) \leq f(y)$ it follows that $y=x^*$. So $F(x^*)=f(x^*)$. Since $\inf F \leq \inf f$, it follows that $x^* \in \arg\min\{f\}$.
Is there an example that a minimizer of $F$ occurring in relative boundary of $dom(f)$ is not a minimizer of $f$? – Sunni Oct 25 '11 at 14:20
Consider $f(x)=x$ for $x>0$ and $f(x)=\infty$ for $x < 0$. Then ${\rm dom}f = (0,\infty)$, but $x^*=0$ minimizes $F$ (if you take $\inf$ instead of $\min$ in your definition of $F$, which I think you should be doing). – Jeff Oct 25 '11 at 15:32