Метод поочередного изменения переменных (метод Гаусса–Зейделя)

Движение к оптимуму (рис.1.4.14) происходит по каждой из осей до частного экстремума. Они чередуются. Первая ось, по которой осуществляется поиск минимума (максимума), выбирается произвольно.

Рис.1.4.14. Оси чередуются

Частный экстремум (по одной переменной) может быть найден любым из методов поиска экстремума функции одной переменной.

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

 

Метод пробных движений

Дается приращение по всем переменным

i – номер переменной, j – номер шага 

и вычисляются значения целевой функции.

Из всех опробованных направлений выбирается то, в котором уменьшение (увеличение) целевой функции наибольшее. В этом направлении делается рабочий шаг h, больший

и находится новая точка, из которой делаются пробные движения. Процедура повторяется до достижения заданной точности поиска. 

 

Поиск по деформируемому многограннику

Графическая иллюстрация (рис.1.4.15) определения новых точек:

Рис.1.4.15. Определение новых точек

Поиск по деформируемому многограннику (метод Нелдера и Мида) основан на использовании нерегулярных многогранников (деформируемых симплексов). Для случая двух переменных регулярный симплекс – равносторонний треугольник (три точки); в случае трех переменных – тетраэдр (четыре точки) и т.д.

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

Наличие оврагов и хребтов целевой функции приводит к необходимости изменять размеры и форму симплекса в процессе поиска.

В методе Нелдера и Мида минимизируется функция n независимых переменных с использованием n + 1 вершин деформируемого многогранника. Каждая величина идентифицируется вектором .

Вершина, в которой значение       максимально, проектируется через центр тяжести оставшихся вершин. Улучшенные значения целевой функции находятся последовательной заменой точки с максимальным значением         на более «хорошие» точки, пока не будет найден минимум