Questions tagged [subgradient]
This tag is for questions relating to subgradient, an iterative method for solving convex minimization problems, used predominantly in Nondifferentiable optimization for functions that are convex but nondifferentiable. The subgradient method is a very simple algorithm for minimizing convex nondifferentiable functions where newton's method and simple linear programming will not work.
254
questions
1
vote
1
answer
24
views
Prove that any subgradient of the hinge loss function $max\lbrace 0, y\langle\mathbf{w}, \mathbf{x}\rangle\rbrace$ is of the form $\alpha\mathbf{x}$
I tried to prove the following claim,
Let $f(\mathbf{w})=max\{0,1−y\langle\mathbf{w}, \mathbf{x}\rangle\}$, where $y\in\lbrace -1, 1\rbrace$, be a hinge loss function, then any subgradient of $f$ at $...
- 315
1
vote
0
answers
28
views
Subdifferential of $\sqrt{a(x)_+^2 + b(x)_+^2}$ where $a,b$ are convex
Let $a:R^k\to R$ and $b:R^k\to R$ be finite valued convex functions. Let $t_+=\max(0,t)$ be the positive part for any real $t\in R$. Define
$$F(x)=\sqrt{a(x)^2_+ + b(x)^2_+}$$
I am looking for ...
- 1,777
0
votes
1
answer
59
views
Proof that $f(y) \ge f(x) + g^T(y-x)$, for all $y \in U \Rightarrow g \in \partial f(x)$ where U is a open neighborhood of x
Can anyone help me this problem ?
For a convex function f, show that if $x \in U$ where $U$ is a open neighborhood in its domain, then
$f(y) \ge f(x) + g^T(y-x)$, for all $y \in U \Rightarrow g \in \...
- 11
0
votes
0
answers
28
views
Subgradients of piecewise maximum function
For convex functions $g_1, \dots, g_m: (\mathcal{D} \subseteq \mathbb{R}^d) \to \mathbb{R}$,
define $g(\boldsymbol{x}):= \max_{1 \leq i \leq m} g_i (\boldsymbol{x})$. Show that
$$\partial g(\...
4
votes
0
answers
70
views
Is a non-differentiable function Lipschitz continuous if and only if its subgradient is bounded?
It's well known that a differentiale continuous function is Lipschitz if and only if its gradient is bounded. (Is a function Lipschitz if and only if its derivative is bounded?)
Can this result be ...
- 41
1
vote
0
answers
22
views
Subdifferential of a convex function and a continuous mapping
Let $f:\mathbb{R}^n\to\overline{\mathbb{R}}$ be convex and $x^*\in int(dom (f))$. If there exists a mapping $g:int(dom(f))\to \mathbb{R}^n$ satisfying
$g(x)\in\partial f(x)$ for any $x\in int(dom(f))$...
- 13
0
votes
1
answer
59
views
$f$ a real sub linear function, prove that: $\partial f(a)= \left \{ z \in \partial f(0) | z\cdot a = f(a) \right \}$
Question:
Let $f:\mathbb{R}^n\rightarrow \mathbb{R}$ a sub linear function and $ a \in \mathbb{R^n}$. We have to prove that: $\partial f(a)= \left \{ z \in \partial f(0) | z\cdot a = f(a) \right \}$
...
- 1,210
1
vote
2
answers
158
views
Let $A,B,C \subset \mathbb{R}^n$ be convex, bounded and closed set, then $A+C=B+C \Rightarrow A=B$
Here a question and I would like to know if my solution is correct.
I think that it is not needed to use the fact that those sets are convexe, bounded & closed in order to solve the exercice, ...
- 1,210
1
vote
0
answers
64
views
Convex optimization - bound on a subgradient
Consider the following optimization problem:
$$
\min_{b\in \mathbb{R}^d} \sum_{i=1}^n |y_i-x_i^{\top}b|.
$$
A text I'm reading states without a proof that
$$
\left\|\sum_{i=1}^n \operatorname{sgn}(y_i-...
- 710
0
votes
1
answer
42
views
Where does the $\ell_2$ norm subdifferential come from?
Looking at the definition of the subdifferential, we have that $v$ is a subdifferential of a function $f$ at a point $x$ if
$$ f(y) \geq f(x) + g^T(y-x), \forall y$$
Now, for $f(x) = \|x\|_2$, it's ...
- 5
1
vote
1
answer
58
views
If $p$ is bounded and bounded away from $0$, can we find upper and lower bound for $\|\nabla\hat p\|^2+\Delta\hat p$?
Let $d\in\mathbb R^d$ and $p:\mathbb R^d\to(0,\infty)$. Moreover, let $\sigma>0$, $$\tilde p(x):=p(\sigma x)\;\;\;\text{for }x\in\mathbb R^d$$ and $$\hat p:=\frac12\ln\tilde p.$$
Question: Can we ...
- 13.2k
1
vote
2
answers
97
views
The steepest descent direction constrained to non-negative variables
Recently, another user asked about the steepest descent direction constrained to non-negative variables, but using the $L_1$ norm to avoid null directions, see this link. His ideas led to the ...
- 716
0
votes
0
answers
22
views
Relation between the inclusion of a point in a convex hull and inclusion of the subdifferentials of a convex function at that point?
I'm looking to prove a intuitive enough propriety of the subdifferentials of a convex function : let $f : E \to \mathbb{R}$ be a convex function, $n \in \mathbb{N}$ and let $p_1,p_2,\dots,p_n \in E^n$....
- 1
3
votes
1
answer
115
views
Fundamental Theorem of Calculus for non-differentiable convex functions
Suppose $C\subset\mathbb{R}^n$ is a convex set and $f:C\to\mathbb{R}$ is a convex function. I wonder if the following statement is true.
Suppose $g:C\to\mathbb{R}^n$ satisfies $g(x)\in\partial f(x)$ ...
- 667
1
vote
1
answer
60
views
Relation Between Subgradients of a Random Function and Its Expectation
Suppose $\mathcal{X}\subset\mathbb{R}^n$ is a convex set. Let $f:\mathcal{X}\times\mathbb{R}^m\to\mathbb{R}$ be a function such that for every $y\in\mathbb{R}^m$, the function $f(\cdot,y)$ is convex, ...
- 667
1
vote
0
answers
130
views
KKT conditions for non-differentiable constraints
So I know that for the problem:
$$
\begin{align*}
\text{minimize} \quad & f_0(x) \\
\text{subject to} \quad & f_i(x) \leq 0, \quad i = 1, 2, \ldots, m \\
\end{align*}
$$
We have the following ...
- 281
0
votes
0
answers
19
views
Does the subgradient and normal align at the maximum of a convex function?
It is well known that a convex function is minimised over a convex set, if and only if there is a subgradient which is inwards normal to the set at that point. i.e the negative subgradient (direction ...
- 10.2k
1
vote
0
answers
49
views
Subdifferential and affine transformation
I'm having trouble proving this theorem.
$\mathbf{Theorem.}$ Suppose $f:\mathbb R^m\to \mathbb R$ is a convex function and $A\in \mathbb R^{m\times n}, b \in \mathbb R^n$. If we let the mapping $h:\...
- 788
0
votes
0
answers
98
views
Subgradient of the spectral norm
I am working on developing a numerical algorithm that needs to use a subgradient of $\|\cdot\|_2$ (matrix norm) at each iteration. According to Characterization of the Subdifferential of Some Matrix ...
- 1
0
votes
0
answers
30
views
Brezis' Exercise 4.10.4
I'm trying to solve part (3.) of below exercise in Brezis' Functional Analysis, i.e.,
Let $(\Omega, \mathcal F, \mu)$ be a measure space with $\mu(\Omega) < \infty$. Let $p \in [1, \infty)$ and $j:...
- 16.8k
0
votes
0
answers
39
views
Convex positive homogeneous of degree one function and propierties of linearity for minimization problem
I'm studying the algorithm of Nesterov and i'm having problems of some concepts and passages that he make to demostrate. We are considering the problem
$$
min [ F(f(x)) | x \in Q ]
$$
where $Q$ is a ...
0
votes
1
answer
33
views
Show that $\langle y^1 - y^2 , x^1 - x^2 \rangle \geq 0 $
I am trying do this exercise:
Exercise: Let $f : \mathbb{R}^n \rightarrow \mathbb{R}$ a convex funciton. Show that:
$$\langle y^1 - y^2 , x^1 - x^2 \rangle \geq 0, \qquad \forall x^i \in \mathbb{R}^n,...
- 45
0
votes
0
answers
33
views
Optimality check for non-differentiable convex function
I have a doubt on how to check if a given point of a convex, but nondifferentiable, function is a minimum/maximum. For instance, let's say that I have the following function:
$$
f \left( x \right) = ...
1
vote
0
answers
35
views
Subgradient of projection distance function
I want to find subgradient of the function $f({\bf x}) = {\rm inf}_{{\bf y} \in \mathcal{C}} \|{\bf x} - {\bf y}\|_2$, where $\mathcal{C}$ is a closed convex set.
Now, $f$ just measures the ...
3
votes
1
answer
132
views
Boundary Point of Subdifferential as the Limit of a Sequence of Gradients
Let $\Omega\subset\mathbb{R}^n$ be an open convex set. Let $f:\Omega\to\mathbb{R}$ be a convex function. We know that $f$ is differentiable almost everywhere. The subdifferential of $f$ at $x\in\Omega$...
- 667
1
vote
0
answers
80
views
Normal Cone to the Level Sets of a Quasiconvex Function
Let $\mathcal{S}\subset\mathbb{R}^n$ be a nonempty open convex set and let $f:\mathcal{S}\to\mathbb{R}$ be quasiconvex and differentiable on $\mathcal{S}$. Consider the following sets:
$$\tilde{\...
- 33
1
vote
1
answer
68
views
Convexity and continuity imply subdifferentiability
It is well-known that differentiability implies the continuity. I am looking for the converse and found the following result.
Theorem: (Prop 2.36 page 85 [1]) If the convex function $f : X \...
- 1,344
0
votes
1
answer
32
views
Dual Descent and Primal infeasibility (near feasible)?
Suppose one considers a constrained and convex primal optimization problem:
$$P=\max f(x), \text{s.t.}\quad Ax\leq c$$
Consider now its Lagrangian:
$$L=\max f(x)+ \lambda ^T(c-Ax) $$
Suppose we ...
- 351
0
votes
0
answers
273
views
subdifferential and superdifferential
Let $$D^+u(x) = \left\{v \in \mathbb{R}; \limsup_{y\to x}\frac{u(y)-u(x)-v\cdot (y-x)}{|y-x|} \le0\right\}$$ and
$$D^-u(x) = \left\{v \in \mathbb{R}; \liminf_{y\to x}\frac{u(y)-u(x)-v\cdot (y-x)}{|y-x|...
1
vote
0
answers
90
views
Finding subdifferentials of lasso regularizers
Let $\phi: \mathbb{R}^{n}\rightarrow \mathbb{R}$ be a regularizer combining lasso , group lasso, and fused lasso that is given by:
$\phi\left ( x \right ) = \lambda\left \| x \right \|_{1} + \mu\sum_{...
- 21
1
vote
0
answers
79
views
Subdifferentials and optimality conditions of $l$-$0$ minimization
Consider the $l$-$0$ minimization problem: $$\min_{x} f(x) + \lambda \|x\|_0$$ First, prove that $g(x) = \|x\|_0$ is lower semicontinuous and then find the limiting subdifferential $\partial g(x)$ and ...
- 21
1
vote
1
answer
176
views
How to calculate the subgradient of $|Ax+b|$.
I know We have the chain rule if $f(x)=g(Ax)$, then $∂f(x)=A^T∂g(Ax)$. I cannot really understand that. Since if the $f(x) = g(Ax)$, then we have $∂f(x)=A^T∂g(Ax) = A^T∂f(x)$.
For example, we have $f(...
- 13
0
votes
0
answers
300
views
Derivation of subgradient of a matrix's nuclear norm
I was going through the derivation of subgradient of the nuclear norm of a matrix from an old homework of a Convex Optimization course (CMU Convex Optimization Homework 2 - Problem 2).
The setup is ...
0
votes
0
answers
28
views
Subdifferentials of a strictly convex function are disjoint
I'm trying to prove below result which is mentioned in page 24 of Santambrogio's Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Modeling. Could you have a check on my ...
- 5,462
0
votes
1
answer
152
views
Are subgradients bounded on compact subsets of an open set?
Context & Motivation: This is a preliminary question that I wanted to answer in order to generalize the nonconvex projected gradient descent method in Chapter 3 of the book Non-convex Optimization ...
- 21
1
vote
0
answers
20
views
Convergence Rate of Stochastic Gradient Method analysis with more realistic stochastic graident bound
I am reading this Lectur Slides of SGD convergence analysis. In page 3, it says the realistic bound "Just get some extra terms in the result."
I tried to use this bound and derive the result,...
- 27
1
vote
0
answers
61
views
Defining the Subgradient with Polar of the Tagent Cone on the Epigraph, or the Convex Hull
To start, I would like to state both definitions for sub-gradient and where they came from.
Definition 1
Let $f$ be $\mathbb E \mapsto \mathbb {\bar R}$ with $x\in \text{dom}(f)$ then $v\in \mathbb E$...
- 53
1
vote
1
answer
157
views
Subgradient method for nonconvex nonsmooth function
Gradient descent or stochastic gradient descent are frequently used to find stationary points (and in some cases even to local minimum) of a nonconvex function. I was wondering if the same can be said ...
- 53
0
votes
0
answers
147
views
subgradient - subdifferential of spectral norm for a complex matrix
I found the following definition in this answer
$$
\partial f(x) := \{x^* \in X^* \mid f(x') \ge f(x) + \langle x^*, x'-x\rangle\;\forall x' \in X\}
$$
Can I define this $$ \langle A, B\rangle\ = Re(...
- 1
0
votes
0
answers
61
views
Strong convexity definition based on subgradient
Suppose that we have $f: \mathbb R^d \to \mathbb R$ is convex and satisfies
$$f(\textbf y) \geq f(\textbf x) + \nabla f(\textbf x)^\top(\textbf y - \textbf x) + \frac{\mu}{2} \| \textbf x - \textbf y \...
- 409
0
votes
1
answer
73
views
Existence of accelerated subgradient methods
Heavy Ball method and Nesterov's gradient method are two kinds of accelerated versions of gradient methods that achieve optimal convergence for smooth optimization. I wonder whether there is an ...
- 1
0
votes
1
answer
913
views
If a function is convex, then its subgradient set is non-empty
Theorem: A function $f: \textbf{dom}(f) \to \mathbb R$ is convex if and only if $\textbf{dom}(f)$ is convex and $\partial f(\textbf x)$ is not empty for all $\textbf x \in \textbf{dom}(f)$
I know the ...
- 409
1
vote
1
answer
353
views
Convex and Lipschitz implies "bounded" subgradient in Banach spaces
In this question: Lipschitz implies bounded gradient it is shown that if $f: \mathbb{R}^n \to \mathbb{R}^n$ is convex and L-Lipschitz the gradient is bounded by L. I wonder if this holds in Banach ...
- 831
0
votes
0
answers
81
views
Large number of absolute value expressions in constrained, non-convex optimization problem
Say I have a problem given by
\begin{align}
\min_{x\in\mathbb{R}^n} & \ ||g(x)||_1, \\
\text{s.t. } &z_i(x)+||c^{(i)}(x)||_1 \leq d_i, \ i\in\{1,...,N\},
\end{align}
where $g:\mathbb{R}...
- 292
1
vote
0
answers
104
views
Constant step lengths in subgradient method
I was reading these notes (if the previous link doesn't work, use this) on the subgradient method, it says that the choice for step sizes (or step lengths) are determined before the algorithm is run, ...
- 109
0
votes
1
answer
91
views
"Adding" to an inner product
I wanted to get some clarification on a linear algebra operation I've not seen before.
In demonstrating how subgradients are found, a lecuturer did the following:
$$\begin{align} 0 &\geq \langle g,...
0
votes
0
answers
115
views
subdifferential of a convex multivariate function
I want to calculate the subgradient of the following function:
$$f(w, b) = \max \{0, v(w^T u + b)\}+ \rho\|w\|_{l^1}$$
where $u\in \mathbb{R^n}$ and $v\in \mathbb{R}$ are given, $w \in \mathbb{R^n}$ ...
- 1,371
0
votes
0
answers
62
views
compute the subgradient set of $\max(x,0)$ using Danskin
I'd like to compute the subgradient set of $f(x):=\max(x,0)$ using Danskin's theorem, similar to what is done here.
We have
\begin{align}
f(x) = \max(x,0) = \max\{\phi(x,z): z\in Z\}
\end{align}
where ...
- 2,611
1
vote
0
answers
31
views
subdifferential set of nested nonsmooth function
I am trying to compute the subdifferential set of the convex function
\begin{align}
f_n(x_1,x_2,\ldots, x_n) := \max(x_1+\max(x_2 + \cdots + \max(x_n,0),0),\cdots0).
\end{align}
I'm considering for ...
- 2,611
0
votes
1
answer
138
views
least squares with L1 regularization in selected entries
Say for $x \in \mathbb{R}^n$, I'm minimizing $\|Ax - b \|_2^2$ with L1 regularization on selected entries of $x$. i.e. instead of directly add a $\|x\|_1$ regularization term, it would be on $|x_i| + |...
- 255