Tag Info

New answers tagged

1

angryavian's answer should also point you into the right direction for your second question on why no norm-minimal element exists: For any $f \in C$ there holds $$\int_0^{1/2} f(x) \,\text{d}x \leq \frac 1 2 \| f \|_\infty \quad\text{and}\quad - \int_{1/2}^1 f(x) \,\text{d}x \leq \frac 1 2 \| f \|_\infty,$$ so a norm-minimal $f$, i.e. $\| f \|_\infty = 1/2$ ...


3

In my comment above, I noted $$\int_0^{1/2} f(t) \mathop{dt} - \int_{1/2}^1 f(t) \mathop{dt} \le \|f\|_\infty.$$ I have a hunch that the definition of $M$ should be $$\int_0^{1/2} f(t) \mathop{dt} - \int_{1/2}^1 f(t) \mathop{dt}=1/2$$ in order for part ii) to work. [Or more generally, the number in the definition of $M$ and the number in part ii) should be ...


2

I like Valeriy's answer, but let me also point out that the first question is a special case of Helly's theorem, which says that in $\mathbb R^d$, if you have at least $d+1$ sets such that any $d+1$ of them have a non-empty intersection, then the intersection of all the sets is non-empty.


3

For second question, let $m=2, n=3$. We can easily draw tree circles each pair of which intersects and all three of them have empty intersection. So the answer is negative. As for the first one, a convex set $X$ has, by definition, a property that for any two points $u, v \in X$ point $au + (1-a)v$ belongs to $X$ for any $a \in [0, 1]$. In any words, whole ...


2

Convexity implies $f(y)\ge f(x)+\langle \nabla f(x),y-x\rangle$ for all $x,y$. Specializing this to the points of your set, you will find they are points where $f$ attains its global minimum, say $m$. Argue that $\{x:f(x)=m\}$ is convex.


2

If convex, the equality is $\geq$. If concave, the equality is $\leq$. If both a true, the function is both concave and convex. Therefore, it is linear (try showing this using definitions of convex, concave and linear). Also, I'm not sure, but I think such implication holds without the assumption that f is convex.


1

It implies that $x \mapsto f$ is a linear function.


0

Since you didn't provide any context, this is guesswork. I assume $x = (x_1,\dots,x_n)^T$, where $x_i\in[l,u]$ are real numbers. Then $$ M = \pmatrix{1\\x}\pmatrix{1 & x^T} = \pmatrix{1\\x_1\\\vdots\\x_n}\pmatrix{1&x_1&\cdots&x_n} = \pmatrix{ 1&x_1&x_2&\cdots&x_n \\ x_1 &x_1^2 & x_1 x_2 &\cdots&x_1 x_n \\ x_2 ...


2

This seems to be a little trickier than I thought first! I'll be using the following lemma: A function $f$ is convex if and only if its epigraph $$\text{epi}(f) = \{(p, t) | \; p \; \text{in domain of} \;f \; \text{and} \; f(p) \leq t\}$$ is a convex set. Let $f(x, Q) = x^T Q^{-1}x$ with domain $\mathbb{R}^n \times S^n_{++}$ where $S^n_{++}$ is the set ...


1

Here's a solution to the first problem. (For these sorts of problems I suggest drawing pictures - it's amazing how helpful blobs on a page can be.) Harald's gives you the second. Because $K$ is closed, there's a point in $K$ of minimal distance to the origin; call it $v=(x,y)$. Then consider the normal line $D = \text{span}(-y,x)$. It suffices to show that ...


3

Two hints for the price of one: For the first one, consider the point $P\in K$ closest to the origin, and take $D$ to be normal to the line from $O$ to $P$. For the second one, apply the first one to the set $K-L=\{u-v\colon u\in K, v\in L\}$.


3

