Метод покоординатного спуска в задачах без ограничений

Это задача безусловной минимизации, т. е. задача минимизации целевой функции у = f (х₁, х₂,…, х_n) на всем пространстве переменных (на всем евклидовом пространстве). Если требуется решить задачу максимизации, то выражение целевой функции умножают на (– 1) и снова решается задача минимизации.

Суть данного метода заключается в построении последовательности точек х⁽⁰⁾, х⁽¹⁾, х⁽²⁾,…, х⁽ⁿ⁾, монотонно уменьшающих значение целевой функции f (х⁽⁰⁾) ³ f (х⁽¹⁾) ³ f (х⁽²⁾) ³ … ³ f (х⁽ⁿ⁾).

Согласно этому методу направления спуска выбирается параллельно координатным осям, т. е. сначала спуск осуществляется вдоль первой оси OХ₁ затем вдоль второй оси OХ₂ и т. д. до последней оси OХ_n.

Пусть х⁽⁰⁾ – начальная точка (рис. 3.11), a – некоторое положительное число. Вычисляют значение целевой функции в этой точке – f (х⁽⁰⁾). Далее вычисляют значение целевой функции при х = х⁽⁰⁾ + а и проверяют выполнение неравенства

f (х⁽⁰⁾ + а) < f (х⁽⁰⁾).

Если это неравенство справедливо, то вдоль направления оси 0X₁ значение функции f уменьшилось, и поэтому полагают x⁽¹⁾ = x⁽⁰⁾ + a. Если неравенство не выполняется, то делают шаг в противоположном направлении и проверяют выполнение неравенства

f (х⁽⁰⁾ – а) < f (х⁽⁰⁾).

В случае выполнения этого неравенства полагают x⁽¹⁾ = x⁽⁰⁾ – a. Если оба неравенства не выполняются, то x⁽¹⁾ = x⁽⁰⁾.

Рис. 3.11. Графическая иллюстрация поиска точки минимума методом
покоординатного спуска

Второй шаг производят вдоль координатной оси OX₂. Вычисляют значение функции в точке (x⁽¹⁾ + a) и сравнивают его с предыдущим значением, т. е. проверяют выполнение неравенства

f (х⁽¹⁾ + а) < f (х⁽¹⁾).

Если это неравенство выполняется, то полагают x⁽²⁾ = x⁽¹⁾ + a. Если оно не выполняется, то делают шаг в противоположном направлении и проверяют выполнение неравенства

f (х⁽¹⁾ – а) < f (х⁽¹⁾).

В случае выполнения последнего неравенства считают, что x⁽²⁾ = x⁽¹⁾ – a. Если оба предыдущих неравенства не выполняются, то принимают x⁽²⁾ = x⁽¹⁾.

Так перебирают все n направлений координатных осей. На этом первая итерация закончена. На n-м шаге будет получена некоторая точка x⁽ⁿ⁾. Если x⁽ⁿ⁾ ¹ x⁽⁰⁾, то аналогично, начиная с x⁽ⁿ⁾ осуществляют вторую итерацию. Если же x⁽ⁿ⁾ = x⁽⁰⁾ (это имеет место, если на каждом шаге ни одно из пары неравенств не окажется выполненным), то величину шага нужно уменьшить, взяв, например, a_n+1 = a_n/2, и в следующей итерации использовать новое значение величины шага.

Последующие итерации выполняют аналогично. На практике вычисления прекращают при выполнении какого-либо условия окончания счета, например

½f (х)_{(k + 1)} – f (х)_(k)½< d,

где f (x)_{(k + 1)} – значение целевой функции на (k + 1) итерации; f (x)_(k) – значение целевой функции на k-ой итерации; d – некоторое положительное число, характеризующее точность решения исходной задачи минимизации целевой функции.