|
Часть
I. Элементы теории
1. Постановка задач
оптимизации. Локальный и глобальный
экстремумы. Классификация
экстремальных задач (ЭЗ). Примеры.
2.
Выпуклые множества. Пересечение и
линейная комбинация выпуклых множеств,
их свойства.
3.
Конус, выпуклый конус. Аффинное
множество, две формы представления
аффинного множества.
4.
Выпуклая, неотрицательная и аффинная
комбинация точек. Выпуклая, коническая и
аффинная оболочки множеств. Их связь с
комбинациями точек.
5.
Относительная внутренность и
относительная граница множества.
Свойства относительной внутренности
выпуклого множества.
6.
Проекция точки на множество. Свойства
проекций.
7.
Отделимость множеств. Свойства
отделимости выпуклых множеств.
8.
Опорная гиперплоскость. Существование
опорной гиперплоскости.
9.
Сопряженное множество. Второе
сопряженное множество. Их свойства.
10.
Сопряженный конус и сопряженное
линейное подпространство.
11.
Конус двойственный к сумме конусов и
конус, сопряженный к пересечению
конусов.
12.
Многогранные множества, полиэдры.
Множество, сопряженное к многогранному
множеству.
13.
Выпуклые, строго и сильно выпуклые
функции. Определения, примеры, свойства.
14.
Непрерывность и дифференцируемость по
направлению выпуклой функции.
15.
Множество уровня выпуклой и сильно
выпуклой функции.
16.
Дифференциальные критерии выпуклой (сильно
выпуклой) функции.
17.
Эпиграф функции, свойства эпиграфа
выпуклой функции.
18.
Субдифференциал функции. Существование
и свойства субдифференциала.
19.
Теорема о субдифференциале суммы
выпуклых функций.
20.
Индикаторная функция множества.
Субдифференциал индикаторной функции
выпуклого множества.
21.
Субдифференциал выпуклой на
функции на
выпуклом множестве.
22.
Теорема Вейерштрасса и её следствия.
Выпуклая экстремальная задача. Теорема
о глобальном экстремуме.
23.Условия
оптимальности экстремальных задач в
терминах субдифференциалов.
24.
Касательное направление, касательный
конус. Конус возможных направлений. Их
свойства.
25.
Производная функции по касательному
направлению. Теорема о необходимом
условии экстремума в терминах
производных по касательному
направлению.
26.
Необходимое условие экстремума в
терминах касательных направлений для
дифференцируемых функций.
27.
Необходимое и достаточное условие
экстремума для выпуклой ЭЗ в терминах
производных по направлению.
28.
Необходимое и необходимое и достаточное
условия экстремума дифференцируемой
функции на выпуклом множестве.
29.
Необходимые и достаточные условия
экстремума для задачи безусловной
минимизации (БМ).
30.
Регулярные и нерегулярные множества.
Необходимое условие экстремума для
регулярной ЭЗ на пересечении множеств.
31.
Необходимое и достаточное условия
экстремума для классической задачи (КЗ)
на условный экстремум. Регулярная и
нерегулярная КЗ.
32.
Необходимое и достаточное условия
задачи математического
программирования (МП). Регулярная и
нерегулярная задачи МП.
33.
Необходимое и достаточное условия общей
здачи математического программирования
(ОМП). Регулярная и нерегулярная задачи
ОМП.
34.
Необходимое и достаточное условия
выпуклой задачи ОМП. Регулярная и
нерегулярная выпуклые задачи ОМП.
35.
Седловая точка функции Лагранжа задачи
ОМП. Её свойства.
36.
Двойственная задача ОМП. Двойственная
задача линейного программирования (ЛП),
их свойства.
Часть
2. Численные методы
1.
Унимодальные функции одной переменной.
Метод дихотомии, свойства его
сходимости.
2.
Метод Фибоначчи, свойства его
сходимости.
3.
Метод золотого сечения, свойства его
сходимости.
4.
Понятие о численных методах оптимизации.
Сходимость методов оптимизации. Условия
остановки численных методов.
5.
Общая схема исследования итерационных
методов решения задачи БМ. Конус
направлений убывания. Два способа
выбора шага в одномерном поиске.
6.
Класс градиентно-согласованных методов.
Свойства его сходимости.
7.
Градиентный метод решения задач БМ. Его
свойства.
8.
Метод Ньютона решения задачи БМ.
Свойства его сходимости.
9.
Метод сопряженных градиентов для
минимизации квадратичных функций.
Свойства его сходимости.
10.
Метод сопряженных градиентов для
решения задач БМ.
11.
Аппроксимационные методы решения задач
БМ и систем нелинейных уравнений.
12.
Задача линейного программирования (ЛП).
Общая, каноническая и другие формы
задачи ЛП. Преобразование условий
задачи ЛП к желаемой форме.
13.
Угловые точки в задаче ЛП.
Алгебраический критерий угловой точки.
14.
Симплекс-метод (СМ) решения задачи ЛП.
Достаточное условие экстремума.
Табличная форма СМ.
15.
Модифицированный СМ решения задачи ЛП.
16.
Двухфазный симплекс-метод.
17.
М-задача решения задачи ЛП.
18.
Метод проекции градиента.
19.
Метод условного градиента.
20.
Общая схема метода штрафных функций.
21.
Метод внешних штрафных функций,
свойства его сходимости.
22.
Метод внутренних штрафных функций,
свойства его сходимости.
23.
Метод возможных направлений.
24.
Метод модифицированной функции
Лагранжа.
25.
Методы дискретной оптимизации. Метод
Гомори (отсечений).
26.
Методы дискретной оптимизации. Метод
ветвей и границ. |
