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 of (1)
$$
(2) \quad L(x,\mu,\nu)= a^\top x+\mu^{\top}\left(B^\top x-c\right)-\nu^{\top}x,
$$
Consider also the dual of (1)
$$
(3) \quad \max_{y} c^\top y,\\
\quad \quad \quad \text{s.t. } By \leq a
$$
Question: what is the relation between the dual of (1) and the Lagrange multipliers of (1)?
Let $\mathcal{X}^*$ be the set of argmin of (1).
Let $\mathcal{Y}^*$ be the set of argmax of (3).
Let $\mathcal{M}^*$ be the set of Lagrange multipliers $\mu$ corresponding to each element of $\mathcal{X}^*$.
Let $\mathcal{V}^*$ be the set of Lagrange multipliers $\nu$ corresponding to each element of $\mathcal{X}^*$.
Is $\mathcal{Y}^*=\mathcal{M}^*$? What is the relation between $\mathcal{Y}^*$ and $\mathcal{V}^*$?
Best Answer
The relationship is that $\mu=-y$ and $\nu$ is the slack variable in the constraint: $By + \nu = a$. You can obtain this by deriving the dual from the Lagrangian: $$\min_x L(x,\mu,\nu)= \min_x \left\{ (a+B\mu-\nu)^\top x-\mu^{\top}c \right\}=\begin{cases}-\mu^Tc & \text{if } a+B\mu-\nu=0 \\ -\infty &\text{otherwise.} \end{cases}$$