Prev Next

@(@ \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( Ablambdamuuvyz )

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.
Input File: l1_newton_quad.m