Skip to main content

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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
23 views

How to conduct error analysis for gradient descent with a function not differentiable everywhere

I am trying to bound the error of a method which uses gradient descent on a function which has the term $\lVert Ax - b \rVert$. The analytical solution of the derivative of $\lVert Ax - b \rVert$ is $\...
beanbanx's user avatar
2 votes
1 answer
61 views

Chain rule for Clarke-derivatives

The Clarke-gradient is often introduced to extend ideas from convex analysis to non-convex functions, see [Clarke, Sec 2.1]. In particular, given $f:\mathbb{R}^n\rightarrow \mathbb{R}$ Lipschitz in $x$...
Bazinga's user avatar
  • 183
0 votes
0 answers
24 views

Connection between minimal norm subgradient and steepest descent

In my optimization course it was mentioned that for a non-smooth convex function, the subgradient with smallest norm provides the direction of steepest descent of the function, so if $f: \mathbb{R}^n \...
Len's user avatar
  • 123
0 votes
1 answer
43 views

Clarke regularity of piecewise linear functions

Let $f:X\rightarrow\mathbb{R}$, with $X\subseteq\mathbb{R}^n$, be a Lipschtiz continuous piecewise linear function. Is this sufficient to guarantee that $f$ is Clarke-regular (Definition 2.3.4 in [1])...
Bazinga's user avatar
  • 183
1 vote
0 answers
29 views

Example of convex function that does not have subgradient

Through self-study, I found out that there are some pathological functions that do not have subgradients. https://www.stat.cmu.edu/~siva/teaching/725/lec2.pdf On page 2: Except for some very ...
learning's user avatar
  • 633
0 votes
0 answers
24 views

Swap integral and subgradient for convex functions

A very nice and helpful result is that for convex functions, the integral of a subgradient is always a subgradient of the integral, without any domination assumption needed. More precisely, let $T$ be ...
TrivialPursuit's user avatar
7 votes
1 answer
263 views

When do two functions have the same subdifferentials?

For two functions $f$ and $g$, if $\nabla f(x) = \nabla g(x)$, $f = g + c$ for some constant $c$. Does the same hold if the gradient is replaced by the (convex) subdifferential, ie $\partial f(x) = \...
P. Camilleri's user avatar
1 vote
0 answers
56 views

Verify proof: absolutely continuous function convex if gradient monotone wherever it exists

Let $A$ be a convex and compact subset of $\mathbb{R}^2$ and consider some absolutely continuous $F:A\to \mathbb{R}$. Then $\nabla F$ exists almost everywhere on $A$. I want to show that $F$ is convex ...
qscty's user avatar
  • 151
3 votes
1 answer
48 views

How to construct a parabola that tangent to the function $\max \left\{ {x,0} \right\}$ and lie above it?

What would be the correct way to construct a parabola that tangent to the function $\max \left\{ {x,0} \right\}$ and lies above it? One of the thing that is difficult is that the max function is ...
Tuong Nguyen Minh's user avatar
1 vote
2 answers
128 views

Subdifferential of convex functions is nonempty

I read the counterexample in this post, and I am wondering if it is possible to fix the statement in this way: Given a convex function $f:\mathbb R^d\rightarrow\mathbb R\cup\{\infty\}$ and $x\in\...
Yakumo Yuyuko's user avatar
0 votes
0 answers
49 views

Same result in every iterations from subgradient and proximal gradient method.

I'm trying to implement the subgradient method and proximal gradient method with constant stepsize for the lasso problem but the result for the subgradient method and proximal gradient is almost ...
Help me pls's user avatar
1 vote
1 answer
80 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 $...
Tran Khanh's user avatar
1 vote
0 answers
49 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 ...
jlewk's user avatar
  • 2,072
0 votes
1 answer
115 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 \...
MY_NAME_S3M's user avatar
1 vote
0 answers
63 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(\...
Lagranngekmno4's user avatar
4 votes
0 answers
150 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 ...
Five Mr's user avatar
  • 41
1 vote
0 answers
34 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))$...
Eve_11037's user avatar
-1 votes
1 answer
62 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 \}$ ...
X0-user-0X's user avatar
1 vote
2 answers
188 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, ...
X0-user-0X's user avatar
1 vote
0 answers
70 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-...
Robert W.'s user avatar
  • 724
0 votes
1 answer
163 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 ...
Sparsity's user avatar
  • 119
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 ...
0xbadf00d's user avatar
  • 13.9k
1 vote
2 answers
139 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 ...
R. W. Prado's user avatar
3 votes
1 answer
163 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)$ ...
Kittayo's user avatar
  • 709
1 vote
1 answer
121 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, ...
Kittayo's user avatar
  • 709
1 vote
0 answers
267 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 ...
Dylan Dijk's user avatar
1 vote
0 answers
69 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:\...
Nasal's user avatar
  • 798
0 votes
0 answers
131 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 ...
PT_98's user avatar
  • 11
0 votes
1 answer
38 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,...
Dtinas10's user avatar
1 vote
0 answers
37 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) = ...
TheLearner's user avatar
1 vote
0 answers
96 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 ...
The Limit Does Not Exist's user avatar
3 votes
1 answer
187 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$...
Kittayo's user avatar
  • 709
1 vote
0 answers
86 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{\...
Beton's user avatar
  • 33
1 vote
1 answer
86 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 \...
Leonard Neon's user avatar
  • 1,364
0 votes
1 answer
36 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 ...
Cris's user avatar
  • 351
0 votes
0 answers
447 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|...
Tardigrady's user avatar
1 vote
0 answers
129 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_{...
lucifer's user avatar
  • 21
1 vote
0 answers
93 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 ...
lucifer's user avatar
  • 21
1 vote
1 answer
285 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(...
uuunkown's user avatar
1 vote
1 answer
463 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 ...
Phat Tran's user avatar
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 ...
Analyst's user avatar
  • 5,817
0 votes
1 answer
209 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 ...
William Kong's user avatar
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,...
Jason Miller's user avatar
1 vote
0 answers
74 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$...
Alto Lagato's user avatar
2 votes
1 answer
311 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 ...
blueArrow's user avatar
0 votes
0 answers
189 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(...
Med B's user avatar
  • 1
0 votes
0 answers
98 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 \...
Đào Minh Dũng's user avatar
0 votes
1 answer
84 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 ...
lucmon's user avatar
  • 1
1 vote
1 answer
1k 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 ...
Đào Minh Dũng's user avatar
1 vote
1 answer
576 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 ...
user202542's user avatar

1
2 3 4 5 6