Let $A= \{ \lambda \in (0,1)^3 | \sum_k \lambda_k = 1 \}$ and define $\phi:A \to \mathbb{R}$ by $\phi(\lambda) = f(\sum_k \lambda_k x_k )-\sum_k \lambda_k f(x_k)$. Note that $\phi$ is convex and since $f$ is convex on $D$, we have $\phi(\lambda) \le 0$ for $\lambda \in A$. By assumption, $\phi(t) = 0$, so $\phi$ has a maximum on $A$ at $t$. It follows that ...


0

This's a theorem in real analysis whose proof is based on the following two inequalities: (Clarkson's Inequality) Let $f$ and $g$ be in $L^p$, then (1) For $p\geq 2$, $$\|{\frac{f+g}{2}}\|_p^p+\|\frac{f-g}{2}\|_p^p\leq \frac{1}{2}(\|f\|_p^p+\|g\|_p^p).$$ (2)For $p\in(1,2)$, $$\|f+g\|^p_p+\|f-g\|_p^p\leq2(\|f\|^p_p+\|g\|^p_p)^{q-1}.$$ To prove these ...


1

In Minkowski's inequality, equality holds if and only if $f$ and $g$ are linearly dependent. If $f,g$ have norm $1$, the only way for them to be linearly dependent is if $f = \lambda g$ with $|\lambda| = 1$. Plugging this into your expression for $h$, we get $$h = \frac{1}{2}(f+g) = \frac{1}{2}(\lambda g+g) = \frac{\lambda+1}{2}g.$$ Then $$\|h\| = ...


1

But this is not true. For $y(x)$ to be convex, you need $\frac{dy}{dx}$ to increase, not $\frac{y}{x}$. And $$ \frac{dy}{dx}= \frac{dy}{dI}:\frac{dx}{dI} = \frac{\frac{dy}{dI}}{1-\frac{dy}{dI}} $$ (since $x = I-y$). So $\frac{dy}{dx}$ iff $\frac{dy}{dI}$ increases, or, in other words, $y(x)$ is convex iff $y(I)$ is convex. Consider the following example (it ...


2

Suppose for some $x\in\mathbb{R}^k$, there are two distinct $p_1$ and $p_2$ s.t. $|x-p_1|=|x-p_2|=\min_{y\in E}|x-y|$. But the function $f(t)=|x-(tp_1+(1-t)p_2)|$ is a strictly convex hyperbola (except if $x\in E$), and $f(0)=f(1)$. By Rolle's theorem, we know that $\exists c\in (0,1)$ s.t. $f'(c)=0$ and that must be the unique minimum point of the ...


3

It suffices to show that in any closed convex set there is a unique closest point to $0$. if $0 \in E$ this is obvious so assume $0 \notin E$. If $d = \inf_{y \in E} |y|$, then $E \cap \{y \text{ }|\text{ }|y| \le d + 1\}$ is closed and bounded, hence compact. The norm on $\mathbb{R}^n$ is continuous, and so the norm attains a minimum is attained at some ...


0

It seems the following. Each six points form a hexagon (excluding some degenerated cases), but this hexagon may be non-convex. A polygon is convex iff each four vertices of it form a convex quadrilateral. May be four points form a convex quadrilateral iff them can be separated into to pairs, say $\{a,b\}$ and $\{c,d\}$ such that segments $[a,b]$ and ...


0

Let $\lambda_n$ be such that $|f_n(x)-f(x)|\leq \lambda_n$. Since $f_n(x)$ is convex we have: $$ f_n^+(x) \leq \frac{f_n(x+\delta_n)-f_n(x)}{\delta_n}$$ for a sequence $\delta_n$ to be detemined later. By using the uniform converge of $f_n(x)$ we have: $$ f_n^+(x) \leq \frac{f(x+\delta_n)-f(x)+2\lambda_n}{\delta_n} $$ $$ \leq ...


2

Let ${\cal H_x}$ be the set of closed halfspaces containing $x$ in their interior. Hahn Banach shows $\cap_{H \in {\cal H_x}} = \{x\}$. Suppose $x_n \to x$, and select $H \in {\cal H_x}$. Then there is some $N$ such that $x_n \in H$ for all $n \ge N$ and so we have $K_n \subset H$ for all $n \ge N$. Consequently, $\cap_n K_n \subset H$. Hence we have $\cap_n ...


0

gerw is right. $u^Tx\leq \|u \|_2\|x\|_2$, restricting that $\|u\|_2 \leq 1$, then $u^Tx\leq \|u \|_2\|x\|_2\leq \|x\|_2\leq y$.


4

We first show that if $\{x_n\}$ converges to $x$ then $\bigcap_{n=1}^\infty K_n = \{x\}$. For $\epsilon > 0$, let $N$ be large enough that $n > N$ implies $|x_n - x| < \epsilon$. Then for all $n > N$, the set $T_\epsilon = \{(y_1, \dots, y_n) \text{ }|\text{ }|x_i - y_i| \le \epsilon \text{ for all }i\}$ is clearly a closed convex set containing ...


1

Assume, to make things simpler, that $f$ has a derivative. As $f$ is convex, for each $a$: $$ f(y) \ge (y-a)f'(a) + f(a) $$ so in particular, as $\phi\ge 0$: $$ \int f(u(x))\phi(x) dx \ge \int \left[ (u(x)-a)f'(a) + f(a)\right] \phi(x) dx \\= \int (u(x)-a) \phi(x) dx \times f'(a) + f(a) $$ Now with $a = \int u(x)\phi(x) dx$, $ \int (u(x)-a) \phi(x) dx ...


