Гребневых целевых функций

Методы оптимизации в случае овражных или

Метод барьерных функций или метод внутренней точки

Метод внешней точки

Сведение задач условной оптимизации к безусловной

Метод полиноминальной аппроксимации

Метод чисел Фибоначчи

β_k = β_k-1 + β_k-2 , где β₂ = β₁ , β_k = 1,1,2,3,5,8,13,21,34,55,89…

k = 0,1,2,3,4,5, 6, 7, 8, 9, 10,…

ε ≈ В-А / 1,618^N ,

где N – число итераций (число последовательных вычислений). N задаётся.

Определяется порядковый номер числа Фибоначчи К = N + 2

Это – максимальный номер числа Фибоначчи- К.

с_n = a_n +α_nl_n ; α_n = β_N+2-n / β_N+3-n ;

d_n = b_n- α_nl_n.

f(h) = a₀ + a₁h + a₂h² h` = a₁/2a₂

h` = h_c + (h[f(h_a) – f(h_b)]) / (2[f(h_a) – 2f(h_c) + f(h_b)])

h_a = h_c – H₁

h_b = h_c + H₁

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

Например, имеем ограничения типа неравенств φ(X) < 0

Ф(Х) = F(X) + Q_k(X)

Q_k(X) = r_k ∑ [max {0; φ_i(X)}] ²; r_k > 0 – функция штрафав методе внешней точки.

Решаем задачу. Найти минимум целевой функции при выполнении ограничений - min F(X)

ХД = {X| φ(X) < 0}

Ищем минимум новой функции

min Ф(Х)

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

ΔХ = Х_k+1 – Х_k < δ.

Ф(Х) = F(X) – r_k ∑ 1/φ_i(X)

Где функция штрафа имеет вид: Q_k(X) = -r_k ∑ 1/φ_i(X)

В большинстве практических задач оптимизации целевая функция имеет сложный профиль. У нее наблюдаются овраги при минимизации или гребни при максимизации. Характерным отличием этих целевых функций является резкое различие значений её градиента вдоль и поперек оврага или гребня. В этой ситуации, рассмотренные ранее методы: покоординатного спуска, градиента, наискорейшего спуска и Ньютона становятся малоэффективными по причине очень медленного поиска или зацикливания и прекращения поиска задолго до точки экстремума. Были предложены методы, которые эффективны в такой ситуации.