Is the optimal objective of a linear program continuous in its right-hand-side?

Question

Consider a linear program $$f(b)=\min_{x}\{c^\top x: A x = b, x\geq 0\}$$ (assume it is feasible and bounded for all $b$). My understanding is that $f(b)$ is a convex piecewise linear function of $b$ (can be shown taking the dual of the LP, see below).

My question

Can I also say that $f(b)$ is continuous? Or when can I say that?

Below my attempts to workout a proof, though I strongly believe someone has done that already.

---

Proof that $f(b)$ is convex and piecewise linear

By strong duality $$f(b)=\min_{x}\{c^\top x: A x = b, x\geq 0\}=\max_\pi\{\pi b:\pi A\leq c\}$$ If we let $\pi_1,\ldots,\pi_K$ be the extreme points of $\{\pi A\leq c\}$ we can rewrite the dual as $$f(b)=\max_{\pi_1,\ldots,\pi_K}\{\pi_i b\}$$ This gives us a piecewise linear function in $b$. Furthermore, the pointwise max of a set of linear functions is convex, hence $f(b)$ is convex and piecewise linear in $b$.

---

Working out a proof

Assume we take $b\in B$ where $B$, loosely speaking is the set of vectors $b$ for which the linear program has a finite optimal solution, i.e. $f(b)$ is defined.

Now, since linear functions are continuous, if the pointwise maximum of continuous functions is continuous the proof is done (but I do not know if that holds). I will try in another way:

Take a sequence $(b_n)$ converging to $b_0$ (assume $B$ is closed). I need to show that $\lim f(b_n)=f(b_0)$ $$\begin{align} \lim f(b_n) =& \lim\max_{\pi_1,\ldots,\pi_K}\{\pi_i b_n\}\\ =&\max_{\pi_1,\ldots,\pi_K}\{\lim\pi_i b_n\}\\ =&\max_{\pi_1,\ldots,\pi_K}\{\pi_i\lim b_n\}\\ =&\max_{\pi_1,\ldots,\pi_K}\{\pi_i b_0\}\\ =&f(b_0) \end{align}$$ Hence $f(b)$ is continuous. But I am walking on thin ice when I say that the limit of the maximum is equal to the maximum of the limit (second line).

Answer 1

If the linear program is feasible and bounded for all $b$, then $f(b)$ is finite, i.e. $-\infty < f(b) < +\infty$ for all $b \in \mathbb{R}^m$. By strong duality, $f(b)$ is also convex, as you have shown.

It is a classical result that all convex functions finite on $\mathbb{R}^m$ are continuous. See for example the book Convex Analysis by Rockafellar, Corollary 10.1.1. To demonstrate the usefulness of the corollary, an example about the pointwise supremum of convex functions is given, which is very similar to your question.

Things might be a little bit more complicated if there exist $b$ such that $f(b) \in \{-\infty,+\infty\}$, but for this case, Convex Analysis should also be a good resource.

Rockafellar, R. T. (1970). Convex analysis (No. 28). Princeton university press.