Методы поиска экстремума функций многих переменных

Метод случайного поиска

Random-walk method

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

Метод половинного деления один из методов решения нелинейных уравнений и основан на последовательном сужении интервала, содержащего единственный корень уравнения F(x)=0 до того времени, пока не будет достигнута заданная точность Е. Метод используется при решении квадртных уравнений и уравнений высших степеней. Достоинство метода половинного деления: более быстрая сходимость к заданной точности, чем у шагового. Недостаток: если на отрезке [а,b] содержится более одного корня, то метод не работает.

Методы поиска экстремума функций многих переменных

Методы поиска экстремумов функций f (х ₁,..., х_n) подразделяются на градиентные и безградиентные по следующему признаку: градиентные основаны на вычислении и анализе частных производных функции f (х ₁,..., х_n), безградиентные не используют значений производных.

Будем рассматривать эти методы как методы поиска min f (x ₁, x ₂,..., x_n). Вначале рассмотрим некоторые градиентные методы.

.4.1 Метод координатного спуска

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

к увеличению значения целевой функции (рисунок 2.9).

Методы градиента Идея методов: Каждая следующая точка поиска min f (x ₁, x ₂,..., x_n) (каждый новый член минимизирующей последовательности) получается в результате перемещения из предыдущей точки по направлению антиградиента целевой функции.

Метод наискорейшего спуска

Так называют модификацию метода градиента с постоянным шагом, позволяющую сократить общий объем вычислений при некотором увеличении числа членов минимизирующей последовательности за счет меньшего количества вычислений частных производных целевой функции. При использовании этого метода аргументы целевой функции изменяются в соответствии с выражением (2.8), но значения ее производных не пересчитываются до тех пор, пока не сложится ситуация f (х ₁^{(k +1)}, х ₂^{(k +1)},..., х_n ^{(k +1)}) ³ f (х ₁^(k), х ₂^(k),..., х_n ^(k)) (рисунок 2.12). Дробление шага поиска производится, когда во вновь выбранном направлении (после пересчета значений частных производных) не удается сделать ни одного результативного шага, останов поиска – при выполнении неравенства (2.6).