# KKT conditions for a convex optimization problem with a L1-penalty and box constraints

I am having some trouble deriving / understanding optimality conditions for a convex optimization problem of the form:

\begin{align} \min_{x\in\mathbb{R}^d}~ & f(x) + C.\|x\|_1 &\\ &x_i \leq u & \text{ for } i = 1,\ldots,d \\ &x_i \geq l &\text{ for } i = 1,\ldots,d \end{align}

where:

• $f:\mathbb{R}^d \rightarrow \mathbb{R}$ is smooth and (strictly) convex
• $C>0$ is a $L_1$ regularization penalty
• $l<0$ is lower bound for each element of $x$
• $u>0$ is upper bound for each element of $x$

To derive optimality conditions, I let $\lambda_i^+$ and $\lambda_i^-$ denote the dual variables for the upper and lower bound constraints. The Lagrangian is then:

$$f(x) + C.\|x\|_1 + \sum_{i=1}^d \lambda_i^+(x_i - u) + \sum_{i=1}^d \lambda_i^-(l - x_i )$$

And I believe that the KKT conditions should be:

\begin{align} \mathbf{0} & \in \nabla f(x) + C.\partial \|x\|_1 + \lambda^+ - \lambda^- & \text{(stationarity)} \\ x_i &\in [l,u] \quad i = 1,\ldots,d & \text{(primal feasibility)} \\ \lambda_i^+, \lambda_i^- &\geq 0 ~~~~~\quad i = 1,\ldots,d & \text{(dual feasibility)} \\ \lambda_i^+(x_i - u) & = 0 ~~~~~\quad i = 1,\ldots,d & \text{(comp. slackness #1)}\\ \lambda_i^-(l- x_i) & = 0 ~~~~~\quad i = 1,\ldots,d & \text{(comp. slackness #2)} \end{align}

where $\lambda^+ = [\lambda_1^+,\ldots,\lambda_d^+]^T$, $\lambda^- = [\lambda_1^-,\ldots,\lambda_d^-]^T$ and

$$\frac{\partial}{\partial x_i} \|x\|_1 = \begin{cases} 1 \qquad ~~~\mbox{ if } x_i > 0\\ [-1,1] ~~~\mbox{ if } x_i = 0\\ -1 \qquad \mbox{ if } x_i< 0 \end{cases}$$

I am wondering:

1. Can I use the subgradient of the $L_1$-norm to derive KKT conditions for this problem?
2. Are the KKT conditions both necessary and sufficient for this problem?
3. If $x_i = u$, then do the KKT conditions imply that $(\nabla f(x))_i + C + \lambda_i^+ = 0$?
• Stephen Boyd's Lectures go into this. stanford.edu/class/ee364b/videos.html He also has slides if you want to get to the answer more quickly. – Baby Dragon Jun 10 '15 at 3:35
• Thank you! I was using the B&V textbook to write out the KKT conditions. I was just confused since he does not seem to talk much about the case where the objective is non-differentiable. – Elements Jun 10 '15 at 17:14

There is an error with the Lagrangian: it should contain $\lambda_i^-(l-x_i)$ (not $\lambda_i^-(-l-x_i)$), which also effects the slackness condition, which should be $\lambda_i^-(l-x_i)=0$.
1) The KKT system you have written is nothing else than the subgradient optimality condition $$0\in \partial J(x),$$ where $$J(x) = f(x) + c\|x\|_1 + I_{(-\infty,u]}(x) + I_{[l,+\infty)}(x),$$ where $I_{(-\infty,u]}$ and $I_{[l,+\infty)}$ are the indicator functions of the boxes $(-\infty,u]$ and $[l,+\infty)$. Now verify that the conditions for the subgradient sum rule are fulfilled, and write out the individual subgradients to obtain your system.
• Thank you! I fixed the mistake. I'm a little confused by the indicator functions since I'm used to taking on values of 1 when the condition is true and 0 when the condition is false. To be clear, in this case, $I_{(\infty,u]}(x) = \infty$ if $x > u$ and $0$ if $x \leq u$ -- right? – Elements Jun 10 '15 at 17:11
• Yes, these indicator functions take values in $\{0,+\infty\}$ to force possible minimizers to satisfy the constraints. – daw Jun 10 '15 at 17:13
• Thanks! That does seem much easier to work with! One more silly question - would the subgradient $\frac{\partial}{\partial x_i} I_{(-\infty,u]}(x)$ be in that case? I'm guessing $\frac{\partial}{\partial x_i} I_{(-\infty,u]}(x) = 0$ if $x<u$, but what would happen at $x = u$ and $x > u$. – Elements Jun 10 '15 at 17:20
• $\partial I_{(-\infty,u]}(x)=\begin{cases} \emptyset & \text{ if } x>u\\ [0,+\infty) & \text{ if } x=u\\ 0 & \text{ if } x<u\\ \end{cases}$ - it is the set of directions pointing outward from the interval at $x$ – daw Jun 10 '15 at 17:30