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 (3)

11
votes
3answers
5k views

Midpoint-Convex and Continuous Implies Convex

Given that $$f\left(\frac{x+y}{2}\right)\leqslant \frac{f(x)+f(y)}{2}~,$$ how can I show that $f$ is convex. Thanks. Edit: I'm sorry for all the confusion. $f$ is assumed to be continuous on an ...
16
votes
4answers
4k 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 ...
18
votes
3answers
2k views

Example of a function such that $\varphi\left(\frac{x+y}{2}\right)\leq \frac{\varphi(x)+\varphi(y)}{2}$ but $\varphi$ is not convex

Rudin's Real and Complex Analysis Chapter 3 Exercise 4 is: Assume that $\varphi$ is a continuous real function on $(a,b)$ s.t. $$\varphi\left(\frac{x+y}{2}\right)\leq \frac{\varphi(x)+\varphi(y)}{2}$$...
10
votes
1answer
8k 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 ...
22
votes
2answers
8k 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.
21
votes
6answers
3k 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 ...
12
votes
2answers
2k 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!
12
votes
1answer
1k 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 ...
6
votes
1answer
2k views

Continuity of a convex function

I'm trying to solve the following problem: Let $f:K\rightarrow \mathbb{R} $, $f$ convex and $K \subseteq \mathbb{R}^n$ convex. Then $f$ is continuous on $K$. I have proved the only case $n=1$, but ...
4
votes
1answer
146 views

Chebyshev sets in finite dimension are closed and convex

Prove a finite-dimensional converse to the “best approximation theorem”: Let $K$ be a subset of a finite-dimensional Hilbert space $H$ which satisfies the following property: for each $x \in H$ there ...
2
votes
1answer
139 views

Constructing a quasiconvex function

