Министерство образования и науки РФ

Федеральное государственное автономное образовательное учреждение высшего образования

Национальный исследовательский

Томский политехнический университет

УТВЕРЖДАЮ

Зам. директора ИК

по учебной работе

_____________

«___»_________________2015 г.

МЕТОДЫ ОПТИМИЗАЦИИ

Методические указания к выполнению лабораторной работы № 2

«Численные методы одномерной минимизации с использованием производной»

по дисциплине

«Методы оптимизации»

для студентов направления 01.03.02

«Прикладная математика и информатика»

Томск 2015 г.

УДК 519.8 ББК 22.14

Методы оптимизации. Методические указания к выполнению лабораторной работы № 2. «Численные методы одномерной минимизации с использованием производной» по дисциплине «Методы оптимизации» для студентов направления 01.03.02 «Прикладная математика и информатика». – Томск: Изд. НИ ТПУ, 2015. – 11 с.

Составитель – доц. канд. техн. наук

Резензент – доц. канд. техн. наук

Методические указания рассмотрены и рекомендованы к изучению методическим семинаром кафедры прикладной математики «___»_________2015 г.

Зав. кафедрой

Доцент, к. т.н. _________________

Лабораторная работа № 2

Тема: Численные методы одномерной минимизации с использованием производной.

Цель работы: Приобретение практических навыков для решения задач одномерной минимизации численными методами.

Постановка задачи

Требуется найти безусловный минимум функции одной переменной , то есть, такую точку , что .

Методы, рассмотренные в лабораторной работе 1, используются при минимальных требованиях к целевой функции - она должна быть унимодальной.

НЕ нашли? Не то? Что вы ищете?

В данной работе предполагается, что целевая функция является выпуклой и дифференцируемой (один раз или дважды). Причем, производная может быть вычислена в произвольно выбранных точках. Считается, что эффективность методов, использующих информацию о производных при поиске точки минимума можно существенно повысить.

Численные методы одномерной минимизации с использованием производной

К основным численным методам одномерной минимизации с использованием производной относят:

- метод средней точки;

- метод хорд;

- метод Ньютона;

- метод кубической аппроксимации и др.

1. Метод средней точки [1]

Метод средней точки направлен на повышение эффективности метода деления отрезка пополам при использовании технологии исключения отрезков за счет замены вычислений функции в трех точках на операцию вычисления производной в средней точке .

Если , то точка лежит на участке монотонного возрастания , поэтому и точку минимума следует искать на отрезке .

Если , то точка лежит на участке монотонного убывания , поэтому и точку минимума следует искать на отрезке .

Равенство означает, что точка минимума найдена точно и .

Такое исключение отрезков требует на каждой итерации только одного вычисления и уменьшает отрезок поиска точки минимума ровно в два раза.

Поиск заканчивается, если абсолютная величина производной меньше заданной погрешности.

Алгоритм поиска точки минимума методом средней точки

Алгоритм поиска минимума функции сводится к выполнению следующих этапов.

1 этап. Задается начальный интервал неопределенности и - требуемая точность.

2 этап. Задать .

3 этап. Вычислить среднюю точку .

4 этап. Проверить условие окончания:

- если , то процесс поиска завершается и ;

- если , то сравнить с нулем.

Если , то продолжить поиск на отрезке , положив , .

Если , то продолжить поиск на отрезке , положив ,.

Перейти к этапу 3.

2. Метод хорд [1]

Метод хорд опирается на равенство , которое является необходимым и достаточным условием глобального минимума выпуклой дифференцируемой функции .

Если на концах отрезка производная имеет разные знаки, то на интервале найдется точка, в которой и поиск точки минимума на отрезке эквивалентен решению уравнения

, .

Таким образом, любой приближенный метод решения уравнения , можно рассматривать как метод минимизации выпуклой дифференцируемой функции на отрезке . Одним из таких методов является метод хорд. Он основан на исключении отрезка путем определения точки

пересечения с осью хорды графика функции на очередном отрезке.

Отрезок дальнейшего поиска определяется по следующему правилу.

Новыми точками отрезка для осуществления следующей итерации являются концы того из отрезков и , который содержит точку . Его определяют по знаку производной .

Если , то точка лежит на участке монотонного возрастания , поэтому и точку минимума следует искать на отрезке , то есть .

Если , то точка лежит на участке монотонного убывания , поэтому и точку минимума следует искать на отрезке , то есть .

Равенство означает, что точка минимума найдена точно и .

На каждой итерации, кроме первой, следует вычислять одно новое значение .

Поиск заканчивается, если абсолютная величина производной меньше заданной погрешности.

Алгоритм поиска точки минимума методом хорд

Алгоритм поиска минимума функции методом хорд сводится к выполнению следующих этапов.

1 этап. Задается начальный интервал неопределенности и - требуемая точность, - малое положительное число.

2 этап. Задать . Вычислить .

Если , то перейти к этапу 3, иначе к этапу 5.

3 этап. Вычислить.

4 этап. Проверить условие окончания:

- если , то процесс поиска завершается и ;

- если , то сравнить с нулем.

Если , то продолжить поиск на отрезке , положив , .

Если , то продолжить поиск на отрезке , положив ,.

Перейти на этап 3.

