Properties of the Lagrangian in a linear programming problem

86 Views Asked by At

Consider the following linear minimisation problem $$ (1) \quad \min_{x\geq 0} a^\top x,\\ \quad \quad \quad \text{s.t. }B^\top x=c $$ where

  • $x$ is the $p\times 1$ vector of unknowns.

  • $a$ is a $p\times 1$ vector of real numbers.

  • $B$ is a $p\times k$ matrix of real scalars.

  • $c$ is a $k\times 1$ vector of real scalars.

  • $p>k$.

Consider the Lagrangian

$$ L(x,\mu,\nu)= a^\top x+\mu^{\top}\left(B^\top x-c\right)-\nu^{\top}x, $$

Question: consider the set of solutions $(x^*, \mu^*, \nu^*)$. Is it true here that for each $(\mu^*,\nu^*)$, there is one and only one $x^*$? Could you offer some intuitive explanations with your answer?

My thoughts: I don't know the "analytical" answer. By doing some simulations, it seems to me that the above is true.