Ideal exact gradient line-search step

This is an ideal one-step line-search oracle that uses the negative-gradient direction of Gradient descent and replaces only its step-selection rule. It is not a second definition of the gradient-descent iteration.

Inputs: an open convex set $U\subseteq {\mathbb{R}}^d$, a $C^2$ objective $f:U\to \mathbb{R}$, an initial point $x_0\in U$ whose sublevel set $K:=\{y\in U:f(y)\le f(x_0)\}$ is compact, and a current point $x\in K$. Admissible conditions: for some $0<m\le M$, there is a convex open set $V\subseteq U$ containing $K$ on which the Hessian satisfies $mI⪯H_f(y)⪯MI$. Output: if $\mathrm{\nabla }f(x)=0$, return $(x,\mathtt{\text{stationary}})$. Otherwise set $g:=\mathrm{\nabla }f(x)$ and return $(x-t_{\ast }g,\mathtt{\text{exact-step}})$, where $t_{\ast }$ is the unique minimizer of $t\mapsto f(x-tg)$ over all $t\ge 0$ with $x-tg\in U$. The set $K$ is nonempty because $x_0\in K$, and the continuous restriction $f{\mathrm{\mid }}_K$ attains a minimum at some $x^{\ast }\in K$ by A continuous real-valued function on a nonempty compact metric space is bounded and attains a greatest and a least value. Every $y\in U\setminus K$ satisfies $f(y)>f(x_0)\ge f(x^{\ast })$, so $x^{\ast }$ is an attained global minimizer of $f$ on $U$. Thus the algorithm inputs supply the minimizer premise of Exact gradient line search has a global objective-gap contraction ↗, whose remaining hypotheses are stated above.

The minimization is an exact real-valued oracle; this definition gives no finite evaluation procedure or floating-point accuracy claim. A finite implementation must report its own search status and error bounds.