# Tag Info

1

As I said in my comment, in a convex optimization setting, one would normally not use the derivative/subgradient of the nuclear norm function. It is, after all, nondifferentiable, and as such cannot be used in standard descent approaches (though I suspect some people have probably applied semismooth methods to it). Here are two alternate approaches for ...

1

It is the quadratic term in $\gamma$ and $\alpha$ inside that first norm that makes it non-convex. It is convex separately in $\alpha$ and $\gamma$, just not jointly.

1

Yes, it is. Note that your problem is completely decoupled. That is, you're really solving $n$ separate scalar optimization problems:$$\begin{array}{ll}\text{minimize} & x_i^2+c_ix_i \\ \text{subject to} & x^{\min}_i \leq x \leq x^{\max}_i\end{array}$$ Note also that $x_i^2+c_ix_i=(x_i+c_i/2)^2-c_i^2/4$. Dropping the constant and then taking the ...

2

Start with the SVD decomposition of $x$: $$x=U\Sigma V^T$$ Then $$\|x\|_*=tr(\sqrt{x^Tx})=tr(\sqrt{(U\Sigma V^T)^T(U\Sigma V^T)})$$ $$\Rightarrow \|x\|_*=tr(\sqrt{V\Sigma U^T U\Sigma V^T})=tr(\sqrt{V\Sigma^2V^T})$$ By circularity of trace: $$\Rightarrow \|x\|_*=tr(\sqrt{V^TV\Sigma^2})=tr(\sqrt{V^TV\Sigma^2})=tr(\sqrt{\Sigma^2})=tr(|\Sigma|)$$ where ...

0

Not assuming convexity, you will have to test each possibility. Given your point $p$ and the locations of each vertex $v_i \in V$, you want the vertex with minimum distance from $p$ (not unique). Let $dist(p,v_i)$ be a function that gives the distance from $p$ to $v_i$. The pseudo code for this is: $v_{min} = v_1$ $d_{min} = dist(p,v_1)$ for $v_i \in ... 0 Charles Crawford, Algorithm 646: PDFIND: a routine to find a positive definite linear combination of two real symmetric matrices, ACM Transactions on Mathematical Software (TOMS), Volume 12, Issue 3, September 1986. Abstract: PDFIND is a FORTRAN-77 implementation of an algorithm that finds a positive definite linear combination of two symmetric matrices, ... 1 Twice differentiable function is convex on a convex set if and only if its Hessian matrix is positive semidefinite on the interior of the convex set. You can use Sylvester’s criterion to check the positive semidefiniteness: $$\begin{cases} a \ge 0, \\ ab - b^2 \ge 0, \\ abc - b^2c-c^2b \ge 0. \end{cases}$$ Using your conditions$a, b, c > 0$we get ... 1 First of all: I would argue that what you are asking for is not a function of$x^*$and$\gamma$, but in fact just$\gamma$. After all,$x^*$depends on$\gamma$. So in fact, the function is just$\text{OPT}(\gamma)$. In general, even if you assume linearity or concavity in the$f_i$functions, you cannot solve this problem analytically. For a given ... 1 Start with the simple case of$U \subset \mathbb{R}$. If$U$is a single interval and$f: U \to \mathbb{R}$satisfies$f'(x) = 0$, do you see why$f$must be constant? If$U$has multiple connected components, do you see why$f$does not have to be a constant function? Now, in the case$U \subset \mathbb{R}^n$, apply the above results to$f$restricted to ... 1 Basically, just plug everything in. Assume we have that $$\bar{x} \in \arg\min_x\{ \frac{1}{2}\|Ax-b\|^2\}$$ and we have$\tilde{x} \in Null(A)$. Then, $$\frac{1}{2}\|A(\bar{x}+\tilde{x})-b\|=\frac{1}{2}\|A\bar{x} + A\tilde{x} -b\| = \frac{1}{2} \|A\bar{x}-b\|.$$ Here, we used the linearity of$A$and the assumption that$\tilde{x}\in Null(A)$. ... 1 I believe this problem is unbounded. Let$\alpha_2=\alpha_3=0$. Then, your objective function reduces to: $$\alpha_1+\alpha_4−2\alpha_4^2$$ and your constraint reduces to $$\alpha_1-\alpha_4 = 0.$$ Note, since$\alpha_2=\alpha_3=0$we also have$\alpha_2\geq 0$and$\alpha_3\geq 0$. Now, set$\alpha_1=\alpha_4$and let both go to infinity. We ... 0 I'll attempt to explain the intuition here. There may be many affine minorants of$h$with a given slope$y, but we only care about the best one: \begin{align} &h(x) \geq \langle y , x \rangle - \alpha \quad \text{for all } x \\ \iff & \alpha \geq \langle y, x \rangle - h(x) \quad \text{for all } x \\ \iff & \alpha \geq \sup_x \, \langle y, x ... 1 This is a partial answer (as I do not have the time to work it out to completion): Eliminate\alpha_4$using the constraint in the form of an equality but add a new inequality$\alpha_1+\alpha_2-\alpha_3\geq 0$that replaces$\alpha_4\geq0$. Call the function$Q(\alpha)$after the elimination of$\alpha_4$,$P(\alpha)$. The problem now reduces to ... 1 Any smooth function can be decomposed into a difference of convex functions. In this case, the following should work. We want$f(x)=g(x)-h(x)$, where$g$and$h$are the convex functions. Since$f$is convex for$x < \sqrt{2 \alpha}$, and concave for$x > \sqrt {2\alpha}$, we can let$g=f$for$x < \sqrt{2 \alpha}$, and$g$be linear for$x > ...

