 Optimization algorithm

An optimization algorithm is a procedure for finding or approximating an optimum of an objective function subject to specified optimization constraints. Its output must be assessed through feasibility, objective quality and a justified stopping rule, rather than only the number of iterations performed.

For $f(x)=x^2/2$, gradient descent with fixed step $\alpha$ gives $x_{k+1}=(1-\alpha )x_k$. It converges to the minimizer for $0<\alpha <2$, oscillates without decay at $\alpha =2$ when $x_0\ne 0$, and diverges for $\alpha >2$. This elementary example shows why an update formula needs a step-size condition. For a nonconvex objective, a small gradient can certify approximate stationarity without certifying a global minimum.