Введение к работе
Актуальность темы. В последние десятилетия вопросы негладкого анализа и недифференцируемой оптимизации привлекают большое внимание ученых и инженеров. Негладкий анализ находит многочисленные применения в теоретической механике, теории упругости, экономике и многих других областях, но преимущественно там, где исследуются задачи экстремального характера. Поэтому в настоящее время особое внимание уделяется конструированию численных методов, позволяющих отыскивать решения подобных задач. Проблематикой негладкого анализа, в частности, развитием теоретической базы и построением численных методов, активно занимается большая группа отечественных и зарубежных математиков, среди которых Р.Габасов, В.Ф.Демьянов, Ю.Г.Евтушенко, Ю.М.Ермольев, А.Д.Иоффе, Ж.- Б. Ириа-Уррути, Ф. Кларк, Ф.М.Кириллова, Б.Ш.Мордухович, Ж.- П. Обен, Ж.-П. Пено, Б.Т.Поляк, Б.Н.Пшеничный, Р.Рокафеллар, A.M.Рубинов, В.М.Тихомиров, Х.Туй, Н.З.Шор, И.Экланд и многие другие.
Данная работа посвящена исследованию некоторых классов негладких функций и соответствующих задач недифференцируемой оптимизации. Основная особенность рассматриваемых классов состоит в том, что изучаемые функции, не являясь гладкими, сохраняют диф-ференцируемость по направлениям. Для дифференцируемых по направлениям функций удается формулировать конструктивно проверяемые необходимые и достаточные условия экстремума и строить численные методы, используя различные условия. Наиболее важными и богатыми классами таких функций являются квазидифференцируемые и ко-дифференцируемые функции. Используя специфику некоторых классов этих функций, например, выпуклых функций, разности выпуклых функций, функции максимума, удается получать более полные и исчерпывающие результаты.
Среди негладких оптимизационных задач одно из центральных мест принадлежит минимаксным задачам. Задача о наилучшем равномерном приближении функции многочленами рассматривалась более века
назад П.Л.Чебышевым. Дальнейшее развитие теории минимаксных задач принадлежит И.В.Гирсанову, Дж. Данскину, В.Ф.Демьянову, Я.И. Забогину, В.Н.Малоземову, Э.Полаку, Б. Н. Пшеничному, В.В.Федорову и др.
Выпуклый анализ является одним из наиболее полно исследованных разделов негладкого анализа. Основания выпуклого анализа были заложены в начале XX столетия Г.Минковским. Большой вклад в развитие этого направления математики был сделан Ж.Ж.Моро, В.Фенхелем, Р.Рокафслларом. Понятия и результаты выпуклого анализа играют фундаментальную роль в теории оптимизации. В отсутствии гладкости свойство выпуклости представляет обширный набор аналитических средств для развития содержательной теории условий экстремальности. Выпуклые множества и выпуклые функции - основной инструмент в теоретических исследованиях во многих вопросах не дифференцируемой оптимизации. Введение такого понятия, как субдифференциал выпуклой функции, явилось толчком для развития нового подхода к исследованию негладких функций. Субдифференциал выпуклой функции является обобщением понятия градиента гладкой функции. В точках недифференцируемости субдифференциал выпуклой функции есть выпуклое замкнутое множество. В терминах субдифференциала формулируются необходимые и достаточные условия экстремума выпуклой функции, строятся численные методы минимизации как на всем пространстве, так и при наличии ограничений. К сожалению, субдифференциальное отображение не является непрерывным в метрике Хаусдорфа. Введение Р. Рокафслларом и Ж.Моро понятия є- субдиффереыциала и его непрерывность в метрике Хаусдорфа при положительном є позволило строить методы минимизации выпуклой функции с непрерывным направлением спуска. Стоит отметить, что многие задачи оптимизации сводятся к минимизации выпуклых функции, поскольку выпуклое программирование представляет собой наиболее хорошо разработанный раздел теории оптимизации. Огромный вклад в развитие численных методов минимизации выпуклой функции внесли Ф.П.Васильев, И.И.Еремин, Ю.М.Ермольев, К. Лемарешаль, Е.А. Нурминский, Б.Т. Поляк, Р.Рокафсллар, Н.З. Шор и многие
другие ученые.
Широким и практически важным классом задач является класс квазидифференцируемых функций. Квазидифференцируемые функции были введены В.Ф.Демьяновым и A.M.Рубиновым п 1979г. Класс квазидифференцируемых функций обладает многими свойствами, удобными с точки зрения численного решения задач оптимизации. Квазидифференциал квазидифференцируемой функции является обобщением понятия субдифференциала выпуклой функции. Дальнейшее развитие теория квазидифференцируемых функций получила в работах В.В.Гороховика, С.И.Дулова, Б.Лудерера, Д.Паллашке, А.Шапиро, З.Шиа и др.
Большое внимание в теории недифференцируемой оптимизации также уделяется изучению экстремальных свойств и построению численных методов минимизации разности выпуклых функций. Эта задача является актуальной, поскольку из теоремы Стоуна - Вейерштрасоа следует, что любую непрерывную функцию на компакте можно аппроксимировать с нужной точностью разностью выпуклых функций. В этой области стоит отметить работы А.Д.Александрова, В.П.Булатова. Ж.Б.Ириа-Уррути, А.С.Стрекаловского, Х.Туя'и других.
В нелинейном программировании широкое распространение имеют методы штрафных функций, как внешних, так и внутренних. Решение оптимизационных задач этими методами сводится к минимизации гладких функций, так как этот аппарат наиболее хорошо изучен. Идея введения штрафной функции восходит еще к Лагранжу. Интерес к ней возродился в 60-е годы XX столетия в применении к задачам математического программирования. При этом выяснилось, что "платой'' за существование точной штрафной функции является негладкость функции, задающей ограничение. Однако прогресс в области методов недифференцируемой оптимизации позволяет преодолеть трудности, связанные с упомянутой негладкостью. Впервые существование точного штрафного параметра для задач выпуклого программирования было замечено И.И.Ереминым и У.И.Зангвилом. Впоследствии этому вопросу были посвящены работы Ю.Г.Евтушенко, В.Г.Жадана, Ди Пилло, В.В.Федорова и др.
Разработка численных методов минимизации негладких функций является актуальной проблемой и в настоящее время.
Цели исследования. Цель данной работы - построение теоретической базы с последующим применением полученных результатов к численной минимизации класса квазидифференцируемых функций, а именно:
изучение оптимизационных свойств класса квазидифференцируемых функций: вывод необходимых и достаточных условий экстремума квазидифференцируемой функции в задачах безусловной и условной оптимизации, построение направлений наискорейшего спуска и подъема квазидифференцируемой функции в задачах оптимизации;
конструирование численных методов минимизации некоторых классов квазидифференцируемых функций: класса гиподифференцируемых функций (функции максимума, функции суммы модулей), разности выпуклых функций;
- разработка методов точных штрафных квазидифференцируемых
функций для решения оптимизационных задач с негладкой целевой
функцией на множестве, заданном негладкой функцией.
Методика исследования базируется на основных фактах математического анализа, выпуклого анализа, негладкого анализа и теории математического программирования.
Научная новизна работы. Все основные результаты диссертации являются новыми. Среди них:
-
Доказаны некоторые новые факты выпуклого анализа: доказана теорема о непрерывности по Какутани конических отображений (нормальных конусов к выпуклому замкнутому множеству), предложен новый подход к вопросу построения гладкой аппроксимации выпуклых замкнутых множеств и выпуклых функций и рассмотрены свойства этой аппроксимации; найдено другое, более конструктивное представление разности выпуклых множеств, введенное В.Ф. Демьяновым.
-
Изучены экстремальные свойства квазидифференцируемых функций. Доказаны необходимые и достаточные условия оптимальности
кпазидифференцируемых функций как на всем пространстве М.п, так и при наличии квазидиффсренцируемых ограничений типа "неравенства11 и типа ''равенства'". Выведены достаточные признаки выполнения условия регулярности квазидиффсренцируемых множеств.
-
Для минимизации непрерывно гиподифференцируемых функций разработан метод гиподиффоренциального спуска - аналог градиентного метода в случае минимизации гладкой функции. Построен алгоритм минимизации с постоянным шагом функции максимума сильно выпуклых функций на К", обладающий геометрической скоростью сходимости и аналогичный алгоритму минимизации с постоянным шагом сильно выпуклой гладкой функции.
-
Выведены теоремы двойственности для задач оптимизации разности выпуклых функций. Построена гладкая функция, аппроксимирующая разность выпуклых функций и обладающая теми же экстремальными свойствами, что и эта разность. Разработаны релаксационный метод минимизации разности выпуклых функций на Ш.п и метод минимизации, использующий свойство непрерывности по Хаусдорфу є -субдифференциального отображения.
-
Рассмотрен метод точных внешних штрафных функций при недифференцируемости штрафных функций; сформулированы конструктивные достаточные условия существования точного штрафного параметра.
Теоретическая и практическая значимость работы. Полученные результаты можно использовать для исследования оптимизационных свойств и численного решения задач негладкого анализа.
Апробация работы. Основные результаты диссертации докладывались на семинаре кафедры математической теории моделирования систем управления факультета прикладной матсматики-процессов управления СПбГУ (рук.- проф. В.Ф.Демьянов); на семинаре кафедры вычислительной математики математико-механического факультета СПбГУ (рук.-проф. В.М.Рябов); на семинаре МГУ " Нелинейный анализ и оптимизация" (рук.- проф. М.И.Зеликин, акад. РАН А.Б.Кур-жанский, акад. РАН Ю.С.Осипов, проф. В.М.Тихомиров, проф.
А.В.Фурсиков); на семинаре ВЦ РАН (рук. - чл.- корр. РАН Ю.Г.Евтушенко); на семинаре Аристотелевского университета ( Греция, г. Салоники, рук. - акад. П. Панагиотопулос); на Всесоюзной конференции по динамическому управлению (Свердловск, 1979); на YII Всесоюзной конференции "Проблемы теоретической кибернетики" (Горький, 1988); на Международном советско-польском семинаре "Математические методы оптимального управления и их приложения" (Минск, 1939); на XI - ой Всесоюзной конференции "Проблемы теоретической кибернетики " (Волгоград, 1990), на III Всесоюзной школе по оптимальному управлению (Кемерово, 1990); на Всесоюзной конференции "Негладкий анализ и его приложения к математической экономике" (Баку, 1991); на Всесоюзной научной конференции "Экстремальные задачи и их приложения" (Нижний Новгород, 1992); на Международном семинаре "Многозначное исчисление и негладкий анализ" (Санкт-Петербург, 1995); на Х-ой Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1997); на семинаре, организованном IX-ой Саратовской зимней школой "Современные проблемы теории функций и их приложения" (Саратов, 1998).
Публикации. Основные результаты диссертации опубликованы в работах [1-26].
Объем и структура диссертации. Диссертация состоит из введения, пяти глав, разделенных на 28 параграфов, и списка литературы из 258 наименований. Работа изложена на 291 странице.
Похожие диссертации на Разработка математической теории и численных методов для решения некоторых классов негладких задач оптимизации
