0
$\begingroup$

I have $f(x)=\max{(5x_1,0)}$ in $\mathbb{R}^ n$ and want to compute the subgradients. Can someone explain me the process of doing this? Thank you!

  • 0
    What's $i$ here?2012-11-04
  • 0
    Sorry, i meant 1 not i.2012-11-04
  • 1
    What is the definition of the subgradients?2012-11-04
  • 0
    subgradient at x are all vectors r with $r*(y- x)+f(x) <= f(y)$ for all y.2012-11-04

1 Answers 1

3

Suppose $f(x) = \max_{1 \leq i \leq p} f_i(x)$, where the functions $f_i$ are convex. Then \begin{equation} \partial f (x) = \textbf{conv} \left(\cup_{i \in I(x)} \partial f_i(x) \right) \end{equation} where $I(x) = \{ i | f_i(x) = f(x) \}$. ("$\textbf{conv}$" means "convex hull". See slide 4-15 entitled "pointwise maximum" in Vandenberghe's 236c notes here. )

So, in your problem... Let $g(x) = x_1$ and $h(x) = 0$, so $f(x) = \max \{g(x),h(x)\}$.

If $x_1 > 0$, then $\partial f(x) = \partial g(x) = \{ \nabla g(x) \} = \{ e_1 \}$, where $e_1 = \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}$.

If $x_1 < 0$, then $\partial f(x) = \partial h(x) = \{ \nabla h(x) \} = \{ 0 \}$.

Finally, if $x_1 = 0$, then \begin{align*} \partial f(x) &= \textbf{conv}\left(\partial g(x) \cup \partial h(x) \right) \\ &= \textbf{conv} \left( \{ \nabla g(x), \nabla h(x) \} \right) \\ &= \textbf{conv} \left( \{ e_1, 0 \} \right) \\ &= \{ \alpha e_1 | 0 \leq \alpha \leq 1 \}. \end{align*}

  • 0
    In my solution I used the following facts: if $G$ is a convex function, then $\partial G(x)$ is convex, so $\textbf{conv}\left(\partial G(x) \right) = \partial G(x)$. Furthermore, if $G$ is differentiable at $x$, then $\partial G(x) = \{ \nabla G(x) \}$.2012-11-04
  • 0
    Why is $\nabla g(x)=e_1?$ And could you maybe help me with this question: http://math.stackexchange.com/questions/548892/non-linear-minimization-problem ? Thank you very much in advance!2013-11-02
  • 0
    @901301 We have $g(x) = x_1$. The components of $\nabla g(x)$ are the partial derivatives of $g$. And you can see that the first partial derivative of $g$ is equal to $1$, and the other partial derivatives are equal to $0$. So $\nabla g(x) = e_1$.2013-11-03
  • 0
    Why is $g(x)\neq 5x_1$? Which would result in $\nabla g(x)= 5e_1$?2013-11-04
  • 0
    @901301 hmm, good question, I'm not sure I even noticed that $5$ there. Might be an error. I'll look at it again later today.2013-11-04