Convex analysis is the study of properties of convex sets and convex functions. For questions about optimization of convex functions over convex sets, please use the (convex-optimization) tag.

learn more… | top users | synonyms (1)

23
votes
2answers
819 views

Does local convexity imply global convexity?

Question: Under what circumstances does local convexity imply global convexity? Motivation: Classically, a twice differentiable function $f:\mathbb{R} \rightarrow \mathbb{R}$ is convex if and only ...
18
votes
0answers
441 views

How many points of intersection between an ellipse and an $L_p$-circle?

Consider an ellipse $E$ in the plane, centered at the origin. (In my case, the minor axis points into the nonnegative quadrant.) Let S be an "$L_p$-circle": $S = \{(x,y) : |x|^p + |y|^p = 1\}$, ...
17
votes
1answer
517 views

Is $[0,1]^\omega$ homeomorphic to $D^\omega$?

Let $n\in \mathbb N$ and let $D^n$ be the closed $1$-ball in $\left(\mathbb R^n, \|\,\cdot\,\|_1\right)$. It is not too hard to show that $[0,1]^n \cong D^n$ in this case. This observation leads to ...
17
votes
2answers
528 views

For what functions $f(x)$ is $f(x)f(y)$ convex?

For which functions $f\colon [0,1] \to [0,1]$ is the function $g(x,y)=f(x)f(y)$ convex over $(x,y) \in [0,1]\times [0,1]$ ? Is there a nice characterization of such functions $f$? The obvious ...
15
votes
6answers
2k views

can any continuous function be represented as a sum of convex and concave function?

I read that any continuous function can be represented as a sum of convex and concave function, meaning for all $f(x)$, $f(x) = g(x) + h(x)$ where $g$ is convex and $h$ is concave. There could be ...
15
votes
6answers
779 views

What are the main uses of Convex Functions?

Up till now I have just learned that the concept of convexity in functions of one variable is used to complete the graphs of functions, meaning to locate points of inflexion and see if the graph is ...
15
votes
1answer
279 views

Expected size of subset forming convex polygon.

