Why does $f:\mathbb{R}^n\rightarrow\mathbb{R}\cup\{\infty\}$ closed, proper, convex imply that $f(x)+\|Ax-b\|^2$ attains a minimum?

Question

I'm currently reading the paper "Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers" by Boyd et al. about the alternating direction method of multipliers (ADMM). There, optimization problems of the form $$ \min_x f(x)+\frac{\rho}{2}\|Ax+Bz-c+u\|^2 $$ are considered, where $f:\mathbb{R}^n\rightarrow\mathbb{R}\cup\{\infty\}$ is closed, proper, and convex, $\rho>0$, $A,B\neq0$ are fixed matrices, and $z,c,u$ are fixed vectors. These optimization problems arise as part of the ADMM. On page 16 of the manuscript the claim is made that, without further assumptions on $A$ and $B$, the above problem is solvable, i.e., a minimum exists/is attained. Unfortunately, no proof or reference is given. I've been trying to understand why that claim holds. In the hopes of being able to adapt an existing proof I've searched for results showing that the proximal operator $$ \mathrm{prox}_f(y)=\arg\min_x f(x)+\|x-y\|^2 $$ (note that this is a set) is nonempty under the given conditions. However, adapting any of the proofs that I could find would require that:

• $f(x)+\frac{\rho}{2}\|Ax+Bz-c+u\|^2$ is strictly or strongly convex, which as far as I understand, can only be achieved by either requiring A to have full-column rank or by requiring $f$ to be strictly/strongly convex. References: „First Order Methods in Optimization“, 2017, A. Beck, Thm. 6.3, Thm. 5.25(a) and „Parallel and Distributed Computation: Numerical Methods“, 1989, D. Bertsekas, Prop. 4.1
• $f(x)+\frac{\rho}{2}\|Ax+Bz-c+u\|^2$ is coercive, i.e., $\lim_{\|x\|\rightarrow\infty}f(x)+\frac{\rho}{2}\|Ax+Bz-c+u\|^2=\infty$, which as far as I can tell, is only possible if $A$ has full column rank or if $f$ is coercive. References: „First Order Methods in Optimization“, 2017, A. Beck, Thm. 6.4, Thm. 2.14

Am I missing something? Can anyone provide an insight on how the claim may be proved using only the assumptions ($f$ closed, proper, convex) made in the paper?

Answer 1

It doesn't. In this paper https://arxiv.org/abs/1507.02051 they construct a very easy counter example, and deduce sufficient conditions.

Answer 2

A simple counter-example is the choice $n=1$, $A=0$, and $f(x)=e^x$. The example can be modified to allow $n>1$ and $A\ne0$.

You are right, some assumption is missing: the resulting functional needs to be coercive to guarantee existence of solutions.