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
2
votes
1answer
53 views

Is a convex function with these properties possible?

Consider $V:[0,1]^2 \rightarrow[0,1]$, satisfying the following properties: $V(x,y) = p(x,y)x+(1-p(x,y))y$, where $p(x,y) \in [0,1]$. In other words, every point in $[0,1]^2$ is mapped to a ...
0
votes
1answer
23 views

A subdifferential formulated as an argmax problem

I am reading the article "Random Variables, Monotone Relaitions and Convex Analysis" by Rockafellar and Royset. It is article number 226 on Rockafellar's website https://sites.math.washington.edu/~rtr/...
0
votes
1answer
25 views

subgradient and subdifferential at the boundary of a closed set for discontinuous function. [closed]

Consider the function $ f:[0,1] \to \mathbb{R}, \qquad$ $ f(x) = \begin{cases} x^2 & \text{if $x > 0$,} \\ 1 & \text{if $x=0$.} \end{cases} $ This function is convex. I want to find ...
0
votes
2answers
43 views

Subgradient of square of L2 norm

A subgradient $g \in \partial f(y)$ at a point $x$ is a $g$ such that $$f(y) \geq f(x) + g^T(y-x)$$ for all $y$ in the domain of $f$. For $f(x) = ||x||_2$, we know that $\partial f(x) = \{\frac{x}{|...
1
vote
0answers
6 views

Subdifferential of Sum

Let $f$ be class $C^{\infty}(\mathbb{R}^d,\mathbb{R}^k)$ functions and let $a<b$ define $1_{[a,b]^d}$. What is a subgradient of $$ f1_{[a,b]^d}? $$ Intuitively it seems like it should be $1_{[a,b]...
3
votes
0answers
22 views

Breaking up subgradients into pieces

I was giving this post some thought and could not help but wonder the following. Suppose that $A_1,\dots,A_k$ are pairwise disjoint open sets and $g_1,\dots,g_k$ are smooth functions, then $1_{A_j}...
0
votes
0answers
13 views

How can I find the gradient of a non linear SVM wrt input?

Given that an SVM will have the following function: And if I was to use a kernel, this would become: Where the kernel can be the Gaussian kernel: How Would I go about finding its gradient wrt the ...
1
vote
0answers
44 views

Is the map $f \mapsto \nabla f(x)$ continuous over the space of convex functions?

Take $V=C(X,\mathbb R)$ as the space of differentiable functions $X \to \mathbb R$ under uniform convergence. Here $X \subset \mathbb R^d$ is some compact domain. For each x is well known the map $\...
0
votes
1answer
35 views

Proximal Mapping - Derivation of the Proximal Operator from the Resolvent of the Sub Differential

I do not really understand the solution for this question. I do not understand how the zero vector was derived to be an element of the subdifferential and why g(u) is strongly convex. Any help and ...
4
votes
0answers
215 views

Need help solving a min-max fixed point equation

I have the following fixed point equation: for all $p\in[0,1]$ $$V(p) = \min_{\lambda_1,\lambda_2\in[0,1]}\max\{pr,(1-p)r,\beta\mathbb{E}_{a,y'}[V(f_{\lambda=(\lambda_1,\lambda_2)}(p,a,y'))]\}$$ ...
0
votes
1answer
23 views

Computing simple subgradients

I am trying to understand how can one compute subgradients for functions $f: \mathbb{R}^2 \supset M \to \mathbb{R}$. I know that $\xi \in \mathbb{R}^2$ is a subgradient for function $f$ in $x_0$ if ...
0
votes
1answer
28 views

Computing subderivative for two variable function

I need to compute a suberivaqtive for the following function $$f\big((x, y) \big) = |x-2y+1| + |x-4y-3| + |2x-y+2|.$$ I also need to find its global extrema. I know that a subderivarive of function ...
0
votes
1answer
30 views

In Subgradient descent method for convex problem: can we say $x^{(k)} \approx x^{(k-1)}$ for iteration $k \rightarrow \infty$?

Apologies for the basic question. Let us say that the general convex problem is $$\min_x f(x).$$ Say, we employ a subgradient method $$x^{(k)} = x^{(k-1)} - t_k \partial f\left( x^{(k-1)}\right) ,$...
0
votes
0answers
97 views

Showing $f(x)=\max_{u\in U} c^Tu+x^T(Au-b)$ is convex

The following is an exercise from a test. I didn't solve it. Let $U$ be a compact, polyhedral set in $\mathbb R^n$ with vertices $u_1, u_2, \dots, u_n$, $A$ an $m \times n$ matrix and $b \in \...
0
votes
0answers
30 views

Solution of Lagrange relaxation of problem does not converge to optimal

I am trying to solve the MILP problem using Lagrange relaxation with subgradient method. I am following the approach described in here: http://www.cs.uleth.ca/~benkoczi/OR/read/lagrange-relax-...
0
votes
0answers
19 views

sub differential exercice

Let $D$ be the unit disc in $\mathcal{R}^2$ and let $f : \mathcal{R}^2 → \mathcal{R}$ be the function $f(x) = d(x, D)$ = the distance from $x$ to $D$. We are looking for the sub differential of $f$ at ...
0
votes
0answers
11 views

Prove that $\arg\max_{\|x\|\le 1} x^Ty=\partial \|y\|_*$

Here $\|\cdot\|$ is a norm and $\|\cdot\|_*$ is the corresponding dual norm. $\partial\|\cdot\|$ denotes the subgradient. How can I prove the equality? Thank you!
0
votes
1answer
48 views

The Sub Differential of a Least Squares and $ {L}_{1} $ Norm Regularization

For real numbers $\lambda > 0$ and $x$, I'm considering the convex minimization problem $$t^{\star} = \mathrm{argmin}_{t}\left[\lambda|t| + \frac{1}{2}(t-x)^{2}\right] := \mathrm{argmin}_{t}\left[...
0
votes
0answers
35 views

Show that if $g(x) = f(Ax + b)$, then $\delta g(x) = A^T \delta f(Ax + b)$

Looking for a simplier expaination for the following: Show the following for sub-gradients: (a) If $g(x) = f(Ax + b)$, then $\delta g(x) = A^T \delta f(Ax + b)$. I've found the trivial ...
1
vote
1answer
99 views

how to compute subgradient of p-norm, $1 \leq p \leq \infty$

I am a graduate student in Communications Engineering and I have an optimization course. I need help in solving my assignments: this one is related to convex optimization. We are asked to compute the ...
0
votes
0answers
12 views

Subgradients of strictly Schur-convex function

Let $F: \mathbb{R}^N \to \mathbb{R}$ be strictly Schur-convex. It is well-known that if $F$ is differentiable, then for any $x=(x_1,\ldots,x_N)$ the following holds: for any $1\leq i,j\leq N$ such ...
1
vote
1answer
37 views

integrating sub derivative of convex function

Let $f$ be a convex function on $\mathbb R$ such that $f(0)=0$, let $g$ be such that for all $x$ in $\mathbb R$, $g(x)$ is a sub-gradient of $f$ at $x$, then it seems to me that for all $x\in \mathbb ...
0
votes
1answer
105 views

Subgradient of a matrix function related to maximum eigenvalue

Consider the function $f(\textbf{X})$ on dom$f=\mathbb{S}^n$.Show that $$vv^T\in \partial f(\textbf{X})$$ where $v$ is a normalized eigenvector of $\textbf{X}$ associated with $\lambda_{max}(\textbf{X}...
0
votes
0answers
16 views

Constrained Minimization Conditions

Let $C$ be a nonempty, closed and convex set in a Hilbert space $H$, and let $f : C \to \mathbb{R}$ be a proper, strongly convex and subdifferentiable function on $C$. Does it hold that $$x^* = \arg\...
0
votes
1answer
64 views

Non Smooth Convex Optimization

I want to solve an optimization of the form $$\underset{x}{\min}f(x) + g(x),$$ where $f(x)$ is $\mu$-strongly convex and differentiable with a Lipschitz continuous gradient (with Lipschitz constant $L$...
0
votes
0answers
28 views

Does strict convexity imply the existence of subgradients?

Suppose $f:\mathbb{R}^d \rightarrow \mathbb{R}$ is a strictly convex continuous function that is non-smooth. Does the continuity and strict convexity of $f$ imply the existence of subgradients at the ...
0
votes
0answers
16 views

Calculate the generalized gradient of $w\mapsto\min(w(x)\varphi(x,y),w(y)\varphi(y,x))\psi(x,y)$ in $L^2$

Let $(E,\mathcal E,\lambda)$ be a measure space, $\varphi,\psi:E^2\to[0,\infty)$ and $$f:E^2\times L^2(\lambda)\to\mathbb R\;,\;\;\;((x,y),w)\mapsto\min(w(x)\varphi(x,y),w(y)\varphi(y,x))\psi(x,y).$$ ...
0
votes
0answers
35 views

Clarke's generalized derivative of $w\mapsto\int\lambda({\rm d}x)\int\lambda({\rm d}y)\min(w(x)φ(x,y),w(y)φ(y,x))ψ(x,y)$ in $L^2(\lambda)$

Let $p,q$ be probability densities on a measure space $(E,\mathcal E)$, $\sigma:E^2\to[0,\infty)$ be symmetric with $$\int\lambda({\rm d}y)\sigma(x,y)q(y)=1\tag1\;\;\;\text{for all }x\in E$$ and $h\in ...
1
vote
0answers
69 views

Subgradient of Ky Fan norm

Given, a matrix $A \in \mathbb{R}^{n \times n}$, its Ky Fan $k$-norm is defined as the sum of largest $k$ singular values. How can I find a sub-gradient of this norm? I tried normal sub-gradient ...
4
votes
2answers
214 views

Derivative of the Prox / Proximal Operator

Consider a proximal operator, $$ \operatorname{Prox}_{ \lambda f( u ) } \left( x \right) = \arg \min_{u} \lambda f \left( u \right) + \frac{1}{2} {\left\| u - \mu x \right\|}_{2}^{2}.$$ What is the ...
1
vote
0answers
113 views

Gradient of the Sinkhorn Distance for Regularized Optimal Transport

Given two probability measures $\mathbf{r}\in \Sigma_n$ and $\mathbf{c}\in \Sigma_n$, Cuturi 2013 [1] defines the Sinkhorn distances as: $$ d_{\mathbf{M},\alpha}(\mathbf{r}, \mathbf{c}) = \min_{\...
3
votes
0answers
39 views

An alternative to $\alpha_k=\frac{C}{k}$ step size

I am trying to implement a derivative of subgradient method that includes a distributed scenario and one of the requirements for convergence is to have a step size which satisifies the following ...
0
votes
1answer
56 views

How do I take the inner product of a subdifferential with a vector?

I'm reading this pdf about an implementation of the PDHG algorithm for convex minimization. At the beginning of page 9, authors make an operation I can't not understand. In short, this is what ...
1
vote
1answer
146 views

Proximal normal cone and convex sets

The proximal normal cone $N_S^P(x)$ for a set $S \subset X$, where $X$ is a Hilbert space, is defined as $$ N_S^P(x) = \{\zeta \in X : d_S(x + t\zeta) = t\|\zeta\|, \text{ for some } t > 0\}. $$ ...
0
votes
1answer
39 views

What will be the value of sub gradient at $0$ for function $|x|$

I am learning about Lasso Regression and came across taking gradient with respect to $0$. I came to know about subgradient but could not understand what will be its value at $0$. In lasso regression, ...
0
votes
0answers
96 views

Gradient of $2$-norm inside absolute value

Compute the gradient of $$ z = | \lVert L x \lVert_2 - P | $$ where $ x \in \mathbb{C}^N $ and $ P \in \mathbb{R}_{+} $. First, I make $ a = \lVert L x \lVert_2 - P $. Also, since $ | a | $ is non-...
0
votes
1answer
42 views

How to estimate subgradient? [closed]

consider a general convex function $f$ which is Lipschitz continuous over $X$, i.e., $\exists M > 0$ such that $$\left|f(x)-f(y)\right| \leq M\|x-y\|.$$ Here $X\subseteq R^n $is a closed ...
1
vote
1answer
105 views

Subgradient of $\|AX\|_1$

If $f(x) = \|AX\|_1$, where $\|.\|$ denotes the entrywise $\ell_1$-norm, what is the subgradient of $f(x)$? Is there an expression similar to $A'A \ \partial \|X\|_1$? For example, $A = [1 \ 1; 1 \ ...
0
votes
1answer
370 views

About subgradient of matrix norm

I am reading Characterization of the Subdifferential of Some Matrix Norms by G.A. Watson. And in the first page the subgradient of $\|A\|$ is defined:$$\partial\|A\| := \{G\in \mathbb{R}^{m \times n}:\...
0
votes
1answer
38 views

How to interpret the expression $0 \in \partial f(\hat y) + (\hat y - x)/\tau$

I'm reading this pdf while learning about subdifferential calculus, and I came across this expressión (page 176): $$0 \in \partial f(\hat y) + (\hat y - x)/\tau \tag{1}$$ I don't know how to ...
2
votes
0answers
34 views

Reconstructing Convex Functional from gradient

Suppose that $f\in \Gamma_0(H)$, that is $f$ is a lsc, convex, and proper functional from a Hilbert space $H$ to the base-field $\mathbb{R}$. Is it possible to reconstruct $f$, from the Fenchel-...
1
vote
0answers
83 views

Subgradient calculus: Understanding weighted sums property proof

I'm reading page 72 of this pdf, and I can't understand the proof of the weighted sums property of the subdifferential $\partial f$. Weighted sums satisfies: Given two convex functions $f$ and $g$ on ...
0
votes
1answer
40 views

Help needed in understanding the following Lemma

We have a matrix inequality defined as follows $$\mathbb{F(\Gamma)}=\mathbb{I}-\sum_{i=1}^K{\lambda_i\mathbb{H_i}}\succeq \mathbb{0}.$$ Where $\mathbb{\Gamma}=\{\lambda_1,\lambda_2,\cdots \lambda_K\}$ ...
2
votes
0answers
69 views

Subgradient of Entropy

If $(X,\Sigma\,u)$ is a finite measurable space, define the map $$ \begin{aligned} X& \rightarrow (-\infty,\infty)\\ T(f)&\triangleq \int_{x \in X} f \log(f)\nu(dx), \end{aligned} $$ where $X\...
0
votes
1answer
96 views

Derivative of nonsmooth functions

If a function is continuous but nonsmooth at point x = a, but has a finite derivative = 4 at x = a - $\epsilon$ and a finite derivative = 7 at $x = a + \epsilon$, both in the limit $\epsilon \to 0$. ...
0
votes
0answers
17 views

Obtaining a valid subgradient

I have a nonconvex function, which could be non-smooth in some places. I also have the expression for computing the gradient vector of the function. This vector is valid as a gradient wherever the ...
0
votes
0answers
180 views

Sub-gradient of square root of modulus of $x$

Can somebody explain how to find sub-gradient of $\vert x\vert^{\frac{1}{2}}$? Also, can we have sub-gradient of a non-convex function? An example would be helpful. I am actually new to sub-gradients ...
3
votes
3answers
274 views

how to find subdifferential of a function $x^2+ |x-1|+|x-2|$

Given a function $f(x) = x^2+ |x-1|+|x-2| $ find it's subdifferential. My approach to solving this was to divide the answer into 5 parts: For |x-1|>1 and |x-2|>2 $f(x) = x^2+ x-1+x-2$ and $f'(x) ...
0
votes
1answer
95 views

Lagrangian relaxation

I have an assignment where I need to solve a small problem using Lagrangian relaxation. $$ \min 3x_1-x_2$$ $$x_1-x_2 \ge -1$$ $$-x_1+2x_2\le 5 $$ $$3x_1+2x_2 \ge 3$$ $$6x_1+x_2 \le 15$$ $$x_1,x_2 \ge ...
1
vote
1answer
224 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 ...