L1-regularized quadratic function: Difference between revisions

Revision as of 17:48, 11 May 2014

Definition

A $L^{1}$ -regularized quadratic function of one variable is a function of the form:

$f (x) : = a x^{2} + b x + c + λ | x |$

where $a, b, c, λ \in R, a > 0, λ > 0$ . Note that we assume $a > 0$ for some of our case analysis, because we consider such functions in the context of modifying the minimization problem for quadratic functions.

The function has a piecewise quadratic function definition:

$f (x) : = {\begin{matrix} a x^{2} + (b + λ) x + c, & x \geq 0 \\ a x^{2} + (b - λ) x + c, & x < 0 \end{matrix}$

Differentiation

First derivative

The expression for the first derivative is obtained from the piecewise definition of the function, using the differentiation rule for piecewise definition by interval. We obtain the expression:

$f^{'} (x) = {\begin{matrix} 2 a x + (b + λ), & x > 0 \\ 2 a x + (b - λ), & x < 0 \end{matrix}$

The first derivative is undefined at $x = 0$ . At this point, the left-hand derivative is $b - λ$ and the right-hand derivative is $b + λ$ .

The derivative function is therefore a piecewise linear function with a jump discontinuity at zero.

Second derivative

The second derivative is defined as:

$f^{″} (x) = 2 a, x \neq 0$

The second derivative is undefined at zero.

Points and intervals of interest

Critical points

As noted above, we have the following expression for the derivative:

$f^{'} (x) = {\begin{matrix} 2 a x + (b + λ), & x > 0 \\ 2 a x + (b - λ), & x < 0 \end{matrix}$

We have at least one and at most three critical points. The three candidates are discussed below.

Critical point	Case that it occurs	Description of critical point
0	Always	The function is not differentiable at the point. The left-hand derivative is $b - λ$ and the right-hand derivative is $b + λ$ .
$\frac{- (b + λ)}{2 a}$	The case that $\frac{- (b + λ)}{2 a} > 0$	It is the unique critical point for the quadratic piece for $x > 0$ . It occurs if and only if the critical point for that piece happens to fall within that piece definition.
$\frac{- (b - λ)}{2 a}$	The case that $\frac{- (b - λ)}{2 a} < 0$	It is the unique critical point for the quadratic piece for $x < 0$ . It occurs if and only if the critical point for that piece happens to fall within that piece definition.

The second and third critical point type cannot both occur. This can be seen arithmetically, since subtracting the second condition from the first contradicts the assumption pair $λ > 0, a > 0$ . It also follows from the fact that the graph of the function is concave up (more on this later).

Here are the combined cases:

Case	Set of critical points
$0 > \frac{- (b - λ)}{2 a}$	${\frac{- (b - λ)}{2 a}, 0}$
$\frac{- (b - λ)}{2 a} > 0 > \frac{- (b + λ)}{2 a}$	${0}$
$\frac{- (b + λ)}{2 a} > 0$	${0, \frac{- (b + λ)}{2 a}}$

Intervals of increase and decrease

We include the three cases below. Recall the assumption that $a > 0, λ > 0$ :

Case	Set of critical points
$0 > \frac{- (b - λ)}{2 a}$	decreasing on $(- \infty, \frac{- (b - λ)}{2 a}]$ increasing on $[\frac{- (b - λ)}{2 a}, \infty)$ : note that the derivative is undefined at 0, but the function is continuous and increasing on both the left and right.
$\frac{- (b - λ)}{2 a} > 0 > \frac{- (b + λ)}{2 a}$	decreasing on $(- \infty, 0]$ . increasing on $[0, \infty)$ .
$\frac{- (b + λ)}{2 a} > 0$	decreasing on $(- \infty, \frac{- (b + λ)}{2 a}]$ : note that the derivative is undefined at 0, but the function is continuous and increasing on both the left and right. increasing on $[\frac{- (b + λ)}{2 a}, \infty)$

Local extreme values

We include the three cases below. Recall the assumption that $a > 0, λ > 0$ . Note that the function is concave up (i.e., a convex function) and therefore has a unique point of local minimum that is also a point of absolute minimum.

Case	Point of unique local minimum that is also a point of absolute minimum	Local minimum value (also the absolute minimum value)
$0 > \frac{- (b - λ)}{2 a}$	$\frac{- (b - λ)}{2 a}$	$c - \frac{(b - λ)^{2}}{4 a}$
$\frac{- (b - λ)}{2 a} > 0 > \frac{- (b + λ)}{2 a}$	0	$c$
$\frac{- (b + λ)}{2 a} > 0$	$\frac{- (b + λ)}{2 a}$	$c - \frac{(b + λ)^{2}}{4 a}$

Intervals of concave up and concave down=

At all points other than 0, the function is twice differentiable and has positive second derivative $2 a$ . At zero, the first derivative jumps upward from $b - λ$ to $b + λ$ . Therefore, the first derivative is increasing throughout the domain.

@@ Line 76: / Line 76: @@
 | <math>\frac{-(b - \lambda)}{2a} > 0 > \frac{-(b + \lambda)}{2a}</math> || decreasing on <math>(-\infty,0]</math>.<br>increasing on <math>[0,\infty)</math>.
 |-
-| <math>\frac{-(b + \lambda)}{2a} > 0</math> || decreasing on <math>\left(-infty,\frac{-(b + \lambda)}{2a}\right]</math>: note that the derivative is undefined at 0, but the function is continuous and increasing on both the left and right.<br>increasing on <math>\left[\frac{-(b + \lambda)}{2a},\infty\right)</math>
+| <math>\frac{-(b + \lambda)}{2a} > 0</math> || decreasing on <math>\left(-\infty,\frac{-(b + \lambda)}{2a}\right]</math>: note that the derivative is undefined at 0, but the function is continuous and increasing on both the left and right.<br>increasing on <math>\left[\frac{-(b + \lambda)}{2a},\infty\right)</math>
 |}
+===Local extreme values===
+We include the three cases below. Recall the assumption that <math>a > 0, \lambda > 0</math>. Note that the function is concave up (i.e., a convex function) and therefore has a unique point of local minimum that is also a point of absolute minimum.
+{| class="sortable" border="1"
+! Case !! Point of unique local minimum that is also a point of absolute minimum !! Local minimum value (also the absolute minimum value)
+|-
+| <math>0 > \frac{-(b - \lambda)}{2a}</math> || <math>\frac{-(b - \lambda)}{2a}</math> || <math>c - \frac{(b - \lambda)^2}{4a}</math>
+|-
+| <math>\frac{-(b - \lambda)}{2a} > 0 > \frac{-(b + \lambda)}{2a}</math> || 0 || <math>c</math>
+|-
+| <math>\frac{-(b + \lambda)}{2a} > 0</math> || <math>\frac{-(b + \lambda)}{2a}</math> || <math>c - \frac{(b + \lambda)^2}{4a}</math>
+|}
+==Intervals of concave up and concave down===
+At all points other than 0, the function is twice differentiable and has positive second derivative <math>2a</math>. At zero, the first derivative jumps upward from <math>b - \lambda</math> to <math>b + \lambda</math>. Therefore, the first derivative is increasing throughout the domain.