Tag Info

New answers tagged

0

Usually to show that a function $g$ (in particular, $g=\log f$) is not concave, we draw or imagine its graph, and then see where the concavity fails, or calculate a second derivative $g’’$ and find a point $x$ such that $g’’(x)>0$. See more at Wikipedia’s page.


1

Hint: Pick a point $p$ and look for a point of maximum of the function $f(k)=||p-k||, k\in K$.


2

Let me do the proof in $d=2$ to make it easy for me but the same idea works in general. We will assume that we are so unlucky that whenever we choose a direction there are not exposed points in that direction. Take a direction $d_1$ (a functional) and consider the support set on $K$ in that direction. It is not a single point. It is a compact interval. ...


0

Hint: Is each extreme point exposed?


0

It seems the following. Let $x=(x_1,\dots,x_d)\in C$. We shall call an index $i$ fixed provided $x_i=\ell_i$ or $x_i=u_i$. Proposition. A vector $x=(x_1,\dots,x_d)\in C$ is a vertex of $C$ iff for each index $i$ there exists a fixed index $j$ such that $x_i=x_j$. Proof. First of all we remark that a point $x$ is a vertex of $C$ iff there exist no ...


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

Let ${\mathbb M}_n$ be equipped with $\| \cdot \|_1$. Denote by $B_1=\{ X\in {\mathbb M}_n;\quad \| X\|_1\leq 1\}$, the closed unit ball in ${\mathbb M}_n$. For $A\in {\mathbb M}_n$, let $\rho_A:{\mathbb M}_n \to {\mathbb M}_n$ be defined by $\rho_A(X)=XA$. Then the problem is to describe the set $$ \rho_{A}^{-1}(B_1)=\{ X\in {\mathbb M}_n;\quad \rho_A(X)\in ...


1

Your answer is correct, and it would be obtained more easily from the 2nd derivative test. The Hessian matrix of $f$ is $$ \begin{pmatrix} 0 & -1 \\ -1 & 0 \end{pmatrix} $$ which has negative determinant; hence, the graph is saddle-like at every point.


1

First lets state the claim. Claim: $I(X;Y)=D(p(x,y)||p(x)p(y))$ is concave in $p(x)$ for fixed $p(y|x)$ and convex in $p(y|x)$ for fixed $p(x)$. One can write the following: $I(X;Y)=H(Y)-H(Y|X)$ where $H$ is the entropy function. The entropy functions can further be written as $$H(Y)=-\sum_y p(y)\log(p(y)) \ \text{ and } \ H(Y|X)=-\sum_x p(x)\sum_y ...


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


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?


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


1

We can use the answer here as follows: $$ B - A \in S^n_{++} \iff\\ I - B^{-1/2}AB^{-1/2} \in S^n_{++} \iff\\ I - A^{1/2}B^{-1}A^{1/2} \in S^n_{++} \iff\\ A^{-1} - B^{-1} \in S^n_{++} $$


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


0

It seems that we should assume monoticity, I'll demonstrate with only one optimizasion, i.e. on $a \in A$ and will abuse the notation bt changing $\inf$ and $\sup$ when ever i'll need. Let $$y=g(x)=f(a_x,x).$$ Then $$x = g^{-1}(y) = f^{-1}(a_x,y)$$ and we need to prove that $$ f^{-1}(a_x,y) = \inf_{a \in A} f^{-1}(a,y)$$ i.e. $$ f^{-1}(a_x,y) \leq ...


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 that $(y,t)$ is such that $\|y\|_\infty \leq t$. Select any $(x,t') \in K$. We apply Hölder's inequality to find $$ \langle(x,t'),(y,t)\rangle =\\ \langle x,y \rangle + t't \geq\\ - \|x\|_1 \|y\|_{\infty} + t't \geq\\ -\|x\|_1 \|y\|_{\infty} + \|x\|_1 \|y\|_{\infty} = 0 $$ Now, suppose that $(y,t)$ is such that $\langle(x,t'),(y,t)\rangle \geq 0$ ...


0

This answer addresses the first question. A real-valued, symmetric matrix is positive-semidefinite if and only if all its eigenvalues are nonnegative -- $0$ counts, no matter how many times it occurs. Also, positive-semidefiniteness everywhere of the Hessian is equivalent to convexity; see this Math.SE question. Hessian matrices of real-valued $C^2$ ...


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


1

Let $x\in(A^*+B^*)^*$. So $\forall{y}\in A^*+B^*, (x,y)\ge0$. It means that $\forall{y}\in A^*, (x,y)\ge0$ so $x\in A^{**}$. Since $A$ is closed $A^{**}=A$ and $x\in A$. Similarly we can show that $x\in B$. So $x\in A\cap B$


1

That $D(u||v)$ is convex in the pair $(u,v)$ means that $$D(u_{\lambda}||v_{\lambda}) \le \lambda D(u_{1}||v_{1}) +(1-\lambda)D(u_{2}||v_{2}) $$ (here $u$ and $v$ and some probability functions, with $u= \lambda u_1 +(1-\lambda) u_2$, etc) Then $$I(X_{\lambda};Y_{\lambda}) = D(p_{\lambda}(X,Y)||p_{\lambda}(X)p_\lambda(Y))$$ where (as shown in the text) ...


1

The epigraph is $\operatorname{epi} f = (B(0,1)\times \mathbb{R}) \cup (\bar{B}(0,1) \times [0, \infty))$. Suppose $x,y \in \operatorname{epi} f$. If both $x,y$ belong to either of the constituent sets, then it is clear that $[x,y]$ is also in the same set. So, suppose $x \in B(0,1)\times \mathbb{R}$ and $y \in (\bar{B}(0,1) \times [0, \infty)) \setminus ...


0

It turns out the condition $A^\dagger_B A = I$ together with the non-negativity implies that you cannot have more than one non-zero entry in any column of $A^\dagger_B$. Hence the answer for the oblique case is the same as for the usual Moore-Penrose pesudo-inverse.


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


2

In general, if $f:\mathbb{R}^n\to \mathbb{R}$ is concave, then for any matrix $A \in\mathbb{R}^{n\times n}$, $f(Ax)$ is also concave in $x$, and the proof uses this fact, i.e., the fact that the concave function of a linear combination is still a concave function. Proof: For any $0\leq \lambda\leq 1$, and any $x_1,x_2 \in \mathbb{R}^n$, $$ f\left(A\left( ...


1

Suppose $u \in K'$. If $x \in K$, then $cx \in K$ for all $c > 0$, and so \begin{align} & \langle u, cx \rangle \leq 1 \quad \forall c > 0 \\ \implies & \langle u, x \rangle \leq \frac{1}{c} \quad \forall c > 0 \\ \implies & \langle u, x \rangle \leq 0. \end{align} Hence, $u \in -K^*$. This shows that \begin{equation} K' \subset -K^*. ...


0

I figured it should be proved as follows: $$f^*(0) = \sup_{x \in X} -f(x) = \inf_{x \in X} f(x) = f^*$$ $$\max_s \min_x [<s,x> - f^*(s)] \geq \min_x 0 - f^*(0) = f^*$$ and by min max > max min, it follows the equality as desired.


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


2

Yes. Let $x,y$ in the closure and $z = \alpha x + (1-\alpha)y$ with $0\leq \alpha\leq 1$. The point $x$ (resp. $y$) is a limit of a sequence $(u_n)_n$ (resp. $(v_n)_n$) of points of $A$, and $z$ is limit of the sequence $(w_n)_n$ with $w_n = \alpha u_n + (1-\alpha) w_n \in A$ by convexity of $A$. Therefore $z$ is limit of a sequence of points of $A$, and is ...


0

Consider $$A:=\{a=(a_1,a_2,...,a_n)\in\mathbb{R}^n:\ a_n\geq0\}$$ Then $x:=(0,0,...,-1)$ and $r:=1/4$.


0

Well, i think a proof could be like this: If T is a linear map, then it has the following form: T(x)=ax for every vector $ x e R^n $ , $ a e R^n $. Then take a vector w e T(A). Now it is w = T(q)=aq =a(λχ+λ'y+λ"z)=λax+λ'ay+λ"az=λΤ(x)+λ'Τ(y)+λ"Τ(z) e conv(T(x),T(y),T(z)) , where λ+λ'+λ"=1 (λ_i>=0). Now, if w e conv(T(x),T(y),T(z)) w= λΤ(χ)+λ'T(y)+ ...


1

$f^{**}\le f$ and $f$ is bounded above on an open set makes $f^{**}$ bounded above on an open set so because $f^{**}$ is convex lower semicontinuous it is continuous on the interior of its domain.


0

Hint: Suppose $y\in\text{conv}(S)$, then we want to show $y\in\text{conv}(V)$. By definition there are appropriate $a_s$ for all $s\in S$ such that $y=\sum a_ss$. Moreover, for each $s\in S$, there are appropriate $\lambda_{s,v}$ for all $v\in V$ such that $a_s=\sum\lambda_{s,v}v$. Why is this true? How does it help?


0

Here is a rigorous—and, accordingly, a bit lengthy—operationalization of the intuition offered by the answer by @OohAah. $\textbf{Proposition}\phantom{---}$ Let $C\subseteq \mathbb R^n$ ($n\in\mathbb N$) be a convex set. If $C$ has no interior, then nor has $\overline C$. $\textit{Proof}\phantom{---}$ Suppose that $(\overline C)^o\neq 0$. I will show that ...


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



Top 50 recent answers are included