Министерство образования и науки РФ
Федеральное государственное автономное образовательное учреждение высшего образования
Национальный исследовательский
Томский политехнический университет
УТВЕРЖДАЮ
Зам. директора ИК
по учебной работе
_____________
«___»_________________2015 г.
МЕТОДЫ ОПТИМИЗАЦИИ
Методические указания к выполнению лабораторной работы № 5
«Численные методы многомерной минимизации c использованием производных второго порядка»
по дисциплине
«Методы оптимизации»
для студентов направления 01.03.02
«Прикладная математика и информатика»
Томск 2015 г.
УДК 519.8 ББК 22.14
Методы оптимизации. Методические указания к выполнению лабораторной работы № 5. «Численные методы многомерной минимизации c использованием производных второго порядка» по дисциплине «Методы оптимизации» для студентов направления 01.03.02 «Прикладная математика и информатика». – Томск: Изд. НИ ТПУ, 2015. – 7 с.
Составитель – доц. канд. техн. наук
Резензент – доц. канд. техн. наук
Методические указания рассмотрены и рекомендованы к изучению методическим семинаром кафедры прикладной математики «___»_________2015 г.
Зав. кафедрой
Доцент, к. т.н. _________________
Лабораторная работа № 5
Тема: Численные методы многомерной минимизации c использованием производных второго порядка.
Цель работы: Приобретение практических навыков для решения задач многомерной минимизации численными методами второго порядка.
1. Постановка задачи
Требуется найти безусловный минимум функции многих переменных 
, то есть, такую точку 
, что
. (1)
2. Методы безусловной оптимизации
Для заданной начальной точки 
генерируется последовательность точек с координатами 
Переход от точки 
к точке 
представляет собой итерацию. Численное решение задачи (1) связано с построением последовательности точек 
, обладающих свойством
. (2)
Общее правило построения последовательности имеет вид
где 
- направление поиска точки из точки , а число 
- величина шага, которая выбирается так, чтобы выполнялось условие .
Эти алгоритмы различаются способом построения вектора и выбора шага
3. Методы второго порядка
К методам второго порядка относят:
- метод Ньютона;
- метод Ньютона-Рафсона;
- метод Марквардта.
3.1. Метод Ньютона
Алгоритм метода Ньютона состоит из следующих этапов.
1 этап. Задать начальную точку 
, погрешности расчета 
, 
, 
- предельное число итераций. Найти градиент функции в произвольной точке 
и матрицу Гессе 
.
2 этап. Принять 
.
3 этап. Вычислить 
.
4 этап. Проверить выполнение критерия окончания 
:
А) если критерий выполнен, расчет закончен 
;
Б) если критерий не выполнен, то перейти к этапу 5;
5 этап. Проверить выполнение неравенства 
:
А) если неравенство выполнено, то расчет окончен: ;
Б) если нет, то перейти к этапу 6.
6 этап. Вычислить матрицу 
.
7 этап. Вычислить матрицу 
.
8 этап. Проверить выполнение условия 
:
А) если , то перейти к этапу 9;
Б) если 
, то перейти к этапу 10, приняв 
9 этап. Определить 
.
10 этап. Вычислить 
, приняв 
, если или выбрав 
из условия 
если .
11 этап. Проверить выполнение условий
А) если оба условия выполнены при текущем значении 
и 
, то расчет окончен и 
;
Б) если хотя бы одно из условий не выполнено, то принять 
и перейти к этапу 3.
3.2. Метод Ньютона-Рафсона
Алгоритм метода Ньютона-Рафсона состоит из следующих этапов.
1 этап. Задать начальную точку , погрешности расчета , , - предельное число итераций. Найти градиент функции в произвольной точке и матрицу Гессе .
2 этап. Принять .
3 этап. Вычислить .
4 этап. Проверить выполнение критерия окончания :
А) если критерий выполнен, расчет закончен ;
Б) если критерий не выполнен, то перейти к этапу 5;
5 этап. Проверить выполнение неравенства :
А) если неравенство выполнено, то расчет окончен: ;
Б) если нет, то перейти к этапу 6.
6 этап. Вычислить матрицу .
7 этап. Вычислить матрицу .
8 этап. Проверить выполнение условия :
А) если , то найти ;
Б) если , то принять .
9 этап. Найти шаг 
из условия 
10 этап. Вычислить 
.
11 этап. Проверить выполнение условий
А) если оба условия выполнены при текущем значении и , то расчет окончен и ;
Б) если хотя бы одно из условий не выполнено, то принять и перейти к этапу 3.
3.3. Метод Марквардта
Алгоритм метода Марквардта состоит из следующих этапов.
1 этап. Задать начальную точку , погрешности расчета , , - предельное число итераций. Найти градиент функции в произвольной точке и матрицу Гессе .
2 этап. Принять 
.
3 этап. Вычислить .
4 этап. Проверить выполнение критерия окончания :
А) если критерий выполнен, расчет закончен ;
Б) если критерий не выполнен, то перейти к этапу 5;
5 этап. Проверить выполнение неравенства :
А) если неравенство выполнено, то расчет окончен: ;
Б) если нет, то перейти к этапу 6.
6 этап. Вычислить матрицу .
7 этап. Вычислить матрицу 
.
8 этап. Вычислить матрицу 
.
9 этап. Вычислить 
.
10 этап. Вычислить 
.
11 этап. Проверить выполнение условия
А) если условие выполняется, то перейти к этапу 12;
Б) если нет, то перейти к этапу 13.
12 этап. Принять 
и перейти к этапу 3.
13 этап. Принять 
и перейти к этапу 7.
Варианты заданий
Варианты заданий приведены в таблице.
Таблица. Варианты заданий
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10.
11.
12.
13.
14.
15.
16.
17.
18.
Задание
1. Составить блок-схемы алгоритмов поиска точки экстремума заданной функции.
2. По разработанным алгоритмам составить программы поиска минимума функции.
3. Найти координаты и значение функции в точке минимума одним из методов (по желанию).
4. Найти точное значение координаты точки минимума, используя необходимые и достаточные условия экстремума.
5. Проанализировать полученные результаты и сделать выводы по достигнутой точности и количеству вычислений функции.
6. Дать письменные ответы на контрольные вопросы.
Контрольные вопросы
1. Главные отличительные признаки методов второго порядка от методов первого и нулевого порядков.
2. Отличия метода Ньютона от метода Ньютона-Рафсона и от метода Марквардта.
Содержание отчета
1. Цель работы.
2. Формулировка задачи.
3. Блок-схемы алгоритмов поиска минимума.
4. Листинги программ.
5. Графическое представление траекторий движения к экстремуму, полученных соответствующими методами.
6. Результаты вычислений.
7. Сравнительная характеристика методов.
8. Выводы.
Литература
1. , Летова оптимизации в примерах и задачах: Учебное пособие. – М.: Высш. шк., 2002. -544с.
2. , Лисовец методов оптимизации: Учебное пособие. – СПб.: Издательство «Лань», 2011. – 352 с.
Временной ресурс:
- аудиторные занятия – 4 часа;
- самостоятельная работа – 9 часов.
Итоговая оценка защиты лабораторной работы
Всего: 9 баллов, в том числе:
- метод Ньютона - 3 балла;
- метод Ньютона-Рафсона – 3 балла;
- метод Марквардта – 3 балла.
Численные методы многомерной минимизации c использованием производных второго порядка
Методические указания к выполнению лабораторной работы
Составитель – Юрий Владимирович Бабушкин
Подписано к печати ___._______. 2015г.
Формат 60*84/16. Бумага офсетная.
Плоская печать. Усл. печ. л. _____. Уч. – изд. л. ____.
Тираж 150 экз. Заказ ____. Цена свободная.
ИПФ НИ ТПУ. Лицензия ЛТ № 1 от 18.07.94.
Типография НИ ТПУ. 634034, Томск, пр. Ленина, 30.
