Лабораторная работа по "Методам Оптимизации"

Лабораторная работа по курсу «Методы Оптимизации»

Численные методы нулевого порядка

Общая характеристика методов 0-го порядка

 

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

 

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

Задана функция одной переменной f(x), где a<=x<=b. Требуется с заданной точностью ε найти значение x0, при котором f(x0) минимально.

Рис. 1. Унимодальные функции. На отрезке  [a, b] функция f₁(x) унимодальна, f₂(x) – нет.

Метод дихотомии 

Метод дихотомии также называется методом деления пополам. Необходимым условием для его применения является требование унимодальности целевой функции f(x): на рассматриваемом промежутке [a,b] функция f(x) должна иметь не более одного экстремума (см. рис 1).

Алгоритм

 

1. На начальном этапе отрезок, на котором ищется минимум, задаётся равным интервалу допустимых значений [a,b]
2. Вычисляется положение центра отрезка c=(a+b)/2 и центров его правой и левой половин: x₁=(a+c)/2, x₂=(c+b)/2
3. Вычисляются значения целевой функции в точках f(c), f(x₁), f(x₂)
4. Значения функции в точках c, x₁, x₂ сравниваются, и определяется положение нового, уточнённого интервала поиска. При этом интервал поиска уменьшается в 2 раза:
1. Если f(c) > f(x₁), то новый отрезок: [a,c]
2. Если f(c) > f(x₂), то новый отрезок: [c,b]
3. Иначе новый отрезок: [x₁,x₂]
5. Если длина отрезка меньше заданной точности ε, то алгоритм завершается, иначе осуществляется переход на шаг 2.

Алгоритм проиллюстрирован рис. 2.

 

Рис. 2. Метод дихотомии. Показан случай, когда f(x₁)<f(c)

 

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

Так как каждый последующий отрезок всегда ровно в 2 раза меньше предыдущего, метод дихотомии обеспечивает увеличение точности в 2 раза за каждые 2 вычисления целевой функции, или, в среднем, в 2^1/2 = 1,41... раза на 1 вычисление целевой функции.

 

Метод Фибоначчи

 

Метод Фибоначчи аналогичен методу деления пополам, но вместо деления  отрезка на равные части в нём  используется деление в золотой пропорции: φ = (1 + 5^1/2) / 2 = 1,6817…. Так же , как и метод деления пополам, метод Фибоначчи требует того, чтобы функция была унимодальной.

Алгоритм

1. На начальном этапе выбирается отрезок [a,b] , на котором ищется минимум.
2. Внутри отрезка выбирается точка c, делящая его в золотом отношении, то есть так, что отношение большей части отрезка к меньшей равно отношению всего отрезка к его большей части:

с = a + (b-a)/ φ

3. Определяется положение дополнительной точки x, которая расположена симметрично точке c относительно центра отрезка:

x = a + b - c

4. Вычисляются значения функции f(a), f(b), f(c), f(x).
5. Значения функции сравниваются и определяется новое положение интервала поиска (см. рис 3):
1. Если c>x:
1. Если f(x) < f(c), то новый отрезок: [a, c]
2. Иначе новый отрезок: [x, b]
2. Если c<x: (эта ситуация может возникнуть на втором шаге и далее)
1. Если f(x) < f(c), то новый отрезок: [c, b]
2. Иначе новый отрезок: [a, x]
6. Если длина отрезка стала меньше заранее заданной точности, алгоритм завершается, иначе итерация повторяется с шага 2.

 

Рис. 3. Метод Фибоначчи. Показан случай, когда f(x)<f(c).

 

Особенностью метода Фибоначчи, позволяющей  экономить дорогостоящие вычисления целевой функции f(x), является то, что, начиная со второго шага, значение функции в точке c известно с предыдущего шага, остаётся вычислить только значение в отражённой точке x.

Например, на рис.3 f(x)<f(c), поэтому новым интервалом поиска становится интервал [a,c]. Точка x в этом случае оказывается внутри нового интервала и делит его в золотом отношении, то есть она становится новой точкой c.

Длина интервала поиска на следующем шаге всегда в φ = 1,68… раз меньше длины на предыдущем шаге. Таким образом, за одно вычисление целевой функции метод Фибоначчи увеличивает точность в 1,68… раз, что больше чем соответствующий показатель метода дихотомии (1.41…).

 

Задание на лабораторную работу

 

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

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

Содержание отчёта

Отчет по лабораторной работе должен содержать следующие элементы:

1. Постановка задания
2. Данные варианта
3. Эскиз графика целевой функции на заданном интервале поиска
4. Аналитически найденное значение экстремума
5. Текст программы (можно привести только часть кода, относящуюся непосредственно к реализации алгоритма)
6. Результаты выполнения программы для базовых значений, приведенных в варианте
7. Выводы

 

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

№	Интервал поиска [a, b]	Метод оптимизации	Целевая функция f(x)	Значения свободных  параметров A, B
				A	B
1	[-2; 2]	Дихотомия	Ax2 + Bx	1	-1
2	[0; π/2]	Фибоначчи	A sin(x) + Bx	1	0,5
3	[-1; 3]	Дихотомия	Ax + Bx	2	-1
4	[-2; 2]	Фибоначчи	1 / (x2 + Ax + B)	0	1
5	[1; 5]	Дихотомия	A ln(x) + Bx	2	-1
6	[-1; 5]	Фибоначчи	Ax2 + Bx	2	-4
7	[1; 5]	Дихотомия	A ln(x) + Bx	3	-2
8	[0; π/2]	Фибоначчи	A sin(x) + Bx	2	√2
9	[0; 3]	Дихотомия	Ax + Bx	1,5	-2
10	[-1; 3]	Фибоначчи	1 / (x2 + Ax + B)	1	1
11	[-2; 3]	Дихотомия	Ax2 + Bx	0,5	2
12	[0; 4]	Фибоначчи	1 / (x2 + Ax + B)	2	1
13	[-2; 2]	Дихотомия	Ax + Bx	½	3
14	[0; π/2]	Фибоначчи	A sin(x) + Bx	1	√3 / 2
15	[-1; 4]	Дихотомия	Ax2 + Bx	1	-2
16	[1; 5]	Фибоначчи	A ln(x) + Bx	-7	3
17	[-3; 3]	Дихотомия	Ax + Bx	e	-1
18	[-5; 0]	Фибоначчи	1 / (x2 + Ax + B)	-2	5
19	[1; 7]	Дихотомия	A ln(x) + Bx	6	-3
20	[-1; 2]	Фибоначчи	Ax2 + Bx	2	2
21	[0; π/2]	Дихотомия	A sin(x) + Bx	3	√3

 

Точность, с которой необходимо искать минимум целевой функции, одинакова дял всех вариантов и равна 10^-6.