![](/user_photo/2706_HbeT2.jpg)
- •Методические указания к лабораторным работам по курсу лекций "методы оптимизации" Сост. К.В. Демидов, а. В. Духанов
- •Определение количества итераций при заданной точности
- •Метод золотого сечения Алгоритм
- •Определение количества итераций при заданной точности
- •Задание к лабораторной работе
- •Варианты заданий
- •Контрольные вопросы
- •Лабораторная работа №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)