1

It is the original Jensen's inequality applied to the real line endowed with the probability measure $\mu(A):=\int_A\phi(x)\mathrm dx$ (the assumptions guarantee that $\mu$ is a probability measure).


4

Let $f(x) = 1- e^{-x}$. Then for $x > 2$ $$g''(x) = e^{-x}(2-x) < 0$$ and $g(x) = xf(x)$ is not convex.


1

If we assume $h:\mathbb R^2 \to\mathbb R$ to be convex and component-wise nondecreasing, i.e. $$h(x,\cdot) \text{ and } h(\cdot, y) \text{ are nondecreasing for all }x,y\in\mathbb R\\ h(\lambda x + (1-\lambda)x', \lambda y + (1-\lambda) y') \le \lambda h(x,y) + (1-\lambda) h(x',y')$$ We can prove that $$h(g_1(x), g_2(y))$$ is convex for $g_1, g_2:\mathbb ...


0

Read Convex Optimization by Boyd & Vandenberghe---Chapter 3 specifically, but you need to be comfortable with the first two chapters to fully digest that. There you will find a set of composition rules that govern when convexity/concavity is preserved in the composition of nonlinear functions. You can see a proof of one of those rules here on Math.SE, ...


1

In finite dimensions the picture is quite clear, because we have the inner product. In $\mathbb{R}^2$, each linear functional is specified by taking the inner product with a vector $x = (x_1,x_2)$. The equation $$ \langle x,y\rangle = 1 $$ specifies a line in $\mathbb{R}^2$ at distance $1/\Vert x\Vert$ from $0$. (This is easy geometry.) Regarding ...


0

The statement is false. For example, the set $$X = \{0\} \cup \{ t_1x + t_2x_2 : t_1,t_2 >0, x_1 \neq x_2 \}$$ is a cone, but if we select $y_n = \frac{1}{n}x_1 + x_2$ then notice $\lim y_n = x_2 \notin X$. The situation can be reformuated with $X - \{ 0 \}$ depending on your definition of a cone.


2

Yes, the "$\subseteq$" is trivial since $A_j\subseteq co(A_j)$. For "$\supseteq$" note that $co(A_1\cup\cdots \cup A_k)$ contains $co(A_j)$ for any $j=1,\cdots,k$. Thus $co(A_1\cup\cdots \cup A_k)$ is a convex set containing $co(A_1)\cup \cdots \cup co(A_k)$, hence it contains $co(co(A_1)\cup \cdots \cup co(A_k))$.


