1
$\begingroup$

Suppose we have this simple optimization problem \begin{align*} \underset{x\in V}{\text{min}} &~ f(x) \\ \text{s.t.}& ~x \leq \beta \end{align*}

Using slack variables \begin{align*} \underset{x\in V}{\text{min}} &~ f(x) \\ \text{s.t.}&~ x - \beta + s \leq 0 \\ & s \geq 0 \end{align*}

Lagrangian \begin{equation*} \mathcal{L} \left(x, \lambda, s, \mu \right) = f(x) + \langle \lambda, x -\beta + s \rangle_{L_2} +\langle \mu, s \rangle_{L_2} \end{equation*} KKT conditions $\forall \delta \lambda, \delta x, \delta \mu, \delta s$ \begin{align*} \mathcal{L}_x (\delta x) &= \langle f'(x), \delta x \rangle_{L_2} + \langle \lambda, \delta x \rangle_{L_2} = 0\\ \mathcal{L}_{\lambda} (\delta \lambda) &= \langle x - \beta + s, \delta \lambda \rangle_{L_2} = 0 \\ \mathcal{L}_{s} (\delta s) &= \langle \lambda , \delta s \rangle_{L_2} + \langle \mu, \delta s \rangle_{L_2}= 0 \\ s \geq 0 ~ \mu \leq 0 & ~\mu s= 0 ~\text{a.e.} \end{align*} Now assume we use an optimization algorithm that replaces the function $f(x)$ with an approximation easier to solve. It also replaces the box constraint $\beta$ with a value closer to the current optimization iteration. One such method is MMA. Because of this substitution, the KKT conditions are different throughout the optimization. After all, the box constraint is different and their lagrange multiplier will be different as well. Is there any way to recover the lagrange multipliers of the original problem during the optimization?

$\endgroup$
1
  • $\begingroup$ From the first of the optimality conditions, you have $f'(x)+\lambda=0$. So if you have computed a solution $x$, then you can use this equation to solve for $\lambda$. At that point, it doesn't matter any more how exactly you got that $x$. $\endgroup$ Jan 2, 2018 at 20:55

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.