Методы покоординатной оптимизации

 

В методах покоординатной оптимизации в качестве направлений поиска выбираются координатные оси пространства варьируемых параметров. При этом на каждой k-й итерации выполняется n шагов циклического покоординатного спуска из текущей точки  вдоль каждой из n координатных осей. Покоординатный спуск сводится к поочередному изменению переменных вдоль одной из осей:

 

(1.17)

 

где  координатный n – мерный векторб у которого i – й элемент равен 1, а остальные элементы равны 0:

 

(1.18)

 

 – длина шага поиска по i – й переменной на k – ой итерации.

Таким образом, в координатной форме шаги циклического спуска имеют следующий вид:

 

…	(1.19)

 

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

Необходимо заметить, что для нелинейной целевой функции линии уровня часто имеют овражный характер. При этом целевая функция сильно меняется по одним направлениям и слабо - по другим. Такие овражные ситуации создают значительные трудности для оптимизации.

Рисунок 1 – Интерпретация траектории покоординатного поиска.

 

К простейшим алгоритмам покоординатной оптимизации можно отнести алгоритм покоординатного спуска с постоянным шагом и релаксационный метод Гаусса-Зейделя. Различия между этими двумя алгоритмами заключается в способе выбора шага поиска .

a. Покоординатный спуск с постоянным шагом.

В этом методе на каждой k-й итерации циклический покоординатный спуск заключается в следующем. Сначала осуществляется движение из точки  с шагом  вдоль 1-й координатной оси:

 

(1.20)

 

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

	(1.21)

В случае уменьшения значения целевой функции осуществляется переход в точку , в противном случае переход в новую точку не производится. Затем рассматривается следующая координатная ось. Аналогичные действия повторяются для всех координатных осей. Если в результате движения вдоль всех координатных осей значение целевой функции не уменьшилось, осуществляется дробление шага, и циклический покоординатный спуск повторяется из точки  с уменьшенной длиной шага. Итерационный процесс заканчивается, когда длины шагов вдоль координатных направлений уменьшатся до некоторого числа ε.

b. Релаксационный алгоритм Гаусса-Зейделя

Отличие данного алгоритма от предыдущего заключается в том, что в нем на каждой k-й итерации определяются оптимальные длины

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

· Задается начальное приближение  и точность

вычислений ε > 0. При этом k=0, .

· Осуществляется циклический покоординатный спуск из точки  по итерационной схеме , i = l...n с выбором оптимальной длины поискового шага  вдоль каждого направления . Эта процедура образует внутренний цикл, в процессе которого осуществляется одномерная минимизация функции  по каждой переменной : 

 

	(1.22)

 

В результате каждого i-го шага внутреннего цикла определяется очередная координата  точки . После окончания внутреннего цикла в качестве нового приближения принимается точка .

· Проверяется выполнение критерия окончания итерационного процесса. Если  для всех i=1..n, работа алгоритме заканчивается. В противном случае осуществляется переход к шагу 2 (при этом k=k+l).

c. Дальнейшим развитием методов покоординатной оптимизации является метод конфигураций Хука-Дживса. В данном методе этап циклического покоординатного поиска вдоль координатных осей чередуется с этапом экстраполяции, т.е. движения в направлении, соединяющем две перспективные точки  и  на двух последовательных шагах (рисунок 2). Первый этап называется в методе Хука - Дживса исследующим поиском вокруг базисной точки, а второй этап поиском по образцу.

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

Рисунок 2 – Шаги метода Хука - Дживса.

 

Если этап исследующего поиска оказывается успешным, т.е. , реализуется этап поиска по образцу. При этом производится движение из точки в направлении , после чего осуществляется исследующий поиск вокруг полученной точки  . Если полученное при этом значение целевой функции меньше, чем значение в точке , поиск по образцу считается удачным. В противном случае (если поиск по образцу неудачен) осуществляется возврат в точку  и исследующий поиск продолжается вокруг нее. Алгоритм заканчивает работу, когда текущая длина шага становится меньше заданной точности ε.

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