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
Filter by
Sorted by
Tagged with
1 vote
24 views

28 views

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 ...
1 vote
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 ...
1 vote
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 ...
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$....
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)$ ...
1 vote
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, ...
1 vote
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 ...
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 ...
1 vote
49 views

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 ...
33 views

1 vote
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 ...
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$...
1 vote
80 views

1 vote
90 views

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 ...
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 ...
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 ...
1 vote
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,...
1 vote
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$...
1 vote
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 ...
147 views

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 ...
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 ...
1 vote
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 ...