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

Рассмотрим метод решения максимизации функции нескольких переменных  f, не использующий вычисление производных [19]. Описанный здесь метод заключается в следующем. При заданном векторе  определяется допустимое направление . Затем, отправляясь из точки , функция f минимизируется вдоль направления  методом циклического покоординатного спуска [20].

Задача линейного поиска заключается в минимизации f (  + l ) при условии, что lÎL, где L обычно задается в форме L=E₁, L = {l: l ³ 0} или L = {l: а £ l £ b}. В формулировке алгоритма для простоты будем предполагать, что точка минимума `l существует. Однако в реальных задачах это предположение может не выполняться. Оптимальное значение целевой функции в задаче линейного поиска может быть неограниченным или оптимальное значение функции конечное, но не достигается ни при каком l. В первом случае целевая функция исходной задачи неограниченна и вычисления прекращаются. Во втором случае можно выбрать такое `l, что f(  + `l ) будет достаточно близким к inf{ f ( + l ): lÎL }.

В этом методе в качестве направлений поиска используются координатные векторы. Точнее, метод осуществляет поиск вдоль направлений d₁, ..., d_n, где d_j — вектор, все компоненты которого, за исключением j-й, равны нулю. Таким образом, при поиске по направлению d_j меняется только переменная х_j, в то время как все остальные переменные остаются зафиксированными. Схематически этот метод проиллюстрирован на рис. 2.1.