20

It is well known that expectation preserves convexity: If $f(x)$ is convex and $Y$ is a random variable, then $\mathbb E[f(x-Y)]$ is convex. This property arises in, for example, inventory theory.

I have not been able to find a good source to cite for this well-known fact. Can anyone suggest one?

(For what it's worth, Boyd and Vandenberghe's book proves another well known property, namely, minimization preserves convexity, but I don't think they prove it for expectation.)

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
LarrySnyder610
  • 13,141
  • 3
  • 41
  • 105
  • 2
    If $f(x)$ is convex, then $f''(x) \succeq 0$ is known. We can write the expectation in the closed form: $\mathbb{E} [f(x - Y)] = \sum_{i \in \mathcal{I}} p_i f(x - y_i)$ where $p_i$ is the probability of $y_i$ to be realized and $\mathcal{I}$ is the set of indices $Y$ can take (if continuous replace with an integration).

    We can use the property that sum of convex functions is convex as well. Therefore, we need to show $p_i f(x-y_i)$ is convex. The second derivative of this function is $f''(x - y_i) \succeq 0 $ since $f$ is a convex function. This concludes the statement if I'm not wrong.

     – independentvariable May 30 '19 at 22:16
  • 1
    @aslv95 Agree. My question is just where I can find that written in a book or article, so I can cite it when I use it. (All else fails, I guess I can cite you. :) ) – LarrySnyder610 May 30 '19 at 22:20
  • 3
    I hope I am not wrong, but this seems like something we can really skip citing. Otherwise, we would need to cite 'linear function is a convex/concave' function all the time since this is easy to see but there is definitely someone who said this first :) But that's interesting because I face this all the time as well. Usually, you can see something is pretty straightforward but also doubt much like 'what if I need to cite this but I don't know if it is online or too low level to cite'... There should be some threshold of the complexity of proof to skip citing, but idk :) – independentvariable May 30 '19 at 22:27
  • 2
    You might be right. If someone knows of a reference, I'll gladly use it, but if not, your comment puts me at ease a bit. – LarrySnyder610 May 30 '19 at 22:31

2 Answers2

16

Reference "Convex Optimization" by Boyd and Vandenberghe https://web.stanford.edu/~boyd/cvxbook/, section 3.2.1, p. 79.

These properties extend to infinite sums and integrals. For example if $f(x, y)$ is convex in $x$ for each $y\in A$, and $w(y) \ge 0$ for each $y\in A$, then the function $g$ defined as $$g(x) = \int_A w(y)f(x, y)\, dy$$ is convex in $x$ (provided the integral exists).

Of course, this extends to Lebesgue-Stieltjes integrals (not mentioned in the referenced book), so should cover any expectation.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Mark L. Stone
  • 13,392
  • 1
  • 31
  • 67
  • 1
    That will work. I swear I looked through that whole book a few years ago looking for this. :/ Thanks. – LarrySnyder610 May 30 '19 at 23:58
  • 2
    @LarrySnyder610 As a side note, you need to assume that $f(x - Y)$ is a continuous random variable for the above to be applicable. – Pantelis Sopasakis May 31 '19 at 00:32
  • 2
    @Pantelis Sopasaki I mentioned the extension to Lebesgue-Stieltjes integrals, even though that is not mentioned in the Boyd and Vandenberghe book. – Mark L. Stone May 31 '19 at 00:44
7

$\newcommand{\E}{\mathbb{E}}\newcommand{\R}{\mathbb{R}}$Define $\phi(x) = \E[f(x-Y)]$ and assume that for all $x\in\R$, $f(x-Y)$ is measurable and integrable. Then, for $x,x'\in\R$ and $\alpha \in [0,1]$

\begin{align} \phi(\alpha x + (1-\alpha)x') {}={}& \E[f(\alpha x + (1-\alpha)x'-Y)] \\ {}={}& \E\left[f\left(\alpha x + (1-\alpha)x'- \alpha Y - (1-\alpha) Y\right)\right] \\ {}={}& \E\left[f\left(\alpha (x-Y) + (1-\alpha)(x'- Y)\right)\right] \\ {}\leq{}& \E\left[\alpha f(x-Y) + (1-\alpha)f(x'- Y)\right] \\ {}={}& \alpha \E[f(x-Y)] + (1-\alpha)\E[f(x'- Y)] \\ {}={}& \alpha \phi(x) + (1-\alpha)\phi(x'), \end{align}

where we have used the linearity of the expectation, the fact that if $Z\leq Z'$ (a.s.) then $\E[Z] \leq \E[Z']$, and the convexity of $f$. We have, therefore, shown that $\phi$ is convex.

Pantelis Sopasakis
  • 749
  • 4
  • 8
  • 1
    Beautiful. But: I'm just looking for a reference. :) Maybe this was a poor question. My intent is just: I use this result all the time. When I use it, I say "it's well known". But I'd like to be able to say "it's well known; see, e.g., [ref.]". I don't want to include a proof in what I'm writing, obviously, since it's "well known". – LarrySnyder610 May 30 '19 at 23:18
  • 4
    @LarrySnyder610 I'll try find something. You could perhaps state that this can be easily verified (if it's for a paper), or give it as an exercise if it's for a course. – Pantelis Sopasakis May 30 '19 at 23:21