Введение к работе
Актуальность темы. Основным понятием в классическом математическом анализе является понятие производной ( градиента в многомерном случае ). Лля изучения негладких функций было введено несколько обобщений понятия производной. В частности, для выпуклых функций и функций максимума таким обобщением является понятие субдифферендиала, для лишпицевых функций эффективным оказался субдифференциал Кларка, для квазидифференцируе-мых функций - понятия квазидифференциала и кодифференциала. Упомянутые обобщения позволяют по-новому ставить и решать типичные задачи, традиционные для классического математического анализа, например, задачи о неявных и обратных функциях, о решении систем негладких уравнений, задачи оптимизации. Подобно тому, как задачи линейной алгебры возникают в качестве вспомогательных при решении ряда упомянутых выше задач, так в негладком случае возникают задачи, получившие название задачи квазилинейной алгебры.
В хорошо известной работе А.Д. Александрова (1949) ставился ряд задач в рамках теории внутренней геометрии выпуклых поверхностей. Одну из этих задач можно сформулировать как задачу отыскания минимальной пары двух выпуклых компактных множеств в классе эквивалентности, который определяет эта пара. Различными авторами предпринимались неоднократные попытки решить эту задачу и предложить алгоритм построения минимальной пары. Вероятно, первой в этом направленнии была работа В.А. Залгал-лера (1963). В ней был дан алгоритм построения минимальной пары в пространстве R2 для произвольных выпуклых компактов, но приемлемым для вычислений он оказался только в случае многогранных множеств. С развитием теории квазидифференцируемых функций встал вопрос о нахождении минимального квазидифференциала, что в свою очередь усилило актуальность задачи поиска решения обсуждаемой задачи. Для нахождения минимального квазидифференциала М. Хандшутом был предложен алгоритм в случае многогранных множеств в пространстве R2 (1989). Позднее, в ряде работ немецкой школы математиков ( Д. Паллашке, С. Шолтес, Р. Урбанский ) было конкретизировано понятие минимальной пары и
в соответствии с ним доказано, что в R такая пара единственна с точностью до сдвига. Там же было показано, что в пространстве размерности 3 и выше минимальная пара неединственна и, более того, множество минимальных пар в одном классе эквивалентности имеет мощность континуума. Заметим также, что в этих работах не были указаны эффективные алгоритмы построения минимальных пар, пригодных для практических вычислений. Конструктивный алгоритм построения минимальной пары в пространстве R2 для произвольных множеств был представлен Демьяновым В.Ф. на международной симпозиуме "Многозначные отображения и негладкий анализ-95" в Санкт-Петербурге. На данном этапе актуальными задачами являлись обоснование алгоритма и создание программного обеспечения.
Одним из наиболее известных и изученных методов решения задач условной оптимизации является метод штрафных функций. Исследованием этого подхода занимались и занимаются многие математики (И.И.Еремин, Дж.Мак-Кормик, Ю.Г.Евтушенко, Ю.М.Ермольев, Н.З.Шор, Б.Т.Поляк, В.В.Федоров). Быстрое и успешное развитие методов недифферендируемой оптимизации позволило по-новому взглянуть на метод штрафных функций и продвинуть методы точных штрафных функций. Так, итальянскими математиками (Ди Пилло, Ди Гршшо, Ф.Фахиней) с помощью производной Кларка были получены достаточные условия существования точной штрафной функции и изучены их свойства. Позднее, используя производную Дини, были найдены более сильные достаточные условия (В.Ф.Демьянов), а привлечение аппарата квазидифференциалов позволило строить и изучать классы квазидифференцируемых функций, которые могут быть использованы в качестве точных штрафных функций.
Цель и задачи исследования. Цель работы заключалась в решении ряда теоретических и практических вопросов в области негладкого анализа. Перед диссертантом были поставлены следующие задачи:
1. Изучить свойства точных штрафных функций, применить их для решения задач условной оптимизации с квазидифферендируе-мыми исходными функциями,
-
Разработать конструктивные численные методы решения квазилинейных и колинейных систем,
-
Построить алгоритм для нахождения минимальной пары двух вьшуклых компактов в их классе эквивалентности (в случае пространства R2), доказать единственность минимальной пары с точностью до сдвига в пространстве R2,
-
Создать пакеты программ, реализующих разработанные алгоритмы, провести численные экперименты.
Научная новизна работы. Показано, что точная штрафная функция в определенном смысле должна быть существенно негладкой функцией. Рядом примеров проиллюстрировано, что поиск точной штрафной функции в конкретной задаче нельзя ограничивать только одним классом функций. Лля некоторых классов квазидиф-ференцируемых функций, которые могли бы послужить точными штрафными функциями в большом множестве задач условной минимизации, получен явный вид квазидифференциалов.
Впервые предлагается целый комплекс численных методов с программной реализацией для решения квазилинейных и колинейных систем. Разработаны эффективные способы нахождения решений, основанные на достаточном условии существования и единственности решения квазилинейной и колинейной систем. Показана сходимость метода покоординатного спуска в случае одного класса негладких функций. Предложен метод минимизации функции, являющейся разностью выпуклых функций.
Разработан аналитический способ вычисления разности — и суммы Минковского двух вьшуклых множеств в пространстве R2. На основании этого дано обоснование метода поиска минимальной пары двух вьшуклых компактов в их классе эквивалентности. Построено наглядное программное обеспечение, демонстрирующее метод.
Практическая значимость работы. Полученные результаты представляют теоретический и практический интерес. Так, например, обоснование обязательности точной штрафной функции быть негладкой избавляет от поиска таких функций в классе гладких
функций. Формулы вычисления квазидифференпиалов, полученные для квазидифференцируемых точных штрафных функций, могут быть использованы при решении конкретных задач условной оптимизации. Представленные в работе примеры наглядно демонстрируют как использовать и проверять достаточное условие существования точной штрафной функци.
Представленные численные методы решения квазилинейных систем являются одним из звеньев в цепочке методов решения разнообразных задач негладкого анализа, где изучаемые функции обладают свойством квазидифференцируемости. Так, полученные результаты могут быть использованы в обобщенном методе Ньютона для квазидифференцируемых функций, в теории неявных функций и т.д. Метод минимизации невязки квазилинейной системы может также с успехом применяться для мішимизации функции, предста-вимой в виде разности двух выпуклых.
Апробация работы. Основные результаты были представлены на семинарах кафедры Математической Теории Моделирования Систем Управления факультета Прикладной Математики - Процессов Управления СПбГУ(1992-1995), на семинаре кафедры Исследования Операций Математико-Механического факультета (1995), в Вычислительном Пентре РАН (1995), на Международном симпозиуме "Set-valued Mapping and Nonsmooth Analysis-95" (СПбИМ им. Стеклова, 1995).
Публикации. По материалам диссертации опубликовано 2 печатные работы.
Объем и структура работы. Диссертация состоит из введения с аналитическим обзором литературы, главы с предварительными сведениями, трех глав, содержащих основные результаты, и приложения с программным обеспечением. Работа изложена на 108 страницах, содержит 5 рисунков; список цитируемой литературы включает 58 наименований.