0

Since $g$ is concave and positive on $S$, for all $x,y \in S$ and $\lambda \in [0,1]$, $$g[\lambda x + (1- \lambda)y] \geqslant \lambda g(x) + (1-\lambda)g(y)> 0.$$ For every $x,y \in S$, we have $f(x),f(y) > 0$ and $$f[\lambda x + (1- \lambda)y] = \frac{1}{g[\lambda x + (1- \lambda)y]} \\\leqslant \frac{1}{\lambda g(x) + (1-\lambda)g(y)}= ...


0

It suffices to show the convexity in the domain $\Omega=\{x_i>0,\ i=1,\dots,n\}$. Once this is done, to check that the standard definition of convexity holds for a generic couple of points $x$, $y$ you can choose a large $M>0$ so that, calling $\vec{M}=(M,\dots,M)$, both $x'=x+\vec{M}\in\Omega$ and $y'=y+\vec{M}\in\Omega$; then you have ...


0

It's a triangle, which is convex, so its convex hull is itself...


1

This long answer is based on many little observations; at every step I will use the preceding ones, sometimes implicitly. Tell me if some step is not clear. Call $P_1:=P_{C_1}$ and $P_2:=P_{C_2}$. You can assume that $C_1$ is compact (if the compact set is $C_2$, with the following argument you will get that $P_2 P^n(x)$ converges to some $\ell$ fixed by ...


1

When we use Lagrange method on [a linear combination of concave functions constrained to a linear space] and find a local max, will it in fact then be a global max? Yes: A linear combination of concave functions is also concave. A concave function restricted to a linear space (e.g. the hyperplane $g = c$) is concave. A local maximum of a concave ...


0

Lemma 1: Suppose $X_1,…,X_N$ are convex cones. Then $$\bigcap_{i=1}^{N}{X_i}\subset \sum_{i=1}^{N}{\frac{1}{N}X_i}$$ Proof of Lemma 1: Take $x\in\cap_{i=1}^{N}X_i$. Then $x\in X_i$. Since $X_i$ is a convex cone, $\frac{1}{N}x\in X_i$ for each $i$. Therefore, $$x=\sum_{i=1}^{N}\frac{1}{N}x\in \sum_{i=1}^{N}\frac{1}{N}X_i.\blacksquare $$ Lemma 2: Let $X$ be ...


0

From Rockafellar's Convex Optimization book, Theorem 23.3: Let $f$ be a convex function, and let $x$ be a point where $f$ is finite. If $f$ is subdifferentiable at $x$, then it is proper. If $f$ is not subdifferentiable at $x$, there must be some infinite two-sided directional derivative at $x$, i.e. there must exist some $y$ such that $f'(x;y) = ...


0

Not sure if this is what you had in mind, but in the very special case where $f$ and $g$ are both normalized modular functions, this formula works: $$ \widehat{f \times g} (x) = \sum_i \sum_j \hat{f}(e_i) \hat{g}(e_j) \min(x_i,x_j) $$ In general, you can use the values of the $\hat{f}, \hat{g}$ to get the values of the $f,g$, which gives you the values of ...


1

Take $z\in X\cap Y$. Then $z=(1/2)*z+(1/2)*z$ and therefore $z\in(1/2)*X+(1/2)*Y$.


0

I am adapting the proof from Convexity and Optimization in Banach Spaces from my own interpretation. Since $\text{epi} f$ is strictly convex, this means for the pair of points $(x,\alpha), (y,\beta) \in \text{epi} f$ we have the condition $$f(z) < t\alpha + (1-t)\beta,$$ where $t\in[0,1]$ and $z = tx + (1-t)y.$ We are required to show that $f(z) \leq ...


1

Given $x$ and $\epsilon > 0$, take $\delta> 0$ small enough that $$\eqalign{f'_+(x) - \epsilon &< \dfrac{f(x+y)-f(x)}{y} < f'_+(x) + \epsilon \ \text{for}\ 0 < y \le 2\delta \cr f'_-(x) - \epsilon &< \dfrac{f(x+y)-f(x)}{y} < f'_-(x) + \epsilon \ \text{for}\ -2\delta \le y < 0 }$$ Take $n$ so large that $|f_n(t) - f(t)| < ...


0

Given the specific wording of your question, you seem to be confusing the convexity of sets and the convexity of functions, or perhaps what it means for an inequality to be convex. When presented with an equation or inequality along with a claim that it is "convex", what is meant is that the points that satisfy that equation/inequality form a convex set. ...


0

It's fairly easy to see that the plane $x=1$ cuts the tetrahedral solid generated by $\{(0,0,0),(1,1,2),(2,4,-6),(1,3,8)\}$ in a triangular section with vertices $(1,1,2),(1,2,-3),(1,3,8)$. The plane $z=1$ then cuts this triangle along a line segment with an endpoint between the first and second of these vertices: $$ \frac{4}{5} \cdot (1,1,2) + \frac{1}{5} ...


2

The functions $\pi_k: \mathbb{R}^n \to \mathbb{R}$ given by $\phi_k(x) = x_k^m$ are convex for $m$ even and positive. As Robert points out in the comments, the sum of convex functions is convex. Hence $(x,y,z) = x^2+y^4+z^2$ is convex. If $f$ is convex, then the set $\{x | f(x) < L \}$ is easily shown to be convex. In your example, $f(x,y,z) = ...


0

Let $\Sigma_m = \{ \mu \in [0,1]^m | \sum_k \mu_k =1 \}$. Call an element of $\Sigma_m$ a convex multiplier. Suppose $x,y \in K$, then $x=\sum_k \xi_k a_k$, $y = \sum_k \upsilon_k a_k$ for some convex multipliers $\xi, \upsilon \in \Sigma_r$. Let $\mu \in [0,1]$, then it is easy to check that $\mu \xi+(1-\mu)\upsilon$ is also a convex multiplier and so ...


1

If you put $z(x)=x+y(x)$ and $g(x)=x+f(x)$, the equation becomes $$z'(x)=e^{z(x)-g(x)},$$ which is separable, with general solution $$z=-\ln\bigl(C-h(x)\bigr),\qquad h(x)=\int_0^x e^{-g(t)}\,dt.$$ Then $$z'(x)=\frac{e^{-g(x)}}{C-h(x)},\quad z''(x)=\frac{e^{-2g(x)}-(C-h(x))e^{-g(x)}g'(x)}{(C-h(x))^2},$$ so the sign of $z''(x)$ is that of ...


1

I think it's enough to focus on $d$ being the origin as the original problem can be restated at origin using translation. So, we are given a subset $S$ of the positive quadrant, and we would like to maximize $s_1\cdot s_2$. Think of the level sets of $f(s) = s_1\cdot s_2$: if we have two points lying on the same level set, then by taking the straight line ...


1

$Q1$: There is an implicit assumption in the theorem, and that is that $f$ is not identically zero. If $f=0$ then $\{x|f(x)=\alpha\}$ is either empty or the whole Banach space $X$, neither of which is a hyperplane. $H^c =\{ x|f(x)\neq \alpha\}$. Suppose $H^c$ is empty. Then $f(x)\neq \alpha$ is impossible, so $f(x) = \alpha$ for all $x$. This contradicts ...


1

The answer is no. On the real line consider $\Phi(x)=|x| $ (and add some smooth convex function with minimum in zero if you like). Then the minimum is in zero but the subgradient at any positive point is about 1.


0

Here's what's happening. First of all: at risk of re-stating something you already know, a convex optimization problem typically involves minimizing a convex function of the variables, subject to the constraint that the variables must lie in a convex set. Notice that the term "convex" is used in three ways: to describe the optimization model, to describe ...



Top 50 recent answers are included