- •Новокузнецк
- •Общие положения
- •1. Постановка задачи
- •2.1 Поисковые методы.
- •2.1.1 Метод сканирования.
- •2.1.2. Метод циклического координатного поиска Гаусса-Зейделя
- •2.1.2 Метод прямого поиска Хука - Дживса.
- •2.1.3. Метод Розенброка
- •2.2 Методы поиска экстремума функции, использующие расчет значений функции в вершинах многогранника.
- •2.2.1. Симплекс метод
- •2.2.2. Метод Нелдера и Мида.
- •2.3 Методы с использованием производных 1-го порядка
- •2.3.1 Градиентный метод
- •2.3.2. Метод наискорейшего спуска.
- •2.3.3 Метод крутого восхождения.
- •2.4 Методы с использованием производных 2-го порядка
- •2.4.1. Метод сопряженных направлений.
- •Алгоритмы и примеры решения задач многомерной оптимизации
2.1 Поисковые методы.
2.1.1 Метод сканирования.
Простейшим методом является сканирование, которое строится аналогично одномерному поиску. Рассчитывается значение целевой функции в узлах сетки, затем определяется координата, в которой функция принимает минимальное значение. Можно проводить локализацию оптимума. Метод очень прост в реализации. Позволяет найти все локальные и глобальные решения поставленной задачи в заданной области определения критерия, а результаты поиска не зависят от вида целевой функции. Однако у этого метода есть один решающий недостаток. Это большое количество вычислений целевой функции, которое необходимо произвести для достижения требуемой точности. Этот недостаток особенно резко проявляется при применении метода сканирования с постоянным шагом, когда число разбиений для каждой переменной подбирается таким образом, чтобы шаг был соизмерим с точностью.
2.1.2. Метод циклического координатного поиска Гаусса-Зейделя
Метод Гаусса-Зейделя или циклического координатного поиска заключается в том, что на итерациях по каждой переменой определяется минимум целевой функции вдоль направления координатных осей. После чего осуществляется поиск вдоль другой координаты. Поиск по направлениям, совпадающим с координатными осями, можно проводить любым известным методом одномерной оптимизации, например, методом золотого сечения или обратного переменного шага. Таким образом, задача сводится к многократному использованию метода одномерной оптимизации. Очередность варьирования переменных обычно устанавливается произвольно и в процессе поиска не меняется. Точность поиска проверяется по сравнению значений переменных и функции на (k + 1) и (k) итерациях.
Алгоритм метода Гаусса-Зейделя.
Начальный этап. Выбрать начальную точку X(1), и 0 - скаляр, используемый в критерии остановки. Пусть единичные координатные направления. Положить Y(1) = X(1), k = j = 1 и перейти к основному этапу.
Основной этап. Шаг 1. Любым методом одномерной оптимизации найти j* - оптимальное решение задачи минимизации функции f(Y(j) + j) и положить Y(j+1) = Y(j) + j*. Если j n, то заменить j на j + 1 и вернуться к шагу 1. Если j=n, то перейти к шагу 2.
Шаг 2. Положить X(k+1) = Y(n). Если ||X(k+1) - X(k)|| , то остановиться; в противном случае положить Y(1) = X(k+1), заменить k на k + 1, положить j = 1 и перейти к шагу 1.
Пример расчета экстремума функции методом циклического координатного поиска Гаусса-Зейделя.
Постановка задачи. Определить экстремум функции f(X) = (x1 - 2)4 + (х1 - 2х2)2 с точностью =0,01 для начального приближения Х(1)=[2.5; 2.5].
Расчет экстремума методом Гаусса-Зейделя для данной задачи реализован средствами EXСEL. Результаты расчета представлены в таблице 2.1. На рисунке 2.1 приведены линии уровня для данной функции и траектория поиска.
Таблица 2.1.
Результаты расчета минимума функции f(x)=(x1-2)4+(х1-2х2)2 методом Гаусса - Зейделя.
№ |
x1 |
x2 |
f(X) |
λ1 |
λ 2 |
||X(k+1) - X(k)|| |
Критерий | |
|
2.500 |
2.500 |
6.31250 |
|
|
|
| |
1 |
3.000 |
2.500 |
5.00000 |
0.500 |
0.000 |
1.0000 |
не достигнут | |
3.000 |
1.5000 |
1.00000 |
0.000 |
-1.000 | ||||
2 |
2.5898 |
1.5000 |
0.28927 |
-0.410 |
0.000 |
0.2051 |
не достигнут | |
2.5898 |
1.2949 |
0.12097 |
0.000 |
-0.205 | ||||
3 |
2.4304 |
1.2949 |
0.05971 |
-0.159 |
0.000 |
0.0797 |
не достигнут | |
2.4304 |
1.2152 |
0.03430 |
0.000 |
-0.080 | ||||
4 |
2.3469 |
1.2152 |
0.02145 |
-0.083 |
0.000 |
0.0417 |
не достигнут | |
2.3469 |
1.1734 |
0.01448 |
0.000 |
-0.042 | ||||
5 |
2.2953 |
1.1734 |
0.01026 |
-0.052 |
0.000 |
0.0258 |
не достигнут | |
2.2953 |
1.1477 |
0.00761 |
0.000 |
-0.026 | ||||
6 |
2.2601 |
1.1477 |
0.00582 |
-0.035 |
0.000 |
0.0176 |
не достигнут | |
2.2601 |
1.1301 |
0.00458 |
0.000 |
-0.018 | ||||
7 |
2.2344 |
1.1301 |
0.00368 |
-0.026 |
0.000 |
0.0129 |
не достигнут | |
2.2344 |
1.1172 |
0.00302 |
0.000 |
-0.013 | ||||
8 |
2.2146 |
1.1172 |
0.00251 |
-0.020 |
0.000 |
0.0099 |
достигнут | |
2.2146 |
1.1073 |
0.00212 |
0.000 |
-0.010 |
Таким образом, после восьми итераций достигнута заданная точность. С такой точностью найдена оптимальная точка Х*=[2.2146; 1.1073]. Следует отметить, что минимум функции находится в точкеХ*=[2; 1].
Рис.2.1 Графическая иллюстрация поиска экстремума функции методом циклического покоординатного поиска Гаусса Зейделя.