Многомерные методы оптимизации.

Пусть целевая функция z - f(x₁ x₂,..._t х_т) — действительная функция многих переменных, определенная на множестве X . Тогда задача оптимизации этой функции является многомерной. В случае, когда ограничения на переменные x₁ x₂,..._t х_т отсутствуют, говорят о задаче безусловной минимизации. В противном случае говорят о задаче условной минимизации.

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

Большинство итерационных методов, применяемых для решения задачи безусловной минимизаций функций многих переменных, относятся к классу методов спуска, т. е. таких методов, для которых каждая итерация (шаг) приводит к уменьшению значения целевой функции: для всех п> 0. На каждой итерации метода спуска находят ненулевой вектор, называемый направлением спуска и вычисляют шаг спуска. Далее находят приближение Х^(п+1) и проверяют выполнение критерия окончания итераций. Последовательность точек, генерируемую методом спуска, называют траекторией спуска.

Покоординатный спуск.

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

Пусть приближение X⁽ⁿ⁾ уже найдено.

Цикл с номером, n + 1 состоит из т шагов. На первом шаге производят спуск по координате x₁. Значения х₂ = остальных координат фиксируют, а выбирают из условия

Фактически решается задача минимизации функции одной переменной

На втором шаге производят спуск по координате Значения х₁ = остальных координат фиксируют и выбирают как решение задачи одномерной минимизации по переменной. Аналогично осуществляют остальные шаги. На последнем m-м шаге координату определяют из условия минимизации функции по переменной х_т. В результате получается очередное приближение в точке минимума. Далее цикл метода снова повторяют пока не выполнится критерий окончания итераций.