- •Программирование численных методов в экстремальных задачах
- •Предисловие
- •Практическое занятие 1. Исследование методов одномерного поиска минимума унимодальных функций
- •1.1. Требования задания
- •1.2. Контрольные вопросы
- •1.3. Содержание отчета
- •Практическое занятие 2. Исследование методов полиномиальной интерполяции для поиска минимума целевых функций
- •2.1. Требования задания
- •2.2. Контрольные вопросы
- •2.3. Содержание отчета
- •Практическое занятие 3. Исследование методов линейного поиска
- •3.1. Требования задания
- •3.2. Контрольные вопросы
- •3.3. Содержание отчета
- •Практическое занятие 4. Исследование градиентных методов
- •4.1. Требования задания
- •4.2. Контрольные вопросы
- •4.3. Содержание отчета
- •Практическое занятие 5. Проектирование программы оптимизации
- •5.1. Требования задания
- •5.2. Контрольные вопросы
- •5.3. Содержание отчета
- •Практическое занятие 6. Исследование модификаций ньютоновских оптимизационных процессов
- •6.1. Требования задания
- •6.2. Контрольные вопросы
- •6.3. Содержание отчета
- •Практическое занятие 7. Исследование методов переменной метрики
- •7.1. Требования задания
- •7.2. Контрольные вопросы
- •7.3. Содержание отчета
- •Практическое занятие 8. Исследование методов сопряженных градиентов
- •8.1. Требования задания
- •8.2. Контрольные вопросы
- •8.3. Содержание отчета
- •Практическое занятие 9. Исследование методов безусловной оптимизации нулевого порядка
- •9.1. Требования задания
- •9.2. Контрольные вопросы
- •9.3. Содержание отчета
- •Практическое занятие 10. Исследование алгоритмов случайного поиска
- •10.1. Требования задания
- •10.2. Контрольные вопросы
- •10.3. Содержание отчета
- •Практическое занятие 11. Исследование методов нелинейного программирования
- •11.1. Требования задания
- •11.2. Контрольные вопросы
- •11.3. Содержание отчета
- •Список литературы
- •1. Метод средней точки (метод Больцано)
- •2. Метод трехточечного поиска на равных интервалах
- •3. Метод Ньютона
- •4. Метод линейной интерполяции (метод секущих)
- •5. Метод кубической интерполяции для одномерной минимизации
- •6. Метод Фибоначчи
- •7. Метод Хука–Дживса с одномерной минимизацией
- •8. Метод Зангвилла
- •9. АлгоритмLPτ-поиска
- •10. Формулы методов переменной метрики
- •11. Минимизация целевых функций в MicrosoftExcel97
- •12. Тестовые функции
- •Содержание
- •197376, С.-Петербург, ул. Проф. Попова, 5
1.2. Контрольные вопросы
Сравнить методы золотого сечения, Фибоначчи и дихотомического поиска по числу вычислений целевой функции для достижения заданной точности.
В чем отличие метода золотого сечения-1 от метода золотого сечения-2?
Как сокращается текущий интервал локализации минимума в методах Фибоначчи-1 и Фибоначчи-2?
Определить достоинства и недостатки методов Ньютона и трехточечного поиска.
Что такое унимодальная функция и каково ее значение в теории оптимизации?
Сформулировать необходимые и достаточные условия минимума функции одной переменной. Как преобразовать задачу на поиск максимума в задачу на минимум?
Указать характерные особенности организации одномерного поиска.
Дать геометрическую интерпретацию двух способов выбора последних точек в методе Фибоначчи.
1.3. Содержание отчета
Цель работы и требования задания.
Краткое описание метода оптимизации на основании материала лекционного курса и описание схемы пошагового выполнения вычислительного алгоритма.
Пооператорная блок-схема программы с пояснением основных ее частей.
Спецификация программы, раскрывающая смысл входных и выходных данных, основных переменных и функций.
Текст программы с детальными комментариями ведущих операторов программы.
Результаты тестирования программы на наборе целевых функций с указанием числа итераций и количества вычислений целевой функции. Таблица, иллюстрирующая вычислительный процесс и изменение ключевых переменных.
Результаты сравнения заданных методов оптимизации по числу итераций при использовании различных критериев окончания поиска, при выборе разных начальных точек x1и при задании различных значений погрешности локализации минимумаε.
Графическая интерпретация процесса оптимального поиска на поле графика целевой функции, построенного средствамиMatlab[8].
Ответы на контрольные вопросы.
Выводы по работе.
Практическое занятие 2. Исследование методов полиномиальной интерполяции для поиска минимума целевых функций
2.1. Требования задания
Цель работы– сравнение двух методов одномерной минимизации – прямого и интерполяционного; разработка программы, реализующей прямой метод на этапе установления границ начального интервала и метод полиномиальной интерполяции для локализации искомого минимума.
Методы одномерной минимизации:
М1 – метод Фибоначчи-1 – Девиса–Свенна–Кемпи(ДСК);
М2 – метод Фибоначчи-2 – ДСК;
М3 – метод дихотомии – Пауэлла;
М4 – метод Больцано – Пауэлла;
М5 – метод золотого сечения-1 – квадратичной интерполяции – экстраполяции;
М6 – метод дихотомии – кубической интерполяции;
М7 – метод линейной интерполяции – кубической интерполяции;
М8 – метод золотого сечения-2 – Пауэлла.
Варианты задания
Вариант |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Метод |
М1 |
М2 |
М3 |
М4 |
М5 |
М6 |
М7 |
М8 |
Тестовая функция |
(2) |
(3) |
(4) |
(5) |
(6) |
(7) |
(8) |
(9) |