ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 1, с. 21-33
УДК 519.853
РЕГУЛЯРИЗОВАННЫЙ МЕТОД НЬЮТОНА ДЛЯ РЕШЕНИЯ ЗАДАЧ РАВНОВЕСНОГО ПРОГРАММИРОВАНИЯ С НЕТОЧНО
ЗАДАННЫМ МНОЖЕСТВОМ1)
© 2007 г. А. С. Антипин*, Ф. П. Васильев**, А. С. Стукалов**
(* 119991 Москва, ул. Вавилова, 40, ВЦ РАН; ** 119992 Москва, Ленинские горы, МГУ, ВМК) e-mail: antipin@ccas.ru; ast@pochta.ru Поступила в редакцию 12.05.2006 г.
Для решения неустойчивых равновесных задач, когда неточно заданы не только целевая функция, но и множество, на котором ищется точка равновесия, предлагается регуляризован-ный метод Ньютона в сочетании со штрафными функциями, исследуется его сходимость. Строится регуляризующий оператор. Библ. 18.
Ключевые слова: равновесное программирование, регуляризация, метод Ньютона, штрафные функции.
1. Пусть Ж0 - заданное множество из гильбертова пространства Н со скалярным произведением {и, V) элементов и, V е Н, функции Ф(V, w), g1(w), ..., gs(w) определены при Vе Ж0, ц> е Ж0. Рассмотрим следующую задачу равновесного программирования: найти точку V* из условий
V* е Ж, Ф( V*, V*) ^ Ф( V*, w) Vw е Ж, (1)
где
Ж = {w е Ж0: g1(w) ^ 0, г = 1, т; g1 (w) = 0, , = т + 1, 5}. (2)
Точку V* со свойствами (1) будем называть точкой равновесия функции w) на множестве Ж.
Многие важные проблемы исследования операций, вычислительной математики, математической экономики сводятся к задаче (1), (2) (см. [1]-[5]). Эта задача неустойчива к возмущениям входных данных w), gi и для надежного определения приближенного решения нужно пользоваться идеями и методами регуляризации [6]-[9]. В работах [10]-[14] предложены и исследованы общие методы регуляризации (методы стабилизации, невязки, квазирешений) для неустойчивых равновесных задач. Метод стабилизации в сочетании с экстраградиентным методом рассматривался в [15] для задач (1), (2) с точно заданным множеством (когда Ж = Ж0), в [16] - с неточно заданным множеством. В настоящей работе предлагается и исследуется регуляризован-ный метод Ньютона в предположении, что целевая функция Ф(^ w) и множество (2) известны приближенно.
Для учета ограничений типа равенств и неравенств, задающих множество (2), будем пользоваться простейшей штрафной функцией (см. [9])
р(w) = w))р, w е Жо, (3)
г = 1
где gi = тах^-; 0} при г = 1, т, gi = |gi| при г = т +1,5 . В качестве стабилизатора, как и в [15], [16], возьмем скалярное произведение w) = {V, w). Введем функцию Тихонова
Гк(V, w) = Ф( V, w) + АкР(^^) + ак{ V, w), V, w е Жо,
(4)
Ак ^ 1, ак> 0, к = 0, 1,....
Работа выполнена при финансовой поддержке РФФИ (код проекта 05-01-00242) и Программы ведущих научных школ (код проекта НШ-2240.2006.1).
Пусть функции Ф(у, w), Р(м>) обладают производными Фреше
2 2 2 ЭФ( у, **- ЭР(^ = w) ЭР ( w ) = Р-(w) vw е W° (5)
дw ' ^ ' ЭvЭw ' дw Р(™Л ^ Р(™)' ™е '(5)
Заметим, что производная Р"^) существует, если функции gii = 1, 5, дважды дифференцируемы и в (3) параметр р достаточно большой (например, р = 4).
Введем операторы
□ Ф( V, V) - Гд^ФСЫ^^д^^
V Ф( V V) = Эф( у, w - ,
Э w „ - V V Эw Э ^
Тогда функция Тихонова (4) имеет производные
дТХу^) _ ЭФ( V, w)
V е W°. (6)
Э w Э w
+ АкР (w) + ак V,
Э Тк(v, ^^) _ Э2Ф( V, w) + А р„ w Э Тк( v, - = Э2 Ф( V, w- + а
(7)
Эw2 Эw2 ' ЭvЭw ЭvЭw
где I - единичный оператор, и, аналогично (6), можно ввести операторы
VwTk(V, V) - ^Ф( V, V) + АкР'( V) + а^V, □ Тк(V, V) = □ Ф( V, V) + АкР"(V) + ак1. (8)
Пусть zk - точка равновесия функции Тк(^ w) на множестве Ж0, т.е.
^к е W°, Тк(2Ъ ) « Тк(2Ъ w) Vw е W°. (9)
Если W0 - выпуклое множество, то точка гк необходимо удовлетворяет условию из [9]
{VКТк(^), w - ¿к> ^ 0 Vw е W°. (10)
Иначе говоря, гк является решением вариационного неравенства
{^(г), w - г> ^ 0 Vw е W°, (11)
где ^к(г) = VwTk(z, г). Для поиска решения вариационного неравенства (11) можно воспользоваться методом Ньютона, который заключается в построении последовательности хк по правилу из [8], [17]: имея к-е приближение хк, в качестве следующего приближения берем решение г = хк + 1 вариационного неравенства
{^(Хк) + (Хк)(г - Хк), w - г> ^ 0 Vw е W°, (12)
где ¥'к (г) - производная Фреше отображения ^к(г). Заметим, что, в отличие от вариационного неравенства (11) с оператором который вообще говоря, нелинейный, в (12) оператор ^к(хк) + + Е'к (хк)(г - хк) уже является линейным по г. Поскольку для = г) производная (г) =
= ПТк(г, г), то применительно к (10) вариационное неравенство (12) будет иметь вид
^КТк(хь хк) + □ Тк(хк, хк)(г - хк), w - г> ^ ° Vw е W°. (13)
Предположим, что вместо точных значений производных (5) и операторов (6) нам известны их приближения
РфЯ/ Р;(*>• р>'>•
(14)
22
(V-Ф( V, V))к = Р^); V)»'- = + к = °, ^
Ж - V
такие, что
max<
fЭФ( v, у)Л дФ ( v, v) V dw ), dw
;||Pk(v) - P(v^ 8lt(1 + 1|v|l),
(15)
ve W0, w e H, k = 0, 1, ..., max{||(ПФ( v, v))k-□ Ф( v, v)||; |pk'( v) -P"(v)||} ^ 62b v e Wo, k = 0, 1, ...,
где 51k & 0, 52k & 0 - параметры погрешности. Тогда в качестве приближений для значений производных (7) при w = v естественно взять
= + AkPk (w) + ak v, = + AkPk'( w),
dw У dw )k k ky ' k ' dw2 I dw2 К
д w ^ dw
2 2 д tk(v, w) _ fa Ф( v, w)
(16)
övöw V dvдw ' + v e k =0'1
(18)
>k
а приближениями значений операторов (8) будут
v, v) = dtkV), Utk(v v) = РФ(v, v))k + AkF¡(v) + akI, k = 0, 1,.... (17) Из (7), (8), (14M17), Ak & 1 следует, что
||Vwtk(V, v) - VwTk(v, v)|| ^ 281 kAk(1 + I vil),
||Dtk (v, v) -□ Tk (v, v )|| ^ 2 82kAk, v e Wo, k = 0, 1,..
Теперь мы можем описать регуляризованный метод Ньютона для решения задачи (1), (2) с неточными входными данными (14)-(17). Пусть v0 e W0 - начальное приближение. Пусть при некотором k & 0 уже известно приближение vk e W0. Следующее приближение vk + 1 e W0 определим из условий
К +1- Vk +11 ^ ek(1 + 1 vЛ), (19)
где -V k +1 e W0 - решение вариационного неравенства
(Vwtk(vk, vk) + □ tk(vk, vk)(z - vk), w - z) & 0 Vw e Wo (20)
по аналогии с (13). Условие (19) означает, что вариационное неравенство (20) можно решать приближенно и вместо его точного решения z = v k +1 брать какую-либо точку vk + 1 e W0, удовлетворяющую неравенству (19), где £k & 0 - характеристика возникающей при этом погрешности.
Заметим, что если в (2) W0 = H, то вариационное неравенство (20) равносильно операторному уравнению
Р tk( vk> vk))(z - vk) = -Vwtk(vk, vk).
Отсюда в случае существования обратного оператора (Utk(vk, vk))-1 вытекает "привычное" явное выражение для (k + 1)-го приближения метода Ньютона (ср. с [9])
v
k +1 = vk - Р tk( vb vk)) 1Vwtk( vb vk),
соответствующее случаю £k = 0 в (19).
2. Формальное описание регуляризованного метода Ньютона закончено. Исследуем его сходимость.
Теорема 1. Пусть верно следующее:
1) W0 - выпуклое замкнутое множество из H, int W0 Ф 0 ; функции Ф(у, w), P(w) определены, непрерывны, обладают непрерывными производными (5), выпуклы по переменной w на W0 при любом фиксированном v е W0, выполнено условие Липшица
||П Ф( v, v)-□ Ф( w, w )|| « L|| v - w||, ||P" (v) - P"(w )|| « L || v - w|| Vv, w е W0; (21)
функция Ф(^ w) положительно полуопределена (кососимметрична, см. [5]), т.е.
Ф( V, V) - Ф( V, w) - Ф(w, V) + Ф^, w) & ° Vv, w е W°; (22)
множество W* решений задачи (1), (2) не пусто, V* - нормальное решение этой задачи, т.е.
V* е W*, IV* - VII; (23)
V е W *
задача
Ф( V*, w) —► шГ, w е W, (24)
имеет сильно согласованную постановку (см. [9]), т.е. существуют числа с, & 0, 1 = 1, 5 , V > 0 такие, что
5
Ф( V*, V*) ^ Ф( V*, w) + £ с(g+(w))* Vw е W°; (25)
1 -1
2) вместо точных производных (5) известны их приближения (14), удовлетворяющие условиям (15);
3) числовые последовательности {ак}, {Ак}, {ек}, {51к}, {52к} положительны и таковы, что
(26)
а A i
Ak * 1, ^ 2, A- ^ 2, k = 0, 1,..., lim (а* + Ak + ек + 8U + 62Ь) = 0,
ak +1 Ak k
где
lim akA^ (P v) = при p > V (если p = v, данное условие не нужно);
k ^^
Ak „ 32 LAk ( 4 51kAk\ —(16 81k + 18 62k) + 4 ek +-k (1 + R)(ek + +
ак lk 2k' k а^ \ k ak )
+ 32LAAk( R\ak - ak +1+ R\Ak - Ak +1) ^ 1 k = 0, 1,...,
2
( ||2 B \ 1/2
R = sup Rk, Rk = MI V* +-пРи P > V Rk = lk* пРи p = V,
k * 0 v akAk p V
(27)
(28)
B = (p-v)pP(p-V)v-V/(p-V)Xh|P'(P-V), R = sup ||P(w)||;
IMI « R
„-Р/(P - v)„-v/(P- |„ | P/(P - v)
i = 1
4) начальное приближение v0 e таково, что
1 a0
V„- « 58la5' (29)
где точка г0 е взята из (9) при к = 0.
Тогда метод (19), (20) определяет последовательность {vk} и
lim |—k - v* = 0, (30)
k ^^
причем сходимость в (30) равномерная относительно выбора M^^V-1—-) , Pk (w), (ШФ( v, v))k, Pk (w) из (15).
Содержательные классы задач (1), (2), для которых выполняются условия (24), (25), приведены в [11]. Например, если функция Лагранжа
Ь(w, Г) = Ф( V*, w) + w), w е Ж0, X = (Х„ ..., ) е Л0 = {X е Е': ^ 0, ..., Хт ^ 0},
г = 1
задачи (24) имеет седловую точку (V*, X*) е Ж0 х Л0, то в (25) можно принять с, = |Х*|, , = 1,5,
V = 1. Существование параметров {ак}, {Ак}, {ек}, {51к}, {52к} метода (19), (20), удовлетворяющих условиям (26), (27), будет показано ниже.
Для доказательства теоремы 1 нам потребуются следующие две леммы.
Лемма 1. Пусть Ж - выпуклое замкнутое множество из Н, функция Ф(^ w) непрерывна по
V на Ж при каждом w е Ж, полунепрерывна снизу по совокупности своих аргументов на Ж х Ж, выпукла и дифференцируема по переменной w на Ж при каждом фиксированном V е Ж, произ-
водная V) = дф(У,мр
д w
непрерывна по V е Ж, выполнено условие положительной по-
луопределенности (22). Пусть множество Ж* решений задачи (1) непусто. Тогда Ж* - выпуклое замкнутое множество и существует, притом единственная, точка V* со свойством (23).
Доказательство. При сделанных предположениях V* е Ж* тогда и только тогда, когда V* является решением вариационного неравенства из [9]
{У^Ф( V*, V*), w - V*) ^ 0 Vw е Ж. (31)
Убедимся, что (31) равносильно другому вариационному неравенству:
{У„Ф(w, w), w - V*) ^ 0 Vw е Ж. (32)
Из выпуклости и дифференцируемости функции Ф(^ w) по w е Ж следует (см. [9])
Ф( V, V) - Ф( V, w) ^ {У„,Ф( V, V), V - w) Vv, w е Ж. Поменяем здесь V и w местами:
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.