We have $A \in \mathbb{R}^{m \times n}$ and rank$(A)=m$.

By strict complementary slackness, we know that if the primal $(P)$ (in standard equality form) has an optimal solution, then the dual $(D)$ also has an optimal solution. Furthermore, there exists optimal solutions $\bar{x}$ and $\bar{y}$ such that for every index $j \in \{1, 2, \dots, n\}$, either $\bar{x}_j = 0$ or $(A^T\bar{y}-c)_j = 0$, but not both.

My question is, do these $\bar{x}$ and $\bar{y}$ uniquely define a partition of the columns of $A$ (i.e. the zero elements)? Or is it possible to have, say, two such sets $\bar{x_1}, \bar{y_1}$ and $\bar{x_2}, \bar{y_2}$ such that $\bar{x_1}$ and $\bar{x_2}$ have different zero elements?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.