0
$\begingroup$

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$?
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Baby Dragon Jun 10 '15 at 3:35
  • $\begingroup$ 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. $\endgroup$ – Elements Jun 10 '15 at 17:14
1
$\begingroup$

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.

2) The KKT conditions of convex programs are always sufficient. They are necessary under constraint qualifications (here: validity of subgradient sum-rule, which holds for your case).

3) Yes, follows from the (corrected) complementarity slackness #2.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Elements Jun 10 '15 at 17:11
  • $\begingroup$ Yes, these indicator functions take values in $\{0,+\infty\}$ to force possible minimizers to satisfy the constraints. $\endgroup$ – daw Jun 10 '15 at 17:13
  • $\begingroup$ 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$. $\endgroup$ – Elements Jun 10 '15 at 17:20
  • 1
    $\begingroup$ $\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$ $\endgroup$ – daw Jun 10 '15 at 17:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.