Consider the following linear programming problem
$$
\min_{x}\sum_{j=1}^J x_ja_j\\
s.t.\\
x_j\geq 0 \text{ }\forall j=1,…,J\\
\sum_{j=1}^J x_jb_{j,r}-c_r=0 \text{ }\forall r=1,…,R
$$
where $a_j, b_{j,r}, c_r$ are known scalars $\forall j=1,…,J$ and $\forall r=1,…,R$. $x$ is a $J\times 1$ vector.
Consider the Lagrangian
$$
\mathcal{L}(x,\mu_1,…,\mu_R,\tau_1,…,\tau_J)\equiv \sum_{j=1}^J x_ja_j+\sum_{r=1}^R \mu_r(\sum_{j=1}^J x_jb_{j,r}-c_r)+\sum_{j=1}^J \tau_j x_j
$$
Question: I'm looking for a way to "perturb" $\mathcal{L}(x,\mu_1,…,\mu_R,\tau_1,…,\tau_J)$ such that the Lagrangian multipliers $\mu_1,…,\mu_R$ are unique and that does not modify "too much" the solution of the original problem.
I'm asking this because the the Lagrangian multipliers $\mu_1,…,\mu_R$ determine another piece of my problem which would be enormously simplified if the Lagrangian multipliers $\mu_1,…,\mu_R$ are unique (too long to explain in details).
I understand that my question is very sloppy, I'm not a mathematician, your comments would be very appreciated also to help me reformulate my question in appropriate terms.
Best Answer
Your primal problem is $$\min_x\left\{a^Tx : B^Tx = c, x\geq 0\right\}$$ The dual problem is: $$\max_y \left\{c^Ty : By \leq a\right\}$$ To ensure that the dual has a unique solution, you could modify the dual into: $$\max_y \left\{c^Ty + \rho ||y||_2 : By \leq a\right\}$$ with $\rho>0$. The corresponding primal is: $$\min_x\left\{a^Tx : ||B^Tx-c||_2 \leq \rho, x\geq 0\right\}$$ If you pick $\rho$ sufficiently small, the optimal value will not change too much.