Градиентные методы. Вопрос к специалистам.

[shukshin]

Добрый день, уважаемые участники форума!
У меня довольно специальный вопрос по градиентному методу с дроблением шага.
Пусть в качестве критерия остановки процесса взят $|| \nabla f(x_1, x_2) || \leqslant \varepsilon $
Как это эпсилон будет связано с $\delta = ||x_k - x^*||$? (фактическая точность решения)

В умных книгах Гилл/Мюррей ничего не нашел. В интернете тем более.
В задаче есть упрощения - дана размерность 2, известна сама функция.

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

Просьба: либо совет, что предпринимать, либо источник где есть.

[dsge]

shukshin в сообщении #1117360 писал(а):

Как это эпсилон будет связано с $\delta = ||x_k - x^*||$? (фактическая точность решения)

Никак. Для любого, как угодно малого, эпсилон найдется функция такая, что при выполнении условия $|| \nabla f(x_1, x_2) || \leqslant \varepsilon $ точка $(x_1, x_2)$ будет лежать как угодно далеко от точки экстремума. Например, функция: $ f(x_1, x_2)= 10^{-n}(x_1^2+x_2^2)$, где $n$ достаточно велико.

[Mikhail_K]

dsge в сообщении #1117526 писал(а):

Никак. Для любого, как угодно малого, эпсилон найдется функция такая

ТС указал, что функция $f$ известна. Поэтому Ваш пессимизм не оправдан.
Разумеется, ответить на вопрос можно только наложив на функцию какие-либо ограничения.
Я бы посоветовал использовать такое ограничение: $(f^{\prime\prime}(x)h,h)\geq \alpha\|h\|^2$ в окрестности точки минимума (лучше, конечно, на всём пространстве). Здесь $f^{\prime\prime}$ - матрица Гессе. Зная функцию $f$, можно сосчитать $\alpha$. Однако нужна уверенность в том, что последнее приближение градиентного метода будет лежать в данной окрестности.
Затем я бы посоветовал разложить функцию $f$ в ряд Тейлора до второго члена включительно - во-первых, в точке минимума $x^*$, во-вторых, в последнем приближении $x$ градиентного метода. Авось, что-то и получится.

[shukshin]

Mikhail_K, с первой частью начал.
Знакомьтесь, наша функция:
$f(x_1, x_2) = x_1 + x_2 + 4 \sqrt{1 + x_1^2 + x_2^2 }$
Выпишем матрицу Гессе (правильность взятия вторых производных на моей совести, не буду здесь выписывать всю технику):
Получилось так:
$H(x_1, x_2) = \frac{4}{(1+x_1^2+x_2^2)^{3/2}}\begin{pmatrix} x_2^2+1 & -x_1 x_2 \\ -x_1 x_2 & x_1^2+1 \end{pmatrix} $
Возьмем произвольный вектор $(h_1 \quad h_2)^T$.
Рассматриваем $(h_1 \quad h_2) H(x_1, x_2) (h_1 \quad h_2)^T = $
[... Немножко преобразований ...]
$= \frac{4(h_1^2(x_2^2+1) - 2 x_1 x_2 h_1 h_2 + h_2^2 (x_1^2+1))}{(1+x_1^2+x_2^2)^{3/2}} \geqslant \alpha(h_1^2 + h_2^2)$
Про себя отмечаю, что если взять $\alpha = \frac {4}{(1+x_1^2+x_2^2)^{3/2}}$ неравенство будет выполнено всегда. Вот только оценка зависит от координат.

[dsge]

shukshin, надо было сразу предъявить функцию. Задача тривиальная.

[shukshin]

dsge, так я прав, что $\alpha$ не подобрать для всех $x_1, x_2$.
Нужно в круге рассматривать?

[dsge]

Икс разумно взять в точке экстремума, а круг (внутренность эллипса?) строить по эйч.