0
$\begingroup$

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?

$\endgroup$

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.