I am struggling to prove the following claim:
Primal problem (1) $\max_{x \geq 0} c^Tx$ subject to $Ax \leq b$ and $Dx \leq d$
Primal problem (2) $\max_{x \geq 0} c^Tx$ subject to $Dx \leq d$
Suppose there exists a feasible solution $x^*$ for both problems that is also optimal for both problems.
Claim: optimal dual variable(s) (vector) $\lambda^*$ that corresponds to the set of constraints $Ax \leq b$ is zero.
Attempt:
$(D1$) is $\min_{\lambda \ge0, \ge0,} ^\lambda+^$ subject to $^\lambda+^\ge $. $(D2)$ is $\min_{\ge0} ^$ subject to $^\ge $. I can use complementary slackness here to deduce the following:
- if $^∗,\lambda^∗,^∗$ solve $(P1)$ and $(D1)$, then $^∗(^\lambda^∗+^^∗−)=0$ and
- if $^∗,\bar{}^∗$ solve $(P2),(D2)$, then $^∗(^\bar{}^∗−)=0$.
It should be interpreted as there exists such choice of $\lambda$ as $\lambda$ need not be unique. For example, consider the case where the matrices are all zeros, we can see that clearly $\lambda$ needs not be $0$.
From strong duality, we know that we can find $y^*$ that is the optimal solution to $(D2)$.
Now, check that $(\lambda, y)=(0, y^*)$ is a solution to $(D1)$ and attains the same optimal value as $(D2)$ and hence $(P1)$ by strong duality.