Численные методы решения экстремальных задач с предвыпуклыми ограничениями

• Автор: Черняев, Юрий Анатольевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Казань
• Количество страниц: 97 с.

ОГЛАВЛЕНИЕ
Введение

Г лава 1. Метод условного градиента для случая предвыпуклых

ограничений с непустым множеством внутренних точек . .

1.1. Постановка задачи и алгоритм метода

1.2. Необходимые условия экстремума.

1.3. Обоснование алгоритма при первом способе выбора шага

1.4. Обоснование алгоритма при втором способе выбора шага

1.5. Результаты вычислений

Выводы по главе 1

Глава 2. Метод проекции градиента для случая предвыпуклых к ограничений с непустым множеством внутренних точек . .
2.1. Постановка задачи и алгоритм метода
2.2. Обоснование алгоритма при первом способе выбора параметров
2.3. Обоснование алгоритма при втором способе выбора параметров
2.4. Обоснование алгоритма при третьем способе выбора параметров
2.5. Результаты вычислений
Выводы по главе 2
Глава 3. Метод проекции градиента для случая ограничений в виде
выпуклой гладкой поверхности.
3.1. Постановка задачи и алгоритм метода
3.2. Обоснование алгоритма при первом способе выбора шага
3.3. Обоснование алгоритма при втором способе выбора шага
3.4. Результаты вычислений
Выводы по главе 3
Глава 4. Эвристические алгоритмы метода проекции субградиента
для предвыпуклмх множеств ограничений
4.1.1 Остановка задачи и алгоритм для ограничений первого типа . .
4.2. Постановка задачи и алгоритм для ограничений второго типа . .
4.3. Результаты вычислений.
Выводы по главе 4
Заключение
Список литературы


В таких задачах оптимизируемая функция является линейной, а область, на которой ищется экстремум, задана линейными равенствами и неравенствами. Задачи этого класса впервые исследовались Л. В. Канторовичем, одной из первых работ которого по данной тематике является статья []. Для решения задач линейного программирования разработаны конечношаговые методы, одним из которых является известный симплекс-метод, или метод последовательного улучшения плана, разработанный Дж. Данцигом. Кроме конечношаговых алгоритмов, для задач линейного программирования успешно разрабатываются итерационные методы, которые в ряде случаев оказываются более эффективными. Отметим, что задачи линейного программирования приходится решать как вспомогательные при реализации некоторых методов нелинейного программирования. Теории линейного программирования и методам решения задач соответствующего класса посвящена обширная литература, в частности, работы [7, , ], отдельные главы работ [,, , , ] и многочисленные статьи. Многие практические задачи, связанные с нахождением экстремума, сводятся к задачам нелинейного программирования. В таких задачах оптимизируемая функция и ограничения, задающие допустимую область, вообще говоря, не являются линейными. Большое разнообразие задач нелинейного программирования не позволяет разработать метод, пригодный для решения любой задачи. Важнейшим классом таких задач является класс задач выпуклого программирования (оптимизируемая функция и допустимое множество выпуклы). Задачи выпуклого программирования обычно приходится решать итерационными методами, позволяющими получать приближённые решения. Эти задачи, в силу своей специфики, позволяют доказывать сходимость численных методов в смысле необходимых и достаточных условий экстремума. Существуют также методы, для которых теоретически не доказана сходимость, но они тоже эффективно используются на практике. Многие методы выпуклого программирования могут быть применены и для решения некоторых невыпуклых задач. Например, в случае гладких целевых функций и выпуклых ограничений доказывается сходимость некоторых методов в смысле необходимых условий экстремума. Для отдельных классов невыпуклых задач с липшицевы-ми целевыми функциями разработаны специфические методы, позволяющие искать глобальной экстремум многоэкстремальных функций. Ф. П. Васильева [И], В. Г. Карманова [], В. Ф. Демьянова и Л. В. Васильева [], Б. Н. Пшеничного и Ю. М. Данилина [], И. В. Романовского [], В. В. Фёдорова [], М. Аоки [6], У. И. Зангвилла [], Ф. Кларка [] и Д. Химмельблау []. Из многочисленных статей, опубликованных в последние годы, отметим [3, 4, 5, , , , , , ]. Среди задач нелинейного программирования выделяются задачи, в которых допустимой областью является вес пространство - задачи безусловной оптимизации. Для таких задач существуют свои итерационные методы решения, например, градиентные методы, использующие аппарат частных производных первого порядка. Иногда экстремум выпуклой функции может быть найден и без привлечения итерационных процедур. Если же функция не является дифференцируемой, вычисление градиента затруднительно или трудно решить уравнение, из которого определяются точки экстремума, то целесообразно применять методы, не использующие аппарат производных, например, метод деформируемого многогранника, методы покоординатного спуска или методы случайного поиска. Если же функция имеет частные производные первого и второго порядка, которые вычисляются без труда, то можно использовать более точные методы поиска, например, метод Ньютона. Что касается задач оптимизации выпуклых негладких функций с ограничениями или без ограничений, то для их решения могут быть применены методы, использующие те или иные обобщения понятия градиента. Ряд таких методов рассматривается, например, в работах В. Ф. Демьянова, Ф. Кларка, А. М. 1 упала, Н. Шора и др. К числу работ указанных авторов относятся, например, [, , , , ]. Интерес представляют также специфические методы оптимизации овражных функций, поскольку обычные методы в этом случае оказываются, как правило, неэффективными. Ряд таких методов рассмотрен в [].