Приборостроения и информатики

Министерство образования РФ

Метод симплексов (Нелдера- Нида)

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

Нужны направления. Раньше их задавал градиент, теперь его нет. Возможен случайный выбор, а можно по координатным осям.

Алгоритм:

1) j:=1

2) min f(x^’-ge_j)=f(x^’’), x^’’:= x’- g*e_j

3) j:=j+1, x^’= x^’’

4) if j £ n then goto 2)

5) if not (условие окончания цикла) then goto 1

Достоинство:

Требуется min функции вдоль только одной прямой.

Алгоритм:

1.Фиксируем x_o…x_n (n+1- точка)

Если n =2, то D (выбир. равнобедренный треугольник)

2.

вычисление отраженной точки

x_j

x_j’

Если f(x_j^’) < f(x_j), то x_j := x_j^’; k:=0, иначе k:=k+1

k- количество идущих подряд неудачных отражений

3. Если k<n, то (если j<n, то j:=j+1, иначе j:=0) goto 2.

4.Иначе сжатие: x_l = argmin f(x_j), 0£ j £ n - ищем вершину, в которой функция минимальна (то есть наименьшее значение из всех существующих вершин

5. Cжатие: x_j = x_l + g(x_j - x_l), "j (сжатие в g раз)

Существует много модификации метода.

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

4.Метод Пауэлла (сопряженных направлений)

Идея:

Для двух точек x₀,x₁ делается шаг в произвольном направлении p_0. Получаем точки x₂,x_3. Следующий шаг делаем в направлении p₁. Находится x*.

p₁= x₃-x₂ x₂ x₃p₁

x*

p₀ p₁

x₀ x₁

Утверждается, что (Ap₁,p_o)=0.

Поэтому для квадратичной функции сойдется за n- шагов. Это один из лучших методов прямого поиска.

Московская государственная академия