The subgradient at $x\in\mathbb{R}^n$ of a convex function $f:\mathbb{R}^n\to\mathbb{R}$ is any vector $g\in \mathbb{R}^n$ such that $$f(y)\geq f(x) + g^T(y-x) \qquad\forall y \in \mathbb{R}^n.$$I have some problem about showing that $$\frac{\partial f}{\partial d}:=lim_{t\to0}\frac{f(x+td)-f(x)}{t}=max\{g^Td\,|\,g\, \text{is a subgradient}\}$$

  • $\begingroup$ Let $g\in\partial f (x)$. Then, $$f(x+td) \geq f(x) + \langle g, x+td-x\rangle = f(x) + \langle g,td\rangle\\ \implies \frac{f(x+td) - f(x)}{t} = \langle g,d\rangle$$ $\endgroup$
    – TSF
    Nov 23 '20 at 17:35
  • $\begingroup$ I did the same things but by this i show that the directional derivate is greater or equal than max $g^Td$. I don't understand why you can deduce that is equal, can you explain it to me? $\endgroup$
    – Antonio B
    Nov 23 '20 at 17:49
  • 1
    $\begingroup$ It's a mistake, I meant to write $\geq$ indeed as you noticed. It was meant as a hint, that's why I didn't put it as an answer. $\endgroup$
    – TSF
    Nov 23 '20 at 18:01

When you refer to a subgradient, you should say at which point otherwise it doesn't make sense. Thus, all "subgradient" instances in your question should be replaced by "subgradient at $x$".

Let me use the standard notation $f'(x; d)$ to denote the directional derivative of $f$ at $x$ in direction $d$: \begin{equation} f'(x; d) = \lim_{t\to 0^+} \frac{f(x+td) - f(x)}{t}. \end{equation} We need to prove that \begin{equation} f'(x; d) = \max_{g\in \partial f(x)} g^T d \quad\forall x,d\in\mathbb{R^n}. \end{equation} This is a standard result in convex analysis and proofs can be found in any books on the topic. My proof below may be slightly different than those, in which I explicitly provide the subset of maximum solutions.

First, notice that \begin{equation} f(x+td) - f(x) \ge g^T(x+td-x) = tg^Td \quad \forall g\in\partial f(x), \forall x,d,t, \end{equation} we obtain \begin{equation} \boxed{f'(x; d) \ge g^T d \quad\forall g\in\partial f(x),\forall x,d.}\tag{*} \end{equation} We can prove the reverse inequality, or alternatively show that there exists $g\in\partial f(x)$ such that equality holds. To this end, we need some fundamental properties of directional derivatives:

  1. $f(y) \ge f(x) + f'(x;y-x) \quad\forall x,y$.

  2. The function $h(u) = f'(x;u)$ is convex and homogeneous of degree 1.

Both can be proved easily using the definition of $f(x;u)$ and the convexity of $f$.

Since $h(u)$ is convex, we have $h(u)\neq\emptyset$ and thus $$h(v) - h(u) \ge g^T(v-u)\quad \forall v,\forall g\in\partial h(u).$$ If we choose $v=tu$ for some $t$, then $h(v) = h(tu) = th(u)$ and we obtain $$(t-1)h(u) \ge (t-1)g^Tu.$$ Because the above holds for any $t$, we must have $h(u) = g^Tu$. Hence, we have proved that \begin{equation} \boxed{h(u) = g^Tu \quad\forall g\in\partial h(u), \forall u.}\tag{**} \end{equation} Using this equality and the above first property of directional derivatives, we get $$f(y) \ge f(x) + f'(x;y-x) = f(x) + h(y-x) = f(x) + g^T(y-x) \quad \forall g\in\partial h(y-x), \forall y,$$ which implies $\partial h(y-x) \subset \partial f(x)\ \forall y$, or equivalently $\partial h(u) \subset \partial f(x)\ \forall u$. Therefore, we see that in $(*)$, equality occurs for any $g$ in the nonempty subset $\partial h(d)$ of $\partial f(x)$. QED


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.