Файл: Сахарова Людмила Викторовна, Лукьянова Галина Викторовна Методы оптиизации для машинного обучения учебное пособие.doc

точками золотого сечения отрезка [а; b]. Это и объясняет название рассматриваемого метода.2. На каждой итерации исключения отрезков с пробными точками (2.15) одна из них переходит на следующий отрезок и значениеf (x) в этой точке вычислять не следует. Если новым отрезком становится [а; х₂], то на него переходит пробная точка исходного отрезка, становясь его второй пробной точкой (х₂^’= х₁) (рис. 2.7). В случае перехода к отрезку [х₁; b] пробная точка исходного отрезка стано­вится первой пробной точкой отрезка [х₁; b].3. Легко проверить, что х₁=а+b–х₂ , и x₂=а+b–х₁. Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания, не используя формул (2.15).4. В конце вычислений по методу золотого сечения в качестве приближенного значения х* можно взять середину последнего из полученных отрезков .На каждой итерации отрезок поиска точки минимума уменьшается в одном и том же отношении , поэтому в результате п итераций его длина становится . Таким образом, точность _n определения точки х* после п итераций находят из равенства , (2.16)а условием окончания поиска точки х* с точностью  служит неравен­ство _n  .Опишем алгоритм метода золотого сечения.Шаг 1. Найти х₁ и х₂ по формулам (2.15). Вычислитьf (x₁) и f (x₂). Положить , .Шаг 2. Проверка на окончание поиска: если _n > , то перейти к шагу 3, иначе – к шагу 4.

---

Шаг 3. Переход к новому отрезку и новым пробным точкам. Еслиf (x₁)  f (x₂) то положить b=x₂ , x₂=x₁ , f (x₂)  f (x₁), x₁=b–(b–a) и вычислитьf (x₁), иначе – положить a=x₁, x₁= x₂ , f (x₁) = f (x₂), x₂=b+(b–a) и вычислить f (x₂). Положить _n = _n и перейти к шагу 2. Шаг 4. Окончание поиска: положить , .Пример 2.6. Метод золотого сечения.Решить задачу, приведенную в примере 2.3: f (x) =x⁴ +е^–xmin, x [0; 1],  = 0, 1.И т е р а ц и я 1. Шаг 1. Находим: x₁ = 0,382, x₂= 0,618, f (x₁) = 0,704,f (x₂) = 0,685, _n = 0,5. Шаг 2. _n = 0,5 >  =0,1, поэтому переходим к шагу 3.Шаг 3.f (x₁) > f (x₂), поэтому полагаем a= 0,382, x₁ = 0,618, f (x₁) = 0,685, x₂= 0,764, _n = 0,309 и вычисляем f (x₂) = 0,807. Переходим к следующей итера­ции, начиная с шага 2.Результаты вычислений на остальных итерациях представлены в табл. 2.3 (стрелки указывают значения, переходящие на данную итерацию с предыду­щей).Таблица 2.3

Номер Итерации	a	b	n	x1	x2	f (x1)	f (x2)	Сравнение f (x1) и f (x2)
2	0,382	1,000	0,309	0,618	0,764	0,685	0,807	f (x1) < f (x2)
3	0,382	0,764	0,191	0,528	0,618	0,668	0,685	f (x1) < f (x2)
4	0,382	0,618	0,118	0,472	0,528	0,673	0,668	f (x1) > f (x2)
5	0,472	0,618	0,073	0,073 < 0,1 – точность достигнута

---

