Tag Info

Hot answers tagged convex-optimization

4

If the hessian is positive semidefinite, and $x_1,x_2\in C$, we want to show that $f(tx_1 + (1-t)x_2) \leq tf(x_1) + (1-t)f(x_2)$. Consider $g(t) = f(tx_1 + (1-t)x_2)$. Write the condition you want to prove of $f$ in terms of $g$. Now, Can you find the second derivative of $g(t)$? Use the fact that the hessian is positive semidefinite to show that ...

3

Well silly me, I think I've found a decent explanation. First note that $$g(\overline{x},\overline{y}) \leq \sup_{y \in Y}g(\overline{x},y)$$ for all $\overline{x} \in X$ and $\overline{y} \in Y$. Then take the infimum wrt $X$ on both sides, giving $$\inf_{x \in X}g(x,\overline{y}) \leq \inf_{x \in X}\sup_{y \in Y}g(x,y)$$ which now holds for all ...

3

We have $dom\ f = (0,\infty),$ and for any $\alpha \in\mathbb R$ $$x\in\ dom\ f\ and\ f(x) \leq \alpha \Leftrightarrow x \ge e^{-\alpha} \Leftrightarrow x \in [e^{-\alpha},\infty).$$ Now, the set $[e^{-\alpha},\infty)$ is closed, so $f$ is a closed function, according to the definition.

3

