2
$\begingroup$

$\sum_{s \in V} \lambda_sf(s) \geq f(\sum_{s \in V} s\lambda_s)$

$V$ is a set of points and corresponding to each point in $V$, there is a $\lambda_s$ which is a scalar so $\sum_{s \in V} s\lambda_s$ is basically another point in the space, which is a linear combination of these points.

$s \in \mathbb{R}^n$ i.e. each s is a point in n-dimensional hyperspace.
$f$ is a convex function.

In my case it is also true that $V$ is actually the set of all vertices of the unit hypercube.

The property has been used in a proof in context of submodular functions and has been attributed to the convexity of the function f.

Edit :

It is also true that :

$\sum_{s \in V} \lambda_s=1 \; \text{ and } \lambda_s\ge 0 \; , \; \forall s \; .$

  • 4
    You probably forgot to put in a condition that $\sum_{s \in V} \lambda_s=1$. Which is a convex combination, not just a linear combination.2011-06-26

1 Answers 1

6

This, if properly formulated, is called Jensen's inequality.

By properly formulated, I mean that only convex combinations are allowed, not any linear combination. Thus, it is required that

$\sum_{s \in V} \lambda_s=1 \; \text{ and } \lambda_s\ge 0 \; , \; \forall s \; .$

  • 1
    Indeed, I'll add that.2011-06-26