# Tag Info

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 ...

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 c$ would 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 ...

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 ...

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$ ...

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 ...

2

To get to know this set, we express the norms using inner products. $$\|x-x_0\|\le\|x-x_1\| \Leftrightarrow \|x-x_0\|^2\le\|x-x_1\|^2 \Leftrightarrow \langle x-x_0, x-x_0 \rangle\le \langle x-x_1,x-x_1\rangle.$$ We have $$\langle x-x_0, x-x_0\rangle = \langle x,x\rangle - 2\langle x,x_0\rangle + \langle x_0,x_0\rangle,$$ thus our inequality becomes $$... 1 Since the hessian is positive semidefinite for all x, the function is convex (though not strictly convex). So the stationary point is a minimum, and a global minimum in fact (by convexity). Think of it this way - the function is increasing in the direction of the eigenvector with eigenvalue 5, and flat in the direction of the eigenvector with eigenvalue 0. ... 1 Yes, those are two different problems, which very likely two different optimal points x. Your post title is deceiving, really: you're not asking about the difference between f(x) and g(f(x)), the scalar case. In that case, there would be no difference. The sum changes things. If the expressions g_k(x) are all positive (all \geq -1, actually), ... 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 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 ... 1 Notice$$\|x-x_0\|\le\|x-x_1\| \iff \|x-x_1\|^2 - \|x-x_0\|^2 \ge 0$$and the quadratic term in the LHS of last expression cancel each other. We find$$S = \big\{\; x \in \mathbb{R}^n : 2 (x_0 - x_1) \cdot x + \|x_1\|^2 - \|x_0\|^2 \ge 0\;\big\}$$This is the equation of a half-space. 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 ... 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 ... 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 ... 1 If you know that \sigma = \min f(\mathbf{x}) subject to \mathbf{x}\in Cand 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 ... 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 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 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 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 ... 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 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 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 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 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 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 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 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 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 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 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$:

Only top voted, non community-wiki answers of a minimum length are eligible