ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 6, с. 947-977
УДК 519.626
УСТОЙЧИВАЯ СЕКВЕНЦИАЛЬНАЯ ТЕОРЕМА КУНА-ТАККЕРА В ИТЕРАЦИОННОЙ ФОРМЕ ИЛИ РЕГУЛЯРИЗОВАННЫЙ АЛГОРИТМ УДЗАВЫ В РЕГУЛЯРНОЙ ЗАДАЧЕ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ1
© 2015 г. М. И. Сумин
(603950Нижний Новгород, пр-т Гагарина, 23, Нижегородский гос. ун-т, механ.-матем. ф-т)
e-mail: m.sumin@mm.unn.ru Поступила в редакцию 19.09.2014 г.
Изучается параметрическая задача нелинейного программирования в метрическом пространстве с операторным ограничением-равенством в гильбертовом пространстве в предположении, что ее полунепрерывная снизу функция значений при выбранном индивидуальном значении параметра обладает определенными свойствами субдифференцируемости в смысле нелинейного (негладкого) анализа. Такая субдифференцируемость может пониматься как в смысле существования проксимального субградиента, так и в смысле существования субдифференциала Фреше. Другими словами, индивидуальная задача обладает соответствующим обобщенным вектором Куна—Таккера. В этом предположении в терминах минимизирующих последовательностей на основе метода двойственной регуляризации доказывается и обсуждается так называемая устойчивая секвенциальная теорема Куна—Таккера в недифференциальной итерационной форме, представляющая собой необходимые и достаточные условия устойчивого конструирования минимизирующего приближенного решения в смысле Дж. Варги в рассматриваемой задаче, исходные данные которой могут быть известны лишь приближенно. Существенным отличием доказываемой теоремы от ее классического одноименного аналога является то, что она учитывает возможную неустойчивость задачи при возмущении исходных данных и, как следствие, наследуемую неустойчивость классических условий оптимальности. Доказываемую теорему можно трактовать как регуляризованное обобщение на случай задачи нелинейного программирования классического алгоритма Удза-вы. В заключение рассматривается приложение доказываемой теоремы в "простейшей" нелинейной задаче оптимального управления, а именно, в задаче оптимального быстродействия. Библ. 29.
Ключевые слова: нелинейное программирование, параметрическая задача, метод возмущений, устойчивость, секвенциальная оптимизация, минимизирующая последовательность, двойственность, регуляризация, принцип Лагранжа, теорема Куна—Таккера в недифференциальной форме, принцип максимума Понтрягина.
БО1: 10.7868/80044466915060137
ВВЕДЕНИЕ
При изучении вопросов, связанных с теорией условий оптимальности в задачах оптимизации, в частности, в задачах математического программирования и оптимального управления, возможны два естественных подхода. В рамках первого из них оптимизационные задачи рассматриваются при фиксированных точных исходных данных. Усилиями многолетних исследований огромного числа авторов в рамках этого подхода была создана и получила фундаментальное развитие классическая теория необходимых и достаточных условий оптимальности, как в конечномерных, так и в бесконечномерных оптимизационных задачах. Наиболее известные и продвинутые результаты в ней связаны, в первую очередь, с принципом Лагранжа, теоремой Куна-Такке-
Работа выполнена при финансовой поддержке РФФИ (коды проектов 12-01-00199-а, 13-07-97028-р_поволжье_а, 13-02-12155-офи_м), Минобрнауки РФ в рамках проектной части государственного задания в сфере научной деятельности в 2014-2016 гг. (код проекта 1727), а также при поддержке гранта в рамках соглашения от 27 августа 2013 г. № 02.В.49.21.0003 между Минобрнауки РФ и Нижегородским госуниверситетом им. Н.И. Лобачевского.
947
3*
ра, принципом максимума Понтрягина (см., например, [1], [2]). В свою очередь, второй подход подразумевает, что исходные данные оптимизационной задачи могут быть известны лишь приближенно, т.е. задаваться с ошибкой, которая может быть как конечной фиксированной, так и в идеале, бесконечно малой, стремиться к нулю. Естественная потребность изучения задач в подобных ситуациях неизбежно появляется, когда мы сталкиваемся с необходимостью решать те или иные практические оптимизационные задачи. Возникающая здесь при получении соответствующих аналогов классических условий оптимальности принципиальная сложность обусловлена, в первую очередь, неустойчивостью самих оптимизационных задач. Эта неустойчивость, естественно, наследуется и соответствующими классическими условиями оптимальности в том смысле, что выделяемые ими формально оптимальные элементы в возмущенных задачах могут быть сколь угодно далеки как по аргументу, так и по функции от исходных оптимальных элементов невозмущенной задачи при сколь угодно малых возмущениях самих задач. Это проявляется уже в полной мере в самых простых по виду выпуклых конечномерных и бесконечномерных задачах. По этой причине в условиях неточного задания исходных данных оптимизационных задач формальное применение классических условий оптимальности может привести и приводит к результатам, имеющим "мало общего" с исходной невозмущенной задачей. Проиллюстрируем сказанное двумя "простейшими" примерами.
Пример 0.1. Пусть имеется задача минимизации сильно выпуклой квадратичной функции двух переменных на множестве, задаваемом аффинным ограничением типа равенства
2 2
x1 + x2—» min, x1 + x2 = 1, 0x1 + 0x2 = 0, x = (xb x2)e 3, (0.1)
с 3 = {x e R2 : 0 < x1 < 1, 0 < x2 < 1}, точное решение которой равно x* = (1/2, 1/2). В силу простоты задачи (0.1) можно непосредственно установить, что вектор Ха = (X^ а, X2, а) = (—1, а) Va e R1 является ее вектором Куна—Таккера. Следовательно, в соответствии с классической теоремой Ку-на—Таккера (см., например, [1], [2]), любая пара (х*,Ха) указанного вида, и никакая другая, состоит одновременно из решений исходной задачи (0.1) и двойственной к ней. Рассмотрим далее возмущенную задачу (0.1) при 5 > 0
x\ + x2—► min, x1 + x2 = 1, 5x2 = 52, (x1, x2)e 3.
Очевидно, ее единственная допустимая точка x5 = (x^, x\) = (1 — 5, 5) является и ее решением. Как показано при анализе этого примера в [3] (пример 0.1), указанная возмущенная задача обладает вектором Куна—Таккера (единственным) X5 = (^ , Х2) = ^25 - 2, -2 ( 2^—^ . Другими словами, пара (х5, X5) является в соответствии с классической теоремой Куна—Таккера единственной парой, состоящей одновременно из решений возмущенной задачи и двойственной к ней. Итак, с одной, формальной стороны, точка x5 "претендует" на то, чтобы называться приближением к решению исходной задачи (0.1). С другой же стороны, она не сходится к ее единственному точному решению х* = (1/2, 1/2) при 5 —► 0. При этом зависящие от 5 значения задачи терпят разрыв I рода при 5 = 0. Заметим одновременно, что в силу вырожденности двумерной системы, задающей ограничение-равенство в задаче (0.1), очевидно, в любой "окрестности" последней существуют возмущенные задачи с пустым множеством допустимых элементов и, стало быть, со значением +да.
Естественно, имеются и "совсем простые" по виду задачи выпуклого программирования с бесконечномерными ограничениями, в которых наблюдаются эффекты неустойчивости, подобные рассмотренным в предыдущем примере. Более того, в таких бесконечномерных задачах могут быть и дополнительные неприятности, связанные с тем, что в них ни классический принцип Лагранжа, ни классическая теорема Куна—Таккера и вовсе не могут быть применены из-за того, что их утверждения не верны в таких задачах (см. пример 02 в [3]). Одним из "простейших" содержательных примеров в этом случае является постоянно встречающаяся в различных физических приложениях задача нахождения на некотором множестве, задаваемом априорными ограничениями, нормального решения линейного операторного уравнения I рода, частными случаями которого служат интегральные уравнения Вольтерра и Фредгольма I рода.
Пример 0.2. Рассмотрим задачу минимизации сильно выпуклого функционала с операторным ограничением типа равенства
\\z\\2— min, Az = p, z e 3, (0.2)
с выпуклым замкнутым ограниченным множеством Э с Z, Z — гильбертово пространство, с линейными вполненепрерывными инъективными операторами A, А* : Z—- Z, такими, что R(A) = Z,
R (A * ) = Z. В этом случае, как известно из бесконечномерного выпуклого анализа (см., например, [5], [6]), плотным в domß, где ß : Z—► R1 u {+да} — выпуклая полунепрерывная снизу функция значений задачи (0.2), как функция параметрар е Z, является множество точекр с dß(p) Ф 0, dß(p) — субдифференциал в смысле выпуклого анализа. Для каждой задачи (0.2) ср из этого множества существует вектор Куна—Таккера, в качестве которого можно взять любой элемент из dß(p) (см. классический параметрический принцип Лагранжа в [3], [4]). Однако, как можно показать (см. анализ примера 0.4 в [3]), вообще говоря, для каждой задачи (0.2) с указаннымр можно указать такую последовательность точекpk, к = 1, 2, ...,рк —«- р, к —»- да, для каждой из которых в соответствующей задаче (0.2) с р = рк субдифференциал dß(pk) Ф 0 и, стало быть, в ней можно применить классическую теорему Куна—Таккера. При этом решения задач (0.2) прир = pk не сходятся к решению исходной задачи (0.2) при к —» да и, к тому же, последовательность значений ß^k), к = 1, 2, ., оставаясь ограниченной, не сходится при к —»- да к ß(^). Как и при анализе
предыдущего примера, заметим одновременно, что в силу свойств R(A) Ф Z, R (A ) = Z, задающего ограничение задачи оператора А, очевидно, в любой "окрестности" последней существуют возмущенные задачи с пустым множеством допустимых элементов и, стало быть, со значением +да.
Обе рассмотренные выше в примерах задачи можно записать в общем виде в форме
f(z) —- min, g(z) = p, p е Э,
где Z — гильбертово пространство, f : Z—R1 — сильно выпуклый функционал, g : Z—► Z — линейный ограниченный оператор такой, что g(Z) Ф Z, Э — выпуклое замкнутое множество. Тогда ситуации, возникающие в обоих этих примерах и являющиеся характерными для огромного числа содержательных оптимизационных задач, можно описать в терминах множества достижимости g^) задачи общего вида: для любой граничной точки множества достижимости в задаче с ограничением g(z) = р, р е ôg(S), в любой ее "окрестности" с
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.