Prove that the objective value of a maximisation problem is a concave funciton of the RHS

Question

My question is the same as the one in this question. However, the answer remains unclear to me.

The question is as follows:

For each $b \in \mathbb{R}^m$, let $\xi^*(b)$ denote the optimal objective function value for the following linear program:

$$\begin{align}&\text{maximize} & c^T x \\&\text{subject to} & Ax & \leq b \\& & x & \geq 0\end{align}$$

Suppose that $\xi^*(b) \lt \infty$ for all $b$. Show that the function $\xi^*(b)$ is concave (a function $f$ on $\mathbb{R}^m$ is called concave if $f\left(tx+(1−t)y\right) \geq tf(x)+(1−t)f(y)$ for all $x$ and $y$ in $\mathbb{R}^m$ and all $0 \lt t \lt 1$). Hint: Consider the dual problem.

(Vanderbei, Linear Programming: Foundations and Extensions 4e, exercise 10.2)

The poster suggests the following answer:

For $b_1$, the simplex method guarantees an optimal primal solution $x_1$ and optimal dual solution $y_1$ with corresponding costs $c^T x_1 = b_1^T y_1$. Perturb $b_1$ to $t b_1 + (1-t) b_2$. Then $y_1$ remains dual feasible, and $(t b_1 + (1-t) b_2)^T y_1$ provides a lower bound for the optimal objective value of this new problem.

That is,

$$\begin{align} \xi^*\left(t b_1 + (1-t) b_2\right) & \geq (t b_1 + (1-t) b_2)^T y_1 & \text{because $y_1$ remains dual feasible} \\ & = t b_1^T y_1 + (1-t) b_2^T y_1 \\ & \geq t b_1^T y_1 + (1-t) b_2^T y_2 & \text{because $b_2^T y_1 \geq b_2^T y_2$} \\ & = t \xi^*(b_1) + (1-t) \xi^*(b_2) \end{align}$$

($y_2$ denotes the optimal solution to the problem where $b = b_2$, and we know $b_2^T y_1 \geq b_2^T y_2$ because it is a minimization problem.)

Though I am unclear on the first inequality, since in my understanding, weak duality in the case where the primal is a maximisation problem, states that $c'x \le b'y$ Where $c'x$ corresponds to the primal objective, $b'y$, corresponds to the dual, and $x$ and $y$ are feasible solutions to each problem.

Furthermore, why is it ensured that after perturbing $b_1$ to $t b_1 + (1-t) b_2$, that $y_1$ is dual feasible?

Answer 1

Let $x^*_b$ and $x^*_a$ denote the optimal solution to the problem corresponding to $\xi^*(b)$ and $\xi^*(a)$ respectively, both with corresponding dual solutions $y^*_b$ and $y^*_a$.

Then, by strong duality, it holds that $c'x^*_b = b'y^*_b$. In addition, if $b$ is perturbed into $\lambda b + (1-\lambda) a$, $y^*_b$ remains dual feasible for the problem corresponding to $\xi^*(\lambda b + (1-\lambda) a)$ (perturbing $b$ only affects the objective in the original dual problem). $$ \begin{align} \xi^*(\lambda b + (1-\lambda) a) &= x^*_{\lambda b + (1-\lambda) a} & \\ &= (\lambda b + (1-\lambda) a)' y^*_{\lambda b + (1-\lambda) a} & \text{(Strong duality)}\\ &= \lambda b'y^*_{\lambda b + (1-\lambda) a} + (1-\lambda) a'y^*_{\lambda b + (1-\lambda) a} & \\ &\ge \lambda b'y^*_{b} + (1-\lambda) a'y^*_{a} & \text{(Dual is minimising)}\\ &= \lambda c'x^*_{b} + (1-\lambda) c'x^*_{a} & \text{(Strong duality)}\\ &= \lambda \xi^*(b) + (1-\lambda) \xi^*(a) \end{align} $$

Answer 2

Actually, you could also prove the concavity with only the primal problem. Let $x_1^*$ et $x_2^*$ be optimal solution for the problem at $b_1$ and $b_2$. And let $b= \lambda b_1 + (1-\lambda)b_2$. Then it suffices to check that $x = \lambda x_1^* + (1-\lambda)x_2^*$ is feasible at $b$. Then $\xi^*(b) \geq c^Tx = \lambda c^Tx_1^* + (1-\lambda) c^Tx_2^* = \lambda\xi^*(b_1) + (1-\lambda)\xi^*(b_2)$.