Why do we need the "subgradient inequality" here?

Question

So, I don't quite know what the "subgradient inequality is".

But, we have a function $Q(x)$ which is the optimal objective value of a linear programming problem. So, $Q(x) = \min_y \{ \ c^Ty\ |\ \text{s.t.} \ Ay = b - Tx, y \ge 0\}$.

This $Q(x)$ is assumed to be convex.

Let $z_0$ be the dual solutions to that linear program for some $x_0$. Then for this $x_0$, we have $$Q(x_0) = z_0^T(b - Tx_0)$$ which just says that the optimal value of the primal equals optimal value of the dual.

Now, my textbook says that "because $Q$ is convex and because of the subgradient inequality, we have for all $x$" $$Q(x) \ge z_0^T(b - Tx)$$

Could somebody please explain what this means? Why do we need convexity and what is the subgradient inequality, and how does the above equation follow from it?

Does the inequality not just follow directly from the fact that the dual solution $z_0$ is now just some feasible solution and therefore due to weak duality, we have that the dual objective value $z_0^T(b - Tx)$ is a lower bound on the optimal value $Q(x)$? So what do I need the "subgradient inequality" for?

Answer 1

Welcome to Math.SE!

The subgradient inequality is the generalization of the inequality

$$ f(y)\geqslant f(x)+\nabla f(x)^\text{T}(y-x) $$

to convex functions which aren't differentiable (such as piecewise-linear convex functions, as in this example). See these slides for an illustration of the geometry of subgradients.

Does the inequality not just follow directly from the fact that the dual solution $z_0$ is now just some feasible solution

Indeed it does. In fact, this is exactly how Van Slyke and Wets prove this result in their original paper (see Proposition 3)! Invoking the subgradient inequality is just an alternative, (arguably) more sophisticated way to prove the same thing.