$\newcommand{\R}[1]{{\rm #1}}$$\newcommand{\B}[1]{{\bf #1}}$
L2 Objective with L1 Regularization Newton Step

Syntax
[ du , dv , dy , dz ] = l1_newton_quad( A, b, lambda, mu, u, v, y, z )

Notation
We use $I_n \in \B{R}^{n \times n}$ to denote the identity matrix and $1_n \in \B{R}^n$ to denote the vector will all elements equal to one. Given a vector $u \in \B{R}^n$ we use $D(u) \in \B{R}^{n \times n}$, to denote the corresponding diagonal matrix. If $v$ is also in $\B{R}^n$, $u / v \in \B{R}^n$ denotes element-wise division. The notation $u^{-1}$ is defined by $u^{-1} = 1_n / u$.

Purpose
We are given a positive semi-definite matrix $A \in \B{R}^{n \times n}$, a vector $b \in \B{R}^n$ and the scalars $\lambda \in \B{R}_+$, $\mu \in \B{R}_+$. The function $F : \B{R}^{4n} \rightarrow \B{R}^{4n}$ is defined by $$F \left( \begin{array}{c} u , v , y , z \end{array} \right) = \left( \begin{array}{c} D ( u ) y \\ D ( v ) z \\ + A (u - v) + b - y + \lambda 1_n \\ - A (u - v) - b - z + \lambda 1_n \end{array} \right)$$ Given $(u, v, y, z) \in \B{R}_+^{4n}$ this routine solves for $( \Delta u, \Delta v, \Delta y , \Delta z )$ such that $$F (u, v, y, z) + F^{(1)} (u, v, y, z ) \left( \begin{array}{c} \Delta u \\ \Delta v \\ \Delta y \\ \Delta z \end{array} \right) = \mu \left( \begin{array}{c} 1_n \\ 1_n \\ 0 \\ 0 \end{array} \right)$$

A
The argument A is an $n \times n$ positive definite real matrix.

b
The argument b is real column vector of length $n$.

lambda
The argument lambda is a real scalar. It corresponds to $\lambda$ in the discussion above (see Purpose ).

mu
The argument mu is a real scalar. It corresponds to $\mu$ in the discussion above.

u, v, y, z
The arguments u, v, y, and z are real column vectors of length $n$. All the elements of these vectors must be greater than zero.

du, dv, dy, dz
The return values du, dv, dy, and dz are real column vectors of length $n$. They correspond respectively to $\Delta u$, $\Delta v$, $\Delta y$, and $\Delta z$ in the discussion above.

Example
The file newton_quad_ok.m contains an example and test of l1_newton_quad. It returns true if the test passes and false otherwise.