Tag Info

Hot answers tagged

4

Note that the eigenvalues of a matrix depend continuously on its entries. So, if there exist a $\sigma_1$ such that the smallest eigenvalue $A + \sigma_1 B$ is positive, then there exists an $\delta > 0$ such that the lowest eigenvalue $A + \sigma B$ is positive for any real $\sigma$ with $|\sigma - \sigma_1| < \delta$. This is enough to show that $a ...


4

Details of Nesterov smoothing for computing Nash equilibria in matrix games Let $A \in \mathbb{R}^{m\times n}$, $c \in \mathbb{R}^n$ and $b \in\mathbb{R}^m$, and consider a matrix game with payoff function $(x, u) \mapsto \langle Ax, u\rangle + \langle c, x\rangle + \langle b, u\rangle$. The Nash equilibrium problem is \begin{eqnarray} \underset{x \in ...


3

The point $v_0$ is the intersection of the surface of the sphere and the ray that comes from the origin and passes through $v$. Proof: Consider $B'$ the sphere centered at $v$ with radius $r=d(v,v_0)$. Clearly $v_0\in B\cap B'$. Let $w$ be any other point in space $\Bbb R^3$. If $w$ is in the segment $\overline{0v}$, then $w$ is in $\overline{0v_0}$ and ...


3

If a finite set of points satisfies a linear inequality, so does any convex combination of those points. Hence, given a finite set $S$ and a point $t$, if there is a linear inequality that is satisfied by $t$ but not by any member of $S$ then $t\notin \operatorname{conv}(S)$. Let us now look at every point of $D$. Point $e_1=(1,0,0)$ satisfies the linear ...


3

Not necessarily. Consider $Y$ such that $Pr[Y=0]=Pr[Y=1]=1/2$. Define $g(x,Y)=e^{Yx}$. Then $g(x,Y)$ is log concave in $x$ because $\log g(x,Y) = Yx$ is linear. But: $$ E[g(x,Y)] = \frac{1 + e^x}{2} $$ and $\log E[g(x,Y)] = \log(1/2) + \log(1 + e^x)$, which is no longer concave.


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.


2

No, your thinking is not correct; the LHS and RHS describe exactly the same function of $x$ in different ways. The problem with your interpretation of the LHS is that $x$ is not yet known. It is impossible for the LHS to return just one function $f_{k^*}(x)$, because the proper choice of $k^*$ depends on $x$. The two expressions are exactly equivalent. At ...


2

Any convex combination of positive numbers must be greather than 0, hence {e_1,e_2, e_3} must be in the hull. Suppose that some of the last 3 vector doesn't exist in the hull, for example $(1/2, 1/2, 1)$. Let $\Delta := conv({e_1,e_2, e_3})$. It is known that vector $(1/2, 1/2, 1)$ can be written as convex combination of vector $v \in \Delta$ and vectors: ...


2

By hyphotesis $B$ is compact; so you can define a function $F:B\longrightarrow \mathbb{R}$ such that maps every $v_0 \in B$ to its distance to $v$. Then by WeierstraƟ theorem the function $F$ admits minimum and maximum since $B$ is compact, then you can show that this function assume the minimum in only one point. You can see it supposing that there exists ...


2

The projection of $z$ onto the set $\{x:\ Ax=b\}$ is given by the solution of $$ \min \frac12\|x-z\|^2 \quad \text{ subject to } Ax=b. $$ The KKT system is a necessary (since constraints are linear) and sufficient (since this is a convex problem): $$ Ax=b, \quad x-z +A^T\lambda = 0. $$ Multiply the second equation by $A$, solve for $\lambda$: ...


2

Depends on what you mean. There is the standard reformulation lifting technique (RLT) typically used for bilinear/polynomial problem leading to large LPs. Googling on that leads to a wealth of material by, e.g., Sherali, Balas etc. Then you have lifting to more exotic cones such as semidefinite relaxation. Same thing there, google semidefinite relaxations ...


2

If you consider the function to be minimized $$F= \frac{R^2+G^2\sum_{i=1}^k \alpha_i^2}{2\sum_{i=1}^k \alpha_i}$$ consider its derivatives. They write $$\frac{dF}{d\alpha_j}=\frac{G^2 \alpha_j}{\sum_{i=1}^k \alpha_i}-\frac{R^2+G^2\sum_{i=1}^k \alpha_i^2}{2\Big(\sum_{i=1}^k \alpha_i\Big)^2}$$ Since the same second term appears in all derivatives, then the ...


2

Let $A=(\alpha_1,\alpha_2,\dots,\alpha_k)$ be any optimal solution, and suppose that the values aren't equal. Now consider all possible permutations of $A$: they must all obtain the same optimal value by symmetry. Now consider the mean of those permutations. This mean will have the same value for each $\alpha_i$. The mean is a convex combination, and the ...


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$


2

Apply lagrange multiplier method. The augmented function looks like: $$ f(x)=x^TPx+\lambda^T(Cx-d) $$ Note that here $\lambda\in\mathbb R^m$ is a vector since you have $m$ constraints. The minimum is acquired when: $$ \begin{cases} \partial f/\partial x=2Px+C^T\lambda=0\\ \partial f/\partial\lambda=Cx-d=0 \end{cases} $$ Since $P>0$ and therefore ...


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


1

That comes from the properties of Moore-Penrose inverse . $$A^\dagger AA^\dagger=A^\dagger$$ Combined this with the fact that A is symmetric(and if its convex positive semi-definite but that's not required) : $(x^*)^TAx^*=b^T(A^\dagger)^TAA^\dagger b=b^T(A^T)^{\dagger}AA^\dagger b=b^TA^\dagger AA^\dagger b=b^TA^\dagger b$


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


1

Looking at the definition of $f$ from a statistical standpoint, define the average value of the $\alpha_i$'s to be $\bar\alpha= \frac{1}{k}\sum_{i=1}^k \alpha_i$. Define the variance of the $\alpha_i$'s to be $\sigma^2=\frac{1}{k}\sum_{i=1}^k (\alpha_i - \bar \alpha)^2= \frac{1}{k}(\sum_{i=1}^k \alpha_i^2 - k\bar\alpha^2)$. Then $f$ can be redefined in ...


1

Not an answer, just a long thought that may or may not help This method won't give the eigenvectors directly. You will have more computation to do. But I guess it is better than finding the whole spectrum. I assume that all eigenvalues are real for your matrix, say $A$. Then, add a large positive number $\alpha$ to its diagonal entries. Effectively, you ...


1

This is not specific to total variation; this is how the Legendre-Fenchel transform works for norms. Here one should really think of the space of $C^1_c$ vector fields as the original space, $X$. It is given the supremum norm. The $L^1$ functions induce linear functionals on this space via $$ \langle u,\xi\rangle = \int_\Omega u(x)\text{ div }\xi(x)\,dx $$ ...


1

Given an arbitrary point $a$ in $\mathbb{R}^3$, the distance from $a$ to the set $B$ is defined by $$\tag{1} d(a,B)=\inf_{b\in B}\|a-b\|. $$ Since the map $$ d^a:\mathbb{R}^3\to [0,\infty), \, d^a(x)=\|a-x\| $$ is (uniformly) continuous, and the set $B$ is compact, there exists some point $p(a)\in B$ such that $$\tag{2} d(a,B)=\|a-p(a)\|. $$ This also ...


1

The underlying problem can be formulated as \begin{eqnarray} \text{minimize }\frac{1}{2}\|v_0-v\|_2^2\hspace{1em}\text{ subject to }v_0 \in B. \end{eqnarray} You are minimizing a $1$-strongly convex function on a closed convex set. The minimizer is unique.


1

Hint: Well you can consider distance function $V = (V_{x},V_{y},V_{z})$, then distance between $V$ and the point of $B$ is $\sqrt{(V_{X}-x)^2+(V_{y}-y)^2+(V_{z}-z)^2}$. And think of the domain you evaluate this function certainly, because of nature of $B$ the domain is closed and bounded. Therefore, by extreme value theorem you can deduce maximum and minimum ...


1

It is always possible to convert a convex QCQP into an SOCP. It is not always possible to go the other direction, however. Just express this problem as follows: \begin{array}{ll} \text{minimize} & y \\ \text{subject to} & \|F x\|_2 \leq y \\ & \|G x\|_2 \leq \sigma \\ & 0 \preceq x \preceq x_i^* \\ & A x = b \end{array} where $F$ and $G$ ...


1

A convex function is called closed iff $f = \operatorname{cl} f$, where $\operatorname{cl} f$ is defined as follows: If $f(x) = -\infty$ for any $x$, then $(\operatorname{cl} f)(x) = -\infty$ for all $x$, otherwise $\operatorname{cl} f$ is the function whose epigraph is given by the $\overline{\operatorname{epi} f}$. Since the $f$ in the question is ...


1

Following up on lythia's comment, if you differentiate $f$ with respect to an off diagonal entry of $f$ you get zero, if you differentiate twice with respect to a diagonal entry you just get $f''$, and so $\nabla^2_Xf=f''I$.


1

Let's define $$g:\mathbb{R}^{m\times m}\rightarrow \mathbb{R}, \quad g(X) = f\left(\mathop{\textrm{Tr}}(X)\right) = f\left(\textstyle\sum_i X_{ii}\right).$$ Notice that this function is constant for all off-diagonal elements of $X$, so any partial derivative that involves an off-diagonal element must be zero. So even though I've actually defined $g$ on all ...


1

The point $(\frac 12,\frac 12,\frac 12)$ can be written as a convex combination of three of the points you gave. In particular, $$\begin{align} \left(\frac 12,\frac 12,\frac 12\right) & = \frac 12 \left( \frac 12,\frac 12,1 \right) \\ & + \frac 14 (1,0,0)\\ & + \frac 14 (0,1,0)\\ \end{align} $$



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