Выражение (12) может быть переформулировано как задача линейного
программирования, в случае если данные вещественные, и как зада-
ча математического программирования второго порядка, если данные
комплексные.
Сначала рассмотрим численное решение для случая, когда дан-
ные вещественные. Процедура переформулирования задачи приводит
к задаче минимизации
`
1
-нормы, которая является широко известной
задачей линейного программирования. Введем две переменные
x
+
и
x
−
, определенные как
x
+
i
= max
{
x
i
,
0
}
,
x
−
i
= max
{−
x
i
,
0
}
, при по-
мощи которых
x
может быть легко восстановлен следующим обра-
зом:
x = x
+
−
x
−
. Переменные
x
+
и
x
−
ограничены положительным
октантом и должны удовлетворять условию
x
+
i
x
−
i
= 0
,
8
i
. Оно авто-
матически выполняется, когда рассматривается задача минимизации.
Переформулировав задачу (12), получим
min 1
0
x
+
x
−
при ограничениях
A
−
A
x
+
x
−
= y
и
x
+
x
−
>
0
.
(13)
Численное решение задачи (13) легко найти при помощи симплекс-
метода или метода внутренних точек при линейном программиро-
вании.
Задачу (12) без учета помех можно представить в следующем виде:
min
k
x
k
1
при ограничении
k
y
−
Ax
k
2
2
= 0
.
(14)
С учетом помех уравнение (14) принимает вид:
min
k
x
k
1
при ограничении
k
y
−
Ax
k
2
2
6
β
2
,
(15)
где
β
— параметр регуляризации, который характеризует желаемую
интенсивность помехи. Также может быть предложено несколько аль-
тернативных формулировок задачи. Наиболее широко распространен-
ная формулировка (она, в частности, использована в работах [15, 19])
— это штрафная форма
min
k
y
−
Ax
k
2
2
+
λ
k
x
k
1
.
(16)
Если же поменять местами целевую функцию и ограничение, то по-
лучим третью форму записи:
min
k
y
−
Ax
k
2
2
при ограничении
k
x
k
1
6
δ.
(17)
Следует обратить внимание на то, что можно заменить ограничение
k
y
−
Ax
k
2
2
6
β
2
ограничением
k
y
−
Ax
k
2
6
β
, что приводит к экви-
валентной штрафной форме
min
k
y
−
Ax
k
2
+ ˜
λ
k
x
k
1
.
(18)
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2007. № 3
15
