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?
Best Answer
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)$.