1
$\begingroup$

Suppose we were going to obtain the KKT conditions for a inequality constrained problem in $\mathbb{R}^n$

\begin{align*} \underset{\mathbf{x}\in \mathbb{R}^n}{\text{min}} &~ f(\mathbf{x}) \\ \text{s.t.}&~ x_i \leq \beta ~\forall ~i=1...n \\ \end{align*}

Introduce a slack variable \begin{align*} \underset{x\in \mathbb{R}^n}{\text{min}} &~ f(x) \\ \text{s.t.}&~ x_i - \beta + s_i = 0 &~~\forall ~i=1...n\\ & s_i \geq 0 &~~\forall ~i=1...n \end{align*} Obtain the optimality conditions. Lagrangian:

\begin{equation*} \mathcal{L} \left(x, \lambda, s, \mu \right) = f(x) + \mathbf{\lambda}^T (\mathbf{x} -\mathbf{\beta} + \mathbf{s}) + \mathbf{\mu}^T \mathbf{s} \end{equation*}

KKT conditions: \begin{align} \nabla_x \mathcal{L} &= \nabla f(x) + \mathbf{\lambda} &=0\\ \nabla_{\lambda} \mathcal{L} &= \mathbf{x} -\mathbf{\beta} + \mathbf{s}&=0 \\ \nabla_{s} \mathcal{L} &= \mathbf{\lambda} + \mathbf{\mu} &=0\\ s_i &\geq 0 ~~\forall ~i=1...n \\ \mu_i &\leq 0 ~~\forall ~i=1...n &~\text{dual feasibility} \\ \mu_i s_i &= 0 ~~\forall ~i=1...n &~\text{complementary slackness} \end{align} Doing some manipulations we can obtain: \begin{align} \nabla_x \mathcal{L} &= \nabla f(x) + \mathbf{\lambda} &=0\\ \lambda_i (x_i -\mathbf{\beta}) &= 0 ~~\forall ~i=1...n &~\text{complementary slackness} \end{align}

and we can solve for these conditions. Now, how would we go about the same problem in a $L_2$?

\begin{align*} \underset{x\in L_2}{\text{min}} &~ f(x) \\ \text{s.t.}&~ x \leq \beta ~a.e. \\ \end{align*}

$f:L_2 \rightarrow \mathbb{R}$. Including a slack variable: \begin{align*} \underset{x\in L_2}{\text{min}} &~ f(x) \\ \text{s.t.}&~ x - \beta + s &= 0 ~a.e. \\ &~ s &\geq 0 ~a.e. \\ \end{align*}

Here for the Lagrangian, am I correct in doing the lagrange multiplier-constraints inner products in $L_2$ ? \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*}

Solving \begin{align*} \mathcal{L}_{\lambda} (\delta \lambda) &= \langle x - \beta + s, \delta \lambda \rangle_{L_2} &= 0 ~ \forall \delta \lambda \\ s &= -(x - \beta) &~\text{a.e.}\\ \mathcal{L}_{s} (\delta s) &= \langle \lambda , \delta s \rangle_{L_2} + \langle \mu, \delta s \rangle_{L_2} &= 0 ~ \forall \delta s \\ \mu &= -\lambda &~\text{a.e.} \end{align*}

Therefore, the KKT conditions for the continuous case are: \begin{align} \mathcal{L}_x (\delta x) &= \langle f'(x), \delta x \rangle_{L_2} + \langle \lambda, \delta x \rangle_{L_2} &= 0 ~ \forall \delta x\\ \lambda \left(x - \beta \right) &= 0 ~ \text{a.e.} \end{align}

Are these KKT correct? Is using the $L_2$ inner product the way to go or I should have used another space such as $L_{\infty}$?

$\endgroup$
  • $\begingroup$ How about just projecting the gradient of $f$ onto the convex set $\{x | x \le \beta \}$? $\endgroup$ – copper.hat Mar 21 '17 at 16:27
  • $\begingroup$ I am trying to translate an optimization algorithm (MMA) into its continuous version. They use slack variables to obtain the optimality conditions. $\endgroup$ – balborian Mar 21 '17 at 19:51
  • $\begingroup$ It is a bit of a leap, the KKT conditions translate naturally to a Hilbert space, but with a finite number of real constraints. The constraints $x \le \beta$ can be viewed as an infinite number of constraints, so more work is needed. $\endgroup$ – copper.hat Mar 21 '17 at 20:16
  • $\begingroup$ To me, MMA involved people in a cage kicking each other... $\endgroup$ – copper.hat Mar 21 '17 at 20:18
  • $\begingroup$ people.kth.se/~krille/originalmma.pdf $\endgroup$ – balborian Mar 21 '17 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.