Содержание к диссертации
Введение
Глава 1. Метод условного градиента для случая предвыпуклых ограничений с непустым множеством внутренних точек . 21
1.1. Постановка задачи и алгоритм метода 22
1.2. Необходимые условия экстремума 25
1.3. Обоснование алгоритма при первом способе выбора шага . 28
1.4. Обоснование алгоритма при втором способе выбора шага . 31
1.5. Результаты вычислений 32
Выводы по главе 1 38
Глава 2. Метод проекции градиента для случая предвыпуклых ограничений с непустым множеством внутренних точек . 39
2.1. Постановка задачи и алгоритм метода 40
2.2. Обоснование алгоритма при первом способе выбора параметров 43
2.3. Обоснование алгоритма при втором способе выбора параметров 46
2.4. Обоснование алгоритма при третьем способе выбора параметров 54
2.5. Результаты вычислений 56
Выводы по главе 2 62
Глава 3. Метод проекции градиента для случая ограничений в виде выпуклой гладкой поверхности 63
3.1. Постановка задачи и алгоритм метода 64
3.2. Обоснование алгоритма при первом способе выбора шага . 66
3.3. Обоснование алгоритма при втором способе выбора шага . 70
3.4. Результаты вычислений 74
Выводы по главе 3 78
Глава 4. Эвристические алгоритмы метода проекции субградиента для пред выпуклых множеств ограничений 79
4.1. Постановка задачи и алгоритм для ограничений первого типа . 80
4.2. Постановка задачи и алгоритм для ограничений второго типа . 83
4.3. Результаты вычислений 84
Выводы по главе 4 89
Заключение 90
Список литературы 92
- Необходимые условия экстремума
- Обоснование алгоритма при первом способе выбора параметров
- Обоснование алгоритма при втором способе выбора шага
- Постановка задачи и алгоритм для ограничений второго типа
Введение к работе
Тематика диссертации. Диссертация посвящена разработке и доказательству сходимости численных методов решения задач математического программирования с невыпуклыми ограничениями, названными В. И. Заботиным и Ю. А. Полонским предвыпуклыми. Получение необходимых условий экстремума в задачах с предвыпуклыми ограничениями восходит к работам Б. Н. Пшеничного и Р. Рокафеллара, где в качестве допустимого множества рассматривалась теоретико-множественная разность конечномерного евклидова пространства и некоторого выпуклого множества и исследовались задачи минимизации выпуклой функции на данном множестве. Надо отметить, что эти необходимые условия были получены как "побочный продукт" теорий, которые строились указанными авторами.
Было, однако, ясно, что в указанных задачах применим аппарат отделимости выпуклых множеств, дальнейшее развитие применения которого было получено в работах В. И. Заботина и Ю. А. Полонского. Ими вводится понятие предвыпуклого множества, частными случаями которого являются выпуклое множество, выпуклая поверхность, а также множества, рассматриваемые Б. Н. Пшеничным и Р. Рокафелларом. Предвыпуклым было названо множество в линейном пространстве, дополнение которого до его выпуклой оболочки является выпуклым множеством. В работах В. И. Заботина и Ю. А. Полонского показано, что необходимым и достаточным условием предвыпуклости множества является возможность его представления в виде теоретико-множественной разности двух выпуклых множеств. Основным результатом работ указанных авторов было обобщение теорем отделимости, которое позволило получать необходимые условия экстремума выпуклых функций на различного рода предвыпуклых множествах, включающие в себя и результаты, полученные ранее Б. Н. Пшеничным и Р. Рокафелларом.
Оставался, однако, открытым вопрос создания и обоснования численных методов для экстремальных задач с предвыпуклыми ограничениями. Геометрия предвыпуклых множеств позволяла надеяться, что можно создавать регулярные численные методы, сходящиеся на уровне необходимых условий экстремума. Настоящая диссертация как раз и посвящается проблеме разработки и доказательства сходимости таких методов. Исследуется сходимость алгоритмов оптимизации гладких функций и предлагаются эвристические алгоритмы оптимизации выпуклых негладких функций на предвыпуклых множествах двух видов.
Актуальность проблемы. В математическом программировании существует большое количество эвристических алгоритмов, а также алгоритмов, сходимость которых доказана для одного класса задач (например, доказатель-
І РОС HAlKinHViNHVl
1 «"у С. Петербург
j 'ЫУРИ
ства сходимости проводятся, как правило, в предположении о выпуклости множества ограничений), но применяемых в задачах из других классов. С точки зрения практики такое применение часто бывает оправданным, но с точки зрения математики актуальной является не только проблема разработки алгоритмов для нового класса задач, но и проблема их обоснования, то есть доказательства сходимости в том или ином смысле. В настоящей диссертации предлагаются численные алгоритмы для нового класса задач (для задач математического программирования с предвыпуклыми ограничениями) и доказывается их сходимость в смысле необходимых условий экстремума. С этой точки зрения данная работа удовлетворяет требованию актуальности.
С практической точки зрения представляют большой интерес, например, задачи оптимального в том или ином смысле расположения группы объектов на поверхности Земли, приближённо являющейся выпуклой гладкой поверхностью, задачи выведения искусственного спутника Земли в оптимальную точку шарового слоя космического пространства, задачи покрытия сферы или её части сферическими кругами минимального радиуса и другие задачи, каждая из которых может быть сформулирована как задача математического программирования с предвыпуклыми ограничениями. Значит, необходима разработка численных методов, учитывающих специфику таких задач, а следовательно, тематика предлагаемой диссертации актуальна не только с теоретической, но и с практической точки зрения.
Цель работы заключается в разработке численных алгоритмов для задач с предвыпуклыми ограничениями, теоретическом обосновании этих алгоритмов (доказательстве их сходимости), а также в разработке программ для реализации указанных алгоритмов на ЭВМ.
Задачи исследования. В настоящей диссертации необходимо было решить следующие задачи:
-
исследовать некоторые необходимые условия экстремума для задач с предвыпуклыми ограничениями;
-
разработать численные алгоритмы решения поставленных задач;
-
доказать сходимость алгоритма метода условного градиента для пред-выпуклых ограничений с непустым множеством внутренних точек при различных способах выбора итерационного шага;
-
доказать сходимость различных вариантов метода проекции градиента для предвыпуклых ограничений с непустым множеством внутренних точек;
-
доказать сходимость метода проекции градиента для ограничений в виде выпуклой гладкой поверхности при различных способах выбора шага;
-
провести вычислительные эксперименты для иллюстрации сходимости рассматриваемых методов.
Методы исследования. При исследовании рассматриваемых в диссертации задач используются методы математического анализа, выпуклого анализа, выпуклого программирования и теории экстремальных задач.
На защиту выносятся следующие результаты:
-
постановки задач оптимизации на предвыпуклых множествах ограничений, содержащих внутренние точки или являющихся выпуклой гладкой поверхностью;
-
исследование некоторых необходимых условий экстремума для задач с предвыпуклыми ограничениями;
-
формулировки алгоритмов решения поставленных задач;
-
обоснование сходимости указанных алгоритмов при различных способах выбора параметров;
-
результаты вычислительных экспериментов, проведённых с помощью разработанного автором программного обеспечения алгоритмов.
Научная новизна диссертации состоит в разработке, теоретическом обосновании и сравнительном анализе новых алгоритмов решения задач математического программирования для различных видов предвыпуклых ограничений. Предлагаются алгоритмы, обобщающие метод проекции градиента и метод условного градиента на случай предвыпуклых множеств. Получены доказательства сходимости алгоритмов в смысле необходимых условий экстремума, представляющие теоретический интерес. При помощи программного обеспечения, реализующего указанные алгоритмы для некоторых видов предвыпуклых множеств, проведены расчёты, на основе которых рассматриваются вычислительные аспекты методов.
Практическая ценность диссертации. Как было сказано выше, в работе созданы и обоснованы численные методы решения нового класса экстремальных задач, что представляет собой практическую ценность.
С точки зрения конкретных приложений, рассматриваемые в диссертации методы могут найти своё практическое применение, например, при решении задач проектирования спутниковых созвездий кратного обзора земной поверхности или обзора атмосферного слоя вблизи поверхности Земли. Здесь возникают задачи отыскания экстремума гладких функций и некоторых функций типа максимина, описанные в работах Г. В. Можаева, Ш. И. Галиева и В. И. Забо-тина; при этом экстремум отыскивается на множестве, являющемся либо выпуклой гладкой поверхностью, либо теоретико-множественной разностью двух шаров или областей, ограниченных эллипсоидами. Сюда относится, в частности, задача нахождения точки атмосферного слоя (земной поверхности), в каком-либо смысле наиболее удалённой от нескольких фиксированных точек этого атмосферного слоя (земной поверхности). Для негладкой функции макси-
мина возможно предварительное сглаживание, тогда для решения таких задач могут быть использованы методы, которым посвящена диссертация.
Полученные в диссертации результаты могут быть использованы также в учебном процессе при проведении лекций и лабораторных работ по курсу "Методы оптимизации".
Реализация результатов работы. Результаты диссертации реализованы в следующих научных отчётах для Академии наук Республики Татарстан, выполненных в рамках научно-исследовательских работ Отделения математики, механики и машиноведения АН РТ, а также в рамках научно-исследовательских работ, поддерживаемых Фондом НИОКР РТ.
1. Этап 2001 г. "Математическое моделирование и информатика опти
мальных решений в технологиях и управлении".
Тема: "Фундаментальные и прикладные вопросы информационных технологий, моделирования и управления". Договор-подряд № 05-5.2.3 / 2001 (ФП).
2. Этап 2002 г. "Построение и исследование математических моделей
сложных динамических и статических систем".
Тема: "Модели, методы и программное обеспечение оптимального проектирования и оценивания сложных детерминированных и стохастических систем". Договор-подряд № 05-5.2-195 / 2002 (Ф).
3. Этап 2003 г. "Методы и алгоритмы исследования математических мо
делей сложных динамических и статических систем".
Тема: "Модели, методы и программное обеспечение оптимального проектирования и оценивания сложных детерминированных и стохастических систем". Договор-подряд № 05-5.2-195 / 2003 (Ф).
Указанные договоры входят в "Программу развития приоритетных направлений науки в Республике Татарстан" на 2001-2005 годы.
Апробация результатов исследований. Основные результаты, полученные в диссертации, докладывались и обсуждались на следующих конференциях: Научно-техническая конференция "IX Всероссийские Туполевские чтения студентов" (г. Казань, 25-26 октября 2000 года); 6-я Международная конференция "Системный анализ и управление космическими комплексами" (г. Евпатория, 2-8 июля 2001 года); ХШ Международная конференция "Проблемы теоретической кибернетики" (г. Казань, 27-31 мая 2002 года); Международная молодёжная научная конференция "XXX Гагаринские чтения" (г. Москва, 6-Ю апреля 2004 года).
Публикации по теме диссертации. Основные положения настоящей диссертации опубликованы в 9 печатных работах, в том числе в 5 научных статьях "Журнала вычислительной математики и математической физики" Российской Академии наук.
Струкгура и объём диссертации. Диссертация состоит из введения, четырёх глав, заключения и списка литературы. Общий объём диссертации составляет 97 страниц. Работа содержит 3 рисунка. Список литературы включает 70 наименований.
Необходимые условия экстремума
Цель работы заключается в разработке численных алгоритмов для задач с предвыпуклыми ограничениями, теоретическом обосновании этих алгоритмов (доказательстве их сходимости), а также в разработке программ для реализации указанных алгоритмов на ЭВМ.
Задачи исследования. В настоящей диссертации необходимо было решить следующие задачи: 1) исследовать некоторые необходимые условия экстремума для задач с предвыпуклыми ограничениями; 2) разработать численные алгоритмы решения поставленных задач; 3) доказать сходимость алгоритма метода условного градиента для случая предвыпуклых ограничений с непустым множеством внутренних точек при различных способах выбора итерационного шага; 4) доказать сходимость различных вариантов метода проекции градиента для случая предвыпуклых ограничений с непустым множеством внутренних точек; 5) доказать сходимость метода проекции градиента для случая ограничений в виде выпуклой гладкой поверхности при различных способах выбора итерационного шага; 6) провести вычислительные эксперименты для иллюстрации схо димости рассматриваемых методов. Методы исследования. При исследовании рассматриваемых в диссертации задач используются методы математического анализа, выпуклого анализа, выпуклого программирования и теории экстремальных задач. На защиту выносятся следующие результаты: 1) постановки задач оптимизации на предвыпуклых множествах ограничений, содержащих внутренние точки или являющихся выпуклой гладкой поверхностью; 2) формулировки алгоритмов решения поставленных задач; 3) исследование некоторых необходимых условий экстремума для задач с предвыпуклыми ограничениями; 4) обоснование сходимости указанных алгоритмов при различных способах выбора параметров; 5) результаты вычислительных экспериментов, проведённых с помощью разработанного автором программного обеспечения алгоритмов. Научная новизна диссертации состоит в разработке и теоретическом обосновании новых алгоритмов решения задач математического программирования для различных видов предвыпуклых ограничений. Предлагаются алгоритмы, обобщающие метод проекции градиента и метод условного градиента на случай предвыпуклых множеств. Получены доказательства сходимости алгоритмов в смысле необходимых условий экстремума, представляющие теоретический интерес. При помощи программного обеспечения, реализующего указанные алгоритмы для некоторых случаев предвыпуклых множеств, проведены расчёты, на основе которых рассматриваются вычислительные аспекты методов.
Практическая ценность диссертации. Как было сказано выше, в работе созданы и обоснованы численные методы решения нового класса экстремальных задач, что представляет собой практическую ценность.
С точки зрения конкретных приложений, рассматриваемые в диссертации методы могут найти своё практическое применение, например, при решении задач проектирования спутниковых созвездий кратного обзора земной поверхности или обзора атмосферного слоя вблизи поверхности Земли. Здесь возникают задачи отыскания экстремума гладких функций и некоторых функций типа максимина, рассматриваемые в работах Ш. И. Галиева [13], В. И. Заботина [22], и Г. В. Можаева [44], при этом экстремум отыскивается на предвыпуклом множестве, являющемся либо выпуклой гладкой поверхностью, либо теоретико-множественной разностью двух шаров или областей, ограниченных эллипсоидами. Сюда относится, в частности, задача нахождения точки атмосферного слоя (земной поверхности), в каком-либо смысле наиболее удалённой от нескольких фиксированных точек этого атмосферного слоя (земной поверхности). Для негладкой функции максимина возможно предварительное сглаживание, описанное, например, в [13], тогда для решения таких задач могут быть использованы методы, которым посвящена диссертация, как это показано в [61].
Полученные в диссертации результаты могут быть использованы также в учебном процессе при проведении лекций и лабораторных работ по курсу "Методы оптимизации".
Реализация результатов работы. Полученные в диссертации результаты реализованы в следующих научных отчётах для Академии наук Республики Татарстан, выполненных в рамках научно-исследовательских работ Отделения математики, механики и машиноведения АН РТ, а также в рамках научно-исследовательских работ, поддерживаемых Фондом НИОКР РТ. 1. Этап 2001 г. "Математическое моделирование и информатика оптимальных решений в технологиях и управлении". Тема: "Фундаментальные и прикладные вопросы информационных технологий, моделирования и управления". Договор-подряд № 05-5.2.3 / 2001 (ФП). 2. Этап 2002 г. "Построение и исследование математических моде лей сложных динамических и статических систем". Тема: "Модели, методы и программное обеспечение оптимального проектирования и оценивания сложных детерминированных и стохастических систем". Договор-подряд № 05-5.2-195 / 2002 (Ф). 3. Этап 2003 г. "Методы и алгоритмы исследования математических моделей сложных динамических и статических систем". Тема: "Модели, методы и программное обеспечение оптимального проектирования и оценивания сложных детерминированных и стохастических систем". Договор-подряд № 05-5.2-195 / 2003 (Ф). Указанные договоры входят в "Программу развития приоритетных направлений науки в Республике Татарстан" на 2001—2005 годы. Апробация результатов исследований. Основные результаты, полученные в диссертации, докладывались и обсуждались на следующих конференциях: Научно-техническая конференция "IX Всероссийские Ту-полевские чтения студентов" (г. Казань, 25-26 октября 2000 года); 6-я Международная конференция "Системный анализ и управление космическими комплексами" (г. Евпатория, 2-8 июля 2001 года); XIII Международная конференция "Проблемы теоретической кибернетики" (г. Казань, 27-31 мая 2002 года); Международная молодёжная научная конференция "XXX Гагаринские чтения" (г. Москва, 6-10 апреля 2004 года).
Обоснование алгоритма при первом способе выбора параметров
При 2-м способе выбора шага для выполнения правила останова обычно требуется несколько больше итераций, чем при 1-м, но при этом не требуется на каждой итерации решения вспомогательной задачи одно мерной минимизации, что существенно снижает объём вычислений на итерации. С другой стороны, при 2-м способе выбора шага итерационный процесс иногда останавливается в точке, не очень близкой к стационарной, поэтому для получения приемлемого результата при этом способе выбора шага необходимо использовать более жёсткие критерии останова итерационного процесса, что, однако, ведёт к увеличению числа итераций. Рассмотренный в настоящей главе метод в ряде случаев отличается медленной сходимостью по сравнению с методом, описанным в следующей главе. Но метод условного градиента имеет и свой преимущества. Рассматриваемый во второй главе метод является обобщением метода проекции градиента, применяемого для выпуклых множеств ограничений, и требует на каждой итерации решения задачи проектирования на некото рое вспомогательное выпуклое множество. Это выпуклое множество ДЛЯ каждой итерации строится отдельно, а задача проектирования, которая сводится к задаче минимизации квадратичной функции, далеко не всегда решается просто и часто требует привлечения итерационных методов. Что касается метода, предлагаемого в настоящей главе, то при ею реализации на каждой итерации тоже приходится строить вспомогатель ное выпуклое множество, но на этом множестве решается задача миними зации линейной функции. Минимизировать линейную функцию на выпук лом множестве обычно проще, чем квадратичную. Если, например, пред выпуклое множество представляется в виде теоретико-множественной разности выпуклого многогранника и шара в л-мерном пространстве, то на каждой итерации нужно решать задачу минимизации линейной функции на теоретико-множественном пересечении этого многогранника и некото рого замкнутого полупространства. Но пересечение многогранника и полупространства - многогранное множество, а это означает, что на каждой итерации надо решать задачу линейного программирования, для которой существуют конечные методы решения. При использовании метода, предлагаемого во второй главе, надо решать более сложную задачу - задачу квадратичного программирования. Если же многогранник задаётся через множество вершин, то минимизация линейной функции на нём сводится к сравнению нескольких чисел, а решение задачи проектирования на него требует привлечения специальных итерационных методов, которые далеко не всегда быстро сходятся. Выводы по главе 1 В первой главе диссертации получены следующие результаты: 1) поставлена задача минимизации гладкой функции для случая предвыпуклых ограничений с непустым множеством внутренних точек; 2) предложен численный алгоритм решения поставленной задачи, обобщающий алгоритм метода условного градиента; 3) исследованы некоторые необходимые условия экстремума гладкой функции на множестве рассматриваемого вида; 4) для двух способов выбора итерационного шага доказана сходимость алгоритма в смысле необходимых условий экстремума; 5) с помощью разработанного автором программного обеспечения проведены расчёты тестовых примеров, иллюстрирующие сходимость алгоритма, и рассмотрены вычислительные аспекты метода. В настоящей главе исследуется проблема обобщения метода проекции градиента, излагаемого, например, в [11, 33] и применяемого для минимизации гладких функций на выпуклых множествах в «-мерном пространстве, на случай пред выпуклых ограничений с непустым множеством внутренних точек. Во введении к диссертации было сказано, что любое предвыпуклое множество является теоретико-множественной разностью некоторых двух выпуклых множеств. Будет рассмотрен случай, когда множество граничных точек "вычитаемого" множества является гладким многообразием.
Метод проекции градиента относится к итерационным методам решения задач математического программирования и является методом первой вариации, то есть использующим аппарат первых производных минимизируемой функции. В основе метода лежит тот факт, что направление наискорейшего убывания гладкой функции в точке - это направление антиградиента. Однако, при наличии ограничений на допустимые значения аргумента, движение в указанном направлении на итерациях может, вообще говоря, выводить за пределы допустимого множества. В связи с этим, полученную после движения по антиградиенту точку целесообразно спроектировать на допустимое множество. При этом учитывается, что проекция произвольной точки на выпуклое замкнутое множество существует и единственна. Такова идея метода проекции градиента для случая выпуклых множеств.
Что касается невыпуклых допустимых множеств, то задача проектирования на такие множества имеет, вообще говоря, не одно решение, а нахождение произвольной проекции на каждой итерации может не привести к положительному результату при использовании метода, то есть последо вательность приближений не будет сходиться к множеству точек, удовле творяющих необходимому условию экстремума. Это относится, в частно сти, и к предвыпуклым множествам. Идея обобщения классического метода проекции фадиента на случай предвыпуклых множеств заключается в том, что задачи проектирования на итерациях решается не для самого допустимого множества, а для некоторых вспомогательных выпуклых множеств, являющихся его подмножествами. Таким образом, на каждой ите-рации, кроме решения задачи проектирования на выпуклое множество, приходится решать задачу построения этого множества. В настоящей главе формализуется описанная задача минимизации на предвыпуклых множествах, предлагается метод решения поставленной задачи, исследуется сходимость метода в смысле необходимых условий экстремума, обсуждаются вычислительные аспекты метода и приводятся некоторые результаты вычислений. Основные результаты, полученные в этой главе, опубликованы в работах [24, 60, 62, 63, 65].
Обоснование алгоритма при втором способе выбора шага
В настоящей главе, рассматривается проблема обобщения метода проекции субградиента, излагаемого, например, в [11] и применяемого для минимизации выпуклых функций на выпуклых множествах в «-мерном пространстве, на некоторые случаи предвыпуклых ограничений. Во введении упоминалось, что любое предвьшуклое множество является теоретико-множественной разностью некоторых двух выпуклых множеств. Будет рассмотрен случай, когда множество внутренних точек предвыпуклого множества непусто, а множество граничных точек "вычитаемого" множества является гладким многообразием, и случай, когда предвьшуклое множество является выпуклой гладкой поверхностью в смысле [10].
Метод проекции градиента, о котором шла речь во второй и третьей главах настоящей диссертации, использует аппарат частных производных минимизируемой функции, а следовательно, может применяться только для гладких функций. Однако, для случая выпуклых негладких функций существует обобщение понятия градиента. Для характеристики выпуклых функций используется понятие субдифференциала, который иногда называют обобщённым градиентом.
Для решения задач минимизации выпуклых функций при наличии ограничений вышеуказанных типов предлагается использовать алгоритмы, аналогичные приведённым в разделах 2.1 и 3.1 диссертации. Отличие предлагаемых алгоритмов от описанных в тех разделах состоит в том, что при использовании этих алгоритмов на каждой итерации вместо градиента, который для негладкой функции существует не во всех точках, требуется определять произвольный субградиент минимизируемой функции.
В настоящей главе излагаются алгоритмы метода проекции субгра диента для задач с предвыпукльши ограничениями и приводятся некото рые примеры вычислении, показывающие эффективную работу метода для ряда задач математического программирования. Сходимость алгоритмов в настоящее время теоретически не доказана. Рассматривается задача минимизации вида где ф(х) является выпуклой на Я", а множество X представимо в виде теоретико-множественной разности некоторых множеств F и intG, причём F и G выпуклы и замкнуты, intG5 0 и граница G является гладким многообразием. В этом разделе будет рассмотрен случай, когда множество внутренних точек X непусто. Предполагается, что решение поставленной задачи существует, что может обеспечиваться, например, ограниченно стью множества . Задача, аналогичная данной, ставилась в разделе 2.1 диссертации. Различие состоит в том, что там рассматривается случай гладкой функции ф(х), на которую не требование выпуклости, а здесь - случай выпуклой р(х), на которую не налагается требование гладкости. В силу выпуклости на R", функция р(х) в любой точке Xимеет непустой субдифференциал. Для решения поставленной задачи минимизации выпуклой функции предлагается использовать алгоритмы, аналогичные тем алгоритмам, которые приведены в разделе 2.1. Отличие предлагаемого здесь алгоритма состоит в том, что при его использовании на каждой итерации вместо гра диента, который для негладкой функции существует не во всех точках, требуется определять произвольный субградиент минимизируемой функ ции. Для гладких выпуклых функций субдифференциал в каждой точке состоит из единственного элемента - градиента, поэтому для таких функций нахождение субградиента сводится к нахождению градиента. При изложении и обсуждении алгоритма для множества X первого типа будут использоваться обозначения, введённые в первой главе диссертации: s(x) - проекция точки х на множество G; п(х) - вектор внешней ортонормали к G в точке s(x); Г(х) - опорное полупространство к G в точке s(x); P(x)=T(x)f\F. Везде будем считать, что хеХ. Множества Г(х) и Р(х) и проекции s(x), построенные для точки хкъ будут обозначаться соответственно Гк, Рк, sk. Субдифференциал функции ц (х) в точке х будет обозначаться через дц (х). Множества Pkt =0,1,2,.., выпуклы и замкнуты, так как являются пересечением выпуклого замкнутого множества F с замкнутыми полупространствами Гк, поэтому задача проектирования точки хк-акск на Рк при =0,1,2,,,. имеет единственное решение. Однако даже при заданном способе выбора чисел ак, =0,1,2,... последовательность {хк} строится, во-обще говоря, неоднозначно, так как элемент ск на каждой итерации выбирается из д р(хк) произвольным образом. Числа ak на итерациях могут выбираться различными способами. Что касается выбора значений а при реализации алгоритма, то их можно выбирать, исходя из условий При этих условиях в [11] доказывается сходимость метода проекции суб-градиента для задачи выпуклого программирования. Этим условиям удов-летворяют, например, числа Что касается определения субградиентов, то, в общем случае, сложной является задача нахождения не только субдифференциала, но и произвольного субградиента в заданной точке. Однако, для некоторых функций субдифференциал определяется просто. Если, например, функция (р(х) задана в виде а функции Ф,( ), /є/, являются выпуклыми.и гладкими, то, как показано в [17], функция ф(х) является выпуклой и В данном случае дц (х) в каждой точке X либо состоит из единственной точки (в случае существования р (х) в данной точке), либо является вы пуклым многогранным множеством, все вершины которого содержатся среди точек ф/(Х), ieR(x). Поэтому в качестве произвольного субградиен та в точке хк может быть взят, например, любой из векторов f ф/OOs i RiXk)- Для повышения эффективности вычислений вместо про извольного субградиента ск дц {хк) можно на каждой итерации находить вектор ск = min fcjj, так как такой вектор есть направление наискорейшего спуска для функции ф(х) в точке хк как показано в [17]. В данном случае для нахождения такого вектора можно использовать стандартные итерационные методы проектирования начала координат на многогранник, описанные в [18]. Если при этом ск 0, то точка хк является точкой глобального минимума р(х) на Хв силу необходимого и достаточного условия экстремума выпуклой функции.
При реализации алгоритма последовательность приближений содержит, вообще говоря, бесконечное число итераций, так что выполнения условия хк =хк+] обычно не удаётся добиться ни на какой итерации. Поэтому на практике приходится останавливать вычисления на некоторой итерации.
Постановка задачи и алгоритм для ограничений второго типа
Итак, во всех рассмотренных примерах найденное приближённое решение достаточно близко к точному. Это позволяет предполагать, что при некоторых условиях обеспечивается сходимость метода. Выполнение w правила останова при использовании метода достигается, как правило, лишь через достаточно большое число итераций. При этом на первых итерациях {ц (хк)} иногда не убывает, а наоборот, возрастает, поскольку вышеуказанный выбор чисел ак не гарантирует монотонного убывания (p{jt). Несмотря на медленную сходимость, объём вычислений на одной , итерации при реализации метода не очень велик, если задача построения множества Рк и проектирования на него на каждой итерации решается просто. Определение чисел ак осуществляется элементарно и не требует решения каких-либо вспомогательных задач. Если предложить на итерациях определение чисел ак из условия наискорейшего спуска, то стоило бы ожидать более быструю сходимость метода, но объём вычислений был бы значительно больше. Эффективность метода снижается, если решение задач проектирования на итерациях требует привлечения каких-либо итерационных процедур. Отметим, что предлагаемый метод в общем случае не может сходиться к точке глобального минимума ф(х) наХ. Рассмотрим, например, взадачу минимизации линейной (а значит, и выпуклой) функциипри ограничении в виде разности кругов с центрами (0,-а) и) и радиусами а и Ъ соответственно, где 0 Ь а. В этом случае точка (0,0) лежит в допустимом множестве, но если её взять в качестве начального приближения х0 то множество Р0 будет состоять из единственной точки ха и мы из этой точки "не выйдем". Но точка (0,0) в действительности даёт не минимум, а максимум ф(х) на допустимом множестве, в чём нетрудно убедиться. Минимум достигается лишь на множестве Р0, которое здесь состоит из единственной точки (0,0). Замечая, что ф(л;) является гладкой, мы можем сказать, что в данном случае итерационный процесс сходится к точке JC =(0, 0), которая удовлетворяет необходимому условию экстремума (1.2,1). Таким образом, можно говорить о предполагаемой сходимости метода только в смысле необходимых условий экстремума. Сходимость алгоритмов, предложенных в этой главе, в настоящее время теоретически не доказана, но проведённые вычисления показали, что метод может быть успешно применён к решению ряда негладких экстремальных задач. Выводы по главе 4 В четвёртой главе диссертации получены следующие результаты; 1) поставлена задача минимизации выпуклой функции для случая предвыпуклых ограничений с непустым множеством внутренних точек; 2) поставлена задача минимизации выпуклой функции для случая ограничений в виде выпуклой гладкой поверхности; 3) предложены численные алгоритмы решения поставленных задач, обобщающие алгоритм метода проекции субградиента; 4) с помощью разработанного автором программного обеспечения проведены расчёты тестовых примеров, иллюстрирующие сходимость алгоритмов, и рассмотрены вычислительные аспекты метода. В диссертации получены следующие основные результаты: 1) поставлена задача создания численных методов оптимизации на предвыпуклых множествах, содержащих внутренние точки или являющихся выпуклой гладкой поверхностью; 2) разработаны численные методы оптимизации, обобщающие методы проекции градиента и субградиента на множества обоих указанных типов и метод условного градиента на множества первого типа; Ч 3) исследованы некоторые необходимые условия экстремума глад ких функций на предвыпуклых множествах указанных типов; 4) доказана сходимость метода условного градиента (на уровне необходимых условий экстремума) при различных способах выбора величины итерационного шага; 5) доказана сходимость метода проекции градиента для первого из двух указанных типов предвыпуклых ограничений (на уровне необходимых условий экстремума) при различных способах выбора параметров; 6) доказана сходимость метода проекции градиента для второго из двух указанных типов предвыпуклых ограничений (на уровне необходимых условий экстремума) при различных способах выбора величины ите ь рационного шага; 7) проведены расчёты примеров на основе разработанного автором программного обеспечения, реализующего алгоритмы указанных методов для предвыпуклых множеств в виде сферы и-мерного пространства, а так же теоретико-множественной разности двух шаров или выпуклого много гранника и шара двумерного или трёхмерного пространства; к 8) рассмотрены вычислительные аспекты алгоритмов указанных ме тодов, и проведён сравнительный анализ этих алгоритмов при различных способах выбора параметров. Постановка задачи математического программирования с пред вы пуклыми ограничениями, а также формулировки алгоритмов методов про екции градиента и субградиента, изложенные в разделах 2.1, 3.1, 4.1 и 4.2 р диссертации, принадлежат научному руководителю. Доказательство пред ложения 2-ій доказательство леммы 3.1 получены автором диссертации и руководителем совместно. Остальные результаты, полученные в диссертации, принадлежат ее автору. К путям дальнейшего развития полученных в работе результатов можно отнести, в частности, проблему обоснования алгоритмов метода проекции субградиента, рассмотренных в четвёртой главе, проблему раз работки и обоснования новых методов решения задач математического программирования с предвыпуклыми ограничениями, а также проблему обобщения рассмотренных в диссертации алгоритмов на более широкие классы невыпуклых множеств ограничений. Интересной является также г проблема переноса полученных результатов на случай бесконечномерных функциональных пространств.