It's closed. It's level sets are of the form $[b, \infty[$ and hence, closed.

2

As stated, the problem might have no solutions at all. If the constraint would be replaced by $\|D\|\le 1$ then there is at least one solution. If $n>1$ then the problem never has a unique solution. Let $D_1$ be such at solution. Then there are plenty other matrices $D$ such that $Da = D_1a$ and $\|D\|\le1$, hence $D$ is also a solution. Hence, the ...

2

I guess that $\mu_i\geq 0$ for all $i$. You can reformulate the problem as $$\max \sum_{i=1}^n \log( y_i )\\ s.t.\\ y_i = x_i\cdot \mu_i \quad i=1,\ldots,n\\ \sum_{j=1}^k \mu_i = 1\\ \mu_i \ge 0 \quad i=1,\ldots,n$$ Assuming that $x_i$ are such that $y_i\geq 0$ for all $i$, this is a convex problem you can solve with a standard optimizer.

2

You've already said it: $b-Ax=0$. So each term of $y \circ (b-Ax)$ is zero because the right-hand side is always zero. Technically speaking, the term "complementary slackness" is not used to refer to the equality constraints $Ax=b$ and their Lagrange multipliers $y$. There is nothing "slack" about them: even the slightest perturbation $b$ will render $x$ ...

2

You need the Matrix Cookbook. But honestly, it is not that difficult to derive this particular case by looking at each element: $$\frac{\partial L}{\partial a_i} = \frac{\partial}{\partial a_i}\sum_{j=1}^n(b_j-a_j)^2 = 2(b_i-a_i)\cdot -1 = -2(b_i-a_i).$$ From here, you simply have $$\frac{\partial L}{\partial \mathbf{a}} = \begin{bmatrix} \frac{\partial ... 2 A=[0,1] and B=(1,2] are convex. f(x)=0 for x \neq 1 and  f(1)=1. What do you think of this case? 2 I assume the following meaning of "coercive": An extended valued map f : X \to [-\infty,+\infty] is coercive if whenever \|x\|\to+\infty, f(x)\to+\infty. Here, the set of functions is called F. The set C of coercive functions do not form a linear space, because if f(x) is coercive, -f(x) is not coercive. Moreover, we can come across ... 2 The set H(A,B) is the set of all affine hyperplanes separating A and B; not just those that pass through the origin. To prove it's a convex cone, assume (w_i,d_i)\in H(A,B) for each i, and take linear combination with nonnegative coefficients \alpha_i. The pair$$\left( \sum_i \alpha_i w_i, \sum_i \alpha_i d_i \right)$$belongs to H(A,B), ... 2 This problem is not convex and therefore cannot be represented as an SOCP. However, it is possible to appriximate it using the convex-concave procedure, as described here. To summarize, you replace your constraint ||Dx||_2 = g by two constraints: ||Dx|| \le g, which is convex ||Dx|| \ge g, which is nonconvex You solve a sequence of SOCP problems, ... 2 By considering \| \cdot\| the 2-norm, the Hessian is given by H = \left [ \begin{array}{cc} \frac{\partial^2 f(x_1,x_2)}{\partial x_1^2} + \lambda & \frac{\partial^2 f(x_1,x_2)}{\partial x_1 \partial x_2} \\ \frac{\partial^2 f(x_1,x_2)}{\partial x_2 \partial x_1}& \frac{\partial^2 f(x_1,x_2)}{\partial x_2^2} + \lambda\\ ... 2 For an unbounded set, f(x)=x in \mathbb{R}. For a non-closed set, f(x)=1/x in (0,1) 2 An equivalent definition is \|x\|_C = \inf \{ t>0 | {x \over t } \in C \}. This is a little more convenient here. Let C = \bar{B}(0,1), with the \|\cdot\|_p norm. If \|x\|_p \le t, then {x \over t} \in C, and so \|x\|_C \le t. If \|x\|_p > t, then for some \epsilon>0 we have \|x\|_p > t+\epsilon. Then \|{x \over s} \|_p ... 2 First, a disclaimer: I'm not sure I see the statistical validity of combining both linear and logistic regression with the same measurement vectors x_n. I am going to assume you know what you are doing :-) and address the optimization question only. Some quick and dirty approaches: My Matlab toolbox CVX 2.1 can handle this, although with a caveat ... 2 I think it is not. The two constraints in the OR relation can make the space non-convex (e.g. for a single variable x: f(x) = x + 1, g(x) = -x - 1, then the two parts are even disjoint so it cannot be convex). However, you can solve the problem first using only the first constraint, then using only the other constraint and then you choose the better ... 1 Yes. Wlog. c\ne 0. If x_0 is an optimal solution, then the hyperplane c^Tx=c^Tx_0 intersects the solution space in a convex polyhedron. This polyhedron has a vertex x_1 (if if the polygon happens to be unbounded). If x_1 is not a vertex of the original polyhedron, then there is a line segment through x_1 that has points on both "sides" of the ... 1 I would suggest an alternating minimization approach. Define two matrices:$$W_x \triangleq \begin{bmatrix} \sqrt{\lambda_1}V^{(1)} \\ \sqrt{\lambda_2}V^{(2)} \end{bmatrix}, \quad W_y \triangleq \begin{bmatrix} \sqrt{\lambda_1}V^{(1)} & \sqrt{\lambda_2}V^{(2)} \end{bmatrix}$$Let x_0 be a right singular vector associated with the minimum singular ... 1 \partial f(x) = \{ h | f(y) - f(x) \ge \langle h, y-x \rangle \ \forall y\}. It is straightforward to see that D_y = \{ h | f(y) - f(x) \ge \langle h, y-x \rangle \} is a closed half space, hence convex. Since \partial f(x) = \cap_y D_y, we see that \partial f(x) is closed and convex. If f is finite on some open set U containing x, then ... 1 1) Let a,b\in F(C), let show that ta+(1-b)t\in F(C) for all t\in[0,1]. We have that a=F(x)=L(x)+b and b=F(y)=L(y)+b for certain x,y\in C. By linearity of L,$$at+(1-t)b=tF(x)+(1-t)F(y)=tL(x)+(1-t)L(y)+tb+(1-t)b=L(tx+(1-t)y)+b=F(tx+(1-t)y)$$But C is convexe, therefore tx+(1-t)y\in C and thus at+(1-t)b\in F(C). We conclude that F(C) is ... 1 The set of coercive functions is not a linear space, because -f is not coercive, if f is coercive. So one don't get inverse elements of addition. No its not conical because t \geq 0 and not t>0 so you can choose t=0 and so tf is not in the cone. It is convex. Take the convex combination \lambda f +(1-\lambda)g. So the coefficients are ... 1 Ah sorry you're right. Replace g(x) by g(x)=-x^4. I understand the test in that way, that one has to consider f+g if g is bounded from above. f cannot be bounded from above by coerciveness. Edit: I wanted to post it under your comment. 1 Suppose A is affine, and let \{x_n\}_n, \{y_n\}_n be two sequences in V(A). Then x_n \to x \in A and y_n \to y \in A, so since A is affine, the set \{ \lambda x + (1-\lambda) y \, | \, \lambda \in \mathbb R \} is contained in A, and in particular the sequence \lambda x_n + (1-\lambda) y_n converges to \lambda x + (1-\lambda)y, so \{ ... 1 A convex set is equal to the intersection of all half-spaces that contain it. Every half-plane can be written as H(r,x):=\{z:\ r\geq\langle x,z\rangle\}, for some r and some x. Moving r parallel translates the boundary of the half-space. If H(r,x) contains the set A then$$A\subset H(\sigma_A(x),x)\subset H(r,x).Therefore if C is convex ... 1 You can also use the orthogonal projection to show \sigma_C\equiv\sigma_D \Rightarrow C=D (the other implication is trivial...). To do this fix a point c\in C. Since D is closed and convex, there exists the orthogonal projection of c onto D, i.e. there is some d\in D such that \begin{align*} \langle c-d,x-d\rangle\leq0\qquad\forall x\in D. ... 1 In this case I is an index set. For example, you could take I = \{1,2,3\}, I = \mathbb{N}, or even I = \mathbb{R}. Your set of functions is then going to be \{g_1, g_2, g_3\}, \{g_1,g_2, g_3, g_4, \dotsc\}, or \{g_i: i\in\mathbb{R}\} respectively (unfortunately there is no better way to write the last set since we can't count off real ... 1 Here's the TL;DR version, for your specific example. The Lagrangian isL(X,Z) = f(X) - \langle Z, K - XX^T \rangle$$where the inner product is the simple elementwise inner product, and the Lagrange multiplier Z is positive semidefinite. A more general discussion: the Lagrangian looks like this:$$L(x,\lambda) = f(x) - \langle \lambda, c - g(x)\rangle ...

1

Hint: if $x_n \to x$ and $y_n \to y$, what about $t x_n + (1-t) y_n$?

1

I found the relevant proofs in Appendix B (p. 1082) of: http://www.math.uwaterloo.ca/~cswamy/courses/co759/approx-material/ellipsoid-survey.pdf Which was a reference in the paper posted by Michael Grant. Interestingly, it proves the bounding ellipsoid update formulas for more general cases than my question asked. I.e. for different parameters of alpha the ...

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