I am trying to follow the proof of the first claim of Proposition 7 on this page: https://blogs.princeton.edu/imabandit/2013/02/05/orf523-advanced-optimization-introduction/
Basically, we are given:
"Definition 1: Let $\mathcal{X} \subset \mathbb{R}^n$ be convex, and $f : \mathcal{X} \rightarrow \mathbb{R}$. $f$ is convex if it always lies below its chords, that is
$$\displaystyle \forall (x,y,\gamma) \in \mathcal{X}^2 \times [0,1],\ f((1-\gamma) x + \gamma y) \leq (1-\gamma)f(x) + \gamma f(y) .$$"
and
"Definition 2: Let $\mathcal{X} \subset \mathbb{R}^n$, and $f : \mathcal{X} \rightarrow \mathbb{R}$. Then $g \in \mathbb{R}^n$ is a subgradient of $f$ at $x \in \mathcal{X}$ if for any $y \in \mathcal{X}$ one has
$$\displaystyle f(x) - f(y) \leq g^{\top} (x - y) .$$
The set of subgradients of $f$ at $x$ is denoted $\partial f (x)$."
We are to prove:
"Proposition 1: Let $\mathcal{X} \subset {\mathbb R}^n$ be convex, and $f : \mathcal{X} \rightarrow {\mathbb R}$. If $\forall x \in \mathcal{X}, \partial f(x) \neq \emptyset$ then $f$ is convex."
Now for the proof. Let $g \in \partial f((1-\gamma)x+\gamma y)$. Then we setup the inequalities
$$f((1 - \gamma)x + \gamma y) \leq f(x) + \gamma g^T(y-x)$$ $$f((1 - \gamma)x + \gamma y) \leq f(y) + (1-\gamma)g^T(x-y)$$
They go on to say that convexity is now easy to prove by adding the inequalities, taking care to scale appropriately. Naively I do:
$$2f((1 - \gamma)x + \gamma y) \leq f(x) + f(y) + \gamma g^T(y-x) + (1-\gamma)g^T(x-y)$$
But now I'm stuck. I see that I somehow need to convert this form into the form of definition 1, but I don't see how I will get the $\gamma$-factors to the $f$-terms. Can someone point me in the right direction?
In your last step, you added the two equations as they are. Rather than doing that, you should multiply them separately by $(1-\gamma)$ and $\gamma,$ like this:
$$ (1-\gamma)f((1 - \gamma)x + \gamma y) \leq (1-\gamma)f(x) + (1-\gamma)\gamma g^T(y-x)$$
and
$$ \gamma f((1 - \gamma)x + \gamma y) \leq \gamma f(y) + \gamma(1-\gamma) g^T(x-y)=\gamma f(y) - (1-\gamma)\gamma g^T(y-x).$$
Now you can easily add them together to get the desired result.