Метод покоординатного спуска относится к тем численным методам, которые удобно изучать последовательно, шаг за шагом. Почему именно так? Потому что он не предполагает одновременного изменения всех переменных. Вместо этого поиск минимума выполняют по очереди по отдельным координатам. Благодаря этому сложная задача минимизации функции нескольких переменных становится значительно проще.
Кроме того, такой подход хорошо подходит для учебного объяснения. Он позволяет увидеть, как строится алгоритм, как формируется новое приближение и когда целесообразно завершать вычисления. Далее мы последовательно рассмотрим суть метода, схему одного полного цикла, условия остановки и практический пример.
Метод Покоординатного Спуска: Где Его Применяют и в Чём Заключается Суть
Пусть задана функция нескольких переменных
\[
f(\bar{x})=f(x_1,x_2,\dots,x_n),
\]
где \( \bar{x} \) — вектор переменных. Нужно найти точку минимума этой функции или приближение к точке локального минимума. Именно для таких задач и применяют метод покоординатного спуска.
Суть метода заключается в том, что на каждом этапе изменяют только одну переменную, а все остальные считают фиксированными. Следовательно, многомерная задача минимизации раскладывается на последовательность одномерных задач. А это уже значительно проще и для анализа, и для вычислений.
Начинают с некоторого начального приближения
\[
\bar{x}^{(0)}=\bigl(x_1^{(0)},x_2^{(0)},\dots,x_n^{(0)}\bigr).
\]
После этого по каждой координате по очереди выполняют поиск минимума. Сначала изменяют \( x_1 \), затем \( x_2 \), далее \( x_3 \), и так продолжают до \( x_n \).
Когда такой подход удобен? Прежде всего тогда, когда минимизацию по каждой отдельной координате можно выполнить относительно просто. Кроме того, важно, чтобы функция была определена в тех точках, через которые проходит процесс поиска. Именно поэтому метод покоординатного спуска часто считают одним из базовых подходов в численной оптимизации.
В то же время здесь следует сразу сделать важное уточнение. В общем случае этот метод приводит к приближению именно к локальному минимуму, а не обязательно к глобальному. Поэтому полученный результат может зависеть от выбора начального приближения.
Минимизация по Координатам: Как Выглядит Один Полный Цикл
После выбора начального приближения можно перейти к описанию самого вычислительного процесса. Пусть у нас есть точка
\[
\bar{x}^{(0)}=\bigl(x_1^{(0)},x_2^{(0)},\dots,x_n^{(0)}\bigr).
\]
На первом шаге фиксируем все координаты, кроме \( x_1 \), и рассматриваем функцию одной переменной
\[
\varphi_1(x_1)=f(x_1,x_2^{(0)},\dots,x_n^{(0)}).
\]
Далее находим такое значение \( x_1 \), при котором эта функция достигает минимума. Пусть это значение равно \( x_1^{(1)} \). Тогда после первого шага получаем новое промежуточное приближение \( \bigl(x_1^{(1)},x_2^{(0)},\dots,x_n^{(0)}\bigr) \).
После этого переходим ко второй координате. Теперь фиксируем уже обновлённое значение \( x_1^{(1)} \), а также все остальные координаты, кроме \( x_2 \), и рассматриваем функцию
\[
\varphi_2(x_2)=f(x_1^{(1)},x_2,\dots,x_n^{(0)}).
\]
Найдя её минимум, получаем следующее промежуточное приближение \( \bigl(x_1^{(1)},x_2^{(1)},\dots,x_n^{(0)}\bigr) \).
Аналогично процесс продолжают для всех остальных координат до \( x_n \). После того как все переменные пройдены по одному разу, получаем новую точку
\[
\bar{x}^{(1)}=\bigl(x_1^{(1)},x_2^{(1)},\dots,x_n^{(1)}\bigr).
\]
Именно этот переход от \( \bar{x}^{(0)} \) к \( \bar{x}^{(1)} \) и называют одним полным циклом метода.
Здесь важно не путать два понятия.
- Шаг метода — это минимизация по одной координате.
- Полный цикл — это последовательное выполнение таких шагов для всех координат.
После каждого обновления отдельной координаты значение функции, как правило, не возрастает. Следовательно, после завершения полного цикла также имеем
\[
f\bigl(\bar{x}^{(1)}\bigr)\leq f\bigl(\bar{x}^{(0)}\bigr).
\]
Если далее выполнить ещё один цикл, то получим точку \( \bar{x}^{(2)} \), и тогда будет выполнено неравенство
\[
f\bigl(\bar{x}^{(2)}\bigr)\leq f\bigl(\bar{x}^{(1)}\bigr)\leq f\bigl(\bar{x}^{(0)}\bigr).
\]
Итак, образуется последовательность приближений
\[
\bar{x}^{(0)},\bar{x}^{(1)},\bar{x}^{(2)},\dots
\]
для которой значения целевой функции формируют монотонно невозрастающую последовательность.
Таким образом, после описания одного полного цикла уже хорошо видна главная логика алгоритма: каждый новый цикл уточняет предыдущее приближение, а значение функции постепенно уменьшается или, по крайней мере, остаётся на том же уровне.
Метод Покоординатного Спуска: Когда Целесообразно Останавливать Вычисления
После того как схема одного полного цикла стала понятной, возникает вполне естественный вопрос: когда именно нужно завершать процесс вычислений? Ведь циклы можно повторять много раз. Однако на практике алгоритм останавливают тогда, когда дальнейшие изменения уже становятся достаточно малыми.
Здесь важно подчеркнуть: условие остановки чаще всего проверяют именно после полного цикла, а не после каждого отдельного шага. Почему так? Потому что после одного шага изменяется только одна координата, тогда как после полного цикла обновляется вся точка
\[
\bar{x}^{(k)}=(x_1^{(k)},x_2^{(k)},\dots,x_n^{(k)}).
\]
Именно поэтому логично сравнивать приближения \( \bar{x}^{(k)} \) и \( \bar{x}^{(k+1)} \), полученные после двух соседних полных циклов.
Один из наиболее часто используемых критериев остановки связан с изменением самой точки:
\[
\|\bar{x}^{(k+1)}-\bar{x}^{(k)}\|<\varepsilon,
\]
где \( \varepsilon>0 \) — заданная точность. Здесь норма показывает, насколько новое приближение отличается от предыдущего в целом по всем координатам. Если эта разница уже очень мала, то процесс можно завершить.
Ещё один распространённый критерий связан с изменением значения функции:
\[
\bigl|f(\bar{x}^{(k+1)})-f(\bar{x}^{(k)})\bigr|<\varepsilon.
\]
В этом случае проверяют, стало ли улучшение значения функции достаточно малым. Если да, то дальнейшие циклы уже не дают существенного результата.
Кроме того, иногда задают ограничение на максимальное количество полных циклов:
\[
k\geq k_{\max}.
\]
Такой критерий нужен для того, чтобы алгоритм не работал слишком долго, если сходимость происходит медленно.
На практике часто используют сразу несколько условий остановки. Это удобно, ведь позволяет контролировать и изменение точки, и изменение значения функции, и общую длительность вычислений.
Итак, метод покоординатного спуска — это последовательный процесс минимизации по отдельным координатам, который повторяют до тех пор, пока не будет выполнено выбранное условие остановки.
Практическая Часть: Как Метод Покоординатного Спуска Работает на Примере
Теперь перейдём к конкретному примеру применения метода покоординатного спуска. Именно на практической задаче лучше всего видно, как последовательно изменяются координаты, как формируется новое приближение и когда вычисления уже можно завершить.
Пример 1. Найти минимальное значение функции \( f(x_1,x_2)=x_1^2+x_1\cdot x_2+x_2^2-6\cdot x_1-4\cdot x_2 \) с точностью \( \varepsilon=0.05 \), используя метод покоординатного спуска
Рассмотрим заданную функцию двух переменных. Она является квадратичной, а значит, достаточно гладкой для применения метода покоординатного спуска. Возьмём начальное приближение
\[
\bar{x}^{(0)}=(0,0).
\]
Условие остановки будем проверять после каждого полного цикла по правилу
\[
\|\bar{x}^{(k+1)}-\bar{x}^{(k)}\|<0.05.
\]
Здесь важно сразу отметить, что в этом примере для минимизации по каждой координате используется не отдельный численный одномерный метод, например метод дихотомии, метод Фибоначчи или метод золотого сечения, а точное аналитическое нахождение минимума соответствующей одномерной квадратичной функции через производную. Такой подход позволяет яснее увидеть саму логику метода покоординатного спуска без дополнительного усложнения промежуточными численными процедурами.
Начинаем первый полный цикл. Сначала фиксируем \( x_2=0 \) и минимизируем функцию по переменной \( x_1 \). Тогда получаем
\[
\varphi_1(x_1)=f(x_1,0)=x_1^2-6\cdot x_1.
\]
Вычислим производную:
\[
\varphi_1′(x_1)=2\cdot x_1-6.
\]
Далее приравняем её к нулю:
\[
2\cdot x_1-6=0.
\]
Из этого следует, что
\[
x_1^{(1)}=3.
\]
Итак, после первого шага получаем промежуточное приближение \( (3,0) \).
Теперь фиксируем ( x_1=3 ) и минимизируем функцию по переменной \( x_2 \):
\[
\varphi_2(x_2)=f(3,x_2)=3^2+3\cdot x_2+x_2^2-6\cdot 3-4\cdot x_2.
\]
После упрощения имеем
\[
\varphi_2(x_2)=x_2^2-x_2-9.
\]
Тогда
\[
\varphi_2′(x_2)=2\cdot x_2-1.
\]
Приравниваем производную к нулю:
\[
2\cdot x_2-1=0.
\]
Следовательно,
\[
x_2^{(1)}=0.5.
\]
После завершения первого полного цикла получаем точку
\[
\bar{x}^{(1)}=(3,0.5).
\]
Вычислим значение функции в этой точке:
\[
f\bigl(\bar{x}^{(1)}\bigr)=f(3,0.500)=-9.250.
\]
Теперь проверим, выполняется ли условие точности:
\[
\|\bar{x}^{(1)}-\bar{x}^{(0)}\|
=\sqrt{(3-0)^2+(0.5-0)^2}
=\sqrt{9.25}\approx 3.041.
\]
Поскольку
\[
3.041>0.05,
\]
вычисления продолжаем.
Продолжение итерационного процесса
Переходим ко второму полному циклу. Фиксируем \( x_2=0.5 \) и рассматриваем функцию
\[
\varphi_1(x_1)=f(x_1,0.5)=x_1^2+0.5\cdot x_1+0.25-6\cdot x_1-2.
\]
После упрощения получаем
\[
\varphi_1(x_1)=x_1^2-5.5\cdot x_1-1.75.
\]
Тогда
\[
\varphi_1′(x_1)=2\cdot x_1-5.5.
\]
Приравниваем её к нулю:
\[
2\cdot x_1-5.5=0.
\]
Отсюда
\[
x_1=2.75.
\]
После этого получаем промежуточное приближение \( (2.75,0.5) \).
Теперь фиксируем \( x_1=2.75 \) и минимизируем по \( x_2 \):
\[
\varphi_2(x_2)=f(2.75,x_2)=2.75^2+2.75\cdot x_2+x_2^2-6\cdot 2.75-4\cdot x_2.
\]
После упрощения имеем
\[
\varphi_2(x_2)=x_2^2-1.25\cdot x_2-8.938.
\]
Найдём производную:
\[
\varphi_2′(x_2)=2\cdot x_2-1.25.
\]
Приравниваем её к нулю:
\[
2\cdot x_2-1.25=0.
\]
Следовательно,
\[
x_2=0.625.
\]
После второго полного цикла получаем точку
\[
\bar{x}^{(2)}=(2.75,0.625).
\]
Вычислим значение функции:
\[
f\bigl(\bar{x}^{(2)}\bigr)=f(2.75,0.625)\approx -9.328.
\]
Снова проверим, выполняется ли условие точности:
\[
\|\bar{x}^{(2)}-\bar{x}^{(1)}\|
=\sqrt{(2.75-3)^2+(0.625-0.5)^2}
\approx 0.28.
\]
Поскольку
\[
0.28>0.05,
\]
переходим к следующему циклу.
Рассмотрим третий полный цикл. Сначала фиксируем \( x_2=0.625 \). Тогда
\[
\varphi_1(x_1)=f(x_1,0.625)=x_1^2+0.625\cdot x_1+0.391-6\cdot x_1-2.5.
\]
После упрощения получаем
\[
\varphi_1(x_1)=x_1^2-5.375\cdot x_1-2.109.
\]
Её производная равна
\[
\varphi_1′(x_1)=2\cdot x_1-5.375.
\]
Приравниваем к нулю:
\[
2\cdot x_1-5.375=0.
\]
Поэтому
\[
x_1=2.688.
\]
Далее фиксируем \( x_1=2.688 \) и минимизируем функцию по \( x_2 \):
\[
\varphi_2(x_2)=f(2.688,x_2)=2.688^2+2.688\cdot x_2+x_2^2-6\cdot 2.688-4\cdot x_2.
\]
После упрощения имеем
\[
\varphi_2(x_2)=x_2^2-1.312\cdot x_2-8.903.
\]
Тогда
\[
\varphi_2′(x_2)=2\cdot x_2-1.312.
\]
Приравниваем к нулю:
\[
2\cdot x_2-1.312=0.
\]
Отсюда
\[
x_2=0.656.
\]
Итак, после третьего полного цикла получаем точку
\[
\bar{x}^{(3)}=(2.688,0.656).
\]
Вычислим значение функции:
\[
f\bigl(\bar{x}^{(3)}\bigr)=f(2.688,0.656)\approx -9.333.
\]
Проверяем, выполняется ли условие точности:
\[
\|\bar{x}^{(3)}-\bar{x}^{(2)}\|
=\sqrt{(2.688-2.75)^2+(0.656-0.625)^2}
\approx 0.069.
\]
Поскольку
\[
0.069>0.05,
\]
выполняем ещё один цикл.
На четвёртом полном цикле сначала фиксируем \( x_2=0.656 \). Тогда рассматриваем функцию
\[
\varphi_1(x_1)=f(x_1,0.656)=x_1^2+0.656\cdot x_1+0.43-6\cdot x_1-2.624.
\]
После упрощения получаем
\[
\varphi_1(x_1)=x_1^2-5.344\cdot x_1-2.194.
\]
Её производная равна
\[
\varphi_1′(x_1)=2\cdot x_1-5.344.
\]
Приравниваем к нулю:
\[
2\cdot x_1-5.344=0.
\]
Отсюда
\[
x_1=2.672.
\]
После этого фиксируем \( x_1=2.672 \) и рассматриваем функцию по переменной \( x_2 \):
\[
\varphi_2(x_2)=f(2.672,x_2)=2.672^2+2.672\cdot x_2+x_2^2-6\cdot 2.672-4\cdot x_2.
\]
После упрощения имеем
\[
\varphi_2(x_2)=x_2^2-1.328\cdot x_2-8.892.
\]
Тогда
\[
\varphi_2′(x_2)=2\cdot x_2-1.328.
\]
Приравниваем её к нулю:
\[
2\cdot x_2-1.328=0.
\]
Следовательно,
\[
x_2=0.664.
\]
После четвёртого полного цикла получаем
\[
\bar{x}^{(4)}=(2.672,0.664).
\]
Теперь снова проверяем условие остановки:
\[
\|\bar{x}^{(4)}-\bar{x}^{(3)}\|
=\sqrt{(2.672-2.688)^2+(0.664-0.656)^2}
\approx 0.018.
\]
Поскольку
\[
0.018<0.05,
\]
итерационный процесс можно завершить.
Вычислим значение функции в последней найденной точке:
\[
f\bigl(\bar{x}^{(4)}\bigr)=f(2.672,0.664)\approx -9.333.
\]
Итак, приближённое значение точки минимума равно
\[
\bar{x}^{*}\approx (2.672,0.664),
\]
а приближённое минимальное значение функции равно
\[
f_{\min}\approx -9.333.
\]
Сравнение с точным ответом
Проверим, как этот результат согласуется с точным ответом. Для этого решим систему условий стационарности:
\[
\frac{\partial f}{\partial x_1}=2\cdot x_1+x_2-6=0,
\qquad
\frac{\partial f}{\partial x_2}=x_1+2\cdot x_2-4=0.
\]
Отсюда получаем
\[
x_1=\frac{8}{3}\approx 2.667,
\qquad
x_2=\frac{2}{3}\approx 0.667.
\]
Соответствующее точное минимальное значение равно
\[
f\left(\frac{8}{3},\frac{2}{3}\right)
=-\frac{28}{3}\approx -9.333.
\]
Кроме того, в этом примере можно показать, что найденный минимум является не только локальным, но и глобальным. Действительно, матрица вторых производных имеет вид
\[
H=
\begin{pmatrix}
2 & 1\\
1 & 2
\end{pmatrix}.
\]
Её главные угловые миноры удовлетворяют условиям
\[
2>0,
\qquad
\det(H)=4-1=3>0.
\]
Следовательно, матрица \( H \) является положительно определённой, а функция — строго выпуклой. Именно поэтому точка
\[
\left(\frac{8}{3},\frac{2}{3}\right)
\]
является единственной точкой глобального минимума.
Таким образом, этот пример последовательно показывает полный путь применения метода покоординатного спуска: от выбора начального приближения и построения одномерных функций до проверки точности, вычисления значения функции после каждого полного цикла и нахождения минимального значения. В то же время он ясно демонстрирует, что в данном случае минимизация по каждой координате выполнялась аналитически через производную, без использования отдельных численных методов одномерного поиска.
Что Стоит Рассмотреть Дальше: Полезные Темы для Продолжения
Тему метода покоординатного спуска мы уже рассмотрели последовательно: от основной идеи до практического примера. Однако на этом знакомство с методами минимизации не заканчивается. Что ещё стоит прочитать дальше, чтобы лучше увидеть разницу между подходами и их возможностями?
- Метод градиентного спуска: Как двигаться в направлении наискорейшего убывания — В этой статье речь пойдёт о том, как находить минимум функции нескольких переменных с помощью направления наискорейшего уменьшения.
- Метод Ньютона: Как использовать вторые производные для поиска минимума — В этой статье речь пойдёт о том, как метод Ньютона помогает находить точку минимума функции нескольких переменных и почему он часто сходится быстрее.
- Метод Ньютона с параметром: Как управлять шагом поиска минимума — В этой статье речь пойдёт о том, как параметр в методе Ньютона влияет на ход вычислений и делает процесс поиска более устойчивым.
Метод Покоординатного Спуска в Программировании: Попробуйте Реализовать Алгоритм Самостоятельно
Если вам интересно не только читать о методе, но и увидеть, как он работает в программной реализации, обратите внимание на блок-схему ниже. Она может стать удобной основой для создания небольшой программы на удобном для вас языке программирования, которая находит минимальное значение функции нескольких переменных методом покоординатного спуска.
Такая попытка помогает лучше понять сам алгоритм, увидеть связь между математическими записями и кодом, а также проверить работу метода на разных функциях. Это уже не просто теория, а вполне практический шаг к собственной реализации.
