Consider the following linear programming
$$
(1) \quad \min_{x\geq 0} a^\top x,\\
\quad \quad \quad \text{s.t. }B^\top x=c
$$
Consider the dual of (1)
$$
(2) \quad \max_{y} c^\top y,\\
\quad \quad \quad \text{s.t. } By \leq a
$$
Suppose we impose the linear independence constraint qualification (LICQ) to (2). LIQC states that, for each $y\in \{y\in \mathbb{R}^k: By\leq a\}$, it holds that
$$
\text{The vectors } \{\nabla (B_qy-a_q)\}_{q\in \Gamma(y)} \text{ are linearly independent}
$$
where $\Gamma(y)\equiv \{q\in \mathbb{N}: 1\leq q \leq p\text{ and } B_qy-a_q=0\} $, $p$ is the number of inequality constraints in (2), $B_qy-a_q\leq 0$ is the $q$-th inequality constriant in (2).
Question: I've read that imposing LIQC means imposing that (1) has a unique argmax $x^*$. Is this correct? Does it ensure that also (2) has a unique argmin $y^*$?
Another way to ensure that (1) and (2) have unique solutions could be to add a strictly convex penalty term to (2)
$$
(3) \quad \max_{y} c^\top y + \epsilon ||y||_2,\\
\quad \quad \quad \text{s.t. } By \leq a
$$
with $\epsilon >0$ but small, so that the primal becomes
$$
(4) \quad \min_{x\geq 0} a^\top x,\\
\quad \quad \quad \text{s.t. }||B^\top x-c||_2\leq \epsilon
$$
What is the relation between my solution to ensure uniqueness and LIQC? Do they achieve the same objective?
Best Answer
Yes, that is correct, but it does not mean that $y^*$ is unique. If $y^*$ is optimal for the dual and satisfies the LICQ (so the LICQ only needs to hold for $y$), then there is a unique corresponding primal solution $x^*$. This follows directly from complementary slackness, i.e., when constraint $i$ in the dual is not binding, $x_i=0$, so the $x_i$ that can be nonzero are uniquely determined by $B^Tx = c$. This only shows that for each $y^*$ there is a corresponding unique $x^*$, so is it possible that two different $y^*$ give rise to different $x^*$? The answer is no, because every optimal $x^*$ satisfies strong duality and therefore complementary slackness (the equivalence between complementary slackness and strong duality is well known and easy to derive: $a^Tx = c^Ty$, so $a^Tx = (B^Tx)^Ty$, so $x^T(a-By)=0$). So each $y^*$ has the same set of optimal $x^*$ and vice versa.
The penalty term ensures that (3) has a unique solution (if the problem is not unbounded!) but not that (4) has a unique solution (what if $a=0$?). Problem (4) satisfies the LICQ: there is only one constraint and the derivative exists and is nonzero as long as $B^Tx - c \neq 0$.