Метод спуска

Ме́тод спу́ска, 1) в уравнениях математической физики – приём, позволяющий из формулы для решений заданного уравнения получить формулы для решений такого же уравнения с меньшим числом независимых переменных (Тихонов. 2013^[1]); 2) метод решения задачи минимизации

${\displaystyle f\left(x^{*}\right)=\min _{x}f(x),}$

где ${\displaystyle f}$ – некоторая функция переменной ${\displaystyle x=\left(x_{1},\ldots ,x_{n}\right)}$. Итерационная последовательность ${\displaystyle \left\{x^{k}\right\}}$ метода спуска вычисляется по формуле

${\displaystyle x^{k+1}=x^{k}+\alpha _{k}g^{k},}$

где ${\displaystyle g^{k}}$ – вектор, указывающий некоторое направление убывания функции ${\displaystyle f}$ в точке ${\displaystyle x^{k}}$, a ${\displaystyle \alpha _{k}}$ – итерационный параметр, величина которого указывает длину шага в направлении ${\displaystyle g^{k}}$. Если функция ${\displaystyle f}$ дифференцируема и ${\displaystyle x^{k}}$ не является её точкой экстремума, то вектор ${\displaystyle g^{k}}$ должен удовлетворять неравенству

${\displaystyle \left(f^{\prime }\left(x^{k}\right),g^{k}\right)<0,}$ (*)

где ${\displaystyle f^{\prime }\left(x^{k}\right)}$ – градиент функции ${\displaystyle f}$ в точке ${\displaystyle x^{k}}$.

Если ${\displaystyle f}$ – достаточно гладкая функция (например, дважды непрерывно дифференцируемая) и последовательность векторов ${\displaystyle \left\{g^{k}\right\}}$ удовлетворяет неравенству (*), то существует такая последовательность ${\displaystyle \left\{\alpha _{k}\right\}}$, что

${\displaystyle f\left(x^{0}\right)>f\left(x^{1}\right)>\ldots >f\left(x^{k}\right)>\ldots }$

При определённых ограничениях (Пшеничный, Данилин. 1975) на функцию ${\displaystyle f}$ и способ выбора параметров ${\displaystyle \left\{\alpha _{k}\right\}}$ и векторов ${\displaystyle g_{k}}$ последовательность ${\displaystyle \left\{x^{k}\right\}}$ сходится к решению ${\displaystyle x^{*}}$ исходной задачи.

К методам спуска относятся градиентные методы, в которых векторы ${\displaystyle \left\{g^{*}\right\}}$ каким-либо образом выражаются через векторы ${\displaystyle \left\{f^{\prime }\left(x^{k}\right)\right\}}$. Одним из наиболее распространённых является случай, когда

${\displaystyle g^{k}=-B\left(x^{k}\right)f^{\prime }\left(x^{k}\right),}$

где ${\displaystyle B(x)}$ – симметрическая матрица, удовлетворяющая для любых векторов ${\displaystyle x}$ и ${\displaystyle y}$ неравенству

${\displaystyle m(x,x)\leqslant (B(y)x,x)\leqslant M(x,x)}$

с некоторыми константами ${\displaystyle M\geqslant m>0}$. При дополнительных предположениях (Пшеничный. 1975^[2]) относительно ${\displaystyle f}$ и специальном выборе ${\displaystyle \left\{\alpha _{x}\right\}}$ градиентный метод обеспечивает сходимость последовательности ${\displaystyle \left\{x^{k}\right\}}$ к решению ${\displaystyle \left\{x^{*}\right\}}$ исходной задачи со скоростью геометрической прогрессии со знаменателем ${\displaystyle g<1}$. Частным случаем градиентных методов является метод наискорейшего спуска, в котором матрица ${\displaystyle B(x)}$ выбирается единичной.