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)

12
votes
4answers
3k 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 ...
4
votes
1answer
153 views

Convexity of $\mathrm{trace}(S) + m^2\mathrm{trace}(S^{-2})$

I have the following function $f(S)=\mathrm{trace}(S)+m^2\mathrm{trace}(S^{-2})$ where $S\in \mathcal{M}_{m,m}$ symmetric positive definite matrix. I'm trying to prove the convexity of this function ...
11
votes
2answers
264 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 ...
5
votes
1answer
668 views

Do projections onto convex sets always decrease distances?

Suppose $(M, d)$ is some $\ell_p$ metric space (not necessarily Euclidean), and $C \subseteq M$ is a closed convex set. Consider the projection function $f_C:M\rightarrow C$ defined such that: ...
11
votes
1answer
633 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 ...
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 ...
11
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!
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 ...
9
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.
11
votes
2answers
594 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 ...
5
votes
1answer
4k views

Convexity of the product of two functions in higher dimensions

Exercise 3.32 page 119 of Convex Optimization is concerned with the proof that if $f:\mathbb{R}\rightarrow\mathbb{R}:x\mapsto f(x)$ and $g:\mathbb{R}\rightarrow\mathbb{R}:x\mapsto g(x)$ are both ...
4
votes
1answer
320 views

Limit of derivatives of convex functions

Let $(f_n)_ {n\in\mathbb{N}}$ be a sequence of convex differentiable functions on $\mathbb{R}$. Suppose that $f_n(x)\xrightarrow[n\to\infty]{}f(x)$ for all $x\in\mathbb{R}$. Let ...
3
votes
1answer
109 views

minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$

Suppose there are $n$ points $(x_i, y_i)$ for $i = 1,\ldots,n$. Please find another point $(x, y)$ to minimize function: $$\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$$
3
votes
1answer
604 views

Prove that the convex hull of a set is the smallest convex set containing that set

How do you prove that the convex hull of A is the smallest convex set containing A? edit: definition of a convex hull: Given a set A ⊆ ℝn the set of all convex combinations of points from A is called ...
1
vote
1answer
233 views

interior points and convexity

Question: Let If $P\subseteq \mathbb{R}^n$ be a convex set. show that $int(P)$ is a convex set. I know that a point $x$ is said to be the interior point of the set $P$ if there is an open ball ...
17
votes
1answer
554 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 ...
8
votes
1answer
906 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 ...
15
votes
1answer
294 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 ...
5
votes
1answer
110 views

A convex function that is bounded on a neighborhood is Lipschitz

Let consider a normed vector space $V$. I want to prove that If $f:V\to \mathbb R$ is a convex function and if for some $x_0 \in V$ the function is bounded on a neighborhood $W$ of $x_0$, then ...
3
votes
1answer
398 views

Differentiability of Moreau-Yosida approximation.

I want to show that if $X$ is a reflexive Banach space with norm of class $\mathcal{C}^1$ and $f\colon X\to\mathbb{R}\cup \{+\infty\}$ is convex and lower semicontinuous, then $f_{\lambda}$ is ...
2
votes
2answers
531 views

Convex combination in compact convex sets.

Let's $K\subset\mathbb{R}^n$ compact. If $K$ is convex then who to prove that any point of $K$ is convex combination of one or two extremal points of $K$? Intuitively, for any closed ball that is ...
1
vote
3answers
717 views

How to prove that $e^x$ is convex? [closed]

