Tag Info

New answers tagged

0

$g(x, \lambda, v)$ as a function of $x$ is convex only if $v\leq 0$ (the hessian is diagonal positive semidefinite), otherwise it has at least one negative eigenvalue. Hence for $v\nleqslant0$, $\inf_{x}g(x,\lambda,v)=-\infty$, and thus the max of $g(\lambda, v)$ must be at a point where $v\leq0$. Therefore the Lagrange relaxation and the dual of the LP ...


1

First of all, note that $$J = \mathop{\textrm{Trace}}(W^TQW), \qquad Q \triangleq \sum_{i=1}^N a X_i - b Y_i$$ Furthermore, if we break $W$ into columns, and stack them on top of each other to produce a long vector $\bar{w}$, $$W \triangleq \begin{bmatrix} w_1 & w_2 & \dots & w_N \end{bmatrix}$$ then we can express $J$ as $$J = \sum_{i=1}^N ...


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


0

It cannot be done in a convex optimization or a standard quadratic programming framework. Lower bounds on the norm are non-convex. No efficient method exists that will reliably obtain the global solution to such a problem. On the CVX Forum, a user asked a similar question here. Professor Stephen Boyd offered up an answer that is not specific to CVX, but can ...


0

In high dimensions, $X^T$ would be rank deficient and have a non-trivial kernel, ensuring the existence of $\Delta W \in null(X^T)-\{0\}$. Now plug this $\Delta W$ in Michael's illustration, and we're done.


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.


0

In general an equality constraint can be handled by using it to eliminate one of the variables (using ordinary linear algebra) before any of the clever optimization algorithms is let loose on the problem. This works well for a general optimization algorithm, but if one wants to allow your method to be specialized to a particular sparse shape of the goal ...


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


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


0

There are several definitions that come into play. Let's take $V$ - our vector space with scalar product A linear operator $A$ is called positive, if $$\forall x\in V \quad (Ax,x)>0.$$ A linear operator $A$ is called positive definite, if there exists a positive constant such that $$\forall x\in V \quad (Ax,x)\ge c \|x\|^2.$$ Let $B$ be a bilinear form ...


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


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


0

The definition of positive definite is that $x^\top A x > 0$ for all $x \neq 0$. The definition of coercive is that $x^\top A x > c\lVert x \rVert^2$ for some constant $c >0$. Obviously, coercive implies positive definite. For the reverse impliciation, I suggest thinking about $x^\top A x$ restricted to the unit sphere. What can you say about ...


2

For an unbounded set, $f(x)=x$ in $\mathbb{R}$. For a non-closed set, $f(x)=1/x$ in $(0,1)$


0

A function over an interval is said to be convex if, for all $a,b$ in the interval, the line segment joining the two points $(a,f(a))$ and $(b,f(b))$ lies above $f(x)$ for all $x \in (a,b)$. (This definition over an interval can be generalized to convex sets in a natural way.) Consider the function $f(x) = \begin{cases} (x+1)^2 & \text{if $x \leq 0$} \\ ...


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?


0

The existence of a solution follows because the set of admissible values of x,y,c and d is compact and the objective function is continuous. The uniqueness follows because the set of admissible values of x, y, c and d is convex, and the objective function is strictly concave. One has to show compactness, convexity, continuity, and strict concavity, but if ...


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


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


3

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


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.


0

Without further restrictions on $f$ this problem may have no solution. Suppose, for example, that f is strictly decreasing. Pick any values of $x$ and $y$. Then the function to be maximized strictly decreases in $c$ and $d$. Thus, the smaller $c$ and $d$ are the larger the value of the function to be maximized. Moreover, there is no lower bound on $c$ and ...


1

I do not have the proof for you, but I do have some good reading material: Martin Henk, "Löwner-John Ellipsoids", Documenta Mathematica, Extra Volume: Optimization Stories (2012), pp. 95-106. A PDF of this article can be found here. These are stable links. A discussion of Khachiyan's ellipsoid algorithm begins on page 101; at the top of this page, you will ...


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

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

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


0

Ex.1 No, your answer is not rigorous. It is true, but you need to prove it. My suggestion is to show that $$\lim_{\|(x_1,x_2)\| \to +\infty} \frac{x_1 x_2}{x_1^4+x_2^4}=0.$$ Ex.2 If $x \perp a$, then $f(x)=0$. And since on the subspace $\{a\}^\perp$ there are vectors of arbitrarily large norm... Ex. 3 If $x_1=x_2=t$, then $f(t,t)=0$ for any $t>0$. ...


0

