Введение к работе
^сйртгАК'туальность проблемы. Методы оптимизации в настоящее
я**"
фемя стали мощным средством решения прикладных оптимизационных іадач. Сфера приложений этих методов огромна. Прежде всего это шономика, технология, экология, проектирование сложных систем і многое другое. Однако растущие запросы практики выдвигают на іервьій план проблему численного решения не одной задачи оптини-іации, а их систену, т.е. семейство связанных между собой задач. 1 качестве примеров можно указать задачи о вычислении седловых ючек, равновесные и игровые задачи, а также системы вариационных неравенств. Не всё из арсенала методов оптимизации может іьіть использовано для решения сложных систем задач оптимизации, 'ак например, хорошо известные методы оптимизации, построенные іа идеях линейной и квадратичной аппроксимации (градиентные, іьютоновские и др.),не сходятся к седловыы точкам выпукло-вогну-'ых вырожденных функций и тем более они не сходятся к равнове-:ию по Нэшу в простейших играх с ненулевой сумной.
Для решения сложных оптимизационных систем предлагается юдход, который основан на идее управления вычислительными провесами с помощью обратных связей. Вычислительный метод в этом юдходе трактуется как управляемый динамический процесс, :оторый описывается с использованием системы дифференциальных їли итеративных уравнений градиентного и проксимального (регу-іяризационного) типа. В связи с этим рассматривается задача: в іекотором классе обратных связей необходимо выбрать управление как функцию состояния динамической системы), которое обеспечи-ю бы сходимость траектории к равновесию сложной системы. Дру-'ими словами, необходимо синтезировать алгоритм управления, с юмощыо которого траектория динамической системы переводится из іроизвольного начального состояния в равновесное (оптимальное).
Перейдем к описанию трех классов задач, которые рассматри-іаются в работе.
I. Задача выпуклого программирования. Требуется определить іектор I , доставляющий оптимум целевой функции 1(1) на юпустимом множестве:
і*єАгзшМ(х): ?(i)<0, ieQ}. (1)
Іектор I и выпуклое множество Q принадлежат конечномерному івклидову пространству, целевая функция |(l) и каждая компо-
нента векторной функции 9(1) - выпуклые скалярные функции.
2. Задача о седловых точках. Смысл этой задачи состоит
поиске (вычислении) для выпукло-вогнутых функций какой-либо
седловой точки, удовлетворяющей системе неравенств
1(х\р) < Ї.(І*,Р") <. 1<1,р") для всех ХЄО и Р> 0. Важный примером таких функций является функция Лагранжа задачи выпуклого программирования.Сформулир задачу о вычислении седловых точек функции Лагранжа в форме:
i,',p,,eSdunLn{?(i): ^9(1) < 0, ieQ). Здесь выражение SdMn{ І обозначает все множество сед вых точек функции Лагранжа (Х,р) = f(Х)+<р,9(Х)>. Символ SdtmLni* } обобщает известное выражение Azgmlni' } Решение задача (2) эквивалентно решению вышеприведенной сист неравенств.
3. Обратная задача выпуклого программирования. В этой
задаче требуется определить решение X ,U , удовлетворяю
щее системе, содержащей экстремальное включение и неравенств
x*eAz9fflLn{f(x,u"): 9(x,u*)<0, хєО}, u*eU, G(x*,u*) < 0,
т.е. в задаче параметрического выпуклого программирования требуется выбрать параметр (управление) U=U и отвечающий ем: оптимум, такой, чтобы выполнялась система неравенств G(X,U)< В случае сильной выпуклости целевой функции |(X,U) и линейно G(X,U) система (3) переходит в систему нелинейных уравнени
х* = а*9юіл{?(х,іГ): з(х,и*)<0, xeQ), iTeU, G»r* = GaM* а,
здесь U - также выпуклое замкнутое множество конечномерного эвклидова пространства. Размерности матриц Gj и Gj и переменных X,U согласованы так, что второе уравнение из (4) описывает непустое линейное многообразие для всех X и р.
Перечисленные задачи расположены по возрастающей трудної их решения. Соответственно этому перечислению классы задач иі ют различное алгоритыическое обеспечение. А именно, задача ві пуклого программирования имеет почти завершенную теорию методов поиска оптимума с огромным набором различных методов, доказательствами их сходимости и оценками скорости сходимості (Ф.П.Васильев, Ю.Г.Евтушенко, В.Г.Карманов, Б.Т.Поляк и др.) В этом классе задач целесообразно разрабатывать методы с новыми свойствами (например, свойствами допустимости).
Задача о поиске седловых точек имеет небольшой разроэнен-:ый набор подходов для ее решения. Это методы модифицирований функции Лагранжа (Б.Т.Поляк, Е.Г.Гольштейн, Н.В.Третьяков,
і.г.Евтушенко, R.T.RocKafB-Kaz, D.M.Beztaecaa и др.), методы,
снованные на идеях прогнозного шага (Г.М.Корпелевич) и итера-ивной регуляризации (Б.Т.Поляк, А.Б.Бакушинский,Ф.П.Васильев і др.). Общей концепции, теории или принципов построения ието-[ов вычисления седловых точек не существует, поэтому стоит зада-іа разработки такой концепции. В отличие от седловых задач, для іешения которых существуют итеративные процессы, сходящиеся к іешениям, для обратных задач оптимизации, напротив, такие не [звестны. Этот важный класс задач не имеет алгоритмической под-(ержки.
Проблема алгоритмического обеспечения перечисленных классов іадач является актуальной и особенно остро стоит она для двух юследних классов. Хорошо известно, что для описания больших ре-ільньїх систем (экономических, технологических, вычислительных) імеются адекватные игровые математические модели (именно к ітому классу моделей относятся задачи обратной оптимизации), но :фера их применения для решения прикладных задач резко ограни-іена, так как они не имеют алгоритмического обеспечения.Успешное і эффективное применение математических моделей для решения іажньїх народнохозяйственных задач в значительной степени зави-:ит от существования соответствующих методов их численного ана-іиза.
Цели и задачи работы. Основной целью диссертации является юзработка алгоритмической поддержки вышеперечисленных классов іадач. При этом решаются следующие задачи.
-
Разработка непрерывных и итеративных методов линейной и [вадратичной аппроксимации для решения задач выпуклого програми-ювания. Методы квадратичной аппроксимации имеют свойство допус-имости (внутренности).
-
Разработка единой теории (схемы) непрерывных и итера-ивных управляемых вычислительных методов поиска седловых точек іьшукло-вогнутьіх вырожденных функций.
-
Разработка методов решения обратных задач выпуклого ірограммирования.
Методы исследования. Основным инструментом исследования :лужит аппарат неравенств выпуклого анализа. Классическая сие-
теыа используемых неравенств дополнена новыми неравенствами, предложенными автором. Для обоснования предлагаемых методов разработана специальная техника доказательства сходимости непрерывных и итеративных вычислительных процессов. Научная новизна работы состоит в следующем.
-
Для задач выпуклого программирования разработан новый внутренний метод квадратичной аппроксимации, с помощью которого можно строить последовательности, лежащие строго внутри допустимой области. Получены оценки скорости сходимости. В отличие от методов внутренних штрафов вспомогательные задачи предложенного метода имеют невозрастающий объем вычислений на каждой итерации. В отличие от методов возможных направлений предложенный метод монотонно, по норме, сходится к оптимуму.
-
Для вычисления седловых точек функции Лагранжа задач выпуклого программирования предложена новая методология и развита соответствующая ей техника управления вычислительными процессами с помощью обратных связей. Для управления градиентными и проксимальными (проксимальный оператор является оператором регуляризации) непрерывными и итеративными процессами предложены различные (по невязке ограничений, по производной и их комбинациям) обратные связи, которые обеспечивают сходимость процессов к какой-либо седловой точке. Некоторым видам обратных связей отвечают новые итеративные процессы. Рассмотрены процессы первого и второго порядка.
-
Для обратных задач линейного и квадратичного программирования разработаны методы решения этих задач. Доказана их сходимость, тем самым предложен подход к решению проблемы алгоритмической поддержки этого важного класса игровых задач.
Практическая ценность работы связана с разработкой алгоритмического обеспечения задач выпуклого программирования, задач поиска седловых точек выпукло-вогнутых вырожденных функций и обратных задач выпуклой оптимизации.
Аппробация работы и публикации. Основные результаты диссертации докладывались на Международной конференции по методам математического программирования (Польша,Закопане,1977), Всесоюзном семинаре по оптимизации и ее приложениям (Душанбе,1986), IV-н Всесоюзном симпозиуме по методам решения нелинейных уравнений и задач оптимизации (Вильянди.1987), IV Международном симпозиуме "Автоматизация и научное приборостроение" (Болгария,
Іарна,І987), ІО-м Всесоюзной сиипозиуне по системам програимно-о обеспечения решения задач оптимального планирования (Нар-а,1988), VII-н семинаре ИФАК по приложениям в нелинейном прог-іанмировании и оптимизации (Тбилиси, 1988), Ш-й школе-семинаре Численные методы для высокопроизводительных систем" (Фрун-е,1988), Всесоюзной конференции по методам математического рограымирования и программного обеспечения (Свердловск,1989), 4-й Международной конференции ИФИП по системам моделирования и птимизации (Лейпциг,1989), а также на семинарах в ИПК АН СССР, НИИСИ, ВЦ АН СССР, факультете вычислительной математики и ки-ернетики МГУ. Аппробация диссертации в целом проведена на семи-аре ИПК АН СССР в 1990 г. По теме диссертации опубликована 21 збота (все без соавторов).
Структура и объем работы. Диссертация изложена на 231 границах машинописного текста и состоит из введения, четырех іав, заключения и списка литературы, содержащего 84 работы.
