Is this objective function convex?

Question

Given that $F(x)$ is the cumulative distribution function (CDF) of continuous random variable $X$, is

$$\frac{\int_0^\infty 1-F(x) dx}{\int_{-\infty}^0 F(x) dx}$$

convex? or is it non-convex/concave? How can you derive the answer?

And based on the derived answer, what optimization (i.e. programming) method would you use for (maximizing/minimizing) this objective function?

Answer 1

If (as in @Ben's comment) $F$ is constant, then your expression is also constant, and hence is trivially convex. In the more interesting case where $F$ is not constant, then $J$ is a functional $J : A \to \mathbb{R}$ defined by $$ J[F] = \frac{\int_0^\infty 1 - F(x) dx}{\int_0^\infty F(x) dx} $$ over the space $A$ of cdfs.

Proposition: The functional $J$ is neither convex nor concave.

Proof: First note that $A$ is an affine space (see Lemma 1 below), which we need to define convexity in the first place. Convexity means that for any $F, G \in A$ and any $t \in [0, 1]$ we have $$ J[tF + (1 - t)G] \le t J[F] + (1 - t)J[G] $$ (it's important that $A$ is an affine space because that means that $tF + (1 - t)G$ will be a cdf).

I'm going to prove that $J$ is not convex by finding two functions $F, G \in A$ and a number $t \in [0, 1]$ where this inequality is false. To find them, let's simplify \begin{align} J[tF + (1 - t)G] & = \frac{\int_0^\infty 1 - tF(x) - (1 - t)G(x) dx}{\int_{-\infty}^0 tF(x) + (1 - t)G(x) dx} \\ & = \frac{\int_0^\infty t + (1 - t) - tF(x) - (1 - t)G(x) dx}{\int_{-\infty}^0 tF(x) + (1 - t)G(x) dx} \\ & = \frac{ t \int_0^\infty 1 - F(x) dx + (1 - t) \int_0^\infty 1 - G(x) dx}{t \int_{-\infty}^0 F(x) + (1 - t) \int_{-\infty}^0 G(x) dx} \\ & = \frac{ t a + (1 - t) b}{t c + (1 - t) d} \end{align} where I've simplified the notation by defining

\begin{align} a = \int_0^\infty 1 - F(x) dx & \qquad b = \int_0^\infty 1 - G(x) dx \\ c = \int_{-\infty}^0 F(x) dx & \qquad d = \int_{-\infty}^0 G(x) dx \end{align}

Notice that this will simplify further if we choose $t = 1/2$, then the inequality we want to disprove is \begin{align} J[tF + (1 - t)G] & \le t J[F] + (1 - t)J[G] \\ \frac{a + b}{c + d} & \le \frac{1}{2} \left( \frac{a}{c} + \frac{b}{d} \right) \\ 2(a + b)cd & \le (ad + bc)(c + d) \\ 2acd + 2bcd & \le acd + ad^2 + bc^2 + bcd \\ acd + bcd & \le ad^2 + bc^2 \\ a + b & \le a(d/c) + b(c/d) \end{align} Now, by Lemma 2 (see below), for any non-negative real numbers $a, b, c, d \ge 0$, we can find $F, G \in A$ so that the four equations for $a, b, c, d$ in terms of the integrals above hold. This means that we only need to find four non-negative numbers where $a + b \le a(d/c) + b(c/d)$ is false.

For a specific counter example, choose $a = b = 1$ and $(d/c) = 1/2$, then this would say that $1 + 1 \le 1/2 + 2$ which is false. This proves that $J$ is not convex, since there are two functions $F, G \in A$ and a value of $t = 1/2 \in [0, 1]$ such that $$ J[tF + (1 - t)G] > t J[F] + (1 - t)J[G]. $$

To show that $J$ is not concave, we need to disprove the reverse inequality $$ J[tF + (1 - t)G] \ge t J[F] + (1 - t)J[G] $$ as well, which we can do by choosing $a = 4$, $b = 1$ and $(d/c) = 1/2$, and thus $a + b \le a(d/c) + b(c/d)$ is equivalent to $4 + 1 \le 4(1/2) + 1(2)$, which is false. So we have proved that neither the inequality for convexity nor the one for concavity holds for all functions $F, G \in A$ and all numbers $t \in [0, 1]$. Therefore, $J$ is neither convex nor concave.

Proposition: J has a minimum of 0 and does not have a maximum.

This is clear by Lemma 2, because we can choose $a, c \ge 0$ to make $J[F] = a/c = 0$ by choosing $a=0$, and we can make $J[F]$ arbitrarily large by choosing a fixed $c$ and choosing $a$ to be arbitrarily large.

Lemma 1: The space $A$ of all cdfs is an affine space.

Proof: A function $F$ is a cdf if it is a non-decreasing càdlàg function with the additional properties that $\lim_{x \to -\infty} F(x) = 0$ and $\lim_{x \to \infty} F(x) = 1$. For any $F, G \in A$, if we define $H = tF + (1 - t)G$ for some $t \in [0, 1]$, then we have that

1. By properties of limits, $H$ is càdlàg and $\lim_{x \to -\infty} H(x) = 0$ and $\lim_{x \to \infty} H(x) = 1$.
2. Because $F$ and $G$ are non-decreasing, $x \le y \Rightarrow F(x) \le F(y) \Rightarrow tF(x) \le tF(y)$ and $x \le y \Rightarrow G(x) \le G(y) \Rightarrow (1 - t) G(x) \le (1 - t) G(y)$. And by adding the two inequalities we have $x \le y \Rightarrow tF(x) + (1 - t) G(x)\le tF(y) + (1 - t) G(y) \Rightarrow H(x) \le H(y)$, so $H$ is non-decreasing.
3. The zero function is not an element of $A$ because $\lim_{x \to \infty} 0 \ne 1$, so the space is not a vector space. Hence $A$ is an affine space.

Lemma 2: For any real numbers $a, b \ge 0$, there exists a cdf $F \in A$ such that $\int_0^\infty 1 - F(x) dx = a$ and $\int_{-\infty}^0 F(x) dx = b$.

Proof: Let $I_B (x)$ denote the indicator function of the set $B$. One such function $F$ is then given by $$ F(x) = \frac{1}{3} I_{[-3b, 0)} (x) + \frac{2}{3} I_{[0, 3a)} (x) + I_{[3a, \infty)} (x) $$