# Tag Info

2

Yes, and a more general fact is true: If $h:\mathbb R\to\mathbb R$ is convex and $g:\mathbb R^n\to \mathbb R$ is linear, then the composition $h\circ g$ is convex. Proof: The definition of convexity requires us to show that for all $\mathbf x,\mathbf y\in\mathbb R^n$ and all $t\in [0,1]$ we have $$h(g((1-t)\mathbf x+t\mathbf y)) \le ... 1 This result is true for any bounded operator with \|T\|\leq1. Fix x\in X with \|x\|\leq1. Put$$ C=\overline{\{t\,T^nx:\ t\in[0,\tfrac1{2}],\ n\in\mathbb N\}}\subsetneq B_X $$(every element in C has norm at most 1/2). This is the most general possible result: let T=(1+\delta)I for some \delta>0. A subset C as desired satisfies ... 4 A continuously differentiable function \mathrm{f} is convex on an interval I if, and only if$$\mathrm{f}(x) \ge \mathrm{f}(y)+\mathrm{f}'(y)\cdot(x-y)$$for all x,y \in I. In your case \mathrm{f}(x) = \mathrm{e}^x and I = \mathbb{R}. Hence, we need to show that$$\mathrm{e}^x \ge \mathrm{e}^y + \mathrm{e}^y \cdot(x-y)$$for all x,y\in ... 0 The second derivative describes where a function is concave or convex. (e^x)'' > 0 for all x so e^x is convex everywhere. 0 A function of real variable is convex on an interval if it has nonnegative second derivative on this interval. This is a simplification of the Hessian condition for convexity to the case \mathbb{R}\rightarrow \mathbb{R}. The second derivative of e^{x} is e^{x}, and this is of course nonnegative on the entire real line. 1 Take, in \Bbb R^2, X to be the graph of y=x^2 together with the set of points "above it". Then the cone C of X is the non-closed set \bigl\{\,(x,y)\mid y>0\,\bigr\}\cup\{\,(0,0)\,\}. (I think any strictly convex closed body tangent to the origin will do.) 0 I believe you need f to be closed (equivalent to lower semi-continuous for a proper function). Define f:\mathbb R^2 \to\mathbb R \cup\{+\infty\} as follows: f(x,y) = \begin{cases} 0, & x=0, y=0\\ y, & y >0 \\ +\infty, & \text{otherwise}\end{cases} f is proper, convex, L_{\leq 0} = \{ (0,0) \} which is bounded and  \mathbb{R} ... 0 Not assuming convexity, you will have to test each possibility. Given your point p and the locations of each vertex v_i \in V, you want the vertex with minimum distance from p (not unique). Let dist(p,v_i) be a function that gives the distance from p to v_i. The pseudo code for this is: v_{min} = v_1 d_{min} = dist(p,v_1) for v_i \in ... 1 Yes, it is true. Let's first consider the case when Y is closed. Let P\colon \mathbb{R}^n \to Y be the projecion, i.e. d(x,P(x)) = d(x,Y) for all x\in\mathbb{R}^n. For p\in Y^c\cap Z^c, Y lies entirely on one side of the hyperplane$$H = \{ x : \langle p-P(p), x-P(p)\rangle = 0\},$$and p lies on the other side, so we have, writing y_p = ... 1 Since f is logconcave and f>0, we can write f(x)=e^{g(x)} where g is concave. Obviously, f'<0 is equivalent to g'<0. Note that$$F(x):=f(x)+x f'(x) \leq 0$$if, and only if,$$\log(f(x)) \leq \log(-x \cdot f'(x))$$by the monotonicity of the logarithm. Using that f(x)=e^{g(x)}, we see that this is equivalent to$$x^{-1} \leq ...

1

Twice differentiable function is convex on a convex set if and only if its Hessian matrix is positive semidefinite on the interior of the convex set. You can use Sylvester’s criterion to check the positive semidefiniteness: $$\begin{cases} a \ge 0, \\ ab - b^2 \ge 0, \\ abc - b^2c-c^2b \ge 0. \end{cases}$$ Using your conditions $a, b, c > 0$ we get ...

0

The if part: $cl(C_1)=cl(ri(C_1))=cl(ri(C_2))=cl(C_2)$. The only if part: $ri(C_1)=ri(cl(C_1))=ri(cl(C_2))=ri(C_2)$. See proof of Proposition 1.3.5 in Convex Optimization Theory by Bertsekas.

