I'm working through Boyd and Vandenberghe's "Convex Optimization" and I'm stuck on the proof of sufficiency of the first-order convexity condition on page 70
To show sufficiency, assume the function satisfies (3.4) for all x and y in dom f
(which is an interval). Choose any x $\neq$ y, and 0 ≤ θ ≤ 1, and let $z = θx+ (1 − θ)y$.
Applying (3.4) twice yields
$f(x) \geq f(z) + f′(z)(x − z)$, $f(y) \geq f(z) + f′(z)(y − z)$.
Multiplying the first inequality by θ, the second by 1 − θ, and adding them yields
$θf(x) + (1 − θ)f(y) \geq f(z)$,
which proves that f is convex.
Here, 3.4 is the statement $f(y) \geq f(x) + f'(x)(y-x)$
This is were I'm having problems. After the additions, I have:
$θ(f(x)) + (1-θ)f(y) \geq θ(f(z) + f′(z)(x − z))+(1-θ)(f(z)+f′(z)(y − z))$
The left side of the inequality is fine. But on the right side, I have:
$f(z) +f'(z)[θ(x-z)+(1-θ)(y-z)]$
instead of $f(z)$ as the book says.
Any help is kindly appreciated!
Best Answer
You're on the right track! Just a bit of algebra and you're done --
\begin{aligned} \theta(x-z)+(1-\theta)(y-z) &= \underbrace{\left(\theta x + (1-\theta) y\right)}_{=z} - z\\ &=0, \end{aligned} so the lower bound becomes $f(z) + f'(z)[0]=f(z)$.