- •Методические указания к лабораторным работам по курсу лекций "методы оптимизации" Сост. К.В. Демидов, а. В. Духанов
- •Определение количества итераций при заданной точности
- •Метод золотого сечения Алгоритм
- •Определение количества итераций при заданной точности
- •Задание к лабораторной работе
- •Варианты заданий
- •Контрольные вопросы
- •Лабораторная работа №2. Метод ломаных
- •Постановка задачи
- •Теоретическая часть
- •Сходимость и оценка погрешности метода
- •Оценка константы Липшица
- •Задание к лабораторной работе
- •Варианты заданий
- •Сходимость и оценка погрешности метода
- •Метод условного градиента Алгоритм
- •Сходимость метода и оценка погрешности
- •Задание к лабораторной работе
- •Варианты заданий
- •Контрольные вопросы
- •Сходимость метода и оценка погрешности
- •Задание к лабораторной работе
- •Варианты заданий
- •Сходимость метода
- •Задание к лабораторной работе
- •Варианты заданий
- •Список литературы
Министерство образования РФ
Владимирский государственный университет
Кафедра физики и прикладной математики
Методические указания к лабораторным работам по курсу лекций "методы оптимизации" Сост. К.В. Демидов, а. В. Духанов
Владимир 2003
Сост: доц. Демидов, асс. Духанов
Методические указания к лабораторным работам по курсу лекций "Методы оптимизации" /Владим. гос. ун-т; Сост: К.В. Демидов, А.В. Духанов. Владимир, 2003.
В методических указаниях содержатся материалы для лабораторных работ по методам решения задач минимизации функций. Описание каждой лабораторной работы включает краткую постановку задачи, описание используемого метода и варианты индивидуальных заданий.
Пособие предназначено для студентов, обучающихся по специальности «Прикладная математика».
Содержание
Лабораторная работа № 1. Минимизация функций одной переменной методами дихотомии и золотого сечения 4
Лабораторная работа №2. Метод ломаных 9
Лабораторная работа №3. Метод касательных 14
Лабораторная работа №4. Градиентные методы 17
Лабораторная работа №5. Метод покоординатного спуска 24
Лабораторная работа №6. Метод штрафных функций 26
Список литературы 30
Лабораторная работа № 1. Минимизация функций одной переменной методами дихотомии и золотого сечения
Постановка задачи
Используя методы дихотомии и золотого сечения, найти на отрезке точку , в которой достигается минимальное значение унимодальной функции . Вычислить минимальное значение .
Теоретическая часть
Опр. 1. Функция является унимодальной на отрезке , если непрерывна на и , такие, что
1) строго монотонно убывает при (если );
2) строго монотонно возрастает при (если );
3) , при .
Случаи, когда один или два из отрезков вырождаются в точку, не исключаются.
Метод дихотомии (деления отрезка пополам)
Алгоритм
Пусть задана функция унимодальная на отрезке . Выберем значение точности , с которой необходимо найти минимальное значение функции, а также значение , являющееся параметром метода.
Определим точки по формулам:
(1)
Рис. 1. Определение точек и .
Найдем и сравним значения функции в точках . Здесь возможны два случая:
1) (см. рис. 1);
2) .
Определим новый отрезок в зависимости от того, какой из этих случаев имеет место. В первом случае концы отрезка (рис. 1) определяются следующим образом:
, (2)
во втором случае
(3)
Для нового отрезка заново вычисляются точки по формуле (1) и определяется очередной отрезок меньшей длины при помощи формул (2) или (3). Дальнейшие итерации выполняются аналогично. При этом в силу унимодальности функции искомая точка минимума принадлежит каждому из построенных отрезков.
Итерации по определениию отрезков продолжаются до тех пор, пока не будет достигнута заданная точность .
Определение количества итераций при заданной точности
После нахождения к-го отрезка в качестве приближенного значения к точке минимума следует взять середину этого отрезка . В этом случае погрешность решения, т.е. расстояние от точки до множества точек минимума , оценивается сверху величиной, равной половине длины отрезка :
. (5)
Учитывая необходимость достижения заданной точности , получаем, что количество требуемых итераций должно удовлетворять неравенству:
(6)
или
(7)