# Tag Info

## Hot answers tagged convex-optimization

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