The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
5 views

Convergence results for incremental generalized gradient methods

Are there convergence results of incremental and stochastic subgradient / generalized gradient methods for locally Lipschitz functions that are not necessarily convex? I am mainly interested in ...
0
votes
1answer
38 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
0answers
30 views

Confusion related to this optimization algorithm [closed]

I was reading this paper http://rain.aa.washington.edu/@api/deki/files/168/=CDC13_0909.pdf. However, in page 3 of the paper, it has something like this It is saying that the standard dual ...
1
vote
1answer
21 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
26 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 ...
0
votes
0answers
55 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
1answer
17 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
245 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
40 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
58 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
50 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
0answers
51 views

KKT minimization problem

Solve $x^2 - 2y \rightarrow \min$ subject to $\max\{3x^2, e^y + 2\} + \sqrt{x^2 + y^2 - 2x + 1} \leq 6x + \sqrt{5}$ and $ \sqrt{x^2 + y^2 - 4x - 4y +8} -2x+2y \leq 0$ I tried computing the ...
0
votes
0answers
26 views

Confusion related to Newton's method for optimization

I am trying to use Newton's method for optimizing a certain function f. However, I am having some issues. I am using Armijo rule for finding the step size. So my iterations are like this $x_{t+1} = ...
0
votes
2answers
51 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
290 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
79 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
43 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
208 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
56 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
70 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
191 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
88 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
68 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
179 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
201 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
109 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
177 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 ...