- What's the intuitive difference between quasi-concavity and concavity?
- Can you give an example of a quasi-concave function that is not concave?
2 Answers
$\begingroup$A function with this graph is quasiconcave, but not concave. It can be proved that a function $f$ is quasiconcave if and only there exists $x_0$ s.t. $f$ is nondecreasing for $x<x_0$ while $f$ is nonincreasing for $x>x_0$. I don't write precisely about a domain. It should be interval on a real line. Of course, quasiconcavity could be also defined on a plane or on any linear space.
Another characterization of quasiconcavity: $f:D\to\Bbb R$ (where $D$ is a convex subset of a linear space) is quasiconcave iff $$ f\bigl(tx+(1-t)y\bigr)\ge \min\{f(x),f(y)\} $$ for any $x,y\in D$, $t\in[0,1]$.
This graph consists of two convex pieces. Nevertheless, the whole function is quasiconcave.
- A function $f(x)$ is said to be quasi-concave if its domain and all its $\alpha$-superlevel sets defined as
$$\mathcal{S}_\alpha \triangleq\{x|x\in dom f, f(x)\geq\alpha\}$$
are convex for every $\alpha$. Another representation of quasi-concave functions: $f(x)$ is called quasi- concave if and only if
$$f(\theta x+(1-\theta)y) \geq \min\{f(x),f(y)\}$$
for all $x,y \in dom f$ and $\theta\in[0,1]$.
A function $f(x)$ is said to be concave if the two conditions below satisfied:
(i) $dom f$ is convex.
(ii) For all $x,y\in dom f$ and $\theta\in[0,1],$
$$f(\theta x+(1-\theta)y) \geq \theta f(x) + (1-\theta)f(y)$$
In fact, this implies that if a function is convcave then that's also quasi-concave but not necessarily the converse is true.
For example $f(\mathbf{X}) = \text{rank}(\mathbf{X})$ is a quasi-concave on $\mathbb{S}^n_{+}$.
Ceiling function $f(x)= \lceil x \rceil$ is a quasi-concave function (also, it is quasi-convex which is called quasi-linear).
References for more info.:
- Convex Optimization for Signal Processing and Communications, by Chong-Yung Chi.
- Convex Optimization by Stephen Boyd.
