Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [subgradient]

The tag has no usage guidance.

1
vote
1answer
28 views

When are sublevel sets of convex subdifferentiable functions bounded?

Consider a convex subdifferentiable function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ (meaning that at every point in the domain of $f$, the subdifferential is non-empty). Are there some minor ...
1
vote
0answers
15 views

For non-differentiable functions, does fundamental theorem of calculus give the subgradient?

As we know, if $f:R→R$ is continuous, and $F(x)=\int_0^xf(y)dy$, then $F$ is differentiable and $F'(x)=f(x)$. (Fundamental Theorem of Calculus) Consider the case that $f$ is not continuous, let $F(x)=...
2
votes
0answers
34 views

Is there an equivalence between subgradient and stochastic gradient?

Consider the optimization problem $$\min_x \; f(x) := \sum_{i=1}^m f_i(x).$$ A subgradient method at each iteration takes a subgradeint descent step $$ x^+ = x - \alpha g, \quad g\in \partial f(x)...
0
votes
3answers
69 views

Why do we need sub-gradient methods for non-differentiable functions?

Why do we need sub-gradient methods for non-differentiable functions? Consider optimizing $f(x) = max_{i} (a_{i}^Tx+b_{i})$. Clearly this is non-differentiable at multiple points, and the ...
0
votes
0answers
25 views

Do there exists computational rules for subgradients?

I have a function $f : \mathbb{R^n} \to \mathbb{R}$, which has a subgradient $g$. Now I need the subgradient of $h(x) := (f(x)-a)^2$, where $a$ is a constant. Do there exist an easy way to calculate ...
0
votes
0answers
21 views

Undefined values in subgradient optimization

I saw subgradient optimization of a function $f$ described as the following algorithm: start with any $\lambda^{(0)} \ge 0$ then repeat the following for $i = 1, 2, \dots$ compute a subgradient $g$ ...
1
vote
1answer
35 views

Unbounded Values in Lagrangian Relaxation

I'm trying to learn about Lagrangian relaxation from Korte and Vygen (2018) and found a case where I don't know how to proceed. When optimizing $\max \{c^\top x : A'x \le b', x \in Q\}$ the book ...
0
votes
1answer
38 views

Getting the final solution for the subgradient of function $F(x) := \max \{0, \frac1{2}(x^2 - 1)\}$

I have to find the subgradients of the following function. $$F(x) := \max \left\{0, \frac1{2}(x^2 - 1)\right\}$$ Analytically I can see subdifferentials at $x=-1$ is $\nabla f(-1) \in [-1 ,0] $ and ...
0
votes
0answers
20 views

(Sub)gradient of a function with vector dot products

I am trying to understand the subgradient of a function for a time series, where for each time instance t: $f_t: p \in \Delta_K \mapsto \ell_t(\mathbf{p}\cdot \mathbf{x_t} )\in \mathbb{R}_+ $ the ...
0
votes
1answer
82 views

Sparse group lasso derivation of soft thresholding operator via subgradient equations

In the sparse group lasso paper SGLpaper, they derive a condition for $\beta=0$ from the equation: $$ \frac{1}n {X^{(k)}}^T(y-\sum_{l=1}^m X^{(l)} \beta^{(l)}) = (1-\alpha)\lambda u+ \alpha \lambda v$$...
0
votes
0answers
29 views

About the feasibility of a subgradient step

A vector $v \in \mathbb{R}^d$ is a subgradient of a function $f\colon \mathbb{R}^d \to \mathbb{R}$ in a point $x \in \mathbb{R}^d$ if, for every $y \in \mathbb{R}^d$, $$f(y) \ge f(x) + \langle x - y,...
3
votes
1answer
39 views

Upper bound for the dual norm of a subgradient of a convex function?