I need a help with proving of $e^x$ function. We know $e^x$ is a convex function. $$f(c(x')+(1-c)(x'')) ≤ c\cdot f(x')+(1-c)\cdot f(x''), \quad 0 ≤ c ≤ 1$$ Thanks.
1
vote
2answers
183 views

The distribution of barycentric coordinates

Let $\mathcal{X} = \{x_1,\dots,x_n\} \subset \mathbb{R}^d$ and let $Z$ be a random variable uniformly distributed over convex hull of $\mathcal{X}$, denoted as $\text{conv}(\mathcal{X})$. Assuming ...
5
votes
1answer
2k views

The composition of two convex functions is convex

Let $f$ be a convex function on a convex domain $\Omega$ and $g$ a convex non-decreasing function on $\mathbb{R}$. prove that the composition of $g(f)$ is convex on $\Omega$. Under what conditions is ...
2
votes
3answers
239 views

I don't understand this proof of the AM-GM inequality?

The proof uses this lemma which I understand: $\mathbf {Lemma}$: Suppose $x$ and $y$ are positive real numbers such that $x>y$. If we decrease $x$ and increase $y$ by some positive quantity $E$ ...
2
votes
2answers
126 views

When does it make sense to define a generator of a set system?

In a set system, such as a topology, sigma algebra or convexity structure, a generator is defined to be a class of subsets such that the given set system is the coarsest such set system ...
2
votes
2answers
215 views

Is this set compact?

Given two densities $f$ and $g$ the squared Hellinger distance between them is defined as follows $$ S(g,f)=H^2(g,f)=\frac{1}{2}\int_{\mathbb{R}}\left(\sqrt{g(y)}-\sqrt{f(y)}\right)^2 \mbox{d}y $$ I ...
1
vote
2answers
140 views

Is every convex function on an open interval continuous?

Let $f:(a,b)\rightarrow \mathbb{R}$. $f$ satisfied the following property: If $\forall x_{1},x_{0},x_{2}\in(a,b)$ and $x_{1}<x_{0}<x_{2};$then$\frac{f(x_{0})-f(x_{1})}{x_{0}-x_{1}}\geq ...
1
vote
0answers
29 views

can we prove that a certain supremum of affine functions is frechet differentiable or at least continuous?

Let $X$ be a Hilbert space. Let $A\colon \operatorname{dom} A\to X$ be linear operator with closed graph (not necessarily bounded). Define $$ g\colon \operatorname{dom}A\to \mathbb{R}:x\mapsto ...
1
vote
1answer
124 views

A weak version of Markov-Kakutani fixed point theorem

Let $\emptyset \not = X\subseteq \Bbb{R}^n$ be convex and compact and let $\cal{A}$ be a commuting family of affine maps from $\Bbb{R}^n$ into $\Bbb{R}^n$ such that $X$ is invariant under each element ...
1
vote
0answers
178 views

how to solve the following expectation? closed-form expression or approximation

Suppose there is a binomial random variable $X\sim B(n-1,p)$,how to solve the following expectation $$E[(1- b^{X})^{m}]$$ where $b\in (0,1]$ and $m\in \mathbb{N} $ are all constants.I have tried my ...
0
votes
0answers
50 views

Fréchet normal cone

Given $x\in \Omega(\subset X)$ (X: Banach space) and $\varepsilon\geq 0$, the set of $\varepsilon-$normals to $\Omega$ at $x$ by \begin{align} \widehat N_\varepsilon(x;\Omega):=\left\{x^*\in X^*\mid ...
0
votes
2answers
52 views

To prove the existing and uniqueness of a solution

Let function $f$ be differentiable and convex in $R^{n}$. How can it be proved that $\forall \lambda > 0$ solution of system equations $f'(x) = -\lambda x$ exists exclusively ($\exists \hspace{3mm} ...
0
votes
1answer
39 views

Are there necessary and sufficient conditions for Krein-Milman type conclusions?

This, the third of three self-answered questions, contains a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The first question is here. The second question is here. ...
0
votes
1answer
17 views

Conditions for augmenting a collection of sets so that the new sets are small but the hull is large?

This is the second of three self-answered questions which will culminate in a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The first question is here. The third ...
0
votes
1answer
39 views

Are there necessary and sufficient conditions so that every element in a partially ordered set is either the least element or in the upset of an atom?

This is the first of three self-answered questions which will culminate in a proof of necessary and sufficient conditions for Krein-Milman type conclusions. The second question is here. The third ...
0
votes
1answer
259 views

Intersection of Two Simplices

How to find vertices a the polytope-intersection of two simplices, if I know the vertices of these simplices. More precisely: Let $T_1$ and $T_2$ be two regular $n-1$ dimensional simplices with ...
6
votes
7answers
3k views

Operations research book to start with

for somebody having a quite strong background in Mathematics, which are some good books for the domain of Operations research? I guess there are textbooks covering topics like linear and nonlinear ...
5
votes
1answer
430 views

Dual to the dual norm is the original norm (?)

I have the following questions about dual norms : How do you prove that the dual of the dual norm is in fact the original norm? This is what I have so far: If I have $\|y\|_* $ as the norm dual of ...
7
votes
3answers
225 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)$.
4
votes
0answers
54 views

Mappings preserving convex polyhedra

It is known that linear mappings between euclidean spaces map convex polyhedra to convex polyhedra. Can you give a characterization of the class of mappings that preserve convex polyhedra?
4
votes
1answer
2k views

Positive definite Hessians from strictly convex functions

Let $f: D \to \mathbb{R}\ $ be a function on non-singular, convex domain $D \subseteq \mathbb{R}^d$ and let us assume the second-order derivatives of $f$ exist. It is well known that $f$ is convex if ...
2
votes
2answers
185 views

Optimize a log det function with respect to a matrix, and the saddle point analysis

Suppose I want to to find the local minima of a logdet function $\mathcal{L}$ with respect to a Matrix $\mathbf{A}$, $$ \mathcal{L} = \log\vert \mathbf{I} + \mathbf{A}\mathbf{S} \vert - ...
8
votes
1answer
387 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 ...
6
votes
2answers
260 views

About the hyperplane conjecture.

I have recently heard about the hyperplane conjecture and I would like to understand better the problematic behind this conjecture. The hyperplane conjecture: There exists a universal constant ...
5
votes
1answer
264 views

Mean value staying in a convex or a subspace

Let $f : \mathbb{R}^n \to \mathbb{R}^m$ such that $\forall x\in \mathbb{R}^n$, $f(x)\in C$ where $C$ is a convex set of $\mathbb{R}^m$ (respectively $f(x)\in F$ where $F$ is a linear subspace of ...
5
votes
0answers
216 views

How does one compute a bounding simplex for a set of points?

An algorithm I've implemented to tessellate an N-dimensional space requires starting with a bounding N-simplex. Given a set of $k$ points $S_{0..k-1} \subset R^N$ is there a procedure to find a ...
4
votes
1answer
64 views

A convex function is differentiable at all but countably many points

Let $f:\Bbb R\to\Bbb R$ be a convex function. Then $f$ is differentiable at all but countably many points. It is clear that a convex function can be non-differentiable at countably many points, ...
3
votes
2answers
184 views

Show that $(1+x)(1+y)(1+z)\ge 8(1-x)(1-y)(1-z)$.

If $x>0,y>0,z>0$ and $x+y+z=1$, prove that $$(1+x)(1+y)(1+z)\ge 8(1-x)(1-y)(1-z)$$ Trial: Here $$(1+x)(1+y)(1+z)\ge 8(1-x)(1-y)(1-z) \\ \implies (1+x)(1+y)(1+z)\ge 8(y+z)(x+z)(x+y)$$ I ...
2
votes
0answers
142 views

Projection and Pseudocontraction on Hilbert space

Let $H$ be a real Hilbert space with inner product $\langle\cdot, \cdot \rangle: H \times H \rightarrow \mathbb{R}$, and induced norm $\left\| \cdot \right\|: H \rightarrow \mathbb{R}_{\geq 0}$. Let ...