Отличие выражения (18) от (16) заключается в том, что первое сла-
гаемое имеет первую степень, а не вторую. Эта форма записи может
быть представлена более наглядно при помощи математического про-
граммирования второго порядка.
Численный метод для
`
p
-оптимизации с учетом помех
min
J
(x) = min
k
y
−
Ax
k
2
2
+
λ
k
x
k
p
p
(19)
был разработан в работе [20]. Метод особенно эффективен при
p <
1
.
Использование
`
p
-алгоритмов с
p <
1
ограничено в связи с возникаю-
щими трудностями, так как
`
p
-норма не является выпуклой для
p <
1
(и даже ее множества уровня не являются выпуклыми). Таким обра-
зом, не гарантируется достижение глобального минимума при помо-
щи методов локальной оптимизации. Вместо использования алгорит-
мов глобальной оптимизации, чаще используют алгоритмы локальной
оптимизации, имея в виду, что есть хорошее начальное приближение.
Использование
`
p
-норм с
p <
1
для обеспечения некорректности
может быть обосновано точно так же, как и использование
`
1
-норм.
Фактически, когда
p <
1
, необходимые условия глобального экстре-
мума
`
p
-задачи без помех (
min
k
x
k
p
p
при ограничении
y = Ax)
ста-
новятся эквивалентными условиям глобального экстремума
`
0
-задачи
(
min
k
x
k
0
0
при ограничении
y = Ax)
, которые являются менее жестки-
ми. Однако нахождение глобального решения
`
p
-задачи без помех для
p <
1
является более сложным, чем для случая, когда
p
= 1
(
`
p
-задача
без помех недостаточно выпукла).
Перейдем к формулировке задачи с помехами:
J
(x) =
= min
k
y
−
Ax
k
2
2
+
λ
k
x
k
p
p
. Кроме невыпуклости возникает еще одна
трудность при использовании
`
p
-целевой функции, которая заключа-
ется в том, что она не дифференцируема в
0
. Фактически, целевые
функции не дифференцируемы для обоих случаев:
p
= 1
и
p <
1
.
Но для
p
= 1
существует способ обойти эту трудность: в случае
вещественных данных представлением
x = x
+
−
x
−
, где
x
+
>
0
,
x
−
>
0
, осуществляется переход к эквивалентной задаче линейного
программирования. Для
p <
1
это невозможно, и вместо этого рассма-
тривают дифференцируемые аппроксимации
`
p
-целевой функции; эти
аппроксимации можно также использовать для
`
1
-целевой функции.
Дифференцируемые аппроксимации обычно содержат параметр, кото-
рый отвечает за компромисс между гладкостью аппроксимации и бли-
зостью к не дифференцируемой функции, для которой производится
аппроксимация. Другими словами, дифференцируемая аппроксимация
— это семейство функций.
16
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2007. № 3