5 этап. Если , то возрастает на отрезке и, следовательно, .

Если , то убывает на отрезке и, следовательно, .

Если , то или , в зависимости от того, на каком из концов отрезка производная .

3. Метод Ньютона [1]

Предполагается, что функция дважды дифференцируема, причем . Тогда для поиска корня уравнения используется метод касательных. Сущность метода заключается в том, что в очередной точке строится линейная аппроксимация функции (касательная к графику ), а точка, в которой линейная аппроксимирующая функция обращается в нуль, используется в качестве следующего приближения .

Координата точки находится по формуле

где - начальная точка выбирается пользователем. Вычисления по приведенной формуле продолжаются до тех пор, пока не выполнится условие

, после чего полагают .

Алгоритм поиска точки минимума методом Ньютона

Алгоритм поиска минимума функции методом Ньютона сводится к выполнению следующих этапов.

1 этап. Задается начальный интервал неопределенности и - требуемая точность.

2 этап. Задать и начальную точку .

3 этап. Вычислить . Проверить условие окончания:

- если , то процесс поиска завершается и ;

- если , то вычислитьи если перейти к этапу 4. В противном случае закончить вычисление связи с нарушением обязательного условия.

4 этап. Вычислить .

5 этап. Принять и перейти к этапу 3.

Примечание. В связи с выбором начального приближения , удаленного достаточно далеко от искомого решения, возможно, что последовательность будет расходиться. В этом случае рекомендуется найти лучшее начальное приближение другим методом (метод золотого сечения и т. д.).

4. Метод кубической аппроксимации [1]

В этом методе полиномиальной аппроксимации в качестве аппроксимирующего полинома используется многочлен третьей степени. Предполагается, что - выпуклая дифференцируемая функция и найден интервал , содержащий ее точку минимума . Это означает, что , а .

Аппроксимирующий кубический полином записывается в виде

где неизвестными являются коэффициенты .

Для определения неизвестных коэффициентов предполагается, что в точках и значения функции и аппроксимирующего полинома совпадают. Это позволяет найти два коэффициента. Для определения недостающих двух коэффициентов дополнительно полагают, что в точках и равны и их производные

Тогда уравнения для определения коэффициентов аппроксимирующего полинома примут вид

Для определения точки минимума производная приравнивается нулю. В результате получается квадратное уравнение, имеющее два корня. Из двух корней выбирается тот, который принадлежит интервалу . Этот корень является точкой минимума приближения на отрезке и используется в качестве приближения к точке минимума .

Новыми точками и для осуществления следующей итерации являются концы того из отрезков и , который содержит точку . Его определяют по знаку производной .

Если , то точка лежит на участке монотонного возрастания , поэтому и точку минимума следует искать на отрезке .

Если , то точка лежит на участке монотонного убывания , поэтому и точку минимума следует искать на отрезке .

Равенство означает, что точка минимума найдена точно и .

Алгоритм поиска точки минимума с кубической аппроксимацией [1]

Алгоритм поиска точки минимума с кубической интерполяцией [2]

Алгоритм поиска минимума функции с кубической интерполяцией сводится к выполнению следующих этапов.

1 этап. Задать начальную точку , величину шага , - малые положительные числа, характеризующие точность (,).

2 этап. Вычислить производную .

3 этап. Проверить знак производной в точке .

Если , то вычислить . до точки , в которой .

4 этап. Положить и вычислить .

5 этап. Найти точку минимума кубического интерполяционного полинома по формуле

где , , .

Вычислить .

6 этап. Проверить условие убывания.

Если , перейти к этапу 7.

Если , вычислить по формуле до тех пор, пока не будет выполнено неравенство .

7 этап. Проверить выполнение условий окончания:

, .

Если оба условия выполнены, то процедура поиска точки минимума закончена и .

Если хотя бы одно из условий не выполнено, то положить либо при , либо при .

Перейти к шагу 5.

Примечание. На этапах 2-3 реализуется эвристическая процедура поиска границ интервала неопределенности, где изменение знака производной свидетельствует о переходе через точку минимума.

Варианты заданий

Варианты заданий приведены в таблице.

Таблица. Варианты заданий

№	F(*X) =*	*Тип экстремума*	*Исходный интервал*	*Погрешность*
1		max	[4; 9]	0.02
2		min	[-1; 0]	0.005
3		max	[4; 9]	0.02
4		min	[-1; 0]	0.005
5		min	[0.5; 1]	0.001
6		min	[-2; 0]	0.01
7		min	[-1.5; 3]	0.01
8		min	[1.3; 3.0]	0.01
9		max	[0; 3]	0.02
10		min	[0; 2.5]	0.02
11		max	[0.8; 2.0]	0.008
12		min	[0; 1.5]	0.01
13		min	[1; 3]	0.012
14		max	[0; 3]	0.02
15		max	[-1; 0.5]	0.005
16		min	[0; 2]	0.01
17		min	[0; 2]	0.01
18		min	[-1; 0]	0.002
19		min	[0; 1]	0.005
20		min	[-1; 1]	0.01
21		max	[2; 6]	0.02
22		min	[0; 2]	0.01
23		min	[0.5; 2]	0.01
24		min	[0; 1.5]	0.01
25		min	[0.5; 2]	0.005
26		min	[0; 2]	0.005