ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 4, с. 602-625
УДК 519.626.2
РЕГУЛЯРИЗАЦИЯ В ЛИНЕЙНО-ВЫПУКЛОЙ ЗАДАЧЕ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
НА ОСНОВЕ ТЕОРИИ ДВОЙСТВЕННОСТИ1^
© 2007 г. М. И. Сумин
(603950 Нижний Новгород, пр-т Гагарина, 23, Нижегородский „ос. ун-т, механ.-матем. ф-т)
e-mail: m.sumin@mm.unn.ru; msumin@sinn.ru Поступила в редакцию 08.11.2006 г.
Конструируется устойчивый к ошибкам исходных данных алгоритм двойственного типа для решения линейно выпуклой задачи математического программирования (МП) с ограничениями типа равенства и неравенства в гильбертовом пространстве. Он заключается в непосредственном решении на основе регуляризации по Тихонову задачи, являющейся двойственной к исходной оптимизационной задаче. Показывается, что процесс двойственной регуляризации параллельно с конструктивным порождением минимизирующей последовательности приводит естественным путем и к получению необходимых условий оптимальности в исходной задаче МП. Рассматривается итеративная регуляризация предлагаемого двойственного алгоритма. Приводится правило останова итерационного процесса в случае конечной фиксированной ошибки задания исходных данных. Библ. 27.
Ключевые слова: математическое программирование, линейно выпуклая задача, двойственность, регуляризующий алгоритм, двойственная итеративная регуляризация, правило останова.
ВВЕДЕНИЕ
Вопросам регуляризации в задачах оптимизации и оптимального управления посвящены многочисленные работы (см., например, монографию [1] и библиографию к ней). Регуляризованные аналоги классических алгоритмов решения задач оптимизации и оптимального управления рассматривались в различных публикациях у нас в стране и за рубежом. Прежде всего это относится к методам проекции градиента, условного градиента, штрафных функций, а также к ряду других классических алгоритмов. При этом относительно небольшое число работ было посвящено вопросам регуляризации оптимизационных алгоритмов двойственного типа (см. [2]-[6]).
В то же время, хорошо известно, что двойственные численные алгоритмы являются одними из самых популярных и эффективных при решении оптимизационных задач с ограничениями (см. [1], [7]). По этой причине представляется естественным ожидать, что развитие методов регуляризации на основе теории двойственности позволит дополнить существующие методы регуляризации оптимизационных задач (см., например, [1]) эффективными методами, в которых самым существенным и непосредственным образом используется классическая идея "снятия" ограничений, заложенная в принципе Лагранжа. Одновременно развитие этих методов расширяет возможности использования хорошо известных преимуществ алгоритмов на основе теории двойственности при решении конкретных прикладных оптимизационных задач, увеличивая тем самым вероятность их эффективного решения.
Типичным представителем классических двойственных алгоритмов оптимизации является предложенный в 1958 г. так называемый алгоритм Удзавы (см. [7]-[9]), заключающийся в непосредственном решении на основе градиентного метода задачи, двойственной к исходной оптимизационной задаче. Этот алгоритм широко используется при решении различных прикладных задач (см., в частности, [10], [11]), вопросы его сходимости рассматривались, например, в [10]-[12].
Рассмотрим для иллюстрации простейшую линейно выпуклую задачу МП в гильбертовом пространстве
fz) —► min, Az = h, z e Э с Z, (1)
Работа выполнена при финансовой поддержке РФФИ (код проекта 04-01-00460).
гдеf: Z —»- [ - сильно выпуклый функционал, A : Z —► H - линейный непрерывный оператор, h е H - фиксированный элемент, Э - выпуклое замкнутое множество, Z, H - гильберовы пространства. Пусть решение задачи (1) существует. Обозначим это единственное решение через z0.
В зависимости от конкретного вида исходных данных задачи (1) она может иметь смысл обратной задачи (см. [4]), уравнения I рода в гильбертовом пространстве (см. [5]) или задачи оптимального управления (см. [6]).
Напомним, что классический двойственный алгоритм Удзавы применительно к решению задачи (1) представляет собой итерационную процедуру
Ak+1 = Ак + ßk(Azk - h), zk = argmin{L(z,Ak), z е Э }, k = 1, 2,..., А1 е H,
L (z,A)= f( z) + (А, Az - h>.
При некоторых достаточно сильных предположениях он сходится одновременно по двойственной и прямой переменным и выполняются предельные соотношения
||Ак- А0|| — 0, ||zk - z0|| —- 0, k —- -где А0 - решение двойственной задачи
minL(z, L) —- max, А е H.
z е Э
Однако соответствующие теоремы сходимости, которые можно найти, например, в [10, Гл. VII, с. 191], [11, Гл. 2, п. 4], содержат два существенных предположения: 1) исходные данные задачи предполагаются заданными точно; 2) функция Лагранжа задачи должна иметь седловую точку. Вместе с тем, оба эти предположения являются весьма ограничительными так как, во-первых, для практических задач характерным является именно наличие ошибки в задании их исходных данных и, во-вторых, для таких задач, как правило, само доказательство существования или не существования седловой точки представляет собой нелегкую математическую задачу. Формальное же применение алгоритма в общей ситуации может привести и приводит к стандартным эффектам неустойчивости приближенного решения. Так уже в рассматриваемом относительно "простом" случае линейно выпуклой задачи (1) с сильно выпуклым функционалом классический двойственный алгоритм оказывается во многих ситуациях малоэффективным из-за его неустойчивости по возмущению исходных данных (см. ниже пример 1) и из-за не существования седло-вой точки функционала Лагранжа или, другими словами, из-за не существования решения двойственной задачи (примеры 2, 3).
Рассмотрим три конкретных примера, иллюстрирующих существенность этих предположений. Каждый из них является частным случаем абстрактной простейшей задачи МП (1).
Пример 1. Пусть имеется задача минимизации сильно выпуклой квадратичной функции двух переменных на множестве, задаваемом аффинным ограничением типа равенства, эквивалентная задаче поиска нормального решения линейной алгебраической системы двух уравнений с двумя неизвестными
I 12 X -
/ \ / \
1 1 1
= , У =
V 00 , V 0 ,
(2)
точное нормальное решение которой равно х* = (0, 5; 0, 5). Двойственная к (2) задача имеет вид К(А) = L(х(А), А) = -4<АА*А, А) - <у,А>^ max, Ае [2,
2 1
где L(x, А) = |х|2 + <А, Ах - у), х(А) = argmin{L(x, А), х е [ } = - 2 А*А. Ее решением является вектор (-1, a) Va е [R1. Рассмотрим возмущенную задачу (2) при 5 > 0
|х|2—«-min, A5 x = y5, x е [2, AS =
/ л
1 1
V 0 62 y
8
, y =
v8y
2
Соответствующая двойственная задача
V5(X) = Ls(x5(X), X) ^ max, X е U2,
имеет решение Xs = ^2-5~5 , 2^3 4 j и при этом вектор x5(X5) = argmin{L5(x, Xs), x е U2} = ^ 1 - g, 1 j
есть, в соответствии с классическим двойственным алгоритмом Удзавы, "приближенное" решение исходной задачи (2), которое при 5 —► 0 не сходится к ее единственному точному решению.
Видно как ошибка в задании исходных данных оптимизационной задачи влияет на сходимость классического алгоритма. Заметим одновременно, что седловая точка функционала Лагранжа исходной задачи в этом примере имеется.
Естественно, в случае когда в исходной задаче отсутствует седловая точка, то все классические теоремы сходимости (см. [10], [11]) теряют смысл, так как в них во всех предполагается одновременная сходимость по прямой и двойственной переменным. Приведем два примера таких задач, в которых для функционала Лагранжа справедливо равенство
sup inf L(z, X) = sup inf L(z, X),
Хе Hz е Э z е Э Хе H
но внешний экстремум в левой части не достигается. Пример 2. Рассмотрим задачу минимизации
b
||z||2—»min, A(z)(x) = JK(x, s)z(s)ds = q(x), a < x < b, z е L2(a, b), q е L2(a, b), (3)
a
эквивалентную задаче поиска нормального решения интегрального уравнения Фредгольма I рода с правой частью q е L2(a, b)
b
A(z)(x) = J"K(x, s)z(s)ds = q(x), a < x < b, (4)
a
с симметрическим непрерывным на квадрате П = [a, b] х [a, b] ядром K. Пусть ядро этого уравнения является замкнутым.
Пусть далее z0 е L2(a, b) - функция, не являющаяся непрерывной (т.е. соответствующий класс эквивалентности не содержит непрерывной функции), q0(x) = A(z0)(x), x е [a, b]. Тогда рассмотрим уравнение (4) с q(x) = q0(x), a < x < b, имеющее по причине замкнутости ядра единственное решение z0, и соответствующую эквивалентную задачу минимизации (3).
Покажем, что соответствующая ей двойственная задача
V(X) = - (1/4XAAX, X) - <q0, X) —»- max, Хе L2(a, b),
не имеет решения, т.е. верхняя грань двойственной целевой функции не достигается. Действительно, если бы максимальное значение двойственной целевой функции достигалось в некоторой точке X е L2(a, b), то эта точка удовлетворяла бы равенству -(1/2)AAX = q0. Но тогда, согласно упомянутой выше замкнутости ядра, мы должны были бы иметь и равенство -(1/2)AX = z0. Последнее же равенство противоречиво, так как z0 - функция, не являющаяся непрерывной, в то время как AX - непрерывная функция (ядро K непрерывно). Последними рассуждениями, по сути дела, доказано также, что в задаче минимизации (3), эквивалентной исходному уравнению при q = q0, принцип Лагранжа не выполняется.
Пример 3. Рассмотрим обратную задачу наблюдения, в которой требуется найти начальное условие v(x), x е (0, 1), по известному в финальный момент времени T решению z[v](-, T) = q е е L2(0, 1) третьей краевой задачи для уравнения теплопроводности
дz/дt - Э2z/dx2 = 0, z(x, 0) = v(x), x е (0, 1), 3z(0, t)/Э x - z (0, t) = 0, dz (1, t)/Э x + z (1, t) = 0, t е [0, T], v(x) е V =[-1, 1 ].
Эквивалентная задача минимизации имеет здесь вид
1
J V2 (X) dx — inf, z [ v ](T) = q, v е Э = { v е L2( 0, 1) : v (x )е[ -1, 1 ] п.в. на (0, 1)}. (5)
0
Определим инъективный оператор I : L2(0, 1) —L2(0, 1) формулой I[v](-) = z[v](-, T) (инъек-тивность может быть установлена, например, на основе результатов [13], [14]) и сопряженный I* : L2(0, 1) —- L2(0, 1) формулой I*[p](-) = nlpK', 0),p е L2(0, 1), где n[p] - решение сопряженной задачи
Эп/Эt + Э2п/ЭX2 = 0, n(X, 1) = p(X), X е
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.