Gradient descent

Mathematical statement

For differentiable f:R^d→R and explicit alpha_k>0, unconstrained gradient descent updates x_(k+1)=x_k−alpha_k*grad f(x_k). The exact family fixes coordinate order and a positive diagonal quadratic f(x)=1/2*sum_i d_i*x_i^2+sum_i b_i*x_i, recalculating every gradient, iterate and objective. A safe finite trace additionally checks strictly0<alpha<2/L with L=max_i d_i and audits each objective comparison. This is not a convergence certificate for arbitrary functions or an unverified infinite sequence. A positive step alone need not descend, a zero gradient may occur at a maximum or saddle, and an unconstrained step is not projected or constrained descent.

Representative formula (exact TeX)

G(f,x,a)=y

Assumptions

• Positive diagonal and linear vectors have the same arity and fixed coordinate order; all values are bounded exact rationals.
• The one-step family requires only alpha>0; a safe trace separately requires0<alpha<2/L.
• Only unconstrained deterministic gradient descent is covered, not projection, stochastic updates or line search.

Symbol scope

• G — gradient-descent update
• f — differentiable objective
• x — current vector
• a — positive step size
• y — next vector

Intuition, definition, and misconceptions

Declare coordinate order, objective and step size together.

Check each safe diagonal-quadratic step rather than substituting alpha>0 for descent conditions.

Stationarity, local/global optimality and convergence are distinct responsibilities.

alpha>0 alone does not imply descent, and neither a zero gradient nor a finite trace proves global optimality or convergence.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Gradient vector — Supply the negative-gradient update.
• Optimization problem — Specify the objective and minimization semantics.
• Sequence — Keep the ordered iterate trace.
• Real vector space — Use Euclidean vector updates and inner products.

Verification boundary

No general convex/nonconvex convergence rate, projection or stochastic update is claimed.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add the L-smooth convex descent lemma, strongly convex rates and projected gradient descent.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.