- •Одномерная оптимизация
- •Метод дихотомии
- •Метод золотого сечения
- •Метод Ньютона
- •Многомерная оптимизация по направлению
- •Метод дихотомии
- •Метод золотого сечения
- •Метод Ньютона
- •Листинг кода метода дихотомии
- •Тест метода дихотомии
- •Листинг кода метода золотого сечения
- •Тест метода золотого сечения
- •Листинг кода метода Ньютона
- •Тест метода Ньютона
Содержание
1. |
Одномерная оптимизация |
3 |
|
|
1.1. |
Метод дихотомии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
4 |
|
1.2. |
Метод золотого сечения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
5 |
|
1.3. |
Метод Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
6 |
2. |
Многомерная оптимизация по направлению |
7 |
|
|
2.1. |
Метод дихотомии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
8 |
|
2.2. |
Метод золотого сечения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
9 |
|
2.3. |
Метод Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |
10 |
A |
Листинг кода метода дихотомии |
11 |
|
B |
Тест метода дихотомии |
16 |
|
C |
Листинг кода метода золотого сечения |
18 |
|
D |
Тест метода золотого сечения |
24 |
|
E |
Листинг кода метода Ньютона |
26 |
|
F |
Тест метода Ньютона |
31 |
1.Одномерная оптимизация
Дана функция |
|
x6 6x5 + 6x3 10x2 + x |
(1) |
Найти точки экстремума функции. Для справки: минимум функции 1 находится в точке
4:9032 2636:55 . На рисунке 1 это видно.
Рис. 1: Вид функции одной переменной вблизи минимума
3
1.1.Метод дихотомии
Метод дихотомии предполагает деление области поиска пополам для поиска оптимума. В приложении A приведён текст программы, в приложении B приведёт тест метода дихотомии. Метод дихотомии при старте в точке 0 и шаге 0:01 нашёл лишь локальный минимум, при старте в точке 4 с шагом 0:01 метод за 7 шагов нашёл область поиска и за 14 проходов нашёл точку минимума.
Для справки приводится последовательное уменьшение области поиска. i Левый Центр Правый
1 |
4.645 |
4.9674 |
5.2899 |
2 |
4.645 |
4.8062 |
4.9674 |
3 |
4.8062 |
4.8868 |
4.9674 |
4 |
4.8868 |
4.9271 |
4.9674 |
5 |
4.8868 |
4.9070 |
4.9271 |
6 |
4.8868 |
4.8969 |
4.9070 |
7 |
4.8969 |
4.9019 |
4.9070 |
8 |
4.9019 |
4.9045 |
4.9070 |
9 |
4.9019 |
4.9033 |
4.9045 |
10 |
4.9019 |
4.9026 |
4.9033 |
11 |
4.9026 |
4.9029 |
4.9033 |
12 |
4.9029 |
4.9030 |
4.9033 |
13 |
4.9030 |
4.9031 |
4.9033 |
14 |
4.9031 |
4.9032 |
4.9033 |
4
1.2. Метод золотого сечения
Метод золотого сечения предполагает использование константы золотого сечения для по- |
|||||
|
p |
|
1 |
||
|
5 |
||||
иска оптимума. Константа золотого сечения ' = |
|
|
|
. В приложении C приведён текст |
|
2 |
|||||
|
|
программы, в приложении D приведёт тест метода золотого сечения. Метод золотого сечения при старте в точке 0 и шаге 0:01 нашёл лишь локальный минимум, при старте в точке 4 с шагом 0:01 метод за 5 шагов нашёл область поиска и за 20 проходов обнаружил точку минимума.
Для справки приводится последовательное уменьшение области поиска.
i |
Левый |
Центр слева |
Центр справа |
Правый |
1 |
4.4697 |
4.7601 |
4.9395 |
5.2299 |
2 |
4.7601 |
4.9395 |
5.0504 |
5.2299 |
3 |
4.7601 |
4.8710 |
4.9395 |
5.0504 |
4 |
4.7601 |
4.8286 |
4.8710 |
4.9395 |
5 |
4.8286 |
4.8710 |
4.8972 |
4.9395 |
6 |
4.8710 |
4.8972 |
4.9133 |
4.9395 |
7 |
4.8710 |
4.8872 |
4.8972 |
4.9133 |
8 |
4.8872 |
4.8972 |
4.9033 |
4.9133 |
9 |
4.8972 |
4.9033 |
4.9072 |
4.9133 |
10 |
4.8972 |
4.9010 |
4.9033 |
4.9072 |
11 |
4.9010 |
4.9033 |
4.9048 |
4.9072 |
12 |
4.9010 |
4.9024 |
4.9033 |
4.9048 |
13 |
4.9024 |
4.9033 |
4.9039 |
4.9048 |
14 |
4.9024 |
4.9030 |
4.9033 |
4.9039 |
15 |
4.9024 |
4.9028 |
4.9030 |
4.9033 |
16 |
4.9028 |
4.9030 |
4.9031 |
4.9033 |
17 |
4.9030 |
4.9031 |
4.9032 |
4.9033 |
18 |
4.9030 |
4.9031 |
4.9031 |
4.9032 |
19 |
4.9031 |
4.9031 |
4.9032 |
4.9032 |
20 |
4.9031 |
4.9032 |
4.9032 |
4.9032 |
5
1.3.Метод Ньютона
Метод Ньютона предполагает использование первой и второй производной для поиска оптимума. Для поиска каждой точки используется формула 2. В приложении E приведён текст программы, в приложении F приведёт тест метода Ньютона. Метод Ньютона при старте в точке 0 нашёл лишь локальный минимум, при старте в точке 4 метод за 12 проходов обнаружил в точке 4:9032 минимум.
xi+1 = xi |
f0(xi) |
(2) |
|||
f00(xi) |
|
||||
Для справки приводится последовательное нахождение точки минимума. |
|||||
i |
xi |
fi0 |
fi00 |
||
0 |
4 |
-1326.9999 |
123.9999 |
|
|
1 |
14.7016 |
2722885.2642 |
1020662.7659 |
|
|
2 |
12.0338 |
887407.1619 |
420422.5842 |
|
|
3 |
9.9231 |
287979.3043 |
173962.3723 |
|
|
4 |
8.2676 |
92673.0227 |
72632.2956 |
|
|
5 |
6.9917 |
29299.7977 |
30908.5375 |
|
|
6 |
6.0438 |
8894.0599 |
13733.7962 |
|
|
7 |
5.3962 |
2432.9718 |
6756.0001 |
|
|
8 |
5.0360 |
496.0993 |
4131.3997 |
|
|
9 |
4.9160 |
43.3726 |
3421.8178 |
|
|
10 |
4.9033 |
0.4475 |
3351.3439 |
|
|
11 |
4.9032 |
4.9251E-05 |
3350.6060 |
|
6