|
|
Prev | Next |
\newcommand{\R}[1]{{\rm #1}}
\newcommand{\B}[1]{{\bf #1}}
[x_out] = l1_with_l2(max_itr, A, a, B, b, delta)
[x_out, info] = l1_with_l2(max_itr, A, a, B, b, delta)
1_\ell \in \B{R}^\ell
to denote the vector will all elements
equal to one.
Given a vector
w \in \B{R}^\ell
we use
D(w) \in \B{R}^{\ell \times \ell}
,
to denote the corresponding diagonal matrix.
A \in \B{R}^{\ell \times n}
,
a vector
a \in \B{R}^\ell
,
a matrix
B \in \B{R}^{m \times n}
, and
a vector
b \in \B{R}^m
.
The problem we wish to solve is
\[
\begin{array}{lll}
\R{minimize}
& \| A x - a^\R{T} \|_1 + \frac{1}{2} \| B x - b \|_2^2
& \R{w.r.t} \; x \in \B{R}^n
\end{array}
\]
p \in \B{R}^\ell
with
p_i > 0
for all
i
, the matrix
A^\R{T} D(p) A + B^\R{T} B
must have rank
n
.
\[
\begin{array}{lll}
\R{minimize}
& \frac{1}{2} \| B x - b \|_2^2 + 1_\ell^\R{T} v_+ + 1_\ell^\R{T} v_-
& \R{w.r.t.} ( v_+ , v_- , x ) \in \B{R}_+^{2 \ell} \times \B{R}_n
\\
\R{subject \; to}
& A x - b = v_+ - v_-
\end{array}
\]
The first order conditions for a minimum of this problem are
equivalent to
F = 0
where
F : \B{R}^{5 \ell +n} \rightarrow \B{R}^{5 \ell +n}
is defined by
\[
F \left( \begin{array}{c} u_+ , u_- , v_+ , v_- , w , x \end{array} \right)
=
\left( \begin{array}{c}
D ( u_+ ) v_+
\\
D ( u_- ) v_-
\\
1_\ell - u_+ - w
\\
1_\ell - u_- + w
\\
A x - v_+ + v_- - a
\\
A^\R{T} w + B^\R{T} B x - B^\R{T} b
\end{array} \right)
\]
\ell \times n
matrix
where
\ell
can not be zero.
\ell
.
m \times n
matrix
where
m
can not be zero (see l1_linear
for the case
where
m
is zero).
m
.
k+1, 1) <=delta (see
First Order Condition
below).
(end, 1) described below.
(k+1, :)
corresponds to iteration
k
of the algorithm.
If l1_linear has satisfied the convergence condition if
and only if
(end, 1) <= delta
u_+^k
u_-^k
v_+^k
v_-^k
w^k
x^k
to denote the corresponding values at iteration
k
of the algorithm.
The value (k+1, 1) is defined by
\[
info(k+1, 1) = \left. \left|
F \left( \begin{array}{c} u_+ , u_- , v_+ , v_- , w , x \end{array} \right)
\right| \right/ \sqrt{5 \ell + n}
\]
(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_with_l2.
It returns true if the test passes and false otherwise.
l1_with_l2.