Let $C\subset\mathbb{R}^2$ be a nonempty convex set. A function $f:C\rightarrow\mathbb{R}$ is called convex if $$ f(\lambda u+(1-\lambda)v)\leq\lambda f(u)+(1-\lambda)f(v), \quad\forall u,v\in C, \...
7
votes
1answer
4k 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 ...
11
votes
2answers
297 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 $p\...
8
votes
1answer
1k 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: $$f_C(x)...
2
votes
2answers
1k 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 \frac{...
1
vote
2answers
125 views

Legendre transform of a norm

Let $||\cdot||$ be a norm on $\mathbb{R}^n$, with dual norm $||x||_* :=\max_\limits{y:||y||\leq 1}y^T x$. I'd like to show $$\max_{x \in \mathbb{R}^n}(x^T d-||x||)=\begin{cases} 0 & \text{ if } ||...
10
votes
1answer
2k 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 ...
6
votes
1answer
1k 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, for ...
11
votes
2answers
1k 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 $\...
7
votes
3answers
186 views

If $f$ is continuous and $\,f\big(\frac{1}2(x+y)\big) \le \frac{1}{2}\big(\,f(x)+f(y)\big)$, then $f$ is convex

Let $\,\,f :\mathbb R \to \mathbb R$ be a continuous function such that $$ f\Big(\dfrac{x+y}2\Big) \le \dfrac{1}{2}\big(\,f(x)+f(y)\big) ,\,\, \text{for all}\,\, x,y \in \mathbb R, $$ then how do we ...
5
votes
1answer
120 views

Concavity of the $n$th root of the volume of $r$-neighborhoods of a set

Let $A$ be a closed subset of $\mathbb{R}^n$. For $r>0$, let $A_r$ be the $r$-neighborhood of $A$, namely the set $\{x:\operatorname{dist}(x,A)\le r\}$. Is the function $f(r) = \mu(A_r)^{1/n}$ ...
17
votes
1answer
355 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
2answers
1k views

Show that $f(x)=||x||^p, p\ge 1$ is convex function on $\mathbb{R}^n$

Show that $f(x)=||x||^p, p\ge 1$ is convex function on $\mathbb{R}^n$. I have tried to use Holder's inequality, but I still cannot solve this problem. Could you help me with this problem? Thank you ...
4
votes
1answer
579 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 $D:=\{x\in\mathbb{R}\...
0
votes
3answers
5k views

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

I need a help with proving convexity 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.
4
votes
1answer
1k 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 ...
4
votes
1answer
3k views

$f$ is convex function iff Hessian matrix is nonnegative-definite.

Let $f: \mathbb{R}^2 \rightarrow \mathbb{R}$, $f \in C^2$. Show that $f$ is convex function iff Hessian matrix is nonnegative-definite. $f(x,y)$ is convex if $f( \lambda x + (1-\lambda )y) \le \...
3
votes
1answer
129 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|)$$
17
votes
1answer
641 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 ...
12
votes
3answers
844 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, ...
3
votes
1answer
3k views

What is a support function: $\sup_{z \in K} \langle z, x \rangle$?

I want to ask that, what is a support function intuitively. It is defined as: $$\sup_{z \in K} \langle z, x \rangle$$ where $z \in K$, $K$ is a nonempty set. In this formulation, $\langle \cdot, \...
3
votes
4answers
97 views

Prove that in triangle $ABC$,$\cos^2A+\cos^2B+\cos^2C\geq\frac{3}{4}$

I have two similar looking questions. $(1)$Prove that in triangle $ABC$,$\cos^2A+\cos^2B+\cos^2C\geq\frac{3}{4}$ $(2)$If $\Delta ABC$ is an acute angled,then prove that $\cos^2A+\cos^2B+\cos^2C<\...
5
votes
1answer
1k 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 ...
11
votes
3answers
7k views

How $x^4$ is strictly convex function?

I hear that $f(x)=x^4$ is a strictly convex function $\forall x \in \Re$. However, strict convexity condition is that the second derivative should be positive $\forall x \in \Re$. For the mentioned ...
4
votes
1answer
197 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 ...
3
votes
1answer
469 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 ...
3
votes
1answer
688 views

convex hull of orthogonal matrices

Where can I find the proof of the fact that the convex hull of the set of orthogonal matrices is the set of matrices with norm non greater than one? It is easy to show that a convex combination of ...
2
votes
2answers
560 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 ...
7
votes
1answer
4k 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 $...
6
votes
1answer
819 views

Lower hemicontinuity of the intersection of lower hemicontinuous correspondences

I have been stumped for long by this exercise (3.12(d)) from Stokey and Lucas's Recursive Methods in Economic Dynamics. Would greatly appreciate any hints. Let $\phi: X \to Y$ and $\psi: X \to Y$ be ...
5
votes
1answer
199 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 ...
4
votes
2answers
5k views

Second derivative positive $\implies$ convex

In proof of the following theorem; If $f$ has a second derivative that is non-negative (positive) over an interval then $f$ is convex (strictly convex). $f$ is in real number space., the book I ...
4
votes
5answers
1k views

Is closure of convex subset of $X$ is again a convex subset of $X$?

Today I was going through my text book exercise and got hold of the following question. Let $X$ be a normed linear space with norm $\lVert\cdot\rVert$ and $A$ is a non empty convex subset of $X$ ...
2
votes
1answer
65 views

Connected-ness of the boundary of convex sets in $\mathbb R^n$ , $n>1$ , under additional assumptions of the convex set being compact or bounded

Is the boundary of every compact convex set in $\mathbb R^n$ , ($n>1 $ ) connected ? is it path connected ? What if we assume only that the convex set is bounded , is the boundary connected ( and ...
2
votes
2answers
705 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 ...
2
votes
1answer
1k views

Proof of Clarkson's Inequality

Trying to find a proof for Clarkson's inequality, which states that if $2 \leq p < \infty$, then for any $f, g \in L^p$, we have that $$\left|\left|f+g\right|\right|_p^p + \left|\left|f-g\right|\...
2
votes
1answer
97 views

Understanding the subdifferential sum rule

A previous question asked: Given: $f$ and $g$ are lower-semicontinuous proper convex functions, $x \in \text{ri dom}(f) \cap \text{ri dom}(g)$, $h = f+g$, $p \in \partial h(x)$, Prove that there ...
2
votes
1answer
160 views

How to prove that $f$ is convex function if $f(\frac{x+y}2)\leq \frac12f(x) + \frac12f(y)$ and $f$ is continuous? [duplicate]

Let $f:(a,b) \mapsto \mathbb{R}$ be continuous function such that $f(\frac{x+y}{2})\leq \frac{1}{2}f(x) + \frac{1}{2}f(y) \;\; \forall x,y \in (a,b)$ Show that $f$ is convex function. Please give ...
1
vote
1answer
274 views

Submodularity of the product of two non-negative, monotone increasing submodular functions

I'm trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions Formally, we have $f$ and $g$ are submodular functions, that is, $f:2^{\Omega}\...
10
votes
1answer
539 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 ...