Tag Info

1

Say, $y_1, y_2 \in T(S)$. So, we can write them as, $y_1=T(x_1), \ y_2=T(x_2)$ where $x_1,x_2 \in S$. $$ty_1+(1-t)y_2 \text{ where } t\in [0,1]$$ $$=tT(x_1)+(1-t)T(x_1)$$ $$=T(tx_1+(1-t)x_2) \in T(S) \text{ because }tx_1+(1-t)x_2 \in S$$

1

HINT Since $T$ is linear $T(tx+(1-t)y)=tT(x)+(1-t)T(y)$ where $t\in [0,1]$ and $x,y\in S$

-1

HINT:What can you say about $T(x_1 + x_2) \leq T(x_1) + T(x_2)$?

1

If you want to find the proximal operator of $\|x\|_{\infty}$, you don't want to compute the subgradient directly. Rather, as the previous answer mentioned, we can use Moreau decomposition: $$v = \textrm{prox}_{f}(v) + \textrm{prox}_{f^*}(v)$$ where $f^*$ is the convex conjugate, given by: $$f^*(x) = \underset{y}{\sup}\;(x^Ty - f(y))$$ In the case of ...

1

You can apply the definition of convexity: for every $x,y \in \mathbb{R}^d$ and $\lambda \in [0,1]$ $$g(\lambda x+(1-\lambda)y)=[f(\lambda x+(1-\lambda)y)]^2$$ and by the convexity of $f$ and $f\ge0$ $$g(\lambda x+(1-\lambda)y)\le[\lambda f(x)+(1-\lambda)f(y)]^2$$ finally by the convexity of $x^2$ $$g(\lambda x+(1-\lambda)y)\le\lambda ... 1 Hint: Without loss of generality you can assume d=1 -- a function is convex on \mathbb R^d iff it is convex on every line through \mathbb R^d. Then just compute g''(x) and see that it cannot be negative given your assumptions. 0 I have to methods for proving the boundedness. The first one uses a contradiction, as proposed by the authors. However, the second method seems to be more elegant and even yields the convergence of the coefficients. Method 1: Assume \{\alpha_k\} is not bounded. Then,$$\frac{\sum_{i=1}^m \alpha_{ki} \, a_i}{\max_{i} \alpha_{ki}} = \sum_{i=1}^m ...

2

Part 2 is easier to answer: no, the way monotone operators are defined in functional analysis, $-F$ is not in general monotone when $F$ is. (This is unlike the concept of monotonicity in real analysis). Monotone operators correspond to (non-strictly) increasing functions. The reverse inequality defines dissipative operators. Part 1, geometric ...

1

This question has been asked and answered on MathOverflow. I have replicated the accepted answer by Ilya Bogdanov below. $\def\sign{\mathop{\rm sign}}$First of all, it is enough to prove the statement when $p=u/v$ is rational, $u$ is even and $v$ is odd (such numbers are dense on the real line). We need this to simplify the last argument. Let the ...

0

There are several problems with your proof: You do not prove the assertion. Indeed, if your proof would be correct, you would have shown that $f$ has a at least a minimizer. I do not get the point of your last sentence. Indeed, $\mu$ is always unique, by definition, independently of the properties of $f$. Your proof is wrong: Indeed, your minimizing ...

2

Recall the definition of strict convexity: $$f(\lambda x + (1-\lambda)y) < \lambda f(x) + (1-\lambda) f(y) \quad \forall x,y\in\mathop{\textrm{dom}}(f), ~ x\neq y, ~\lambda\in(0,1)$$ The strictly convex functions $f(x)=e^x$ and $f(x)=x^2$ have exactly zero and one minimizers, respectively. Now suppose we claim that a strictly convex function $f$ has two ...

1

It's not clear to me under what principle we could have expected "multiplying $A^T$ on both sides" to lead to a proper answer. For one thing, since $m<n$, $A^TA$ is not invertible. (As it is, the correct answer assumes that $A$ has full row rank so that $AA^T$ is invertible; this is of course not always true.) The right way to do this is to use a ...

1