$$f(x_1, x_2) = x_1^2 + x_2^2 - 2x_1x_2$$ is not coercive because $f(x_1,x_2) = (x_1 - x_2)^2$, meaning that $f(x,x) = 0$ no matter how large $x$ is. This means that the statement For all $M>0$, there exists a $N>0$ such that for all $x, ||x||> N$, it is true that $f(x) > M$ Is not true for this function. Similarly, for $f(x) = a^T x$, ...


1

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


0

First of all, \begin{align*} \sigma_A(x)=\sup_A\langle x, z\rangle=\sup\{\langle x,z\rangle\ |\ z\in A\}. \end{align*} To prove that $\sigma_A$ is convex, let $x,y\in\mathbb R^n$ and $t\in[0,1]$. Then \begin{align*} \sigma_A(tx+(1-t)y)&=\sup_{z\in A}\langle tx+(1-t)y,z\rangle \\ &= \sup_{z\in A}\left(t\langle x,z\rangle+(1-t)\langle y,z\rangle\right) ...


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


0

First, show that the intersection $C_1\cap C_2$ is a cone: take $\alpha\ge0$, $x\in C_1\cap C_2$. Then $x\in C_1$ and $x\in C_2$, and since both are cones $\alpha x\in C_1$ and $\alpha x\in C_2$. To prove that the intersection of $n$ cones is a cone, use induction with the above argument in the induction step. The proof for union of cones is a cone, use a ...


1

This is undoubtedly true. I'll give a proof in $\mathbb{R}^3$. Let $a \in B(x,r)$. Then we have $B(a,r_1) \subseteq \overline{C}$ for some small $r_1$. Now let $b_1 b_2 b_3 b_4$ be some tetrahedron in $B(a,r_1)$ that contains $a$ in its interior. For $i = 1, 2, 3, 4$, let $x_{i,n} \in C$ be a sequence of points tending towards $b_i$. For large enough $n$, ...


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

Note that $I(x_0, v)$ actually is an interval. Intervals are convex subsets of $\mathbb R$. The only thing you really need to show is that $I(x_0, v)$ is an interval, i.e. if $\{a,b\}\subset I(x_0, v)$, so is $(a,b) \subset I(x_0,v)$. Do you have an idea how to do that? To prove the statement you proceed in two steps: Let $I:= I(x_0, v)$. Assume ...


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


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


2

By considering $\| \cdot\|$ the $2$-norm, the Hessian is given by \begin{equation} 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\\ ...


0

Please refer to the following page for the correction of this line of code in 1leq_pd.m: http://compsens.eecs.umich.edu/sensing_tutorial.php. Once the code is updated, it works for me.


1

Here's the TL;DR version, for your specific example. The Lagrangian is $$L(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

Submodular functions act like concave function, as they share subadditivity property : A concave function f such that f(0)=0 is subadditive. A submodular function f such that f($\emptyset$) is subadditive. We can't say a submodular function is concave as by nature a submodular function is a set function. Also having a definition of concave and convex ...


1

Hints: The following lemmas are not quite difficult to prove and can be helpful. Let $A\subseteq\mathbb R^n$. Then: $A$ is a subspace $\iff$ $A$ is affine and contains $\mathbf0$. $A$ is affine $\Rightarrow$ $\mathbf{u}+A$ is affine for every $\mathbf{u}\in\mathbb R^n$.


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


0

For any norm (with respect to the definiton you are familiar with) $\Vert \cdot \Vert$ look at $C= \{ x \in \mathbb R : \Vert x \Vert \le 1 \}$ This set satisfies the 3 conditions and if you define a norm using the "new" definition and this $C$, the result is the norm you started with. Hope this helps


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


0

You are trying to solve $\min \{ f(x) | x \in C \}$, where $f(x) = {1\over 2} \|u-x\|^2$ and $C = \bar{B}(y, \epsilon)$. Since $C$ is compact, we know there is a solution $\hat{x}$. Since the Euclidean norm is strictly convex, we see that the solution is unique. Since $f$ and $C$ are convex, we have that $\hat{x}$ solves the problem iff $D f(\hat{x}) ...


1

There is a closed form solution for your problem under the following assumption: $x_i > 0, \mu_i > 0 $, for all $i$. You can rewrite $\sum_{i=1}^N \log(x_i \mu_i) = \log(\prod_{i=1}^N x_i \mu_i)$. Using this identity, it is clear that your problem is equivalent to $$ \max c \prod_{i=1}^N \mu_i~~~{\rm s.t.} ~~ \sum_{j=1}^N \mu_i = 1,$$ where $c = ...


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.


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


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



Top 50 recent answers are included