L1-regularized quadratic function of multiple variables

Definition

A $L^1$-regularized quadratic function of the variables $x_1,x_2,\dots ,x_n$ is a function of the form (satisfying the positive definiteness condition below):

$f(x_1,x_2,\dots ,x_n):=(\sum _{i=1}^n\sum _{j=1}^n{a}_{ij}{x}_i{x}_j)+(\sum _{i=1}^n{b}_i{x}_i)+\lambda \sum _{i=1}^n\left|x_i\right|+c$

In vector form, if we denote by $\overrightarrow{x}$ the column vector with coordinates $x_1,x_2,\dots ,x_n$, then we can write the function as:

${\overrightarrow{x}}^{T}A\overrightarrow{x}+{\overrightarrow{b}}^T\overrightarrow{x}+\lambda |\overrightarrow{x}{|}_1+c$

where $A$ is the $n\times n$ matrix with entries $a_{ij}$ and $\overrightarrow{b}$ is the column vector with entries $b_i$.

Note that the matrix $A$ is non-unique: if $A+A^T=F+F^T$ then we could replace $A$ by $F$. Therefore, we could choose to replace $A$ by the matrix $(A+A^T)/2$. We will thus assume that $A$ is a symmetric matrix.

We impose the further restriction that the matrix $A$ be a symmetric positive definite matrix.

Key data

Item	Value
default domain	the whole of ${\mathbb{R}}^n$

Differentiation

Partial derivatives and gradient vector

The partial derivative with respect to the variable $x_i$, and therefore also the $i^{th}$ coordinate of the gradient vector (if it exists), is given as follows when $x_i\ne 0$:

$\frac{\partial f}{\partial x_i}=(\sum _{j=1}^n(a_{ij}+a_{ji})x_j)+b_i+\lambda \mathrm{s}\mathrm{g}\mathrm{n}(x_i)$

By the symmetry assumption, this becomes:

$\frac{\partial f}{\partial x_i}=(\sum _{j=1}^{n}2a_{ij}{x}_j)+b_i+\lambda \mathrm{s}\mathrm{g}\mathrm{n}(x_i)$

The partial derivative is undefined when $x_i=0$.

The gradient vector exists if and only if all the coordinates are nonzero.

In vector notation, the gradient vector is as follows for all $\overrightarrow{x}$ with all coordinates nonzero:

$\mathrm{\nabla }f(\overrightarrow{x})=2A\overrightarrow{x}+\overrightarrow{b}+\lambda \stackrel{\mathrm{g}}{\mathrm{s}}(\overrightarrow{x})$

where $\stackrel{\mathrm{g}}{\mathrm{s}}$ is the signum vector function.

Hessian matrix

The Hessian matrix of the function, defined wherever all the coordinates are nonzero, is the matrix $2A$.