Для
p
= 1
известна следующая аппроксимация:
k
x
k
1
≈
N
X
i
=1
ρ
(
x
i
)
,
(20)
где
ρ
(
x
) =
(
x
2
i
,
если
|
x
i
|
< γ
;
|
x
i
| −
γ
+
γ
2
,
если
|
x
i
|
>
γ
;
(21)
γ
— параметр. При
γ
→
0
, аппроксимация равномерно стремится к
`
1
-норме. Однако для любого
γ >
0
она дифференцируема. Данная ап-
проксимация может быть переформулирована в задачу квадратичного
программирования [21]. Другая аппроксимация [22], которая работает
при
p <
1
, также как и при
p
= 1
, имеет вид
k
x
k
p
p
≈
N
X
i
=1
|
x
i
|
2
+
ε
p
/2
.
(22)
Здесь
ε >
0
— параметр гладкости. Данная дифференцируемая аппрок-
симация хорошо подходит для поставленных целей и дает модифици-
рованную регуляризирующую функцию
J
(x)
≈
J
ε
(x) =
k
y
−
Ax
k
2
2
+
λ
N
X
i
=1
|
x
i
|
2
+
ε
p
/2
.
(23)
Следует отметить, что
J
ε
(x)
→
J
(x)
, когда
ε
→
0
. В качестве
ε
берем
константу малой величины. Минимизация
J
ε
(x)
в общем случае не
приводит к решению в замкнутой форме, поэтому необходимо исполь-
зовать численные алгоритмы.
Для решения данной задачи оптимизации в [20] используется алго-
ритм полуквадратичной регуляризации [23]. Полуквадратичная регу-
ляризация переводит задачу неквадратичной оптимизации в совокуп-
ность квадратичных задач. Для наших целей достаточно рассмотреть
квазиньютоновский алгоритм [14]. Однако доказательство локальной
сходимости из любой начальной точки основано на полуквадратичных
решениях алгоритма.
Используется следующий итеративный алгоритм:
H ˆx
(
n
)
ˆx
(
n
+1)
= 2A
T
y
,
(24)
где
n
— номер итерации;
H (x)
,
2A
T
A +
λ
Λ (x) ;
(25)
Λ (x)
,
diag
(
p
|
x
i
|
2
+
ε
1
−
p
/2
)
;
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2007. № 3
17
