13
$\begingroup$

I'm having a bit of difficulty getting my head around the different types of subgradients we're currently covering in a nonsmooth optimisation class I'm taking.

These subgradients are (assume $x \in$ dom$f$):

  • Proximal subgradient: $\partial_p(f(x)) = \{v\ |\ \exists \delta>0,\rho > 0\ s.t.\ f(y) \geq f(x) + \langle v, y-x\rangle - \frac{1}{2}\rho ||y - x||^2\ \forall\ y \in B_\delta(x) \}$
  • regular subgradient: $\{v\ |\ \exists\ \delta > 0\ s.t. f(y) \geq f(x) + \langle v, y-x\rangle + o(||y-x||)\ \forall\ y\in B_\delta(x) \}$
  • limiting subgradient, defined by $\partial^\infty(f(x)) = \{v\ |\ (v, 0) \in N_{epi f}(x, f(x))\}$, where $N_C(x)$ is the limiting normal cone $\limsup_{x'\rightarrow _C x}\hat{N}_C(x)$ and $\hat{N}_C(x)$ is the normal cone to $C$ at $x$, with $v \in \hat{N}_C(x)$ iff $\langle v, y - x\rangle \leq o(||y-x||)\ \forall\ y\in C$

However, I'm having trouble conceptualising these; for instance, playing with the relatively straightforward function

$f(x) = -|x|$

it seems like all three of these subgradients coincide ($x = 0$ has no subgradient, everything else has $\partial f(x) = \nabla f(x)$ since the limiting normal cone coincides with the normal cone and there exists no $\delta$ for which $B_\delta(0)$ does not intersect $f(x)$), but playing with the less straightfoward

$f(x) = \begin{cases}x^2 \sin(1/x) &\text{if }x \not= 0\\0 &\text{if } x = 0\end{cases}$

just leaves me completely utterly lost; I can't see how the difference between a limiting normal cone and a normal cone makes a difference, I'm struggling to derive the proximal subgradient, etc.

If anyone could provide some intuition for these three concepts, preferably while working through the two functions I've been playing with, that would be fantastic!

$\endgroup$
1
  • $\begingroup$ I don't agree that there is no subgradient at 0. On the contrary, I would say that the whole interlval ]-1, 1[ is a subgradient at 0. $\endgroup$ Dec 8, 2016 at 9:19

1 Answer 1

6
$\begingroup$

This might not be a satisfying answer, but this is how I personally deal with this issue (at least in the topic of optimization).

I think these concepts are not made for actually computing them but rather for proofs and theoretical statements.

Let's say you want to study a nonsmooth, nonconvex optimization problem. Usually, you cannot hope to find the global minimum, but only apply some kind of iterative method. But what is this iterative method going to compute? A local minimum? Even in the smooth, nonconvex case this might fail and you can only hope for stationary points (which might turn out to be saddle points).

So what kind of object is your iterative method even supposed to compute? Evidently we need to generalize the concept of first order stationarity. What is the "right" generalization, you might ask. Well this is where the different subdifferentials come into play. Depending on the properties of your objective function (e.g. locally lipschitz or not) and the type of iterative scheme you are using the "right" notion might vary.

  • Do you need good calculus?
  • Do you need the subdifferential to be convex?
  • Do you need to graph of the subdifferential map to be closed? (e.g. Murdukhovich, aka limiting differential)

To be at least a bit more concrete: Consider an iterative scheme to solve a given nonsmooth, nonconvex optimization problem $$ \min_x f(x) $$ that produces a sequence ${(x_n)}$ with $x_n \to \bar{x}$. Let's assume that you can prove that at each iteration there is an object $w_n \in \partial f(x_n)$ that fulfills $ w_n \to 0$. You clearly would like to deduce that $0 \in \partial f(\bar{x})$. For this you would need the closedness of the graph of the map $ x \mapsto \partial f(x)$. Last but not least it would be nice to have a theorem saying that if $x$ is a local minimizer, then it stationary wrt your given subdifferential.

If you can prove all these statements, you know that the iterates of your optimization method converge to "good" points. (And as you can see - we used the concept without actually ever computing it.)

Here a very concrete example showing how you can work with different subdifferential without ever computing them: Assume the problem at hand is $$ \min_x h(x) + g(x) $$ such that $h$ is smooth, but nonconvex and $g$ is nonsmooth, but convex. A possible algorithm, utilizing the proximal operator, would be $$ x_{k+1} = \text{prox}_g (x_k - \nabla h (x_k) ) $$ which is equivalent to $$ x_{k+1} = \text{argmin}_y \left\{ g(y) + \langle \nabla h (x_k), y - x_k \rangle + \frac12 || y - x_k ||^2 \right\}. $$ The function to be minimized in the last expression is a convex function so we can use first order optimality and some calculus of the convex subdifferential, to deduce $$ 0 \in \partial g(x_{k+1}) + \nabla h (x_k) + x_{k+1} - x_k. $$ Thus $$ \nabla h (x_{k+1}) - \nabla h (x_k) + x_k - x_{k+1} \in \partial g(x_{k+1}) + \nabla h (x_{k+1}) . $$ Here is where the magic happens! If you have good calculus for your subdifferential, e.g. the Frechet subdifferential $\partial^F$, then $$ \partial g(x_{k+1}) + \nabla h (x_{k+1}) = \partial^F (g + h) (x_{k+1}). $$ Now you have an expression, namely $\nabla h (x_{k+1}) - \nabla h (x_k) + x_k - x_{k+1}$, for which you can usually deduce convergence to zero, inside your subdifferential. The only things you ever had to compute where regular gradients and and proximal operators. Note however, that proximal operators can usually only be analytically computed for "simple" functions (similar to the subdifferential). In nonsmooth optimization it is therefore assumed that the nonsmoothness comes from a "simple" term (like the absolute value) and one tries to put all the "complicated" parts into the smooth function.

$\endgroup$
3
  • 1
    $\begingroup$ I appreciate this perspective and it seems plausible. But what do you do when you need to implement the optimization method? Is there an explicit gap at that point between practice and theory? Or is it that when you do things purely numerically, the distinction between the definitions disappears? $\endgroup$
    – R Hahn
    Jan 11, 2019 at 20:15
  • 2
    $\begingroup$ short answer to the question what is needed for practical implementation: The proximal operator of the nonsmooth part of the objective function. I also updated my answer to reflect this in more detail. $\endgroup$
    – xel
    Jan 13, 2019 at 11:57
  • $\begingroup$ Fantastic explanation, thanks. $\endgroup$
    – littleO
    Jul 28, 2019 at 18:07

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.