The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
26 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
43 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
48 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)$ ...
0
votes
0answers
8 views

First - order necessary condition

If I have the function $f(x1,x2) = 2x_1^4 + 2x_2^4$ and I want to know if the point $(1,1)$ satisfies the first-order necessary condition, can I then say the following and if yes please explain why. ...
3
votes
1answer
23 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
17 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
33 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
66 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) + ...
2
votes
1answer
27 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
0answers
35 views

Can I do gradient ascent this way for a non-differentiable function?

I have a probability distribution $P(x)$ where $x$ is a N-dimensional vector with constraints $sum(x)=1$. This distribution $P(x)$ does not have a closed form. $P(x)$ is a function where I query the ...
0
votes
2answers
25 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
60 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
138 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
41 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 ...
0
votes
1answer
61 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
29 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
46 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
33 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
67 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 ...
1
vote
0answers
69 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
48 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
58 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 ...
1
vote
1answer
25 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
33 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
478 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
40 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
702 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 ...
2
votes
1answer
68 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
1answer
79 views

What is the difference between projected gradient descent and ordinary gradient descent?

I just read about projected gradient descent but I did not see the intuition to use Projected one instead of normal gradient descent. Would you tell me the reason and preferable situations of ...
1
vote
2answers
54 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
57 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] ...
1
vote
1answer
630 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
83 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
61 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
400 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 ...
0
votes
1answer
81 views

Subdifferential calculus

Let $\phi : H \to \mathbb{R}$ ($H$ is a vectorial space) be a convex function $\mathcal{C}^1$. I have the following inequality, for $\sigma \in H$ fixed, $$\forall \tau\in H, \ (\sigma - \tau \mid ...
1
vote
2answers
83 views

How many methods for smoothing an unsmoothed function?

Which is the simplest one? For example, we smooth $f(x)=|x|$ to $$f(x)=\begin{cases} \frac{x^2}{\epsilon}+\frac{\epsilon}{2} & |x| \le \epsilon\\ |x| & |x|\ge epsilon ...
1
vote
1answer
258 views

Solving a constrained Lagrangian dual problem

Consider the following $\max-\min$ integer programming formulation expressed in the binary decision variable $\mathbf{z}$: $$\begin{align*} \max&m \\ s.t.&\\ m \leq& s_i + \sum_j^J ...
0
votes
0answers
134 views

Calculation of the sub gradient of the first norm of a matrix

Lets say I have a matrix X and its first norm $||X||_1$. How do I calculate the subgradient of this norm with respect to matrix X itself.
2
votes
0answers
79 views

Nonlinear optimization of constraint parameter - subdifferential?

Disclaimer: I discovered that the FAQ suggests to post research-level to mathoverflow instead of math.stackexchange. I "moved" the question accordingly, cp. post at mathoverflow. Sorry for the ...
6
votes
0answers
229 views

Subgradient of convex minimization duality

$$\min(f_0(x))$$ $$\text{s.t. }f_i(x) \le y_i \forall i, i = 1 ,\ldots, m$$ $$f_i : \text{convex};\quad x : \text{variable}$$ It is also considered that $g(y)$ is the optimal value of the problem ...
1
vote
0answers
287 views

Gradient Descent for Primal Kernel SVM with Soft-Margin(Hinge) Loss

Given the primal objective $$F({\bf a})=L\sum_{i,j}a_{i}a_{j}k(x_i,x_j) + \sum_{i}max(0, 1-y_i \sum_{j}a_jk(x_i,x_j)$$ for the soft margin SVM, where ${\bf a}=(a_1,...,a_N)$, N being the number of ...
1
vote
1answer
169 views

Why is the set of subgradients a convex set?

I'm struggling to understand an example we were given. The problem description is: Let $f$ be a convex function in $E^n$. Prove that the set of subgradients of $f$ in a given point form a ... convex ...
2
votes
1answer
229 views

Mathematical applications of the subgradient

Do you know mathematical results which can be nicely proved using subgradient? For example, Jensen's inequilaty can be proved like that: Let $\varphi : \mathbb{R}^n \to \mathbb{R}$ be a convex ...