1
$\begingroup$

I'm currently learning about linear programming and optimization methods and the most recent subject was duality

I'm trying to understand the connection between degeneracy of the primal and properties of the dual.

We were told in lecture (at least for the case of standard linear programming) that if the primal is non-degenerate then the dual has a unique optimal solution. But this statement wasn't prove and I wasn't able to prove it by myself

I would appreciate some assistant

just to be clear the standard form requires to $\min(c^t \cdot x)$ subject to $A\cdot x = b$ and $x\geq 0$

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $x \in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$ where the rows of $A$ are linearly independent.

Suppose it is nondegenerate, then there are $m$ components of $x$ which are positive. Denote the set of such indices to be $B$.

By complementary slackness condition, $$\forall i \in B, x_i(p^TA_i-c_i)=0$$

$$\forall i \in B, p^TA_i=c_i$$

Notice that the columns of $A_i$ where $i \in B$ are linearly independent, hence we can solve for $p$ uniquely.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .