Hello I am trying to understand one solution for the following problem:
17.16 Consider the problem
$$
\begin{aligned}
\operatorname{minimize} \ & \boldsymbol{c}^{\top} \boldsymbol{x}, \quad \boldsymbol{x} \in \mathbb{R}^{n} \\
\text { subject to } & \boldsymbol{x} \geq \mathbf{0} .
\end{aligned}
$$
For this problem we have the following theorem.
Theorem: $A$ solution to the foregoing problem exists if and only if $\boldsymbol{c} \geq \mathbf{0}$. Moreover, if a solution exists, $\mathbf{0}$ is a solution.
Use the duality theorem to prove this theorem (see also Exercise 22.15).
Solution:
The dual to the above linear program (asymmetric form) is $$
\begin{aligned}
\operatorname{maximize} \ & \boldsymbol{\lambda}^{\top} \boldsymbol{0}, \quad\\
\text { subject to } & \boldsymbol{\boldsymbol{\lambda}^{\top}}O \leq \mathbf{\boldsymbol{c}^{\top}} .
\end{aligned}
$$
The above dual problem has a feasible solution if and only if $c ≥ 0$. Since any feasible solution to the dual is also optimal, the dual has an optimal solution if and only if $c ≥ 0$. Therefore, by the duality theorem, the primal problem has a solution if and only if $c ≥ 0$.
Where does the statement "Since any feasible solution to the dual is also optimal" come from? Is this from the Complementary Slackness condition because $Ax =b = 0$ yields the 2 slackness condition $0$ ? or is true in every case?
Best Answer
For this particular dual, the objective function $\boldsymbol \lambda^{\mathsf T}\boldsymbol 0$ is the same for every $\boldsymbol \lambda$: it is always equal to $0$. That's why every feasible $\boldsymbol \lambda$ is optimal: no feasible solution to the dual can be better or worse than any other.
In general, the dual linear program is just a linear program like any other, and can have feasible solutions that aren't optimal.