Таким образом, , f ^*f (0,55) = 0,67 (сравните с решением примеров 2.3–2.5). Замечание. Число итераций, необходимое для достижения за­данной точности , можно найти из условия _n   с учетом соотноше­ния (2.16): .Так как N вычислений f (x) позволяют выполнить N– 1 итераций метода золотого сечения, то достигнутая в результате этих вычислений точность определения х* составляет . (2.17)Второй метод деления отрезка пополам. Этот метод, использующий на каждой итерации три пробные точки, обеспечивает последо­вательное уменьшение длины отрезка, содержащего х*, ровно вдвое. Рассмотрим способ исключения отрезков, применяемый в рассматриваемом методе.Разделим отрезок [a; b] на четыре равные части пробными точками , i=1,2,3. Сравним значения f (x₁) и f (x₂). Если f (x₁)  f (x₂), то уменьшенный вдвое отрезок поиска точки х* найден – это [а; х₂]. Если f (x₁) > f (x₂), то произведем еще одно сравнение значений f (x): при f (x₂)f (x₃), перейдем к отрезку [x₁; х₃],а в противном случае – к отрезку [x₂; b].Отметим, что каким бы ни оказался новый отрезок, одна из уже использованных пробных точек переходит на его середину, становясь новой точкой x₂ . Таким образом, для проведения следующей итерации на вновь полученном отрезке потребуется вычисление не более двух новых значенийf (x) (либо только в точке x₁, либо еще и в точке x₃).Перечислим основные шаги алгоритма второго метода деления отрезка пополам.Шаг 1. Положить . Вычислить значение f (x₂) и перейти к шагу 2. Шаг 2. Положить . Вычислить значение f (x₁) и перейти к шагу 3.Шаг 3. Сравнить f (x₁) и f (x₂). Если f (x₁)  f (x₂), то продолжить поиск на отрезке [

---

а;x₂], положив b= x₂, x₂= x₁, f (x₁) = f (x₂), и перейти к шагу 5, иначе – положить , вычислить значение f (x₃) и перейти к шагу 4. Шаг 4. Сравнить f (x₂) и f (x₃). Если f (x₂)  f (x₃), то перейти к от­резку [x₁; x₃], положив a= x₁, b =x₃, иначе – продолжить поиск на от­резке [x₂; b], положив а =x₂, x₂ = x₃, f (x₂)= f (x₃). Перейти к шагу 5.Шаг 5. Проверка на окончание поиска. Вычислить и сравнить с . Если _n> , то перейти к следующей итерации, вернув­шись к шагу 2, иначе – завершить поиск, положив х*  x₂ , f ^*  f (x₂). Пример 2.7. Второй метод деления отрезка пополам. Решить задачу, приведенную в примере 2.3: f (x) = x⁴ +e^–x min, x[0;1], =0,1. И т е р а ц и я 1. Шаг 1. Находим x₂=0,5, f (x₂) = 0,669. Переходим к шагу 2.Шаг 2. Определяем x₁ = 0,25, f (x₁) = 0,783. Переходим к шагу 3.Шаг 3.f (x₁) > f (x₂), поэтому полагаем x₃ = 0,75, вычисляем f (x₃) = 0,789 и переходим к шагу 4.Шаг 4.f (x₁) < f (x₂), поэтому полагаем а = 0,25, b = 0,75 и переходим к шагу 5.Шаг 5. Находим _n= 0,25 > 0,1, т.е. переходим к следующей итерации, начиная с шага 2.Результаты вычислений на остальных итерациях записаны в табл. 2.4.Таблица 2.4

Номер итера­ции	а	b	n	x1	x2	x3	f (x1)	f (x2)	f (x3)	Сравнение f (x1) и f (x2)
2	0,250	0,750	0,25	0,375	0,500	0,625	0,707	0,669	0,688	f (x1) > f (x2) f (x2) < f (x3)
3	0,375	0,625	0,13	0,438	0,500	0,563	0.669	0,669	0,670	f (x1) > f (x2) f (x2) < f (x3)
4	0,438	0,563	0,06	0,06 < 0,1 – точность достигнута

---

Таким образом, x*  x₂ = 0,5, f *  f (x₂) = 0,67. Сравните этот ответ с ре­зультатами решения предыдущих примеров.Замечание. На первой итерации второго метода деления отрезка пополам вычисляется не более трех значений f (x) а на ос­тальных – не более двух. Поэтому N вычислений f (x) гарантируют осуществление (N–1)/2 итераций, и достигнутая точность определе­ния x* составляет . (2.18)Сравнение методов исключения отрезков и перебора. При срав­нении прямых методов минимизации обычно учитывают количество N значений f (x), гарантирующее заданную точность определения точки х* тем или иным методом. Чем меньше N, тем эффективнее считается метод. При этом вспомогательные операции такие, как выбор пробных точек, сравнение значений f (x) и т.п., не учитываются. Во многих прак­тических случаях определение значений целевой функции требует больших затрат (например, времени ЭВМ или средств для проведения экспериментов) и вспомогательными вычислениями можно пренеб­речь. А эффективность метода минимизации особенно важна именно в таких случаях, поскольку позволяет сократить указанные затраты.Эффективность методов минимизации можно также сравнивать, на основании гарантированной точности (N) нахождения точки х*, которую они обеспечивают в результате определения N значений f (x). Из анализа формул (2.10), (2.14), (2.17) и (2.18) следует, что наиболее эффектив­ным из сравниваемых методов является метод золотого сечения, за ним идут методы деления отрезка пополам и наименее эффективен метод перебора. Этот вывод иллюстрирует табл. 2.5 значений достиг­нутой точности (N) в зависимости от количества N найденных значе­нийf (x) на отрезке длины 1 для указанных методов.Таблица 2.5

Методы минимизации	Количество найденных значений f (x)
	N = 5	N = 11	N = 21	N = 51
Метод золотого сечения	0,073	4,1 10–3	3,3 10–5	1,8 10–11
Методы деления отрезка пополам *)	0,125	1,6 10–2	4,9 10–4	1,5 10–8
Метод перебора	0,250	0,100	0,050	0,020

---