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.