3
$\begingroup$

For example, the convex function $f(t)=e^{-t}$ doesn't achieve its minimum 0 on the real line. In a linear regression with $p$ predictors $X$, the loss function $f(\beta)=||Y-X\beta||^2$ achieves its minimum. But for a penalized objective $g(\beta)= ||Y-X\beta||^2+\lambda\sum_{j=1}^p|\beta_j|$ with $\lambda > 0$, does $g(\beta)$ achieve its minimum? How do I prove/disprove this in general?

$\endgroup$
8
$\begingroup$

TL;DR: The property you are looking for is coercivity. This is satisfied for the example in your question (as are properties 1 and 3 below), and hence yes, the penalized objective attains its minimum.


The classical proof of existence of minimizers of (a very general class of) functionals is the so-called direct method of the calculus of variations (originally due to Hilbert and developed in its current form by Tonelli). For the sake of completeness, I give the full version in infinite-dimensional spaces, but you can ignore the fine details if you are only interested in finite-dimensional problems. If you are interested in the full details, I have a set of lecture notes on nonsmooth optimization at https://arxiv.org/abs/1708.04180. (Not that this is the best reference; it's just that I know it's in there.)

Let $X$ be a reflexive Banach space (in particular, $\mathbb{R^N}$) and $F:X\to \mathbb{R}\cup \{+\infty\}$ (this allows including hard constraints into the functional). If $F$ is

  1. proper (meaning that it is not equal to $\infty$ everywhere),

  2. coercive (meaning $\|x\|\to\infty$ implies $F(x)\to \infty$), and

  3. weakly lower semicontinuous (meaning if $x_n \to x$ weakly, then $F(x)\leq \liminf_{n\to\infty} F(x_n)$),

then the minimum of $F$ over $X$ is attained in some $\bar x\in X$ (for which $F(\bar x)<\infty$).

The proof is fairly simple and uses these properties in a straightforward way:

  1. Since $F$ is proper, the set $\{F(x):x\in X\}\subset\mathbb{R}$ attains an infimum $M:=\inf_{x\in X} F(x)<\infty$ (although $M=-\infty$ may be possible). By the definition of the infimum, there exists a sequence $\{x_n\}_{n\in\mathbb{N}}\subset X$ with $$ F(x_n) \to M = \inf_{x\in X} F(x). $$ Such a sequence is called minimizing sequence. Note that from the convergence of $\{F(x_n)\}_{n\in\mathbb{N}}$ we cannot conclude the convergence of $\{x_n\}_{n\in\mathbb{N}}$ (yet).

  2. Suppose now that $\{x_n\}_{n\in\mathbb{N}}$ were unbounded, i.e., that $\|{x_n}\|_X\to\infty$ for $n\to \infty$. The coercivity of $F$ then implies that $F(x_n)\to \infty$ as well, in contradiction to $F(x_n)\to M<\infty$ by definition of the minimizing sequence. Hence, the sequence is bounded and thus contains a weakly (in finite-dimensional spaces, strongly) converging subsequence $\{x_{n_k}\}_{k\in\mathbb{N}}$ with limit $\bar x\in X$. (This limit is a candidate for the minimizer.)

  3. From the definition of the minimizing sequence, we also have $F(x_{n_k})\to M$ for $k\to\infty$. Together with the weak lower semicontinuity of $F$ and the definition of the infimum we thus obtain \begin{equation*} \inf_{x\in X} F(x) \leq F(\bar x) \leq \liminf_{k\to\infty} F(x_{n_k}) = M = \inf_{x\in X} F(x)<\infty. \end{equation*} This implies that $F(\bar x)<\infty$ and that $\inf_{x\in X} F(x)=F(\bar x)> -\infty$. Hence, the infimum is attained in $\bar x$ which is therefore the desired minimizer.

Note how these three properties serve to exclude the obvious counterexamples:

  1. excludes the obviously degenerate case that there's nothing to minimize over and is clearly satisfied for any real-valued functional;

  2. excludes exactly your counterexample $f$; for $g$, you have $$g(\beta) = \|{Y-X\beta}\|_2^2 + \lambda \|\beta\|_1 \geq C\|\beta\|_1,$$ and hence the penalized objective is indeed coercive.

  3. excludes functions such as $$f(t) = \begin{cases} t^2+1 & t\leq 0 \\ t^2 & t>0 \end{cases} $$ for which the infimum is $0$, but this is not attained for any $t\in \mathbb{R}$. In $\mathbb{R}^N$, you don't need to worry about the difference of weak and strong convergence; in particular, the property is satisfied for any continuous $F$ (such as all your examples).

