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

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

Предлагается так же подтвердить полученную оценку численными экспериментами.

Хорошее решение задачи тянет на статью.