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
1
vote
1 answer

Checking Convexity of a function?

I want to check if the following function is convex with respect to the vector variable $x$. $$ R(x) = \log_2 \left( \sum_{i=1}^M {\frac{p}{((x_i-\gamma)^2 + (y_i-\beta)^2 +(z_i-\rho)^2)^\alpha}+\sigma^2} \right) $$ I have tried to check it by…
1
vote
1 answer

$S:=S_1 \cup S_2$ is not convex while $S_1,S_2$ are convex

Show that if $S_1=\{(x_1,x_2):x_1+x_2 \le 0,x_1 \ge 0\}$ and $S_2=\{(x_1,x_2):x_1-x_2 \ge 0,x_1 \le 1\}$ and $S:=S_1 \cup S_2$, then $S_1$ and $S_2$ are convex but $S$ is not. Take $x=(x_1,x_2),y=(y_1,y_2) \in S_1$ and an arbitrary $\lambda \in…
masaheb
  • 918
  • 6
  • 16
1
vote
1 answer

Conic hull of the set $S = \{(x_1,x_2) : (x_1 - 1)^2 + x_2^2 = 1 \}$

Show that the conic hull of the set $$S = \left\{(x_1,x_2) : (x_1 - 1)^2 + x_2^2 = 1 \right\}$$ is the set $$\{(x_1,x_2) : x_1 > 0\} \;\cup \; \{(0,0)\}$$ The set $$S = \{(x_1,x_2) : (x_1 - 1)^2 + x_2^2 = 1 \}$$ is a circle centered around…
1
vote
1 answer

Dimension of polyhedron

Let $A \in R^{m×d}$, $b \in R^m$. $P=[x \in R^d: Ax \leq b]$ is a polyhedron. Suppose there is some $\bar x \in R^d$ such that $A\bar x
user942118
1
vote
0 answers

Convexity of $(x, X) \mapsto x^\top X^{-1} x$

Is the function $f: \mathbb{R}_+^n \times \mathcal{S}_{++}^n$ defined by $$f(x, X) = x^\top X^{-1} x$$ convex on $\mathbb{R}_+^n \times \mathcal{S}_{++}^n$? Note: $\mathbb{R}_+^n$ is the set of component wise non-negative vectors (the non-negative…
Sean
  • 21
1
vote
0 answers

Convexity of the optimal value function

Suppose we have the optimal value function as: \begin{align} v(x) = \max_{y\geq 0}\,&c^\top y\\ s.t. \,&g(x,y) \leq 0. \end{align} If we know $g(x,y)$ is linear in $x$, but nonconvex in $y$, is $v(x)$ a convex function? If no, under what conditions…
Karen
  • 11
1
vote
2 answers

How to show that $ Ax \le b$ is convex?

For $$ A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m, c \in \mathbb{R} $$ one has to show that $$ K:= \{ x \in \mathbb{R}^n: Ax \le b \}$$ is convex. Now I'm aware that by definition, a set is convex $ \iff $ for all $x,y \in K, \lambda \in…
bonifaz
  • 795
  • 8
  • 19
1
vote
1 answer

Showing convexity of $|t|^p$

In my notebook I have 2 consecutive exercises where the second one uses the result from the first one. The first one is the following: (Ex1) Suppose that $f\in C^2(a,b)$ and $f\in C^1([a,b])$. Show that if $f{''}(x)\geq 0$ on $[a,b]$ then $f$ is…
user926287
1
vote
0 answers

Determining the value of m for an m-convex set that is also non-convex

I'm looking within my PhD at atm at decomposing a random non-convex subset of the Euclidean Plane into a union of n convex sets, particularly hoping that the these sets (that from the overall non-convex union) don't overlap. I've found that an…
apg
  • 2,797
1
vote
1 answer

Prove convexity of simple function

I'm trying to understand a quiz question from CVX101, the convex optimisation MOOC. Suppose we have $x \in \mathbb{R}^n$. We define $$\begin{aligned} (x)_+ &= \max \{0,x\}\\ (x)_- &= \max\{0,-x\} \end{aligned}$$ such that $x = (x)_+ - (x)_-$. I…
1
vote
1 answer

Intuition for why a convex set with empty interior lies in an affine set

In Section 2.5.2 of Boyd & Vandenberghe's Convex Optimization, the authors claim that a convex set in $\mathbb{R}^n$ with empty interior must lie in an affine set of dimension less than $n$. Can someone provide some intuitive explanations of what…
Steve
  • 51
1
vote
2 answers

Must convex function $f(x)$ bounded by $\|x\|_0$ be bounded by $\|x\|_1$?

One of my professors stated the following result without proof: Suppose that $f \colon \mathbb{R}^p \to \mathbb{R}$ is convex such that $f({\bf x}) \leq \|{\bf x}\|_0$, then $f({\bf x}) \leq \|{\bf x}\|_1$. (Recall that $\|{\bf x}\|_0$ counts the…
Fei Cao
  • 2,830
1
vote
1 answer

Convexity and Gradient

I'm working on a problem related to the Kullback-Leibler divergence but I'm stuck on one part. $$f(u) - f(v) - \nabla f(v)^\intercal (u-v)$$ The function $f(v) = \sum_{i=1}^n v_i \log v_i$ and $u,v \in \mathbb{R}_{++}^n$. I have already proved that…
1
vote
1 answer

Determine if a specific set is a convex set by definition?

My problem is to determine if the following set is convex: \begin{align*} \sum_{i=1}^N \frac{1}{x_i} \leq 1 \quad \textrm{for } \mathbf{x} \in \mathbb{R}_{++}^N, \end{align*} where $N \in \mathbb{N}$. I have tried the case for $N=2$, I think it can…
Yanni99
  • 13
1
vote
2 answers

Is $[0,1]\cdot A$ a convex set?

Let $A\subset\mathbb{R}^d$ be a convex set. We define \begin{align}[0,1]\cdot A:=\{x\in\mathbb{R}^d:x=\lambda a \text{ for a }\lambda\in[0,1] \text{ and }a\in A\}.\end{align} Is this set convex? I was thinking that in the case $d=1$ the statement is…
Chris S.
  • 154