ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 12, с. 2014-2022
УДК 519.658
О НЕКОТОРЫХ МЕТОДАХ ОПТИМИЗАЦИИ С КОНЕЧНОШАГОВЫМИ ВНУТРЕННИМИ АЛГОРИТМАМИ В ВЫПУКЛЫХ КОНЕЧНОМЕРНЫХ ЗАДАЧАХ
С ОГРАНИЧЕНИЯМИ ТИПА НЕРАВЕНСТВ1)
© 2007 г. И. П. Антипин, А. 3. Ишмухаметов, Ю. Г. Карюкина
(119991 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: aleks@ccas.ru
Поступила в редакцию 06.05.2006 г.
Переработанный вариант 26.04.2007 г.
Предлагаются численные методы для решения конечномерных выпуклых задач с ограничениями типа неравенств при выполнении условия Слейтера. Для задач, в которых сумма целевой функции и функций ограничений является строго равномерно выпуклой, предложен и обоснован численный метод, основанный на решении двойственной к исходной регуляризо-ванной задачи. Для этого метода получены условия сходимости, оценки скорости сходимости по функционалу, по аргументу ко множеству оптимальных элементов и к g-нормальному решению. Для более общих выпуклых конечномерных задач минимизации с ограничениями типа неравенств предлагаются два метода с конечношаговыми внутренними вычислительными процедурами, основанных на методах проекции и условного градиента. Решаются конечномерные задачи, которые получаются при аппроксимации бесконечномерных задач, в частности задач оптимального управления системами с сосредоточенными и распределенными параметрами. Библ. 11.
Ключевые слова: выпуклые конечномерные задачи оптимизации, ограничения типа неравенств, численные методы оптимизации, методы регуляризации.
В теории оптимизации, в частности в задачах математического программирования, при разработке численных методов актуальными являются вопросы их практической реализуемости, эффективности и доведения их до алгоритмов. К таким вопросам относятся разработка методов, алгоритмов без бесконечных внутренних вычислительных процедур, поиск и формулировка критериев, правил останова. Предлагаемые в данной статье методы направлены на решение этих вопросов. Они построены на основе метода регуляризации (см. [1]), методов проекции, условного градиента и двойственного метода (см. [2]-[8]). Для них получены критерии останова, доказаны оценки скорости сходимости по функционалу, сходимость по аргументу ко множеству оптимальных элементов и к нормальному оптимальному элементу. Они в абстрактном, для бесконечномерных гильбертовых пространств предложены в [9], [10]. В конечномерных задачах они имеют свои особенности; в частности, это связано с эквивалентностью слабой и сильной топологий. Кроме того, отметим, что обоснование методов проводится при условии непрерывности градиентов целевой и функций ограничений, и рассматриваются случаи, когда параметр регуляризации можно положить равным нулю, т.е. при отсутствии регуляризации.
Предлагаемые методы являются аналогами предложенных ранее методов, включая бесконечномерные пространства, в частности в задачах оптимального управления с сосредоточенными и распределенными параметрами. Эти методы можно использовать при конечномерных аппроксимациях бесконечномерных задач, что и является целью работы. Поэтому естественно изучить их в конечномерном пространстве и далее совершать предельный переход к исходной задаче. В частности, особенностью методов в конечномерных пространствах является то, что в некоторых случаях параметр регуляризации можно положить нулю, т.е. регуляризации не требуется. Кроме того, методы обоснованы для квадратичных целевых функций и с квадратичными функциями, задающими ограничения на допустимые элементы. В этом случае они сводятся к последовательному решению систем линейных алгебраических уравнений.
Работа выполнена при финансовой поддержке РФФИ (код проекта 04-01-00619, 07-01-00416).
2014
1. ОБЩИЕ И ВСПОМОГАТЕЛЬНЫЕ УТВЕРЖДЕНИЯ
В евклидовом пространстве Е" со скалярным произведением и нормой, соответственно, (а, Ь) = = Ег"= 1 aibi и ||а||2 = Х"= 1 а2 рассмотрим выпуклую задачу минимизации
J(u) —- inf, u е г/ с Е", (1.1)
где U - выпуклое, ограниченное, замкнутое множество, J(u), u е Е", - выпуклая, непрерывно дифференцируемая функция.
Обозначим решения задачи (1.1): нижнюю грань функционала - через J* = inf J( u), множе-
u е U
ство оптимальных элементов - через U* = {u е U: J(u) = J*}. Будем рассматривать случай ограничений типа неравенств
U = {u е Е": gi(u) ^ 0, i е I}, I = {1, 2,..., m}, (1.2)
где gi(u), u е Е", i е I, - выпуклые, непрерывно дифференцируемые функции и для множества U выполняется условие Слейтера, т.е. существует элемент uc е Uтакой, что для gi(uc) < 0, i е I. Будем использовать также класс строго равномерно выпуклых функций. А именно: функция 9(u), u е V, строго равномерно выпукла, если VP е [0, 1] и Vu, v е V справедливо неравенство
ф(Рu + (1-в) v) ^ рф(u) + (1-р)ф( v) - в( 1-р)|(||u - VI), где модуль строгой выпуклости ц(-) удовлетворяет условиям
|(0) = 0, |(t)> 0, 0 < t ^ diam V = sup ||u - VI •
u, v е V
Свойства строго равномерно выпуклых функций изложены, например, в [2], [8].
Пусть eN> 0, eN —» 0, N —► а uNе U,N = 1, 2, ..., - некоторая последовательность, удовлетворяющая условию
iiun - w°|| ^ en, wn = pu(un - J'(un)), N = 1, 2,., (1.3)
где Рг - оператор проектирования на множество U, или условию
0 ^ (J'(un), un - wN) ^ eN, (1.3)'
где
(J'(un), wN- un) = min (J'(un), v - un), N = 1, 2,. .
v е U
Эти условия являются приближениями для, соответственно, следующих двух критериев оптимальности: для u* е U* необходимо и достаточно выполнения условий
u* = Рг(u*- J'(u*)), min ( J'(u*), v - u*) = 0.
v е U
Отметим, что из свойств оператора проектирования следуют неравенства
(J'( u), u - w1) ^ (J' (u), u - w0) ^ ||w°-u\\2 Vu е U, (1.4)
где w0 = PU(u - J(u)), и (J'(u), w1 - u) = min (J'(u), v - u) . Поэтому из (1.3)' следует (1.3).
v е U
Теорема 1. Для последовательности uN е U, N = 1, 2, ..., удовлетворяющей в задаче (1.1) условию (1.3) или (1.3)', справедливы следующие утверждения:
0 ^ J(un) - J* ^ (D + | |J' ( un )||)e n , N = 1, 2, ..., p(uN,U* 0, N—-
Здесь D - диаметр множества U:
D = diam U = sup ||u - v||,
u, v е U
p(u; U*) - расстояние от точки u до множества U*:
р(u; U*) = inf ||u - v||.
v е U *
Доказательство. Используя свойства выпуклых функций Vu* е U* запишем следующие соот-
ношения:
0 ^ J(uN) - J* ^ < J(uN), uN - u*> = <uN - Pv(uN - J(uN)), uN - u*> +
+ <Pv(un - J'(un)) - un + J(un), un - u*> =
= <Un - pu(un - J(Un)), Un - u*> +
+ < pu ( Un - J( un )) - ( un - J ( Un )), Un - Pu ( Un - J ( Un ))> +
+ < Pu ( Un - J ( Un )) - ( Un - J ( Un )), Pu ( Un - J ( Un )) - Puu *>.
Так как, в силу свойства проекций, последнее слагаемое здесь неположительно, то с учетом оценки (1.4) получаем
0 ^ J( un) - J* ^ < un - Pn( un - J ( un)), un - u *> -||Pn( un - J ( un)) - un|| 2 +
+ < J(Un), Un - Pu(Un - J(Un))> ^ (D + | J(Un)||)£n.
Пусть v - предельная точка к uN. Тогда в силу непрерывности J(u) и замкнутости U получаем
v е U*.
Для построения сходящейся к определенному элементу u* е U* последовательности uN е U,
N = 1, 2, ..., можно воспользоваться методом регуляризации Тихонова (см. [1]). Пусть n(u), u е Е", -сильно выпуклая, дифференцируемая функция, причем n'(u), u е U, удовлетворяет условию Липшица. Обозначим через = infП(u), u** е U*, П-нормальное решение: n(u**) = П** =
n
Е
= inf П(u), и введем для (1.1) регуляризующие задачи
и *
TN(u) = J(u) + aNn(u) —► inf, u е U, N = 1, 2,..., (1.5)
где aN> 0, N = 1, 2, ..., aN —» 0, N —► Для этих задач определим последовательность uNе U, N = 1, 2, ..., удовлетворяющую аналогичным соответственно (1.3) и (1.3)' условиям
\\un - w°|| ^ £n, wN = Pu(Un - TN(Un)), (1.6)
0 ^ < TN(Un), Un - wN> ^ £2n, 1 , (1.6)' < Tn(un), Wn - un) = min < Tn(un), v - un) , N = 1, 2,. .
v е U
Для этой последовательности имеют место следующие утверждения о сходимости к решениям задачи (1.1) (см. [10]).
Теорема 2. Для последовательности uN е U, N = 1, 2, ..., удовлетворяющей в задачах (1.5) условиям (1.6) или (1.6)', при £n/aN —- 0, N —► имеет место сходимость
\\uN- u**|| —► 0, N —► <~,
и справедливы следующие оценки по функционалу:
UnП* ^ T* - J* ^ aNП(u*), T* = infTN(u),
U
1/2
aNn* ^ Tn(Un) - J* ^ aNn(u*) + Cx(zn/an) ,
0 ^ J(un) - J* ^ aN[П(u*) - П* ] + C (£n/aN)1/2,
где u* - произвольный элемент из U*, а константа C1 = Cj(u*) не зависит от N.
2. РЕГУЛЯРИЗОВАННЫЙ ДВОЙСТВЕННЫЙ МЕТОД
Для задачи (1.1), (1.2) рассмотрим метод, связанный с решением задач, двойственных к исходным регуляризованным, где в качестве регуляризующей функции берется сумма функций, задающих ограничения g (u) = Хг"= j g( u), u е Е". На каждой итерации метода регуляризации в двойственной задаче определим критерий останова и докажем сходимость метода. Для этого опреде-
лим регулярную функцию Лагранжа
m
L (u,X) = J( u) + ^X1g1( u), u e E", 1еЛ = [X, ^ 0, i e I}, (2.1)
i = 1
и двойственную задачу
X(X) = infL(u, X) —- sup, X e Л. (2.2)
n
E
Пусть X* = supx(X), Л* = {X e Л: x(X) = X*} - ее решения, Л0 = {X: X, > 0, i e I}, Лх = {X e Л: x(X) >
Xe Л
> --}, {X} = min(1, Xx,..., Xm).
Введем функцию S(u) = J(u) + g (u), u e E". При строгой равномерной выпуклости этой функции S(u), u e E", с модулем строгой выпуклости ц(-) функция L(u, X) при фиксированном X e Л0 строго равномерно выпукла на E" с модулем выпуклости {X}^(0 и достигает нижней грани VX e Л0,
т.е. Л0 с Лх. Поэтому можно определить отображение u(X): Л0 —► E", где u(X) - единственный элемент такой, что x(X) = L(u(X), X), X e Л0. Нахождение u(X), X e Л0, во многих случаях является более простой задачей. В частности, при квадратичности функций J(u), g,(u), i e I, элементы u(X) -
решения линейных задач: L'u (u, X) = 0, u e E". Пусть J(X) = J(u(X)), g(X) = g(u(X)) = (gx(u(X)), ..., gm(u(X))), X e Л0. Отметим (см., например, [9]) следующее:
1) множество Лх выпукло, а x(X), X e Лх, вогнута, полунепрерывна сверху, причем непрерывна во внутренних (в относительной топологии множества Л) точках Лх;
2) если множество Лебега MC = {X e Лх: x(X) > C}, C e R, непусто, то оно выпукло, замкнуто и ограничено;
3) отображение u(X): Л0 —► V и функции g(X), J(X), X e
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.