You need the hypothesis that $A$ has rank $m$ so that $AA^T$ is invertible. Since $x^*=A^T(AA^T)^{-1}b$ we have $Ax^*=b$, so for every $x$ such that $Ax=b$ we have $x-x^*\in {\rm ker}A$ and clearly $x^*\in {\rm Im}A^T$, but it is well-known that ${\rm Im}A^T=({\rm ker}A)^\bot$. Thus, by Pythagoras theorem $$\Vert x\Vert^2=\Vert x-x^*\Vert^2+\Vert ... 3 Assuming A is positive definite, i.e. A+A^T is SPD. Then expanding the quadratic form we have$$f_1(\mathbf{x}) = \mathbf{x}^TA\mathbf{x} - \mathbf{x}_k^T(A+A^T)\mathbf{x} + \mathbf{x}_k^T A \mathbf{x}_k - t^2.$$The second-last term should have a positive sign although it has no effect in calculating the gradient. In calculating the gradient of ... 0 Partial answer First, note f is constant on the line L_i=\{\lambda e_i:\lambda\in\mathbb{R}\} for all i (where e_i is the i-th vector of the canonical base of \mathbb{R}^n), so it can't be strongly convex. Second, given z\in\mathbb{R}^{n-1} s.t. \sum z_i\neq 0, define the function g:\mathbb{R}\to\mathbb{R} as g(s)=f(s,z). This function ... 1 In fact, the convex hull \mathrm{conv}\{x_1,\ldots,x_k\} := \{\sum_{1 \le j \le k}t_kx_k | t \in \mathbb{R}^n, t \ge 0, \sum_{1 \le j \le n}t_j = 1\} is compact (in the usual euclidean topology)! Step 1: The simplex \Delta_n := \{t \in \mathbb{R}^k | t \ge 0, \sum_{1 \le j \le k}t_j = 1\} is compact. Indeed it closed, being the intersection of closed ... 0 Here's an example on \mathbb R: f(x) = x^2-\cos x. A way to make lots of examples: Let f be any positive bounded continuous function on [0,\infty). For x\ge 0, set$$g(x) =\int_0^x \int_0^t f(s)\, ds\,dt.$$Extend g to an even function on all of \mathbb R. Then g satisfies the requirements. 0 This is not an entirely silly question, not even in the planar case. Let me give the argument in the plane; a higher dimensional argument works too. Suppose the number of extreme points of A is a finite set P having \ge 2 points. The set A is the convex hull of P, meaning the intersection of all convex closed sets containing P. With some work ... 4 Why are these models equivalent? What does it mean for two models to be equivalent? Here's my answer: two models are "equivalent" if the solution to one model readily leads to the solution of the other, and vice versa. Suppose you have a solution to (1) above: that is, you have an (a,b) pair that satisfies$$a^Tx_i+b>0 ~~ \forall i=1,\dots, M, \quad ...

1

Let $A x^* = -b$, then the alternative representation is $\|A(x-x^*)\|^2 \le 1$. That is, $(x-x^*)^T A^TA (x-x^*) \le 1$. From this we see that we have equivalence when $P^{-1} = A^T A$ and $x_c = x^*$.

3

Just compute the second derivative, we have, by the chain rule $$\def\norm#1{\left|#1\right|} Df(x)h = \frac 1{(1 + \norm{x}^2)^{1/2}} \cdot \def\<#1>{\left<#1\right>}\<x, h>$$ Hence, $$D^2f(x)[h,k] = -\frac 1{(1 + \norm x^2)^{3/2}}\<x,h>\<x,k> + \frac{1}{(1 + \norm x^2)^{1/2}}\<h,k>$$ So, we have \begin{align*} D^2 ...

0

In general, we really can't say anything about the nullspace of a sum of matrices consider $A=-B$ and $c_1=c_2=\frac{1}{2}$ then nullspace of $C$ is whole space or for $A=B=I$ and $c_1=c_2=\frac{1}{2}$, then$\ker C$ is trivial.

1

In general, there is a decomposition of square matrices into a symmetric part and anti-symmetric part: $$A=M+N$$ where $M$ is symmetric and $N$ is anti-symmetric. This is a very general result, and this decomposition is in fact a Hilbert space decomposition so that $M$ is the "closest" symmetric matrix to $A$. It is easy to derive the forms of $M,N$: ...

0