1

Generally speaking: $$||\cdot||:\mathbb{R^n}\rightarrow\mathbb{R}^+,$$ And therefore the minimum of $||x||$ is when $x=0$. Thus, yes, you found out that: $$\min_{b\in\mathbb{R^n}}||x-b||=0,$$ i.e. $b=x$.

1

If you know that $\sigma = \min f(\mathbf{x})$ subject to $\mathbf{x}\in C$and you want to want to minimize $g(\mathbf{x})$ for all such $\mathbf{x}$, I think all you have to do is $$\min_{\mathbf{x}} g(\mathbf{x}) \;\;\; \mathrm{s.t.} \;\;\; f(\mathbf{x})=\sigma \wedge \mathbf{x} \in C.$$ So, if you can solve the original problem and get the minimum ...

0

No, this is not possible. The easiest counterexample is $$\text{Minimize } x^2 \text{ s.t. } -1 = -x^2$$ with minimum $1$ and the relaxation would be $$\text{Minimize } x^2 \text{ s.t. } -1 \le -x^2$$ with minimum $0$.

0

Here is the gist of part 2. Let me know if you have any questions. Let $x_1, x_2 \in C_2$. Then as $g$ convex over $C_2$ this implies that $$g(tx_1 +(1-t)x_2) \le tg(x_1) + (1-t)g(x_2) \le 0$$ as $x_1,x_2\in C_2$ where $t\in [0,1]$ implying that $tx_1 + (1-t)x_2 \in C_2$ and thus $C_2$ is convex. Part 3 is very similar to part 1 and 2. Let $x_1, x_2 \in ... 2 This is not a convex optimization problem as written, because$x^Hx=c$is not a convex constraint. It describes the surface of a hypersphere, which is not convex. The constraint$x^Hx\leq cwould be convex, on the other hand. If that relaxation is acceptable to you, then just solve that instead; it's a simple quadratic program. If you need equality, then ... 7 $$e^{tx} = e^{tx+(1-x)0} \leq xe^t + (1-x)e^0,$$ by convexity. 0 A convex function has an increasing derivative and we can write any function of bounded variation as a difference of two increasing functions. So let us look at the derivative \begin{align} \frac{\mathrm{d}}{\mathrm{d}x}\frac1{1+e^{-x}} &=\frac{e^{-x}}{(1+e^{-x})^2}\\ &=\frac1{(e^{x/2}+e^{-x/2})^2}\\ &=\tfrac14\,\mathrm{sech}^2(x/2) ... 1 A different approach. If f is any function with continuous second derivative let f''_+=\max(f'',0)\quad f''_-=-\min(f'',0). $$Then f''_+ and f''_- are continuous, non-negative and f''=f''_+-f''_-. Now let F_+ and F_- be such that F_+''=f''_+ and F_-''=f''_-. F_+ and F_- are convex, and the constants of integration can be chosen so ... 2$$ \frac{d^2}{dx^2} (1+e^x)^{-1} = \frac{d}{dx} \left(-(1+e^x)^{-2}e^x\right) = e^x\left( -(1+e^x)^{-2}+2(1+e^x)^{-3}e^x \right)  = \frac{e^x (-(1+e^x)+2e^x)}{(1+e^x)^3} = \frac{ e^x(e^x-1) }{(1+e^x)^3}. $$This is a bounded function because it is everywhere continuous and goes to 0 as x\to\pm\infty. So let f(x) = Ax^2 + \dfrac{1}{1+e^x} with A ... 1 I think you need to broaden your definition of a "function" a bit. When you fix a weight vector w and solve the resulting weighted least squares problem, you will obtain a particular value of the cost function \inf_x \sum_i w_i(a_i^Tx-b_i)^2. Let's call that value g. Sure, you'll also get a vector x out of it, but just ignore it for now. Now, if ... 1 g\left(\omega\right) is not the cost function here. g\left(\omega\right) is the infimal value of this special cost function depending on omega: \sum_{i}\omega_{i}\left(a_{i}^{T}x-b_{i}\right)^{2}. This defines a mapping g:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\left\{-\infty\right\}. The set of all points where g is not infinity, we call ... 1 Yes, the primal optimal value is \inf_x \sup_{\lambda \geq 0} L(x,\lambda) and the dual optimal value is \sup_{\lambda \geq 0} \inf_x L(x,\lambda). A primal and dual optimal pair of variables gives you a saddle point of the Lagrangian. This is discussed on p. 238 (section 5.4.1) of Boyd and Vandenberghe, and is also discussed in other convex ... 1 In convex geometry, a supporting line or supporting hyperplane of a convex set C is an affine co-dimension-1 subspace \{y:a^Ty=b\} outside of C that touches C in some point or larger facet, i.e., so that a^TC\le b with equality assumed at least once. From there it is just a twist of thought to compute the constant as b=\sup a^TC and formalize ... 1 Suppose you are given f, and have a candidate function g that might be equal to f^* (the the fenchel conjugate of f), but you're not sure. You can try checking numerically that:$$f(x) + g(y) \ge \langle x,y\rangle$$for various values of x,y. Any counterexample to the inequality is certificate that g \ne f^*. To prove that g=f^*, you need to ... 1 The function \psi(z)= \max(z_1,z_2) is convex, and a convex function satisfies \psi(\theta w+ (1-\theta) z) \le \theta \psi(w)+ (1-\theta) \psi(z) for all \theta \in [0,1]. Letting w=f_1(x), z=f_2(x) gives the desired result. Note: To see why the \max is convex, suppose the functions f_1,f_2 are convex. Then we have (with \lambda \in [0,1]) ... 1 The property in use is$$\max\{a+b, c+d\}\le \max\{a,c\}+\max\{b,d\}$$Proof: a+b\le \max\{a,c\}+b\le \max\{a,c\}+\max\{b,d\}. Similarly c+d\le \max\{a,c\}+\max\{b,d\}. 0 1.\rightarrow. Assume that C_1 is convex. Then by definition$$\sum_{i=1}^{n}\lambda_ix_i \in C_1,$$for all x_i \in C_1 and nonnegative numbers \lambda_1,\ldots,\lambda_n such that \sum \lambda_i=1. Then$$h\big(\sum_{i=1}^{n}\lambda_ix_i\big)=0=\sum_{i=1}^{n}\lambda_ih(x_i),$$where both sides are equal to zero due to the definition of C_1 ... 0 Proof: Let (h^n) \in T_S, where h^n \to h; then we have \bar{x} + \lambda^n h^n \in S for some (\lambda^n) \geq 0. Now consider \gamma \geq 0, then notice that \bar{x} + (\lambda^n/\gamma) \gamma h^n \in S, implying that (\gamma h^n )\in T_S. But by definition, T_S is closed, and hence \gamma h \in T proving the statement. So it was a ... 2$$x\mapsto|x|+x^2{}{}{}{}{}{}0 It is known that the equivalence (1)\iff (2) characterizes inner product spaces. Namely, a parallelogram law holds iff a norm is strongly convex with modulus 1. 1 Yes, that's true. It follows easily from two simple facts: 1) For \|x\|=\|y\|=1, x^TAy is bounded from above by the maximal singular value of A. If \|x\|=\|y\|=1, then x^TAy\leq\|x\|\|Ay\|\leq\|x\|\|A\|\|y\|=\|A\|=\sigma_1. 2) x^TAy=\sigma_1 for some x and y such that \|x\|=\|y\|=1. Let A=USV^T be the SVD with the singular values in ... 0 Here's one way to derive the augmented Lagrangian method. We use the proximal point method to solve the dual problem. (In the derivation we freely use some basic facts about subgradients, conjugates, and prox operators which are discussed in convex optimization theory or in convex analysis.) Consider the problem \begin{align*} \operatorname*{minimize}_x ... 1 The singular values of A are the eigenvalues of the symmetric matrix\begin{bmatrix}0&A\\A^T&0\end{bmatrix}$$Following your first insight, this would mean that the largest eigenvalue can be characterized by$$\max_{\|x\|^2+\|y\|^2\le 1} 2x^TAy$$The set of vectors (x,y) with \|x\|\le 1 and \|y\|\le1 is strictly larger than the unit ... 2 At some point, you have to decide when you make the leap from the theoretical to the practical. As long as you're staying theoretical, it really doesn't matter how many equality constraints you have. Sure, it's O((m+n)^2), but the point of the theoretical exercise is to demonstrate that the problem is representable by semidefinite programming. It frankly ... 0 It's general fact that a convex compact closed set in a Hausdorff locally convex topological vector space is generated by its extreme points, this is Krein-Milman theorem. In particular, your X has to contain all the extreme points of Q, this is by the very definition of extreme points. Now the extreme points for a face( considered as a convex set) is the ... 2 What kinds of operations are may we assume are permissible? I mean, to be perfectly honest, this seems evident, since$$\|\Sigma^{1/2} x\|_2=\sqrt{\|\Sigma^{1/2}x\|_2^2}=\sqrt{\langle\Sigma^{1/2}x,\Sigma^{1/2}x \rangle} =\sqrt{x^T\Sigma^{1/2}\Sigma^{1/2}x}=\sqrt{x^T\Sigma x}.$$But of course, this assumes you accept the definition of a symmetric matrix square ... 1 It is neither convex nor concave, but it is quasiconcave. See my answer to your other question for more information, or go straight to Boyd & Vandenberghe. The good news is that fixed lower bounds on the ratio can be represented in convex optimization problems; since, after all,$$g(x)/a(x) \geq \alpha \quad\Longleftrightarrow\quad g(x) \geq \alpha ... 0 In many cases, the ratio of a concave and a convex function is quasiconcave. Quasiconcavity and quasiconvexity are discussed in, e.g., Boyd & Vandenberghe; consult them for details. A functionf$is quasiconvex if its superlevel sets$\{x\,|\,f(x)\leq\alpha\}$are convex for all fixed$\alpha$; a function$g$is quasiconcave if its sublevel sets ... 1 If$x=(x_1,\dots,x_n)\in\mathbb{R}^n$,$x_k>0$, then $$\frac{g(x)}{f(x)}=n\frac{(x_1\dotsm x_n)^{1/n}}{x_1+\dots+x_n}.$$ Fix$x_2=\dots=x_n=1$. It is easy to see that the resulting function $$n\frac{x_1^{1/n}}{x_1+n-1}$$ is neither concave nor convex, implying the same for$g(x)/a(x)$. Graph of$h(x,y)$for$0<x<1$and$0<y<10$: 2 There is no general rule. Let$f(x)=1$; then$f$is both concave and convex. Let$g(x)=e^{x^2}$, which is convex. However $$\frac{f(x)}{g(x)}=e^{-x^2}$$ is neither concave nor convex. 0 The answer is of course yes since your function is a sum of functions of the form$ r^{-x}$(which is convex for$x>0$) composed with the linear function$x_i + x_{i+1}$. But convex composed with linear is convex, and that completes the proof. 0 I will give an (confirmatory) answer for the following precision of the question. Then the OP can decide if that is what he meant. Let $$f \colon D \rightarrow \mathbb{R}$$ be a convex function where$ D \subset \mathbb{R}^{m\times n}$is a convex function from some convex subset of the set of all real$m\times n$-matrices into$\mathbb{R}$. We can ... 0 No, for example consider$S_1=\{1,3\}$,$S_2=\{2\}$. The intersection is empty, and the intersection of convex hulls is$S_2$. 2 The answer is no. For example the following two subsets of the plane 1 I do not think it is possible to fully answer your question without more information about the algorithm and the particular set of "certain" positive semidefinite matrices you are considering. In other words, what are the constraints on$A$other than semidefiniteness? Still, there are several things that can be said. First: your solution$A_\infty$is ... 1 My preference is to build the Lagrangian right from the original problem if at all possible. Define the multipliers as follows:$v$for the equality constraint$w_p\in\mathbb{R}^n_+$for the$p$inequalities$w_t\in\mathbb{R}_+$for the$t$inequality$(y_{j,1},y_{j,2},z_j)\in\mathbb{R}^3\$ for each of the second-order cone constraints, each of which lies ...

Top 50 recent answers are included