# Is this necessarily true for a convex function?

$$\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 \; .$$

-
If $\lambda_s=0$ then this says that $0\ge f(0)$, which need not be true. – George Lowther Jun 26 '11 at 17:50
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. – Raskolnikov Jun 26 '11 at 18:11

## 1 Answer

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 \; .$$

-
You also need $\lambda_s\ge0$, right? – George Lowther Jun 26 '11 at 18:33
Indeed, I'll add that. – Raskolnikov Jun 26 '11 at 18:55
Thankyou very much. – AnkurVijay Jun 27 '11 at 6:08