1

To show uniqueness is easy, and not covered by other answers. If you have two distinct convex polygons which contain all your points, then their intersection is also a convex polygon which contains all the points. The two original polygons cannot both be minimal unless they coincide. To use your rubber band analogy, assuming $P$ is finite, you could ...

3

Is it normal that I have the hardest time when I'm trying to prove statements that are blatantly obvious on a visual and/or intuitive level? Yes, this is quite common. The Jordan curve theorem is a classic example of a geometrically obvious theorem that is true, but quite hard to prove. The idea that there do not exist space-filling curves is a ...

0

I assume your set P is finite (you are talking about a polygon). You can start by choosing the rightmost point $P_0$ (the lowest one if there are more) and imagining a vertical line through it. Let's call $r$ the bottom ray of the line starting at $P_0$. Now choose the point which minimizes the oriented angle (clockwise) between $r$ (the farther one from ...

1

For practical computation I would use the fact that $\nabla f^*$ is the inverse of $\nabla f$ (see here). By the chain rule, $$\nabla f(x) =|x|^{p-1} \nabla |x| = |x|^{p-1} \frac{x}{|x|}$$ which means the direction of $x$ stays the same but its length is raised to power $p-1$. The inverse of this map is u\mapsto |u|^{1/(p-1)} \frac{u}{|u|} = |u|^{q-1} ... 1 A differentiable function of one variable is convex iff the derivative is non-decreasing. A function f is convex iff for all x,h, the restriction t \mapsto f(x+th) is convex. Combining gives: A differentiable function f is convex iff for all x,h, the restriction t \mapsto f(x+th) is convex iff for all x,h, the derivative (f \circ ... 0 I'll attempt to explain the intuition here. There may be many affine minorants of h with a given slope y, but we only care about the best one: \begin{align} &h(x) \geq \langle y , x \rangle - \alpha \quad \text{for all } x \\ \iff & \alpha \geq \langle y, x \rangle - h(x) \quad \text{for all } x \\ \iff & \alpha \geq \sup_x \, \langle y, x ... 1 Any smooth function can be decomposed into a difference of convex functions. In this case, the following should work. We want f(x)=g(x)-h(x), where g and h are the convex functions. Since f is convex for x < \sqrt{2 \alpha}, and concave for x > \sqrt {2\alpha}, we can let g=f for x < \sqrt{2 \alpha}, and g be linear for x > ... 0 Because you didn't specify the domain and range, assume f is a real function. Also, so the inverse is defined, assume f is one-to-one. Thus f is either increasing or decreasing. Now the inverse of f reflects f about the line y=x. Can you visualize what this reflection does to convex or concave functions? 0 I'm not sure whether you mean the inverse of the function, i.e. f^{-1} such that f(f^{-1}(x))=f^{-1}(f(x))=x or of the reciprocal, i.e. f(x)^{-1}=1/f(x). The reciprocal of a convex function need not be concave, for example look at f(x)=e^x. f is convex. Its reciprocal f(x)^{-1}=1/f(x)=e^{-x} is also convex. On the other hand, if f is convex, ... 1 If you know that \sigma = \min f(\mathbf{x}) subject to \mathbf{x}\in Cand you want to want to minimize g(\mathbf{x}) for all such \mathbf{x}, I think all you have to do is \min_{\mathbf{x}} g(\mathbf{x}) \;\;\; \mathrm{s.t.} \;\;\; f(\mathbf{x})=\sigma \wedge \mathbf{x} \in C. $$So, if you can solve the original problem and get the minimum ... 0 No, this is not possible. The easiest counterexample is$$\text{Minimize } x^2 \text{ s.t. } -1 = -x^2$$with minimum 1 and the relaxation would be$$\text{Minimize } x^2 \text{ s.t. } -1 \le -x^2$$with minimum 0. 0 Here is another way: The supremum of an arbitrary collection of convex functions is convex (this can be seen by noting that the epigraph of the supremum is the intersection of the constituent epigraphs). Since each function z \mapsto \langle c, z \rangle is convex, it follows that the supremum over all c \in C is also convex. 1 The inequality$$ \sup_{x\in A} (f(x)+g(x))\le \sup_{x\in A} f(x)+\sup_{x\in A} g(x)$$holds in general. 0 Here is the gist of part 2. Let me know if you have any questions. Let x_1, x_2 \in C_2. Then as g convex over C_2 this implies that$$g(tx_1 +(1-t)x_2) \le tg(x_1) + (1-t)g(x_2) \le 0$$as x_1,x_2\in C_2 where t\in [0,1] implying that tx_1 + (1-t)x_2 \in C_2 and thus C_2 is convex. Part 3 is very similar to part 1 and 2. Let x_1, x_2 \in ... 2 You can do the following: Generate a random symmetric matrix (Matlab: rand) Do an eigenvalue decomposition (Matlab: eig), returning an orthogonal matrix U Generate a random, positive vector and put it on the diagonal of \Sigma U^\top \, \Sigma \, U is a random, symmetric, positive definite matrix with eigenvectors from U and eigenvalues from ... 1 I think you need to broaden your definition of a "function" a bit. When you fix a weight vector w and solve the resulting weighted least squares problem, you will obtain a particular value of the cost function \inf_x \sum_i w_i(a_i^Tx-b_i)^2. Let's call that value g. Sure, you'll also get a vector x out of it, but just ignore it for now. Now, if ... 1 g\left(\omega\right) is not the cost function here. g\left(\omega\right) is the infimal value of this special cost function depending on omega: \sum_{i}\omega_{i}\left(a_{i}^{T}x-b_{i}\right)^{2}. This defines a mapping g:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\left\{-\infty\right\}. The set of all points where g is not infinity, we call ... 1 Since λ_{\max}(A)=\sup_{\|v\|\le 1} f_v(A) with f_v(A)=v^TAv is the supremum over a family of linear functions, which means it is also a family of convex functions, it inherits the property of convexity. However, you should be careful in defining what it means that a matrix valued function x\mapsto A(x) is convex. What would be the epigraph of the ... 1 Let V = \{ v_k \}_{k=1}^p and suppose C = \operatorname{co} V. Let \Sigma = \{ \lambda \in [0,1]^p | \sum_l \lambda_k = 1 \}. We see that \Sigma is compact (closed & bounded). Define f: \mathbb{R}^p \to \mathbb{R}^p by f(\lambda) = \sum_k \lambda_k v_k. It is easy to see that f is continuous, and so f(\Sigma) = C is compact. Another ... 1 In convex geometry, a supporting line or supporting hyperplane of a convex set C is an affine co-dimension-1 subspace \{y:a^Ty=b\} outside of C that touches C in some point or larger facet, i.e., so that a^TC\le b with equality assumed at least once. From there it is just a twist of thought to compute the constant as b=\sup a^TC and formalize ... 1 Suppose you are given f, and have a candidate function g that might be equal to f^* (the the fenchel conjugate of f), but you're not sure. You can try checking numerically that:$$f(x) + g(y) \ge \langle x,y\rangle$$for various values of x,y. Any counterexample to the inequality is certificate that g \ne f^*. To prove that g=f^*, you need to ... 0 As the proof states, for k > d+1, the k-1 points x_2 − x_1, \ldots, x_k − x_1 must be linearly dependent, since they are in a d dimensional space. For k \le d+1, it is possible that the k-1 points x_2 − x_1, \ldots, x_k − x_1 are linearly independent, so it is not necessarily true that the process of eliminating points can continue. 1 The function \psi(z)= \max(z_1,z_2) is convex, and a convex function satisfies \psi(\theta w+ (1-\theta) z) \le \theta \psi(w)+ (1-\theta) \psi(z) for all \theta \in [0,1]. Letting w=f_1(x), z=f_2(x)  gives the desired result. Note: To see why the \max is convex, suppose the functions f_1,f_2 are convex. Then we have (with \lambda \in [0,1]) ... 1 The property in use is$$\max\{a+b, c+d\}\le \max\{a,c\}+\max\{b,d\}$$Proof: a+b\le \max\{a,c\}+b\le \max\{a,c\}+\max\{b,d\}. Similarly c+d\le \max\{a,c\}+\max\{b,d\}. 0 Your conjecture is false. Define the function f on the unit circle by$$ f(x,y) = x^2 + 3 y^2 $$The unit circle is the boundary of a convex region given by  x^2+y^2 \le 1, you can chect that on the unit circle f has a local maximum for x=1, y=0, but that is not a global maximum (the global maximum has the value 3). 0 1.\rightarrow. Assume that C_1 is convex. Then by definition$$\sum_{i=1}^{n}\lambda_ix_i \in C_1,$$for all x_i \in C_1 and nonnegative numbers \lambda_1,\ldots,\lambda_n such that \sum \lambda_i=1. Then$$h\big(\sum_{i=1}^{n}\lambda_ix_i\big)=0=\sum_{i=1}^{n}\lambda_ih(x_i),$$where both sides are equal to zero due to the definition of C_1 ... 0 Thank you for your helpful comment Dirk. I also had a similar question. By the way, for the cost c(x,y)=|x-y|, if we want to find the subdifferential of \phi(x)=|x|, it would be;$$y\in \partial^c\phi\quad then\quad |z|\geq|x|+|x-y|-|z-y||z-x|\geq|z-y|-|x-y|\geq|x|-|z|$$which is true for any y\in R^n so is it true to conclude that \partial ... 0 Proof: Let (h^n) \in T_S, where h^n \to h; then we have \bar{x} + \lambda^n h^n \in S for some (\lambda^n) \geq 0. Now consider \gamma \geq 0, then notice that \bar{x} + (\lambda^n/\gamma) \gamma h^n \in S, implying that (\gamma h^n )\in T_S. But by definition, T_S is closed, and hence \gamma h \in T proving the statement. So it was a ... 0 I don't think you're going to get anywhere this way- it seems as though what you're trying to prove at the end there is stronger than what is really true! Let Conv(A) denote the convex hull of A, which for me will be the set of all finite convex combinations of elements of A. We need not worry about closures: the Hausdorff distance only sees closures, ... 0 It is known that the equivalence (1)\iff (2) characterizes inner product spaces. Namely, a parallelogram law holds iff a norm is strongly convex with modulus 1. 1 As noted in a comment, this is true. A standard reference: Theorem 25.1 on page 242 of Rockafellar, R. Tyrrell, Convex analysis. Princeton University Press, Princeton, NJ, 1970. By the way, the book has 2885+388 MathSciNet citations as of now (388 coming from its 1997 preprint). 1 It is neither convex nor concave, but it is quasiconcave. See my answer to your other question for more information, or go straight to Boyd & Vandenberghe. The good news is that fixed lower bounds on the ratio can be represented in convex optimization problems; since, after all,$$g(x)/a(x) \geq \alpha \quad\Longleftrightarrow\quad g(x) \geq \alpha ...

0

In many cases, the ratio of a concave and a convex function is quasiconcave. Quasiconcavity and quasiconvexity are discussed in, e.g., Boyd & Vandenberghe; consult them for details. A function $f$ is quasiconvex if its superlevel sets $\{x\,|\,f(x)\leq\alpha\}$ are convex for all fixed $\alpha$; a function $g$ is quasiconcave if its sublevel sets ...

1

You can also have examples of strictly convex functions $f$ such that $\frac{f(x)}{x}$ is not convex. A very easy example is $\frac{e^x}{x}$, which is not convex on $(-\infty, 0)$ (indeed, there it is concave, as you may prove by computing its second derivative).

0

The function $f(x)\equiv 1$ is both convex and concave, whereas $g(x)=\frac{f(x)}{x}=\frac 1x$ has a convex and a concave branch, hence is, globally, neither.

1

If $x=(x_1,\dots,x_n)\in\mathbb{R}^n$, $x_k>0$, then $$\frac{g(x)}{f(x)}=n\frac{(x_1\dotsm x_n)^{1/n}}{x_1+\dots+x_n}.$$ Fix $x_2=\dots=x_n=1$. It is easy to see that the resulting function $$n\frac{x_1^{1/n}}{x_1+n-1}$$ is neither concave nor convex, implying the same for $g(x)/a(x)$. Graph of $h(x,y)$ for $0<x<1$ and $0<y<10$:

2

There is no general rule. Let $f(x)=1$; then $f$ is both concave and convex. Let $g(x)=e^{x^2}$, which is convex. However $$\frac{f(x)}{g(x)}=e^{-x^2}$$ is neither concave nor convex.

1

Note that $-c(z,y) + c(x,y) = \frac{|x|^2}{2} - \frac{|z|^2}{2} - \langle y,x-z\rangle$ and hence, $y$ is in the $c$-subdifferential if for all $z$ it holds that $$\phi(z) + \frac{|z|^2}{2} \geq \phi(x) + \frac{|x|^2}{2} + \langle y,z-x\rangle.$$ This says that some $y$ is in the $c$-subdifferential of $\phi$ at $x$ if and only if it is in the usual ...

Top 50 recent answers are included