The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
16 views

subdifferential of $\max_{i=1,\cdots,k} x_i+\frac{1}{2}\|x\|_2^2,\ \ \ x\in \mathbb{R}^n$

How to find the subdifferential of $$f(x) = \max_{i=1,\cdots,k} x_i+\frac{1}{2}\|x\|_2^2,\ \ \ x\in \mathbb{R}^n$$ My derivation is: $\nabla \frac{1}{2}\|x\|_2^2=\nabla \frac{1}{2}x^Tx=x$ ...
0
votes
0answers
15 views

More understanding about $E_u[\partial_x h(x,u)]$, $u$ is a random variable

Consider the subdifferential "$\partial_x h(x,u)$", $u$ is a random variable. (Note: subdifferential is a set with the definition in subgradient method.) How to understand $$E_u[\partial_x h(x,u)]$$ ...
0
votes
1answer
30 views

Subgradients of non-convex functions

In these notes (section 2.3), it is stated that: A point $x^*$ is a minimizer of a function $f$ (not necessarily convex) if and only if $f$ is subdifferentiable at $x^*$ and $0 \in\partial f(x^*).$...
0
votes
0answers
11 views

Lower bound of averaging gradient method (Prof. Yurii Nesterov's paper)

I am reading the paper of Prof. Yurii Nesterov: Primal-dual subgradient methods for convex problems The last inequality confuses me: (p.231) Note: 1. The ...
0
votes
0answers
25 views

Subdifferential optimality conditions

I need help with subdifferential optimality. Let $f(x_1, x_2)=x_1^2 + x_2^2 + |x_1 -x_2 - y|$. Find: \begin{align} \min_{x_1, x_2} f(x_1, x_2) \end{align} This is convex, so must have unique ...
1
vote
1answer
28 views

Proximal-type support function properties - nonnegative & strongly convex (proof)

I am reading the paper of Prof. Yurii Nesterov: Primal-dual subgradient methods for convex problems The following part confuses me: $\\$ $\\$ ${\color{red}{E}}\...
1
vote
1answer
39 views

Proof of unique solution of strongly convex function (Prof. Nesterov Paper)

I am reading the paper of Prof. Yurii Nesterov: Primal-dual subgradient methods for convex problems I am confused about the green part of the following: $\\$ ...
0
votes
0answers
16 views

Lipschitz condition for the stochastic subgradient

We know that for the subgradient method convergence, $f$ should satisfy the Lipschitz condition, i.e., $|f(x_1)-f(x_2)|\leq G\|x_1-x_2\|_2\ \ \ $ for all $x_1, x_2$ For the stochastic ...
0
votes
0answers
23 views

Subgradient of function of two variables

i do not have any experience in convex analysis and I would be most grateful if you would help me with the concept of subgradient. I get the concept of subderivative (one dimension) but it is hard ...
2
votes
0answers
24 views

Can a subgradient always be found in polynomial time?

Given a convex function, under what conditions can we find a subgradient in polynomial time? There are easy examples such as $f$ being an supremum of a finite number of differentiable functions, but ...
0
votes
0answers
52 views

L1-norm minimisation

I am working on this tutorial question. The question asks me to write a Matlab code to implement the method. I was stuck in how to formulate a code for the proximal operator as well as the gradient ...
0
votes
1answer
37 views

Subgradient at the boundary of a closed set

Suppose I have the convex function $f(x) = |x|$ over the domain $x \in [-1,1]$, and I wish to find the subgradient. It is easy to find the subgradient in the interior of the domain. At the boundaries,...
0
votes
0answers
17 views

Find the subgradient set of $\|x\|$ in $x=0$

Find the subgradient set of $\|x\|$ in $x=0$, $x\in\mathbb{R}^n$ I already solved the problem by definition, but I am asking for another easier way, thanks.
0
votes
0answers
38 views

How to find the subgradients of $f(x)=\|x\|^2-1$ if $\|x\|\geq 1$, $f(x)=0$ if $\|x\|\leq 1$, $x\in\mathbb{R}^2$.

How to find the subgradients of $f(x)=\|x\|^2-1$ if $\|x\|\geq 1$, $f(x)=0$ if $\|x\|\leq 1$, $x\in\mathbb{R}^2$. By definition a subgradient $a$ must satisfy $f(x+y)\geq f(x)+a\cdot y$ I just have ...
0
votes
1answer
40 views

about scaling property of proximal operator

If the proximal operator of $f(x)$ is $\text{prox}_{\lambda f}(x)$, what about $cf(x)$ and $f(cx)$, c is a scalar. For example, If $f(x) = ||x||_{1}$, $x \in \mathbb{R}^{n}$, how about the proximal ...
0
votes
0answers
20 views

Scaling issue with Gradient descent methods

As is the common knowledge that gradient methods are affected by scaling issue of the variables. For example, If minimizing a function of say 2 variables $x_1$, $x_2$. Both variables have different ...
0
votes
1answer
20 views

Conditions of convergence of stochastic subgradient algorithm

It is well known that for appropriate step size, $E[g^t] \in \partial f(x^t)$ is sufficient conditions for this subgradient algorithm to converge. What I'm wondering is whether the requirement has to ...
0
votes
3answers
22 views

Gradient on curves

Please with a bit of explanation, what is the gradient on the curve $y = 16/x$ where $x = 8$. I'm finding it hard to solve problem like this.
3
votes
1answer
62 views

Geometric concept of $A$-orthogonality, $A>0$

Assume the following is in in $\mathbb{R}^n$ 1. If $d_i,d_j$ are orthogonal with $i \neq j$, it means $d_i^Td_j=0$. 2. If $d_i,d_j$ are $A$-orthogonal with $i \neq j$, it means $d_i^TAd_j=0$. In ...
0
votes
1answer
99 views

How to computer the proximal operator of a indicator function?

For $G_{1}(x) = I_{c}(x), c =\{x|Ax=b\}$, the Proximal operator is: $Prox_{\gamma G_{1}}(x) = Proj_{c}(x) = x + A^{T}(AA^{T})^{-1}(y-Ax)$ I hope to know, how to derivative this result. And, for ...
0
votes
1answer
122 views

Gradient of a Lagrange dual function

Consider: $$\min_{x \in \mathbb{R}^n} f(x)$$ $$\ \ \ \ \ \ \ \text{s.t. }\ h(x) \leq 0$$ Lagrangian:$\ \ \ L(x,\lambda) = f(x) + \lambda h(x)$ Suppose $x^* = \arg\min_{x} L(x,\lambda)$ ...
3
votes
1answer
42 views

$\nabla f$ Lipschitz & $f$ Lipschitz

My question is: Which of the following is more restrictive? $\nabla f$ Lipschitz & $f$ Lipschitz I think each one cannot imply the other. For example ($1$D): $$f(x) = \frac {x^2}{3}$$ ...
0
votes
0answers
35 views

Convergence analysis of gradient descent method

From the following: Convex Optimization (S. Boyd) p.467 Content: We will see that the gradient method does in fact require a large number of iterations when the Hessian of $f$, ...
1
vote
0answers
55 views

How to understand a proposition of subgradient

The question is from the following: Convex Optimization Algorithm (p.512)----- Prof. Bertsekas Let $f: R^n \rightarrow (-\infty, \infty]$ be a proper convex function. For every $x \in \...
0
votes
1answer
77 views

Gradient of the elastic net with extra terms

Can anyone tell me the gradient of the below function (w.r.to X) $$ argmin_{X} ~~\frac{\lambda}{2}\lVert X\lVert_2^2 + \lVert X\lVert_1 + tr\bigg(\Delta^T\Big(diag(X)-X\Big)\bigg) + \frac{\rho}{2}\...
2
votes
1answer
62 views

Proof of relationship of subgradients of function to convexity of function

I am trying to follow the proof of the first claim of Proposition 7 on this page: https://blogs.princeton.edu/imabandit/2013/02/05/orf523-advanced-optimization-introduction/ Basically, we are given: ...
0
votes
2answers
44 views

Dual subgradient method - can we solve approximation of dual?

Consider the problem to minimize $f(x)$ under the constraints $x \leq b$ and $x \in X$. I Lagrange relax the constraint $x \leq b$ getting $L(x,u) = f(x) + u^t(x-b)$. When using the subgradient ...
0
votes
0answers
68 views

Getting explicit expression of function from the dual function

Considering the following problem : $$ minimize_{x_1,x_2} \ -2x_1+x_2 \\ subject \ to \ x_1+x_2=\frac52 \\ (x_1,x_2) \in X ,\\$$ where $X=\{(0,0),(0,2),(2,0),(2,2),(\frac54,\frac54)\}$ The dual ...
1
vote
1answer
370 views

Sub-gradient of the “$\ell_0$ norm”

I am trying to characterize the sub-gradient of l0-norm ($f(x) = ||x||_0=\sum_{i=1}^n 1\{{x_i \neq 0}\}$). At first, I thought l0-norm is a convex non-smooth function since it satisfies the triangle ...
1
vote
0answers
99 views

Subdifferential of a convex function

How would I find a convex function $f: \mathbb{R} \to \mathbb{R}$ such that $\partial f(0) = [0,1]$ A subdifferential is just the collection of vectors $w \in \mathbb{R}^n$ such that $f(y) \geq f(...
0
votes
1answer
75 views

Distributed Newton methods for large scale problems

I am keen to know about the literature landscape for distributed convex optimization methods which use second order information like the Newton step. This is as such a less evolved area compared to ...
1
vote
0answers
39 views

Is there a good textbook/book out there that explains sub gradients thoroughly?

I was interested in learning and understanding sub gradients as much as I could from some good resource. I know what the definition is, but I seem unable to apply the definition to prove basic facts ...
0
votes
1answer
77 views

What is the sub-differential of the separable sum $R(w) = \sum^{d}_{j=1} |w_j|$?

Recall the definition of a sub-differential: $$\partial F(w_0) = \{ v : \forall w, F(w)-F(w_0) \geq v \cdot (w - w_0)\} $$ Intuitively, for any w in the domain of the function one can draw a plane ...
1
vote
1answer
41 views

How does $\in$ behave with simple algebra dealing with sub gradients?

I was trying to understand the following optimization problem: $$argmin_{v \in H} {R(v) + \frac{1}{2}||v - w||^2}$$ Assume $R(v)$ is Convex, proper and semi-continuous with a unique minimizer. ...
0
votes
1answer
128 views

Subgradient example

Let $f(x_1, x_2)$ be defined as: if $x_1 =0$ then $f(x_1,x_2)=x^2_2$ else $\infty$ The subgradient of $f(x_1,x_2)$ at $(0,0)$ is given as: $\mathbf{R} \times \{0\}$. (The real line crossed with 0)....
1
vote
0answers
151 views

What is the left derivative of the hinge loss function in the context of subgradients?

Let: $$|a|_+ = max\{0,a\}$$ Then the Hinge loss function (in the context of classification in Machine Learning) is: $$V(-yf(x)) = |1 - yf(x)|_+$$ Note that $y \in \{-1,1\}$ Let $f(x) = \langle w, ...
0
votes
0answers
172 views

gradient descent - cost reduces and then increases

I am optimizing a function using Gradient Descent. The learning rate is fixed. First for few iterations the cost decreases after that it starts increases. What is the reason for this?
0
votes
1answer
79 views

Common subdifferentials of convex function

Let $f: \mathbb R^n \rightarrow \mathbb R$ be a convex function. By a subdifference of $f$ in $x\in \mathbb R^n$ we mean an $h\in \mathbb R^n$ such that $f(x) \geq f(p)+<x-p,h>$ for all $x\...
1
vote
1answer
28 views

Easy question about subdifferential of a functional on $L^2(0,T;L^2)$

Define $J:L^1(0,T;L^1) \to \mathbb{R}$ by $$J(v) = \int_0^T \int_\Omega \Psi(v)$$ where $\Psi(v) = \int_0^v \beta(s)\;ds$ where $\beta$ is a nice function that passes through the origin. We have ...
0
votes
0answers
47 views

Question about meaning of evolution problem.

Consider the following "evolution problem" $f(t) - u_t(t) \in \partial \psi(u(t))$ $u(0) = u_0$ Where $f:[0,T] \rightarrow H$ $ u:[0,T] \rightarrow H$ $ \psi:H \rightarrow (-\infty,\infty]$ is ...
1
vote
1answer
1k views

Smooth approximation of maximum using softmax?

Look at the Wiki page for Softmax function (section "Smooth approximation of maximum"): https://en.wikipedia.org/wiki/Softmax_function It is saying that the following is a smooth approximation to the ...
0
votes
2answers
92 views

gradient norm of a simple function

In this answer Derivation of soft thresholding operator how can I derive that $\nabla(||x-b||_2^2)=b-x$?
4
votes
2answers
1k views

Conjugates of norms

How would one find the conjugate of the following : $$f(x) = \|x\|^2 /2$$ The conjugate function is defined as $ f^*(y) = \max_x y^Tx - f(x)$ I am stuck at how I can derive the explicit form for $x$....
2
votes
1answer
89 views

Finding subgradients

How would I find the subgradients of this : $$ f(x) = \max_{i=1,\ldots,n} a_i^Tx + b_i$$ I'm new to subgradients and any hint on how to start this would be useful for me.
1
vote
2answers
57 views

Subdifferential of $(\eta^{\textrm{T}}\mathbf{K}\eta)^{\frac{1}{2}}$ at the origin

What is the subdifferential of the following norm at the origin \begin{align} \lVert\eta\rVert_{\mathbf{K}}=(\eta^{\textrm{T}}\mathbf{K}\eta)^{\frac{1}{2}} \end{align} where $\mathbf{K}$ is a ...
0
votes
2answers
61 views

Confusion related to calculation of derivative

I have this function \begin{align} &s = f(\theta,x),\\ &s_1 = f(\theta,x_1),\\ &s_2 = f(\theta,x_2),\\ &P = A^T \left[\begin{array}{cc} s_1 & 0 \\ 0 & s_2 \end{array} \right] A....
2
votes
2answers
1k views

proximal operator of infinity norm

What is the proximal operator of $\|x\|_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
0
votes
1answer
88 views

Confusion related to the calculation of gradient

I am having some confusion related to the calculation of gradient. My function $f(X) = g(X) + \lambda||X||_1$ where g(X) is convex and differentiable. I didn't get how the second expression when $...
1
vote
0answers
63 views

Confusion related to calculation of Hessian and notation

I was reading this paper where they have calculate the gradient and hessian of a function as I didn't get what the cross sign means here. Further I am confused about the second row first column ...
0
votes
1answer
657 views

Subdifferential of the sum

Let $C \subset \mathbb R^n$ a nonempty subset. Let us define the indicator function of $C$ $$ I_C(x) = \begin{cases} 0 & x \in C \\ +\infty & x \notin C \end{cases}. $$ Let us consider, in ...