Assume $f: \mathbb{R}^n\rightarrow \mathbb{R}$ is a nondifferentiable convex function on $X$. Let represent a subgradient of the function at point $x \in X$ by $x^* \in \partial f(x)$, that is $$ f(y)...
0
votes
1answer
28 views

Gradients in Cartesian and polar.

I have the equation of a curve passing through the origin of Cartesian coordinate system as: $ f(x)= \begin{cases} x,x>0\\ -x,x<0\\ \end{cases} $ Note that we assume $f(x)$ is not defined if $...
0
votes
1answer
56 views

Dual vectors and subgradients

In Candes and Recht (2008)'s paper on matrix completion, there is a statement that is suggested to be from "standard optimization theory:" I am trying to understand the highlighted statement. I will ...
0
votes
1answer
24 views

Why do we need the “subgradient inequality” here?

So, I don't quite know what the "subgradient inequality is". But, we have a function $Q(x)$ which is the optimal objective value of a linear programming problem. So, $Q(x) = \min_y \{ \ c^Ty\ |\ \...
0
votes
0answers
28 views

A sub gradient equation solution

I have the following equation resulted from sub-derivative of a function wrt $\boldsymbol{\beta}$: $$ \lambda\alpha\hat{\mathbf{s}}+\lambda\left(1-\alpha\right) \left(\hat{\boldsymbol{\beta}}-\mathbf{...
2
votes
1answer
59 views

Why is the subgradient not a descent method?

I am reading this nice document about the subgradient method, which defines the subgradient method iteration as follows. $$x^{k+1}=x^k-\alpha_k g^k,$$ for a $g$ such that $$f(y) \geq f(x)+g^T(y-x)...
2
votes
1answer
92 views

A necessary and sufficient condition for optimality of non-smooth convex functions over convex set

Let $f:\mathbb{R}^n\rightarrow \mathbb{R}$ be a convex function and $K\subseteq \mathbb{R}^n$ be a convex set. Consider the problem of minimizing $f(x)$ over $x \in K$. It is well known that, if $f$ ...
1
vote
1answer
27 views

An optimality condition for constrained problems using subgradients

Let $f:\mathbb{R}^n \rightarrow \mathbb{R}$ be a convex function which is not differentiable everywhere and let $K\subseteq \mathbb{R}^n$ be a convex set. Consider the problem of minimizing $f(x)$ ...
1
vote
1answer
34 views

Proving necessity of a condition for minimum of a convex function

Let $f:\mathbb{R}^n \rightarrow \mathbb{R}$ be a convex function and $C \subseteq \mathbb{R}^n$ be a convex set. Consider the problem of minimizing $f(x)$ subject to $x \in C$, and let $x^\star$ ...
0
votes
0answers
39 views

Left and right derivates of a convex function at its minimum

Take a function $$ f: \mathbb R^p \to \mathbb R $$ with the property that all it's partial left-and right derivatives exist everywhere. That is, for all points $x\in \mathbb R,$ and all $j\in\{1,\...
0
votes
0answers
72 views

Calculate the convex conjugate of f(x)?

$$f(x)=\begin{cases} -\frac{5}{2} + 2 |x| & |x|>0\\ -|\frac{x}{2}| & |x|\le0 \end{cases}.$$ How to calculate the conjugate gradient? I found out that I can rewrite it to $max(-\frac{5}{2}...
0
votes
0answers
31 views

Plot and calculate subgradient of f(x)

I want to calculate the subgradient of $$f(x) = \begin{cases} 0& |x|\le 1\\ |x|-1& 1<|x|\le2\\ +\infty& x > 2 \end{cases}$$ but I do not know how to start and want to plot $f(x)...
0
votes
1answer
35 views

What is the subdifferential of the $f(x)$?

$$f(x_1,x_2)=2|x_1|+3|x_2|$$ I did a plot of this function: The subgradient should be on the red peak on the bottom?
0
votes
1answer
82 views

How to show $\partial f(x) =\{\nabla f(x) \}$ for a convex function?

I want to show that if $f:\mathbb{E}\rightarrow\mathbb{R}$ is convex, and differentiable at $x$, then $\partial f(x) = \{ \nabla f(x) \} $ . I understand that for a convex function, we have the ...
0
votes
0answers
120 views

Subdifferential of Pointwise Maximum

Let $f_1,...,f_m$ be convex functions and $x \in \cap_{ 1 \leq i\leq m }int (dom f_{i})$ ,let $h(x) =\max_{ 1 \leq i\leq m } f_{i}$ and $I(x)$ be the set of all $i \in$ {$1 \dots m$} such that $...
0
votes
0answers
49 views

Why is sub-derivative of $\sqrt{|x|}$ at $x=0$ not equal to 1?

The way I learned the definition of a sub-derivative is Sub-derivative: The sub-derivative of f(x) at x is $d f(x)(u) := \lim_{t \downarrow 0, \,\, \hat u \rightarrow u} inf \frac{f(x+tu)-f(x)}{t}$ ...
0
votes
0answers
30 views

Subgradients of parametrized LP

I'm dealing with this problem. Let $\Lambda(y) := \max_{x\in P}c^\top x + y^\top x$ where $P$ is a polytope (a compact polyhedral set). I need to characterize the subgradients of $\Lambda(\tilde{y}...
1
vote
0answers
82 views

why subgradient of convex function is unique

The subgradient has definition of: $$ \partial f(x) = \{g;f(y) \ge f(x)+ g^T(y-x), \forall y \in dom(f) \} $$ My question is, when function f is convex function and differentiable, why it's the ...
1
vote
1answer
105 views

how to prove the affine composition of the subdifferential?

I'm reading the subdifferential definition, which is the set of all subgradients of a function at point $x.$ I have some difficulty in proving this exercise: if $g(x) = f(Ax+b)$ then subdifferential ...
0
votes
0answers
61 views

(sub)gradient of $\ell_1$ norm

I know that $\|\cdot\|_1$ is non-differentiable, but I'm curious about what happens we attempt to use the Frechet definition to get a subgradient $T: \mathbb{R}^n \to \mathbb{R}$. Specifically, ...
5
votes
2answers
315 views

Proximal Mapping of Least Squares with $ {L}_{1} $ and $ {L}_{2} $ Norm Terms Regularization (Similar to Elastic Net)

I was trying to solve $$\min_x \frac{1}{2} \|x - b\|^2_2 + \lambda_1\|x\|_1 + \lambda_2\|x\|_2,$$ where $ b \in \mathbb{R}^n$ is a fixed vector, and $\lambda_1,\lambda_2$ are fixed scalars. Let $f =...
0
votes
1answer
70 views

To find a point in the intersection of convex sets why do we use this as a possible subgradient?

Screenshot of the notes I am going through the notes of Stephen Boyd and I come across this. I cannot understand why is this a subgradient of the said function? Please check the image attached ...
0
votes
1answer
228 views

Why is supporting hyperplane of a sub gradient to epi(f) at (x, f(x)) is defined by (g,−1)?

Supporting Hyperplane Image We have the following definition of a subgradient vector- We say a vector g ∈ $ R^n $ is a subgradient of f : $ R^n $ → R at x ∈ dom(f) if for all z ∈ dom(f,) $f(z) ≥ f(...
0
votes
0answers
41 views

How to work with subdifferentials in convex optimization problems?

I am trying to build a basic algorithm for convex optimization able to work with non-differentiable functions but I have a doubt. Wherever I read it says that basically the idea is working with the ...
0
votes
1answer
55 views

Differential inclusion has unique solution

Given $f: X \to \mathbb{R}$ a strict convex, lower semi-con. function with $X$ reflexive. Show that the inclusion $$l \in\partial f(x) \mbox{ (subgradient of f)}$$ posses an unique solution for ...
0
votes
0answers
45 views

Existence of subgradient for continuous functions

It is known that there exist real valued continuous functions on any open $\Omega\subseteq\mathbb{R}^n$ with no point of differentiability. The same holds for sub/upper differentiability? In books I ...
1
vote
0answers
45 views

subgradient calculus with dual problem

The following function has its origin in multicriteria optimization. ...
2
votes
1answer
56 views

Weakening uniqueness conditions for gradient descent

Let $f : \mathbb{R}^n \to \mathbb{R}$ be a coercive and strictly convex function. I know that if $f \in \mathcal{C}^1$ (i.e., the first derivatives of $f$ are continuous), then for any initial guess ...
0
votes
0answers
82 views

Lagrange dual variable identities

Define the norm-constrained least squares estimator $$\hat{x}_{(c)} = \arg\min_{\|{x}\| \leq c} \|y - A {x}\|_2^2,$$ for $A \in \mathbb{R}^{n \times p}$, the vectors $y$ and ${x}$ conformable, $\|\...
1
vote
0answers
99 views

connection between the $\epsilon$-subdifferential of a Lipschitz convex function at a point, and its subdifferential at close points.

I read by M. Fabian, P. Habala etc., p. 338, lemma 7.13, which is the following. Let $C>0$ and $f$ be a $C$-Lipschitz convex function defined on a nonempty open and convex subset $U$ of a ...
1
vote
1answer
72 views

Directional subderivatives: definition and computation

For a continuous vector field $f$ and some vector $v$ in a Banach space, the (lower) directional subderivative can be defiend as follows: $$ Df_v(x) \triangleq \liminf_{ \substack{ t \rightarrow 0 \\...
1
vote
0answers
52 views

Find subgradiant

Calculate subgradient of the function $f(x)=|x-3|+|x+1|$ at point $x=-1$ and $x=3$. At $x=-1$ for all $y\in R$ following should be satisfied: $|y-3|+|y+1|\ge4+k(y+1)$, where $k$ is subgradient. But ...
0
votes
0answers
52 views

Set of subgradients at the intersection of k hyperplanes

How to find the set of subgradients at the $(n-k)$-dimensional "edge" created by the intersection of $k$ hyperplanes $(k \lt n)$, say: $a_{11}x_1+...+a_{1n}x_n=b_1,\\ a_{21}x_1+...+a_{2n}x_n=b_2,\\......
1
vote
1answer
77 views

subgradient of one-dimensional least absolute difference

I am trying to solve the following one-dimensional least absolute difference (LAD) optimization problem and I am using bisection method to find the best beta (a scalar). I have the following code: <...
2
votes
1answer
352 views

Sum of subgradients belongs to subgradient of sums?

I was going through this page : https://www.stats.ox.ac.uk/~lienart/blog_opti_basics.html , and at the end of part 1 "Subgradient and First-order Optimality Condition", the author says: Before ...
1
vote
0answers
102 views

Finding gradient descent of soft-margin multiclass SVM with different conditions

this is a homework question that I need some help with. PM me or something if you think I should take this question down So I have the objective functionand the loss function of a multi-class svm. I ...
0
votes
2answers
67 views

Consecutive Proximal Projections?

I have a sparse matrix factorization problem, where I want to decompose a matrix $X\in \mathbb{R}^{n\times m}$ to $A\in \mathbb{R}^{n\times p}$ and $B\in \mathbb{R}^{p\times m}$, such that $X\approx ...
0
votes
0answers
274 views

What non-differentiable functions have subgradient?

In general, what non-differentiable functions have subgradient? Which non-differentiable functions do not have subgradient? Does a function have to be convex for subgradient to be defined for that? ...
0
votes
0answers
187 views

What is the definition of subgradient in words?

I am trying to understand the meaning of subgradient precisely. Is the subgradient of a function at point $x$, any linear underestimator of a function that touches the function in only at $x$? Do you ...