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

[Alcohol_frei]

Цитата:

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

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

[Бодигрим]

Alcohol_frei в сообщении #143858 писал(а):

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

Нет. Если вам не ясно, что такое "на прямой, проходящей через предыдущую точку и параллельной градиенту", так и спросите. Роль одномерной функции играет исходная многомерная, в которой выполнена подстановка $x_n=x_n^0+k {\partial f\over\partial x_n}(x^0)$, после которой она превращается в одномерную функцию от $k$.

Alcohol_frei в сообщении #143858 писал(а):

В каких границах он ищется?

Хм, а в каких границах у вас ищется экстремум многомерной функции? В тех же границах ищите и одномерные экстремумы - им же не полагается вылазить за них.

[Alcohol_frei]

Цитата:

Хм, а в каких границах у вас ищется экстремум многомерной функции?

То есть при задании функции пользователь должен будет задать еще границы ? Вот я валенок!

[ewert]

На самом деле не обязательно. Есть вот какой симпатичный способ.

Пусть $\vec f'$ -- это градиент. На $k$-том шаге минимизации подлежит одномерная функция $\Phi(t)=f\big(\vec x_k-t\cdot\vec f'(\vec x_k)\big)$. В окрестности экстремума она примерно квадратична. Секущая в точке $t=0$, направленная в вершину параболы, задаётся функцией $\widetilde\Phi(t)=f(\vec x_k)-{1\over2}t\cdot\big|\vec f'(\vec x_k)\big|^2$, т.е. имеет вдвое меньший угловой коэффициент, чем соответствующая касательная.

Теперь: поскольку метод градиентного спуска всё равно достаточно груб, нет необходимости минимизировать $\Phi(t)$ хоть сколько-то точно. Достаточно на каждом шаге оказываться где-нибудь рядом с минимумом. Другими словами: достаточно делать лишь пару подшагов одномерной итерационной процедуры. Это, допустим, увеличит необходимое количество шагов "верхнего уровня" в несколько раз, но в несколько же раз уменьшится и трудоёмкость каждого шага.

Отсюда алгоритм. Задаём начальное $t_0$ и некий параметр "сжатия/растяжения" $\theta$ (например, $\theta=1,5$). На каждом $k$-том шаге сперва увеличиваем предыдущее значение $t$ в $\theta$ раз до тех пор, пока не окажется $\Phi(t)\geqslant\widetilde\Phi(t)$. А затем уменьшаем $t$ в $\theta$ раз до тех пор, пока не будет $\Phi(t)\leqslant\widetilde\Phi(t)$. Последнее значение $t$ и принимаем за оценку положения минимума $\Phi(t)$ на данном шаге.

[Alcohol_frei]

ewert, спасибо! Но я на всякий случай попрошу задать границы изначально, т.к. при защите внятно объяснить не смогу почему ТАК.
Попросят переделать - воспользуюсь Вашим.