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
835 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
471 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
2answers
396 views

Convex surface on which any two points $a,b$ can be joined by a curve of length $(\pi/2-\epsilon)|a-b|$

I am trying to solve an exercise on page 13 of the book Metric structures on Riemannian and non-Riemannian spaces by Gromov. Construct a closed, convex surface $X$ in $\mathbb R^3$ such that any ...
17
votes
1answer
524 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
546 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 ...
16
votes
6answers
812 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
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
1answer
287 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
289 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
217 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
281 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
529 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.
13
votes
1answer
101 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 ...
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
465 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
366 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
336 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
542 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
569 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
439 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
259 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 ...
11
votes
1answer
470 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
840 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, ...
10
votes
2answers
583 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
296 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
2answers
185 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$ ...
10
votes
1answer
408 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
146 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
426 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
370 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
179 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
134 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
1answer
262 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
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!
9
votes
2answers
329 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
157 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
193 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
149 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
855 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
191 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
820 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
354 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
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 ...
8
votes
1answer
238 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
224 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
209 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

Is the trace of inverse matrix convex?

Hi I would like to know whether the trace of the inverse of a symmetric positive definite matrix $\mathrm{trace}(S^{-1})$ is convex. Actually I know that the trace of a symmetric positive definite ...
7
votes
4answers
950 views

Is every monotone map the gradient of a convex function?

Recently in a seminar someone mentioned that monotone maps are equivalent to gradients of scalar convex functions, but it's not clear to me why this is true. One direction of the equivalence is ...