If there are $4$ random points in the plane whose horizontal coordinate and vertical coordinate are uniformly distributed on the interval $\left(0,1\right)$, what is the expected largest size (or ...
14
votes
2answers
1k views

Farkas’ lemma: purely algebraic intuition

Here is a statement of Farkas Lemma from the Wikipedia. Let $A$ be an $m \times n$ matrix and $b$ an $m$-dimensional vector. Then, exactly one of the following two statements is true: There exists ...
14
votes
2answers
287 views

Construct an example of set $A$ for which $A+A=A $ but $0∉cl(A)$

How to prove that convexity is necessary condition in this question? Need to construct an example of set $A$ for which $A+A=A$ but $0 \notin cl(A)$. From the linked question follows that $A$ must be ...
14
votes
1answer
205 views

Legendre Transformation of a Lagrangian in Classical Mechanics

I have some questions about the Legendre Transformation of a Lagrangian in Classical Mechanics to the Hamiltonian: We start with a Lagrangian $L(q,\dot{q})=\frac{\langle \dot{q} , \dot{q}\rangle }{2} ...
13
votes
1answer
269 views

A beautiful inequality for convex functions

Let $f\in \mathcal{C}([0,1],\mathbb R_+)$ increasing. Prove that there exist $g,h\in \mathcal{C}([0,1],\mathbb R)$, convexs, such that $g\leqslant f \leqslant h$ and : $$\displaystyle ...
13
votes
2answers
520 views

Two cubes in unit cube

A cube of side one contains two cubes of sides $a$ and $b$ having non-overlapping interiors. How to prove the inequality $a+b \le 1?$ The same question in higher dimensions.
12
votes
4answers
2k views

Why does a convex set have the same interior points as its closure?

Let $C$ be a convex subset of $\mathbb{R}^n$. I've been trying for hours to prove that $\dot{\overline{C}}=\dot{C}$. Somehow my intuition completely fails me. I found a proof in a textbook, but just ...
12
votes
2answers
456 views

A tree of convex sets?

This was suggested by a problem on FreeNode's #math a little while ago... Construct a directed graph $\Gamma$ with vertex set the set of compact convex sets in $\mathbb R^2$, and an arrow $A\to B$ if ...
12
votes
1answer
355 views

Union of convex sets

I have the following problem: Let $K$ and $K'$ be two convex compact sets in $\mathbb{R}^n$, with $n \geq 2$. Assume that $K$ and $K'$ both have a smooth ($\mathcal{C}^2$) boundary. Assume ...
12
votes
1answer
313 views

What is the probability of having a pentagon in 6 points

If the probability that $5$ random points in the plane whose horizontal coordinate and vertical coordinate are uniformly distributed on the interval $\left(0,1\right)$ occur to be the vertices of a ...
11
votes
2answers
515 views

How to show that $\mathbb R^n$ with the $1$-norm is not isometric to $\mathbb R^n$ with the infinity norm for $n>2$?

Could you please give me a hint to prove that $\mathbb{R}^n$ with the 1-norm $\lvert x\rvert_1=\lvert x_1\rvert+\cdots+\lvert x_n\rvert$ is not isometric to $\mathbb{R}^n$ with the infinity-norm ...
11
votes
1answer
539 views

Showing $\left|\frac{a+b}{2}\right|^p+\left|\frac{a-b}{2}\right|^p\leq\frac{1}{2}|a|^p+\frac{1}{2}|b|^p$

For $a,b \in \mathbb R$, $p\geq2$ I try to show $$\left|\frac{a+b}{2}\right|^p+\left|\frac{a-b}{2}\right|^p\leq\frac{1}{2}|a|^p+\frac{1}{2}|b|^p.$$ Is this a popular inequality (At least I could not ...
11
votes
5answers
398 views

Proof of the inequality $(x+y)^n\leq 2^{n-1}(x^n+y^n)$

Can you help me to prove that $$(x+y)^n\leq 2^{n-1}(x^n+y^n)$$ for $n\ge1$ and $x,y\ge0$. I tried by induction, but I didn't get a result.
11
votes
2answers
180 views

n-simplex in an intersection of n balls

Consider a $n$-simplex, $n \geq 2$ with vertices $x_i,i=1,...,n+1$. For each edge $(i,j)$, consider $n$-ball $B_{ij}$ such that vertices $x_i$ and $x_j$ are antipodal on this ball. Fix a point $x_0$ ...
11
votes
1answer
463 views

Elementary applications of Krein-Milman

Recall that the Krein-Milman theorem asserts that a compact convex set in a LCTVS is the closed convex hull of its extreme points. This has lots of applications to areas of mathematics that use ...
11
votes
1answer
814 views

Minkowski Inequality for $p \le 1$

I've been trying to prove the concavity of a particular function which I reduced to proving the reverse Minkowski Inequality for $p \le 1$, $p \ne 0$ for arguments in $\mathbb{R}^{n}_{+}$. That is, ...
11
votes
1answer
93 views

Expected values of some properties of the convex hull of a random set of points

$N$ points are selected in a uniformly distributed random way in a disk of the unit radius. Let $P(N)$ and $A(N)$ denote the expected perimeter and the expected area of their convex hull. For what ...
10
votes
2answers
553 views

If the Minkowski sum of two convex closed sets is a Euclidean ball, then can the two sets be anything other than Euclidean balls?

If for two convex closed sets $S_1$ and $S_2$, the Minkowski sum is a Euclidean ball then can $S_1$ and $S_2$ be anything other than Euclidean balls themselves. I suspect they can be but I haven't ...
10
votes
2answers
281 views

cosh x inequality

While reading an article on Hoeffding's Inequality, I came across a curious inequality. Namely $$\cosh x \leq e^{x^2/2} \quad \forall x \in \mathbb{R}$$ I tried many ways to prove it and finally, ...
10
votes
1answer
386 views

invex functions and their usefulness?

An invex function $f$ is a differentiable function from $\Bbb R^n$ to $\Bbb R$ that for some function $\eta : \Bbb R^n \times \Bbb R^n \to \Bbb R^n$ satisfies for all $x, u$, $f(x) - f(u) \geq \eta(x, ...
10
votes
4answers
145 views

Show that $\frac{x}{1-x}\cdot\frac{y}{1-y}\cdot\frac{z}{1-z} \ge 8$.

If $x,y,z$ are positive proper fractions satisfying $x+y+z=2$, prove that $$\dfrac{x}{1-x}\cdot\dfrac{y}{1-y}\cdot\dfrac{z}{1-z}\ge 8$$ Applying $GM \ge HM$, I get ...
10
votes
1answer
414 views

Surface area of a convex set less than that of its enclosing sphere?

Is the boundary measure ("surface area") of a convex set in $\mathbb{R}^n$ less than the boundary measure of it's enclosing hypersphere (smallest hypersphere that contains the set)? In 2D I've found ...
10
votes
3answers
361 views

Easy but hard question regarding concave functions!

I have a question about concave functions. Let $f:[0,T]\rightarrow R^+$ is a concave function. Let $S=\int_0 ^ T f(x)dx$ and $R=\frac S T$. Show that there is an interval $[a,b]$, where $0\leq a \leq ...
10
votes
2answers
175 views

What is the expected convex depth of a set of $m$ randomly chosen points in the unit square?

Definition. Let $X$ be a set of points in $\mathbb{R}^2$. Then the vertex sequence of $X$ is defined by $X_{0}=X$, and $X_{i+1}=\left\{x\in \operatorname{Conv}(X_{i}): x \notin ...
10
votes
1answer
129 views

How many hyperplanes does it take to separate $n$ points in $\mathbb{R}^m$?

By 'separate', I mean that each point lies in its own little region/cell. For instance, it takes a minimum of $P = 4$ lines to separate $n = 7$ points in $\mathbb{R}^2$ ($m=2$), assuming that no 3 ...
10
votes
2answers
254 views

Convexity of a complicated function

Let $\mathbb{S}$ be a 2-D convex set in the positive quadrant. Let us define \begin{align} y_L=\min_{(x,y)\in\mathbb{S} }y \\ y_R=\max_{(x,y)\in\mathbb{S} }y \end{align} For any positive number ...
10
votes
1answer
260 views

Approximating the area below average of a concave function

Given a non-decreasing concave function $f:[0,1]\rightarrow \mathbb{R}^+$. Define \begin{align*} F(n)=\displaystyle\sum_{i=1}^n \min\left\{\frac{1}{n},\frac{f\left(\frac{i}{n+1}\right)}{n+1}\right\} ...
9
votes
2answers
304 views

On the convexity of element-wise norm 1 of the inverse

Let us define $\|A\|_1$ the element wise norm 1 of a matrix $A \in \mathbb{R}^{n \times m}$ as $$ \|A\|_1= \sum_{i,j} |A_{i,j}|. $$ Obviously, this function is convex over $\mathbb{R}^{n \times m}$. ...
9
votes
1answer
155 views

Subdifferential boundary conditions: Testing pointwise or with $L^2$ functions

Let $\phi \colon \mathbb R^n \to \mathbb R$ be convex, proper and lower semi-continuous (lsc). Let $M$ be a measurable subset of $\mathbb R^n$. We can define a functional $\Phi \colon L^2(M) \to ...
8
votes
1answer
188 views

Show that $2^n>1+n\sqrt{2^{n-1}}$

If $n$ be a positive integer greater than $1$, then prove that $$2^n>1+n\sqrt{2^{n-1}}$$ I found this problem under $AM \ge GM$ chapter. Help me to solve this problem using $AM \ge GM$. ...
8
votes
3answers
147 views

Prove that $\dfrac{b^2+c^2}{b+c}+\dfrac{c^2+a^2}{c+a}+\dfrac{a^2+b^2}{a+b} \ge a+b+c$

If $a,b,c$ are positive , show that $$\dfrac{b^2+c^2}{b+c}+\dfrac{c^2+a^2}{c+a}+\dfrac{a^2+b^2}{a+b} \ge a+b+c$$ Trial: Here I proceed in this way ...
8
votes
2answers
1k views

Dual of a dual cone

Any hint on how to prove the following please: Let $K$ be a convex cone, and $K^*$ its dual cone. Prove that $K^{**}$ is the closure of $K$. Thanks!
8
votes
2answers
791 views

The measurability of convex sets

How to prove the measurability of convex sets in $R^n$ ? I have seen a proof, but too long and not very intuitive.If you have seen any, please post it here.
8
votes
1answer
171 views

Stochastic gradient descent for convex optimization

What happens if a convex objective is optimized by stochastic gradient descent? Is a global solution achieved?
8
votes
1answer
787 views

A real differentiable function is convex if and only if its derivative is monotonically increasing

I'm working on a problem in baby Rudin, Chapter 5 Exercise 14 reads: Let $f$ be a differentiable real function defined in $(a,b)$. Prove that $f$ is convex if and only if $f'$ is ...
8
votes
1answer
333 views

Sequence of convex functions

If a sequence of convex functions $\{ f_n \}$ on [0,1] converges pointwise to a continuous function f, then is the convergence uniform? The questions is almost identical to this one, except that the ...
8
votes
1answer
226 views

Proof that the set of doubly-stochastic matrices forms a convex polytope?

Does the set of all doubly-stochastic matrices form a convex polytope? In general, I wonder how the proofs of convexity and geometry can be established for sets of matrices of this kind? Anything to ...
7
votes
3answers
221 views

How to prove that if convex $A \subset \mathbb{R}^n$ and $A+A=A$ then $0 \in cl(A)$?

How to prove that if convex $A \subset \mathbb{R}^n$ and $A + A = A$ then $0 \in cl(A)$? For a example of $A$ which holds a condition but $0 \notin A$ consider $(0,\infty)$.
7
votes
2answers
3k views

Is the composition of $n$ convex functions itself a convex function?

Is a set of convex functions closed under composition? I don't necessarily need a proof, but a reference would be greatly appreciated.
7
votes
4answers
205 views

Why are convex sets assumed / defined to be subsets of vector spaces (and not of more general spaces)?

Roughly speaking, my question is: Why are convex sets assumed to be subsets of vector spaces? Well, one might answer that convex sets are defined to be subsets of vector spaces, but this is not the ...
7
votes
1answer
2k views

Convexity and equality in Jensen's inequality

The problem: Recall that we saw that when $\mu$ is a probability measure on $X$ and $f$ is integrable with respect to $\mu$, then $$ \exp\left(\int_X f(x)d\mu(x)\right) \leq \int_X ...
7
votes
1answer
164 views

$\max\min$ problem

Suppose there is a real valued function $f(x,y)$ where $x,y$ are vector variables $x\in\mathbb{R}^n$ $y\in\mathbb{R}^m$. Moreover $f$ is strictly/concave in $x$ and strictly/convex in $y$. $f$ is also ...
7
votes
2answers
198 views

How prove this inequality generalized from 1969 IMO problem 6

Let $x_{1},x_{2},y_{1},y_{2},z_{1},z_{2},w_{1},w_{2} $ are all positive numbers, and such $$x_{1}y_{1}z_{1}-w^3_{1}>0,\; \text{ and }\;x_{2}y_{2}z_{2}-w^3_{2}>0.$$ show that ...
7
votes
1answer
188 views

How to understand convex duality intuitively

Is there an intuitive way to understand the convex duality? If the primal problem is minimization, the dual is maximization over another set of variables - but I would love to have a geometric ...