Описание метода решения и расчетного алгоритма

Метод градиента основан на том, что вектор градиента в каждой точке Х Î ХN совпадает с направлением наискорейшего возрастания функции.

Требуется найти: minF(X), если XÎ XN, x=x(x₁, x₂ ,.., x_n), N=1,..,.n.

Алгоритм метода.

1. Выбор стартовой точки Хо.

2. Вычислить F(X) и gradF(X)

3. Из точки х₁₁ и из любой точки х_i,k в антиградиентном направлении с шагом h_i в x_i,k+1 и т.д. по формуле:

где « – » из-за антиградиентного направления.

4. Вычисление F(X) на каждом шаге, если F_k+1 < F_k, то

Графическая интерпретация метода градиента для двумерного случая приведена на рисунке 1. Целевая функция отображена линиями уровней: F(x)=const=a, а траектория движения к точке оптимума – {х₀, х₁, х₂, х₃ , х₄, х₅}

x1

x2

a0 a1 a2 a3 a4 a5

x0

x1

x3

x2

x4

x5

Рисунок 1 - Траектория движения к точке оптимума по методу градиента

Вычисление градиента в точке x₀ начинается с серии пробных шагов. Сначала величине x₁ дается небольшое приращение ∆ x₁> 0, причем в это время x₂ неизменно. Затем определяется полученное при этом приращении значение ΔF, которое можно считать пропорциональным значению величины частной производной в рассматриваемой точке.

Далее дается приращение величины x₂. В это время значение x₁ -постоянно. Получаемое при этом приращение ∆F является мерой другой частной производной.

После нахождения составляющих градиента делаются шаги в направлении вектора градиента, если стоит задача определения максимума и в направлении противоположном, если решается задача поиска минимума.

Таким образом, определяются новые значения x₁ и x₂ в соответствующей точке. После каждого шага оценивается приращение ΔF величины F.

Если ΔF>0 при поиске максимума или ΔF<0 при поиске минимума, то движение происходит в правильном направлении, иначе необходимо уменьшить величину шага.

Численное значение координаты при движении по градиенту для переменной x_i в последующей k+1 точке вычисляется при помощи численного значения этой координаты на предыдущем шаге по следующей формуле:

x_i,k+1 = x_i,k ± h_k * S_i,k

(+ для поиска максимума; – для поиска минимума),

где,

i =1,2 , … ,n ; k=0,1,2, … ,.

n – число варьируемых переменных, k – номер шага поиска.

Величина называется нормой градиента в соответствующей

точке поиска экстремума целевой функции и вычисляется по формуле:

h_k – шаг поиска в точке, который выбирается произвольно.

Глава II. Практическая часть

Разработка компьютерной программы для решения задачи оптимизации градиентным методом с использованием равномерного поиска