ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 5, с. 796-816
УДК 519.626.2
РЕГУЛЯРИЗОВАННЫЙ ДВОЙСТВЕННЫЙ МЕТОД РЕШЕНИЯ НЕЛИНЕЙНОЙ ЗАДАЧИ МАТЕМАТИЧЕСКОГО
ПРОГРАММИРОВАНИЯ1-*
© 2007 г. М. И. Сумин
(603950 Нижний Новгород, пр-т Гагарина, 23, Нижегородский „ос. ун-т, механ.-матем. ф-т)
e-mail: m.sumin@mm.unn.ru; msumin@sinn.ru Поступила в редакцию 24.11.2006 г.
Конструируется устойчивый к ошибкам исходных данных алгоритм двойственного типа для решения нелинейной задачи математического программирования с ограничениями типа равенства в гильбертовом пространстве. Он заключается в непосредственном решении на основе регуляризации по Тихонову задачи, являющейся модифицированной двойственной к исходной задаче математического программирования и предназначен для нахождения ограниченной по норме минимизирующей последовательности допустимых элементов. Рассматривается итеративная регуляризация предлагаемого двойственного алгоритма. Приводится правило останова итерационного процесса в случае конечной фиксированной ошибки задания исходных данных. Библ. 21.
Ключевые слова: нелинейное математическое программирование, двойственность, регуля-ризующий алгоритм, двойственная итеративная регуляризация, правило останова.
введение
Вопросам регуляризации в задачах оптимизации и оптимального управления посвящены многочисленные работы (см., например, монографию [1] и библиографию к ней). Однако среди всего многообразия работ этого направления относительно небольшое число работ было посвящено вопросам регуляризации оптимизационных алгоритмов с использованием теории двойственности (см. [2]-[6]).
В то же время, представляется, что развитие методов регуляризации на основе теории двойственности позволяет дополнить существующие методы регуляризации оптимизационных задач (см., например, [1]) эффективными методами, в которых самым существенным образом используется классическая идея "снятия" ограничений, заложенная в принципе Лагранжа. Известно, что двойственные численные алгоритмы являются одними из самых эффективных для решения оптимизационных задач с ограничениями (см. [1], [7]). Их типичным представителем является предложенный в 1958 году классический алгоритм Удзавы (см., например, [7]-[9]), заключающийся в непосредственном решении на основе градиентной процедуры задачи, двойственной к исходной оптимизационной задаче. Применительно к задаче математического программирования
Iо(2) — ш£, 11 (2) = 0, г е Э, (Р)
в которой Э с 2 - замкнутое множество, 10: 2 —► К1 - функционал, Д: 2 —► Н - оператор, 2, Н -гильбертовы пространства, указанный двойственный алгоритм представляет собой итерационную процедуру
Хк + 1 = Хк + вк1\(,2к), 2к = 2[Хк] = а^шш{Ь(2,Хк), 2 е Э}, к = 1, 2,..., X1 е Н,
Ь(2, Х)= Iо(2) + а II (2)> .
Здесь вк - шаговый множитель и подразумевается сходимость как по двойственной переменной X, так и по основной переменной 2, причем при определенных условиях элементы Хк, 2к стремятся, соответственно, к решениям двойственной и исходной задач
г, к г* 0 к 0 7
X -► X , 2 -► 2 , к -► го,
1) Работа выполнена при финансовой поддержке РФФИ (код проекта 04-01-00460).
X0 = argmax{minL(z, X), Xe H}, z° = argmin{I0(z), I1 (z) = 0, z e a }.
z e a
Этот алгоритм широко используется при решении различных прикладных задач (см. [10], [11]). В то же время, вопросы его сходимости (см., например, [10]-[12]) изучались ранее лишь при двух весьма ограничительных обстоятельствах, одно из которых заключается в предположении точного задания исходных данных оптимизационной задачи, а другое предполагает наличие седло-вой точки соответствующего функционала Лагранжа (см., в частности, [10], [11]). Оба этих предположения являются весьма ограничительными, так как, во-первых, в реальных практических задачах характерным является наличие ошибки в задании их исходных данных и, во-вторых, как правило, в таких задачах невозможно заранее установить факт наличия указанной седловой точки. Формальное же применение алгоритма в его классической форме может приводить и приводит к стандартным эффектам неустойчивости приближенного решения. Простейший пример такой неустойчивости, связанный с задачей минимизации сильно выпуклой квадратичной функции двух переменных на множестве, задаваемом аффинным ограничением типа равенства, эквивалентной задаче поиска нормального решения линейной алгебраической системы двух уравнений с двумя неизвестными можно найти в [6], [13], [14]. Естественно, в случае когда в исходной задаче отсутствует седловая точка, то все классические теоремы сходимости (см. [10], [11]) теряют смысл, так как в них предполагается одновременная сходимость по прямой и двойственной переменным. Примеры линейно выпуклых задач вида (P) с сильно выпуклыми целевыми функционалами, в которых для функционала Лагранжа L(z, X) задачи (P) справедливо равенство
sup inf L(z, X) = inf sup L(z, X),
Xe Hze a ze aXe H
но внешний экстремум в левой части не достигается, могут быть найдены в [4], [5], [14].
В работах [3]-[6], [13], [14] был предложен регуляризованный вариант двойственного алгоритма или, другими словами, алгоритм двойственной регуляризации для линейно выпуклых задач оптимизации в гильбертовом пространстве с сильно выпуклым целевым функционалом. Двойственная регуляризация [3]-[6], [13], [14] для задачи минимизации вида (P) заключается в непосредственном решении возмущенной двойственной к (P) и регуляризованной по Тихонову задачи
V5(X) - a||X||2 —- sup, X e H, V5(X) = inf (I05(z) + <X, lf(z)»
ze a
при согласовании с параметром регуляризации а стремления к нулю ошибки задания исходных данных 5 и конструктивном построении при этом минимизирующей и сходящейся по аргументу в задаче (P) последовательности. В зависимости от конкретного вида задачи (P) она может иметь смысл уравнения I рода в гильбертовом пространстве [4], обратной задачи [5] или задачи оптимального управления [6]. Отличительной особенностью алгоритма двойственной регуляризации, по сравнению с классическим аналогом [7]-[9], является то, что он сохраняет работоспособность как при наличии ошибки задания исходных данных, так и в отсутствие седловой точки функционала Лагранжа оптимизационной задачи. При этом в последнем случае алгоритм приводит, вообще говоря, к сходимости приближенных решений zk, k = 1, 2, ..., к точному решению z0 с одновременным стремлением к бесконечности норм двойственной переменной ||Xk ||. Одновременно был рассмотрен и соответствующий итеративный вариант двойственного алгоритма [4]-[6], [14] с правилом останова при фиксированном конечном уровне ошибки исходных данных [6], [14].
В данной работе регуляризованный двойственный алгоритм [3]-[6], [13], [14] обобщается на случай нелинейной задачи математического программирования в гильбертовом пространстве с
ограничениями типа равенства для случая H = Ее основной целью является обоснование алгоритма конструирования в задаче (P) ограниченной по норме минимизирующей последовательности. В качестве нижней грани в задаче (P), к которой и стремятся значения минимизируемого функционала, здесь также используется обобщенная нижняя грань
ß = ß+0 = lim ߣ, ߣ = inf I0(z), ߣ = , если a£ = 0, a£ = {z e a: I(z)| < e}, e > 0,
£ze a£
и, соответственно, в качестве минимизирующей последовательности используется так называемое минимизирующее приближенное решение в смысле Дж. Варги (см. [15]). Использование понятия минимизирующего приближенного решения (МПР) при конструировании численных алгоритмов
вместо более привычного классического понятия минимизирующей последовательности представляется разумным по следующим трем основным причинам. 1. Оно предпочтительнее с практической (инженерной) точки зрения, так как элементам минимизирующего приближения решения "разрешается" не удовлетворять ограничениям задачи в точном смысле (иметь допуск по ограничениям) и выполнение ограничений предполагается лишь "в пределе". 2. Всегда справедливо неравенство в < в0, где в0 - классическая нижняя грань, причем во многих важных с прикладной точки зрения задачах это неравенство выполняется и в строгом смысле. 3. По сути дела, именно оно является центральным и существенно используется в теории численных методов оптимизации. Указанные моменты позволяют высказать утверждение общего характера, состоящее в том, что понятия минимизирующего приближенного решения и неклассической нижней грани в являются в теории алгоритмов оптимизации более адекватными с прикладной точки зрения по сравнению с их привычными классическими аналогами.
В алгоритме двойственной регуляризации [4]-[6], [13], [14] основной конструкцией является классический функционал Лагранжа L(z, X) задачи (P). Однако, уже при формальном перенесении конструкций двойственной регуляризации в случае линейно выпуклой задачи (P) с сильно выпуклым целевым функционалом на случай "той же задачи" лишь с выпуклым функционалом цели возникают существенные проблемы, связанные с отсутствием "нужных" свойств непрерывности элементов z[X] от X и, как следствие, недифференцируемостью в классическом смысле целевого функционала V(X) двойственной задачи.
В отличие от линейно выпуклого случая [4]-[6], [13], [14] с целью преодоления указанных сложностей в данной работе вместо классического функционала Лагранжа применяется конструкция его модифицированного аналога
10 (z) + <X, Ii (z )> + с (I Ii (z )| + I (z )| 2 ), с > 0.
Соответственно, под двойственной задачей мы подразумеваем модифицированную двойственную задачу
VC(X) —- sup, X е Лс = {X е [m: |X| < с}с [m, VC(X) = inf (Io(z) + <X, Ii(z)> + с(|11(z)| + |Ii(z)|2), с > 0.
z е Э
Процесс конструирования минимизирующей последовательности в данной работе может проходить двояким образом в зависимости от того существует или нет вектор Куна-Таккера в
исходной задаче. При этом под вектором Куна-Таккера понимается вектор X е [m, для которого выполняется неравенство в < L(z, X) Vz е Э.
Если вектор Куна-Таккера в этом обобщенном смысле существует, то для любого с > 0 супердифференциал dV^X) в любой точке X е [m, являющейся вектором Куна-Таккера (в которой вогнутая, в
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.