Questions tagged [convex-analysis]

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.

Convex analysis is the study of properties of convex sets and convex functions.

Formally, a set $S$ is convex if, for all $x, y \in S$ and $t \in [0,1]$, $tx + (1-t)y \in S$. Intuitively, this says that for any two points in $S$, the line segment connecting those points is also in $S$.

Formally, a function $f: S \to \mathbb{R}$ defined on a convex set $S$ is convex, if for all $x,y \in S$ and $t \in [0,1]$, $f(tx + (1-t)y) \leq t f(x) + (1-t) f(y)$. Intuitively, this says that, for any two points on the graph of $f$, the line segment connecting those points lies above the graph of $f$.

Some of the more important results in convex analysis include Carathéodory's Theorem, Jensen's Inequality, Minkowski's Theorem, and the supporting hyperplane theorem.

9641 questions
14
votes
2 answers

closure, convex hull and closed convex hull

Is the closure of the convex hull of some set $A\subseteq\mathbb R^d$ equal to the convex hull of the closure of $A$, i.e. $$\text{cl}(\text{conv}(A))=\text{conv}(\text{cl}(A))?$$ If not, what are the general relations between them?
Andy Teich
  • 1,565
13
votes
2 answers

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 $A$ and $B$ are disjoint and there is a point $a$…
12
votes
3 answers

How to prove that $e^x$ is convex?

I need a help with proving convexity of $e^x$ function. $f(x)$ is a convex function, If it satisfies following condition. $$f(c\cdot x_1+(1-c)\cdot x_2) ≤ c\cdot f(x_1)+(1-c)\cdot f(x_2), \quad 0 ≤ c ≤ 1$$
Rekli
  • 167
12
votes
1 answer

Lovasz Extension Intuition

I am confused by the definition of Lovasz extension. The problem is I don't get the intuition behind the definition. In addition, Lovasz extension can be defined in different ways I don't see that these definition are indeed equivalent. The…
com
  • 5,612
12
votes
2 answers

Is $\frac{1}{2}\|x\|^2$ the only function that is equal to its convex conjugate?

Is $\frac{1}{2}\|x\|^2$ the only function that is equal to its convex conjugate? The convex conjugate is defined as $$ f^{*}(x) = \sup_y\{\langle x, y\rangle - f(y)\}. $$
10
votes
1 answer

Is the Kullback-Leibler divergence *strictly* convex in both $p$ and $q$?

The Kullback-Leibler divergence is convex in both $p,q$, where $$\mathrm{KL}(p||q) = \sum_i p_i \ln \frac{p_i}{q_i}$$ for discrete probability distributions $p_i,q_i$. Is it strictly convex?
a06e
  • 6,665
8
votes
2 answers

Cube/Circle/etc without one point on the boundary convex?

Reading this paper here, about convex optimization (photo page 2-3). What about if the object misses the corner point? I think it is still convex but I am not sure whether my intuition fails me here. Is it convex or not? Is a ball without the…
hhh
  • 5,469
8
votes
4 answers

Show that the maximum of a set of convex functions is again convex

Let $f_1(x), f_2(x), \ldots, f_n(x)$ be a set of convex functions. We define $f(x)$ as $$ f(x) = \underset{i}{\text{max}} \left\{ f_i(x) \right\}. $$ How do I show that $f(x)$ is also convex, and the domain of $f$ is intersection of the domains of…
hkBattousai
  • 4,543
8
votes
1 answer

Extension of convex function to boundary

Let $C\subseteq\mathbb{R}^n$ be an (open) convex set and suppose $f:C\rightarrow \mathbb{R}$ is a convex function. We can extend $f$ to the boundary as follows: For $x\in\partial C$, define $$\tag{1} f(x)=\left\{\begin{array}{ll} \lim_{x'\rightarrow…
8
votes
2 answers

Convex Set with Empty Interior Lies in an Affine Set

In Section 2.5.2 of the book Convex Optimization by Boyd and Vandenberghe, the authors mentioned without proving that "a convex set in $\mathbb{R}^n$ with empty interior must lie in an affine set of dimension less than $n$." While I can intuitively…
p-value
  • 474
8
votes
1 answer

Prove that the Cartesian Product of two Convex Sets is a Convex Subset

Here's the problem: Suppose that $S\subset \mathbb R^m$ is a convex set and $T\subset \mathbb R^n$ is a convex set. Show that the set $$S \times T = \{ (x_1 ,...,x_{m+n}\in \mathbb R^{m+n}):(x_1 ,...,x_m)\in S;(x_{m+1},...,x_{m+n})\in T\}$$ is a…
8
votes
3 answers

Prove that function $w \mapsto m \|w\|^2$ is strongly convex

The definition of strongly convex from Wikipedia: It is not necessary for a function to be differentiable in order to be strongly convex. A third definition for a strongly convex function, with parameter $m$, is that, for all $x$, $y$ in the domain…
Leo
  • 1,539
7
votes
0 answers

Theorem about convex sets

I want to prove a theorem (the link is after the whole text here) and in order to do that I need to prove three preliminary statements. I tried to prove them all but I'm already stuck in the first, and this one seems to be necessary to prove the…
Integral
  • 6,554
7
votes
1 answer

Convexity definition confusion

When one writes $$f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda)f(y)$$ for $x,y\in \mathbb{R}^n$, $\lambda\in(0,1)$ what does this mean? 1) Does it mean that the function is jointly convex in $x = (x_1,\ldots,x_n)$ or convex in each…
jonem
  • 383
7
votes
2 answers

Convexity of the set $S=\{(x_1,x_2):x_2^2\geq8x_1\}$

Using Algebraic approach, test the convexity of the set $$S=\{(x_1,x_2):x_2^2\geq8x_1\}$$ Definition of convexity: $S \in \mathbb R^2$ is a convex set if $\forall \alpha \in \mathbb R, 0 \leq\alpha \leq 1$ and $\forall \vec x,\vec y \in S$ holds:…
1
2
3
69 70