Assumptions: I suppose you're implicitly assuming $P_n(w) > 0$ for all $w$. Now, after removing unnecessary details, your problem can be succinctly formulated as follows: Given constants $\alpha_1, \ldots, \alpha_n \in \mathbb{R}$, show that the function $f : \mathbb{R} \rightarrow \mathbb{R}$ $\zeta \mapsto \log \sum_{1 \le k \le n}\exp(\alpha_k ... 0 Convexity is a property of a subset of a vector space; topology - and, inherently, notions of closed and spaces - is completely irrelevant here. However, since you mentioned that this is homework, my guess is that the next question is to prove that your sum$A=S_1+S_2$is a closed set. If we talk about usual topology, then there is only one compact linear ... 0 Tangent hyperplanes can touch a convex set at multiple points. For the square, you have 4 half-spaces whose defining hyperplanes are tangent to the sides of the square, namely$\{(x,y):y\geq 1\}$,$\{(x,y):y\leq -1\}$,$\{(x,y):x\geq 1\}$and$\{(x,y):x\leq -1\}$. You also have 4 that touch the corners, at 45 degree angles (I won't write them down ... 2 Not in general. Here is a counterexample. Let$X = C([-1,1])$. For$t \in [-1,1]$, let$\delta_t$denote the point mass / evaluation functional$\delta_t(x) = x(t)$. Let$D = \{ \delta_q : q \in [-1,1] \cap \mathbb{Q}\}$. Then$D$is countable and we have$\|x\| = \sup_{f \in D} |f(x)|$for every$x \in X$. Let $$y(t) = \begin{cases} 4t, & -1 \le t ... 1 Yes, you're doing good. For the convex conjugate (aka Legendre transform) of an arbitrary norm, see this answer. Regarding the second part of your question, Claim: Let X be a Hilbert space, \alpha be a nonzero real number, f : X \rightarrow (-\infty, +\infty] be a function, and g = \alpha f. Then g^*(x) \equiv \alpha f^*(x/\alpha). Proof. For ... 0 Could you explain me how we deduce that d(x,K)=1? K is the interior of the unit circle about the origin. If y \in K, then d(\mathbf 0,y) < 1. Now for x = (0,2), d(\mathbf 0, x) = 2. By the triangle inequality d(\mathbf 0, x) \le d(\mathbf 0,y) + d(x, y). So$$d(x, y) \ge d(\mathbf 0, x) - d(\mathbf 0,y) > 2 - 1 = 1.$$Therefore d(x, ... 1 Hint: Try to show Triangle Inequality first. 1 I'll just write down the solution and hope you catch a few tricks from the manipulations :) i) Define g = f + \langle c, .\rangle. For any x \in X, we habe \begin{split} g^*(x) &:= \sup_{z \in X}\langle x, z\rangle - g(z) = \sup_{z \in X}\langle x, z\rangle - \langle c, z\rangle - f(z) = \sup_{z \in X}\langle x - c, z \rangle - f(z) ... 1 f(x)=\left\{\begin{matrix} x^2, x\geq 0\\ 0, x< 0 \end{matrix}\right. 1 Define f as follows:$$f(x)= \begin{cases} & 2x^2 \text{ if } x \leq 0 \\ & 3x^2 \text{ if } x>0 \end{cases}$$Then f is differentiable with:$$f'(x)= \begin{cases} & 4x \text{ if } x \leq 0 \\ & 6x \text{ if } x>0 \end{cases}$$f' is monotonically increasing, thus f is convex. Yet the second derivative does not ... 4 If n=1, \det A=a_{1,1}, which is trivially a convex function of A. If n>1, take two diagonal matrices, with a_{i,i}=1 if i\leq n/2 and 0 otherwise, and b_{i,i}=0 if i\leq n/2 and 1 otherwise. Then \det A=\det B=0. However, for t\in]0,1[, \det [tA+(1-t)B] > 0, hence the function is not convex. 2 I'll just write down the solution and hope that you catch some tricks from the manipulations :) Define \mathbb{R}^n_+ := \{x \in \mathbb{R}^n | x \ge 0\} (the nonnegative nth orthant), and \mathbb{R}^n_- := \{x \in \mathbb{R}^n | x \le 0\} (the nonpositive nth orthant). From these definitions, it's clear that -\mathbb{R}^n_+ = \mathbb{R}^n_-. Now, ... 1 Your mistake is that you're still trying to enforce the |y|\leq 0 constraint after you have built the Lagrangian. Don't do that. Once the Lagrangian is built, the constraint on y goes away. Furthermore, the dual function doesn't include \lambda\geq 0, just the dual problem. So the dual function is$$g(\lambda) = \inf_y y + \lambda |y|$$nothing more. ... 2 Your statement is false. Indeed, let define the following functions:$$g:x\in\mathbb{R}\mapsto|x|\in\mathbb{R},h:x\in\mathbb{R}\mapsto x^2-1\in\mathbb{R}.$$g and h are convex and g is positive. Nevertheless, g\circ h isn't convex. Let assume g and h are \mathcal{C}^2, then, one has:$$(g\circ h)''=h''g'\circ h'+(h')^2g''\circ h.$$Since, ... 0 Credits to both @Tsemo and @Daniel. Basically using the fact that Daniel mentioned, \text{Conv}(C_1 \cup \cdots\cup C_n) is compact. Now LCTVS are Hausdorff, so it is a compact subset of a Hausdorff space which is closed. Otherwise since the convex hull is itself compact, proceed to prove that \text{Conv}(\text{Ext}(\text{Conv}(C))) = \text{Conv}(C), ... 1 Hint: Apply the theorem of Krein-Milman 1 So, the set under study is a linear image S := A\mathbb{B}_\infty, of \mathbb{B}_\infty := \{x | \|x\|_\infty \le 1\}, the unit ball for the \ell_\infty-norm . We're interested in the vertices of S, namely V(S). Define $$V_0 := \{Ax | \|x\|_\infty = 1\}.$$ The aim is to show that V(S) \subseteq V_0. Suppose on the ... 1 No, this is not sufficient. Take, e.g., f(x) = x^2 on the real line and x^k = 1 + 1/k. 0 This statement is false. Let b\in \mathbb R^n be nonzero and let f be the indicator function of the set S=\{b\}. Then f^*(z) = \langle z, b\rangle. So f^* is unbounded below, but f(b) is finite. (I'm using the term "indicator function" in the convex analysis sense.) 0 Without getting into any particularly deep analysis, here are my thoughts: (let's assume, like you say, for simplicity we run over all convex fs that are continuous and defined on all of X) First I would start with thinking about what it would mean for f(S) to not be an interval: this means there is some x\in\mathbb{R} that "separates" f(S) (i.e., ... 1 On one side, let x \in \bar E, choose a sequence (x_n) \in E^{\mathbf N} such that x_n \to x. If now x' \in X' is given such that \Re x'|_E \ge 1. Then, as \Re x' is continuous, we have$$ 1 \le \Re x'(x_n) \to \Re x'(x) $$That is \Re x'(x) \ge 1. Along the same line we see that \Re x'|_E \le 1 implies \Re x'(x) \le 1. For the other ... 0 With a convex hull, all interior angles are less than \pi. This means if we enter a halfplane of l(x,y), we must rejoin l from the same halfplane, and so the other halfplane is out of bounds. If l is the black line, the green line is okay, but the blue line isn't.. 1 More generally, if T: X \to Y is a linear transformation of vector spaces and C is the convex hull of A \subseteq X, then T(C) is the convex hull of T(A). In this case, you're taking the linear transformation of \mathbb R^2 given by (s,t) \to x_1 s + x_2 t. 0 By Carathéodory's theorem, b is in a triangle with vertices in A. The linear functional (u_1,u_2) \mapsto u_1x_1+u_2x_2 is continuous and so attains a global minimum on the boundary of the triangle. Since the level curves are straight lines, the minimum must be attained at a vertex of the triangle, which is in A. To get a clear picture, you may ... 2 There are two relevant geometric observations. Consider the following drawing of a quadrilateral with \theta_1, \theta_2 \geq \frac{\pi}{2}: Then |w_2 - w_1| \leq |z_2 - z_1|. In order to prove it algebraically, we have$$ \left< w_2 - w_1, w_2 - w_1 \right> = \left< (z_1 - w_1) + (z_2 - z_1) + (w_2 - z_2), w_2 - w_1 \right> = \\ ... 1 Statement of the problem: What can we say about a function$f:\mathbb{R}\to\mathbb{R}$with the property that $$(P)\ \ \forall \alpha\in(0,1],\ x,y\in\mathbb{R},\ x\ge y,\ \ f(\alpha x+(1-\alpha)y)\le f^{\alpha}(x/\alpha)f^{1-\alpha}(y)?$$ Since we can take$x=y$,$f(0)$is still the global minimum value. Assume that$f(0)=0\$. We claim in this case that ...

0

the thing you expect is true. I would just emphasize one little point, you cannot allow any self intersection, any two arcs, any arc through some endpoint not its own, coincidence of two endpoints. I guess you did cover that by saying simple closed curve... This probably does it. At each vertex, round off the corner with a short almost-circular arc, making ...

Top 50 recent answers are included