Note that convexity didn't play any role here; what this buys you is that any minimizer is a global minimizer (which is unique if the function is strictly convex). Also, convex functions are weakly lower semicontinuous if they are strongly lower semicontinuous even in infinite-dimensional spaces, where the former is a stronger property than the latter.

$\endgroup$
  • $\begingroup$ Very interesting to learn this. Do you mean $F$ has to maintain properties 1-3 or at least one of three? $f$ satisfies property 3 but it doesn't attain its minimum as you implied. A proof will be helpful and a reference for studying will be appreciated as well. $\endgroup$ – John Smith May 9 '18 at 10:55
  • 1
    $\begingroup$ Yes, all three properties are necessary as the examples show. I've included the proof and (shameless plug) a link to my lecture notes where this topic is treated in detail. $\endgroup$ – Christian Clason May 9 '18 at 11:14
  • $\begingroup$ Very grateful for the detailed answer. $\endgroup$ – John Smith May 9 '18 at 11:32
  • 1
    $\begingroup$ @JohnSmith Yes, that was a typo (as was $\mathbb{R^N}$), which I've just corrected -- thanks! And yes, $X$ is closed -- that is included in the assumption that $X$ is a Banach space. And $\mathbb{R}^N$ is indeed closed (as well as open), it's just not bounded -- but that is not necessary if $F$ is coercive. (Note that any hard constraint $x\in C \subsetneq X$ is included in $F$ by setting the value to $\infty$ outside $C$ -- if $C$ is bounded, $F$ is automatically coercive. If $C$ is weakly closed (or convex and closed), $F$ is also weakly lower semicontinuous.) $\endgroup$ – Christian Clason May 10 '18 at 7:39
  • 1
    $\begingroup$ You'd have to argue as follows: First argue that $\min_{\beta \in \mathbb{R}^n} f(\beta) = \min_{\beta \in \mathrm{ker} X^{\bot}} f(\beta)$, where $\mathrm{ker} X^{\bot}$ is the orthogonal complement of the kernel. Since $\mathrm{ker} X^{\bot}$ is closed, then you can apply the theorem to this new formulation, where $f(\beta)$ is coercive (by construction). $\endgroup$ – Christian Clason Jun 13 '18 at 15:24
0
$\begingroup$

The only thing you can in general say about convex optimisation problems is: If there is a local minimum, this is the global minimum.

It can be relaxed to: If the function has a stationary point, and is convex, this stationary point is a global minimum. Stationary points $\beta^*$ are such that fulfill $\nabla f(\beta^*) =0$. Your function is a sum of two convex functions, which makes it convex. Your function is non-differentiable in $0$. However, it may still have a stationary point $\beta^*$ that is not $0$. If you find such a stationary point, you are done.

In your case, we have $$g(\beta)= \|Y-X\beta\|^2+\lambda\sum_{j=1}^p|\beta_j|,$$ this implies $\nabla g(\beta) = -2(Y-X\beta)X + \nabla h(\beta)$, where the $h(\beta) = \lambda\sum_{j=1}^p|\beta_j|$ and $$ (\nabla h(\beta))_j = \begin{cases}\lambda, &\beta_j \geq 0 \\ -\lambda, &\beta_j < 0\end{cases}. $$ Now you "just" have to find $\beta^*$, which may be easier with a semi-smooth Newton method.

$\endgroup$
  • $\begingroup$ this does not quite answer the OP's question because you a priori assume the existence of a local minimizer $\beta$ (a proof that such a $\beta$ exists is what the OP is asking for) $\endgroup$ – GoHokies May 9 '18 at 11:34
  • $\begingroup$ I don’t. I clarified that. I assume that the function is convex, which I argue, and give steps to check whether it has a stationary points - which is has or hasn’t, depending on the actual parameters. $\endgroup$ – Jonas May 9 '18 at 12:00
  • 2
    $\begingroup$ @jonas But you want to have $\beta_j^*=0$ for as many $j$ as possible (while still matching $Y$ sufficiently well) -- that is the whole point of using this penalty term! And you haven't actually given a way to check a priori that a stationary point exists. (Running a numerical algorithm is not a suitable way, since you have no guarantee that it'll work in practice -- in fact, most convergence proofs assume the existence of a stationary point to show that it convergences to that. If you try to compute something that doesn't exist, you can expect it to blow up in your face...) $\endgroup$ – Christian Clason May 10 '18 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.