Tag Info

New answers tagged

0

If your convex set $C$ is a linear subspace, then you can take some orthonormal basis of it, say $e_i, i=1,..,k\leq n$ and your projection must satisfy $x-y\perp e_i, i=1,2,..,k$. Therefore, if $y$ is represented in the mentioned basis as $y=\sum\limits_{i=1}^{k}{a_ie_i}$, then we must have $(x,e_i)-a_i=0$, i.e $a_i=(x,e_i)\Rightarrow ...


1

With the Lagrangian $$ L(x,\lambda) = -c^Tx + \lambda \frac12 (x^TQx -1) $$ one finds the KKT conditions $$ -c + \lambda Qx = 0, \ \lambda\ge0 , \ \lambda(x^TQx -1)=0, \ x^TQx\le 1. $$ If $x^TQx<1$ then $\lambda=0$, and necessarily $c=0$. Hence $\lambda>0$, $x^TQx=1$, $$ x = \frac1\lambda Q^{-1}c, \ x^TQx = \frac1{\lambda^2}c^TQ^{-1}c = 1, $$ this ...


1

By relaxation the feasible set stays equal or becomes larger. Thus, the global minimum might decrease (depending on the objective function). However, since you have a non convex problem, gradient projection method computes a stationary point, a local minimum at best. So it may give you the same, a larger, or a smaller value. You can't really predict what ...


0

No, the $f_i$'s are not convex in general. A counter-example in any dimension $n$ is the projection onto the $\ell_2$ unit ball $C := \{x \in \mathbb{R}^n | \|x\| \le 1\}$. Indeed, for each $x \in \mathbb{R}^n$ one computes \begin{eqnarray} f(x) := proj_C(x) = \begin{cases}x, &\mbox{ if }\|x\| \le 1,\\\frac{1}{\|x\|}x, &\mbox{ otherwise.}\end{cases} ...


0

I can explain the first question, the author said "if $prox_f$ were a contraction", which is not guaranteed. Banach fixed-point theorem tells us repeatedly applying contraction would find a (here, unique) fixed point. So if $prox_f$ is a contraction, then by repeatedly applying proximal operator will result a fixed point.


0

CVX is robust but a bit slow. YALL1 is another good choice. Simple and fast. SPGL is also good.


2

No. For example take n=1, C = [0,1]. Then f(x) = 0 if x<0; f(x) = x for x in [0,1] and f(x) = 1 for x>1. And this function is not convex.


1

If $h\colon \Bbb R^k \to \Bbb R$ and $g\colon \Bbb R^n \to \Bbb R^k$, then their composition is given by $$f(x)=h(g(x)) \qquad \qquad \operatorname{dom}(f)=\{x\in\operatorname{dom}(g)\mid g(x)\in \operatorname{dom}(h)\}.$$ We denote by $\tilde h$ the extended-value extension of $h$, which assigns the value $\infty$ ($-\infty$) to points not in ...


0

you can try to transform the SOCP problem to SDP problem and use the standard solver (such as CVX) to solve the SDP problem


2

