# Primal-Dual Pair Feasible solution implies optimal solution

calculuslinear programmingoptimization

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?

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.