|
|
Prev | Next |
\newcommand{\R}[1]{{\rm #1}}
\newcommand{\B}[1]{{\bf #1}}
[x_out, info] = l1_quadratic(max_itr, A, b, lambda, delta)
1_n \in \B{R}^n
to denote the vector will all elements
equal to one.
Given a vector
w \in \B{R}^n
we use
D(w) \in \B{R}^{n \times n}
,
to denote the corresponding diagonal matrix.
A \in \B{R}^{n \times n}
,
a vector
b \in \B{R}^n
and a scalar
\lambda \in \B{R}_+
.
The problem we wish to solve is
\[
\begin{array}{lll}
\R{minimize}
& \frac{1}{2} x^\R{T} A x + b^\R{T} x + 2 \lambda \| x \|_1
& \R{w.r.t} \; x \in \B{R}^n
\end{array}
\]
The
\delta
relaxed first order conditions for a minimum are:
for
i = 1 , \ldots , n
\[
\begin{array}{l}
\R{if} \; x_i > \delta \; , \;
\delta \geq \left| \sum_{j=1}^n A_{i,j} x_j + b_i + \lambda \right|
\\
\R{if} \; x_i < - \delta \; , \;
\delta \geq \left| \sum_{j=1}^n A_{i,j} x_j + b_i - \lambda \right|
\\
\R{if} \; | x_i | \leq \delta \; , \;
\lambda + \delta \geq \left| \sum_{j=1}^n A_{i,j} x_j + b_i \right|
\end{array}
\]
n \times n
positive definite real matrix.
n
.
\lambda
in the discussion above
(see Purpose
).
\delta
in the discussion above.
(end, 1) described below.
(k, :)
corresponds to iteration
k-1
of the algorithm.
If l1_quadratic has satisfied the convergence condition if
and only if
(end, 1) <= delta
x^k
to denote the value of
x
at iteration
k
of the algorithm.
The value (k+1, 1) is defined by
\[
info(k, 1) = \max_i \left\{ \begin{array}{ll}
\left| \sum_{j=1}^n A_{i,j} x_j^k + b_i + \lambda \right|
& \R{if} \; x_i^k > \delta
\\
\left| \sum_{j=1}^n A_{i,j} x_j^k + b_i - \lambda \right|
& \R{if} \; x_i^k < - \delta
\\
\max \left [ 0 ,
\left| \sum_{j=1}^n A_{i,j} x_j^k + b_i \right| - \lambda
\right]
& \R{if} \; | x_i^k | \leq \delta
\end{array} \right\}
\]
(k+1, 2) is the relaxation factor
used during iteration
k
.
As this factor decreases to zero, the solution should correspond to
the original problem.
(k+1, 3) is the line search step size
used during iteration
k
.
Values near one indicate good convergence.
Small values indicate that the relaxation factor is decreasing to quickly
(with the exception that (1, 3) is always zero).
l1_quadratic.
It returns true if the test passes and false otherwise.
l1_quadratic.