This is absolutely the case, and it is straight out of the seminal text, Interior Point Polynomial Algorithms in Convex Programming by Yurii Nesterov and Arkadii Nemirovskii. See Section 2.4.3, "Legendre transformation of a self-concordant logarithmically homogeneous barrier." (Or don't. The book is rather... uh... thick. :-)) I don't think this exact ...


1

Let $t \in [0, 1]$. We can construct a sequence of intervals such that $t$ is the only point in their intersection. $C_0 = [0, 1]$, $t \in X_0$ Let $X_{i} = [a, b]$. If $t \in [a, \frac{a+b}{2}]$, then $X_{i+1} = [a, \frac{a+b}{2}]$ If $t \in (\frac{a+b}{2}, b]$, then $X_{i+1} = [\frac{a+b}{2}, b]$ Obviously, it is a sequence of nested intervals, ...


1

I'm going to assume that we may consider matrix norms. Then in fact, the answer is precisely analogous to the answer given for $\mathbb{R}^n_+$ in your other question. Let $\|X\|_*$ be the nuclear norm of $X\in\mathbb{S}^n$; that is, $$\|X\|_*=\sum_{i=1}^n \sigma_i(X) = \sum_{i=1}^n|\lambda_i(X)|$$ Then we have $$X\in\mathbb{S}^n_+ \quad\Longrightarrow\quad ...


2

It seems that you can. Take $\|\cdot\|$ to be the $1$-norm, $A = I$, and $c = (1,\dots,1)^T$. In particular, we have $$ x \in \Bbb R^n_+ \iff |x_1| + \cdots + |x_n| \leq x_1 + \cdots + x_n $$


0

Note that $\alpha=0$ is feasible and gives $-\alpha^T (R\odot M)\alpha+\alpha^Tq=0$ $\quad\Rightarrow\quad$ $f(q,M)\ge 0$ $\quad\Rightarrow\quad$ $g(q,M)=f(q,M)+\frac12\|q\|^2\ge 0$ $\quad\Rightarrow\quad$ $\min\, g(q,M)\ge 0$. Now take $q=0$ $\quad\Rightarrow\quad$ $f(0,M)=0$ $\quad\Rightarrow\quad$ $g(0,M)=0$. Conclusion: the minimum is zero, attained at ...


1

Checkout my answer to a similar question. It explains what prox operators are, and how they're used in modern convex optimization. It also gives useful references for further reading on the subject. If you still have questions, then we can look at those.


2

This is just the soft thresholding operation. The subgradient of $|w|$, where $w$ is a scalar, is $$\partial |w| \triangleq \begin{cases}\{1\} & w > 0 \\ [-1,1] & w = 0 \\ \{-1\} & w < 0 \end{cases}$$ Therefore, to minimize $|x+y|$, we need to choose the value of $x$ closest to $-y$, but not exceeding $1$: ...


0

Hint: to calculate the subgradienet for $f(w)=\|w\|_1=\sum_{k=1}^n|w_k|$, use three facts: $f(w)=\sum_{k=1}^n f_k(w)$, $f_k$ convex $\Rightarrow$ $\partial f(w)=\sum_{k=1}^n\partial f_k(w)$. $f(z)=\max_{1\le k\le n}f_k(z)$, $f_k$ convex and differentiable $\Rightarrow$ $$ \partial f(z)=\text{Convex hull}(\nabla f_k(z)\colon f_k(z)=f(z)). $$ ...


0

Ross B.'s answer confuses me. Zheng Jia's answer is correct but not clear. Let me elaborate a little bit. The general statement does not require differentiability, as convexity already implies the existence of subgradient. The general KKT condition can be stated in terms of subgradient. For any convex program, $(x,y)$ is a pair of primal and dual optimal ...


1

Short answer: No. I general, you wouldn't expect the subgradient to vanish in the neighborhood of a minimum point $x^*$. All you can say is 0∈∂f($x^*$). Indeed, consider the abolute-value function f:x↦|x|. A simple calculation reveals that ∂f(x)=sign(x) if x≠0 and ∂f(0)=[−1,1]. Also, we know (from purely algebraic considerations) that f attains a global ...


0

Most of the times it depends on the signal under consideration. E.g. Images PSNR for recovery or denoising. SSIM for structural similarity in segmentation problem. Edginess inrange image super-resolution. Speech PESQ objective scores. MOS subjective score or listener's test WER word error rate in reconstructed speech. ECG, EEG ...


1

For the first equation $(A - xc^t) x = 0$: If $x$ is a solution of that equation, then we have $$ Ax = x (c^t x). $$ Apart from the trivial solution $x=0$, $x$ needs to be an eigenvector of $A$ and $c^t x$ the corresponding eigenvalue. Let $v$ be an eigenvector to eigenvalue $\lambda$. Then, we have $$ Av = \lambda v = (c^t v) v. $$ So $x = ...


1

Consider $f(x) = \frac12 x^2$ for $x\in\mathbb R$, $q=0$, $p=1$, $w = -1$. Then, we have $(w-q)(w-p) = -1(-2) = 2 \ge 0$ and $f'(1)(-2) = -2 < 0$.


0

Consider the function $f(x,y) = xy$ on $(-\infty,0)$. Then, $f$ is concave (in fact linear) and decreasing in each variable. However, the Hessian of $f$ is indefinite.


2

The answer is no. The reason for that is that the matrix $J^HJ$ is not the Hessian, but an approximation of it. Look at the following one-dimensional example: given constant $y$, solve $\min f(x)$ where $$ f(x)=\left\|\left[\matrix{y_1\\y_2}\right]-\left[\matrix{\cos(x)\\ \sin(x)}\right]\right\|^2. $$ Here $$ J=\left[\matrix{\sin(x)\\ -\cos(x)}\right],\qquad ...


2

The go-to method for attacking your problem is the ADMM (Alternating Directions Method of Multipliers). Your can learn ADMM here. For a more in-dept theory, see Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming 55 (1992) Glowinski, R., Marroco, ...


2

The point of lower semicontinuity (or something like it) is that were it to fail, there's no guarantee that $f(x^\ast)$ has the right value. For example think about what goes wrong in the following: consider $X=[-2,2]$ and the function $f$ which takes $x$ to $-x$ for $x<0$ and takes $x$ to $x+1$ to $x\geq 0$. Take a minimizing sequence $x_n\in[-2,2]$ ...


0

Indeed for any $x$, we have $\nabla \hat{f}(x) = \nabla f(x) + w$ and so $\|\nabla f(x) - \nabla \hat{f}(x)\| = \|-w\| = \|w\|$.


0

I have used such things before in work I've done. We get: \begin{align} &\sum_{t=1}^T \frac{1}{\sqrt{t}}(||x_t-a||^2 - ||x_{t+1}-a||^2) \\ &= ||x_1-a||^2 - \frac{1}{\sqrt{T}}||x_{T+1}-a||^2 + \sum_{t=2}^{T}||x_t-a||^2\left(\frac{1}{\sqrt{t}}-\frac{1}{\sqrt{t-1}}\right) \\ &\leq ||x_1-a||^2 - \frac{1}{\sqrt{T}}||x_{T+1}-a||^2 \end{align}


0

Generally you can solve any problem of the kind \begin{equation} \min f(x) + g(x) \end{equation} where $f$ is a lipschitz-differentiable convex function and $g$ is just a convex function by using proximal gradient descent (that's already the algorithm you're using. https://web.stanford.edu/~boyd/papers/prox_algs.html for details). $\mathcal{L}_\lambda$ is ...


3

Given that an arbitrary regular curve $\gamma$ can be parametrized by arc length, there's no hope of deducing convexity of the arc length function $$ s(t) = \int_{a}^{t} \|\gamma'\| $$ from the shape of the curve. Convexity of the arc length function depends entirely on the parametrization. In particular, convexity of a curve can have no bearing on ...


0

The general way to compute the proximal to function f is to calculate $$ Prox_{f}(x) = \arg\min_y f(y) + \frac{1}{2} ||x-y||^2 $$ The indicator function in convex optimization takes 0 inside and $+\infty$ outside. Thus in your case, the constraint must be satisfied to get the min. The problem is equivalent to $$ Prox_{c}(x) = \arg\min_{y,\ Ay=b} ...


0

Convexity is the exception, rather than the rule. If everything isn't just so in a mathematical program, it is very likely non-convex. In practice, if you did not build your model with convexity in mind from the outset, the likelihood that you will arrive at a convex result is nearly zero. For this specific example, the nonlinear equality constraint ...


0

The Renyi divergence is a family of quantities of which the relative entropy $D(P\|Q)$ is a special case when $\alpha = 1$. The identities you listed involve the entropy and relative entropy of random variables $X$ and $Y$. For example, your first identity is: \begin{align} D(P_{Y \vert X} \vert \vert Q_{Y \vert X } \vert P_X ) &= \sum_x P_X(x) ...


0

First if $\partial f(\bar{x})=0$ you have a necessary and sufficient condition for $\bar{x}$ to be a minimum of f and you satisfy your relation. The line $⟨w,y−x¯⟩≥0, ∀y∈C$ means that in C there is no descent direction for the function f. If this relation is not respected then it means there exists an $x \in C$ such that f decrease strictly which ...


0

This code is not suitable for Matlab. You should vectorize your code. For loops on a high level are extremely slow in Matlab.


0

Since every vertex of $P$ is basic feasible solution and vice versa, a non-degenerate vertex has exactly $m(n-m)$ adjacent vertices. I don't know what gave you the idea that this number is $n$, but this is simply not the case.


1

Since you seem to be unclear about the $f$ part of the energy / cost-function, I'll ignore it ($f \equiv 0$) in what follows. Also, since I imagine you're going to implement this on an actual computer, let's forget the integral, etc., and consider the discretization. The TV semi-norm can then be written as \begin{eqnarray} \begin{split} TV(x) &:= ...


1

(Because the question changed ( $\frac{e^x}{1-e^x}$ became $\frac{e^x}{1+e^x}$), i decided to write another answer) It is still not convex. Your calculations for $n=2$ are correct, but e.g. for $n=3$ it is not correct, here is another counterexample (again, calculated by hand): Take $a=(\ln(\frac{1}{2}),\ln(\frac{1}{5}),0)$,$b=(\ln(\frac{1}{5}), ...


1

This should help. It is always a good idea to plot. Note : $1$-dimensional convex sets are subsets of lines. You don't expect something having to do with exponentials to be a line segment (a priori it could have been, but your first guess should be no).


2

It is not a convex set. I have the following counterexample for $n=2$ (calculated by hand, so it might be wrong): Take $a=(\ln(\frac{1}{4}),\ln(\frac{2}{5}))$,$b=(\ln(\frac{2}{5}), \ln(\frac{1}{4}))$. This gives us $\frac{1}{2}(a+b) = (\frac{1}{2}\ln(\frac{1}{10}),\frac{1}{2}\ln(\frac{1}{10}))$ We have $a,b \in S$ but $\frac{1}{2}(a+b) \notin S$


0

With an eight month delay: Let me first state that I'm not a pro and a self-student myself which might ease our conversation. What I noted is that we seem to use different definitions of the linear independence constraint qualification. Nocedal/Wright's Numerical Optimization (1999, 1E) states in Definition 12.1 (LICQ). Given the point $x^*$ and the ...


0

You can rephrase $\| Q - H \|_\infty$ using additional dummy variables and constraints, and turn the problem into a linear semidefinite program. Just use following the tricks For $x\in\mathbb R, u, v \ge 0$ with $x = u - v$ it follows $|x| \le u+v$. The equality holds if $u$ or $v$ is zero. Instead of minimize $\max\{x,y\}$, minimize $z$ with $x \le z$ ...


0

Well, here's one way to do it. Let $A_{i2}$ and $b_{i2}$ denote the $i$th row of $A_2$ and $i$th element of $b_2$, respectively. Then solve $m$ linear programs: $$\begin{array}{ll} \text{minimize} & A_{i2}^T x - b_{i2} \\ \text{subject to} & A_1 x \geq b_1 \end{array} \qquad i=1,2,\dots, m$$ If any of these have a negative objective, including ...


0

Yes, you could solve this using some proximal algorithm such as the Douglas-Rachford method. Let $C = \{ (A,x) \mid D = A + Mx \}$, and let $I_C$ be the indicator function of $C$: \begin{equation} I_C(A,x) = \begin{cases} 0 & \text{if } D = A + Mx, \\ \infty & \text{otherwise.} \end{cases} \end{equation} Your problem can be restated as ...


3

A not so elegant way would be to determine the vertices of $P_1$ and plug them into the constraints for $P_2$, if each vertex satisfies the $P_2$ constraints, then by convexity, so does the entire polyhedron.


0

I propose solving your problem iteratively using the primal-dual algorithm of Chambolle & Pock (more precisely, Algorithms 1 & 2 of the paper). This is also an opportunity to familiarize the reader with primal-dual & proximal algorithms, a contemporary technology which is apparently not yet quite popular. Relaxed asumptions. You only need to ...


1

This is answered by the sensitivity interpretation of the Lagrange multipliers. (Linear programming books or convex optimization books should discuss the sensitivity interpretation.) If $\lambda$ is a Lagrange multiplier for the constraint $Ax = b$, then $-\lambda$ is a subgradient of $f$ at $b$.



Top 50 recent answers are included