Методы нулевого порядка минимизации функций многих переменных. Постановка задачи. Описание метод (стр. 2 из 2)
Если fe < fl, то можно расширить симплекс до этой точки: присваиваем точке xh значение xe и заканчиваем итерацию (на шаг 9).
Если fe > fl, то переместились слишком далеко: присваиваем точке xh значение xr и заканчиваем итерацию (на шаг 9).
Если fl < fr < fg, то выбор точки неплохой (новая лучше двух прежних). Присваиваем точке xh значение xr и переходим на шаг 9.
Если fh > fr > fg, то меняем местами значения xr и xh. Также нужно поменять местами значения fr и fh. После этого идём на шаг 6.
Если fr > fh, то просто идём на следующий шаг 6.
В результате (возможно, после переобозначения) fr > fh > fg > fl.
6. «Сжатие». Строим точку xs = βxh + (1 − β)xc и вычисляем в ней значение fs = f(xs).
7. Если fs < fh, то присваиваем точке xh значение xs и идём на шаг 9.
8. Если fs > fh, то первоначальные точки оказались самыми удачными. Делаем «глобальное сжатие» симплекса — гомотетию к точке с наименьшим значением xl:
(3)
9. Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 2.
2.1 Метод полного перебора (метод сеток)
Многомерные задачи, естественно, являются более сложными и трудоемкими, чем одномерные, причем обычно трудности при их решении возрастают при увеличении размерности. Возьмем самый простой по своей идее приближенный метод поиска наименьшего значения функции. Покроем рассматриваемую область сеткой G с шагом h (рисунок 4) и определим значения функции в ее узлах. Сравнивая полученные числа между собой, найдем среди них наименьшее и примем его приближенно за наименьшее значение функции для всей области.
Рисунок 4 – Покрытие рассматриваемой области сеткой G с шагом h
Данный метод используется для решения одномерных задач. Иногда он применяется также для решения двумерных, реже трехмерных задач. Однако для задач большей размерности он практически непригоден из-за слишком большого времени, необходимого для проведения расчетов. Действительно, предположим, что целевая функция зависит от пяти переменных, а область определения G является пятимерным кубом, каждую сторону которого при построении сетки мы делим на 40 частей. Тогда общее число узлов сетки будет равно 415 ≈ 108. Пусть вычисление значения функции в одной точке требует 1000 арифметических операций (это немного для функции пяти переменных). В таком случае общее число операций составит 1011. Если в нашем распоряжении имеется ЭВМ с быстродействием 1 млн. операций в секунду, то для решения задачи с помощью данного метода потребуется 105 секунд, что превышает сутки непрерывной работы. Добавление еще одной независимой переменной увеличит это время в 40 раз. Проведенная оценка показывает, что для больших задач оптимизации метод сплошного перебора непригоден. Иногда сплошной перебор заменяют случайным поиском. В этом случае точки сетки просматриваются не подряд, а в случайном порядке. В результате поиск наименьшего значения целевой функции существенно ускоряется, но теряет свою надежность.
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
1. Ю.В. Губарь «Введение в математическое программирование», ИНТУИТ
2. А.Г.Трифонов «Постановка задачи оптимизации и численные методы ее решения», Консультационный Центр MATLAB
3. Материалы интернет портала «Википедия»: http://ru.wikipedia.org/
4. Н.Н. Калинкин «Численные методы», 1978 г., Наука