Let X⊆RnX\subseteq\mathbb{R}^n be a set and f:X→Rf:X\rightarrow\mathbb{R} be a function. An optimisation problem is the problem of finding the smallest value of the objective function ff over the feasible set X,X, whose points are feasible, and the points at which it is attained.

min⁡x‾∈Xf(x‾)\min_{\underline{x}\in X}f(\underline{x})

The optimal value p∗=inf⁡x‾∈Xf(x‾)p^*=\inf_{\underline{x}\in X}f(\underline{x}) is the infimum of ff over X,X, which is −∞-\infty if ff is unbounded below and ∞\infty if XX is empty. A minimiser or optimal solution is a point x‾∗∈X\underline{x}^*\in X with f(x‾∗)=p∗,f(\underline{x}^*)=p^*, and the set of minimisers is written

arg min⁡x‾∈Xf(x‾):={x‾∗∈X:f(x‾∗)≤f(x‾)  ∀ x‾∈X}.\operatorname*{arg\,min}_{\underline{x}\in X}f(\underline{x}):=\left\{\underline{x}^*\in X:f(\underline{x}^*)\leq f(\underline{x})\,\,\forall\,\underline{x}\in X\right\}.

Maximising ff is equivalent to minimising −f,-f, so only minimisation is considered. The problem is unconstrained if the feasible set is Rn\mathbb{R}^n or an open subset of it, so that every point near a feasible point is feasible, and constrained otherwise.

A point x‾∗∈X\underline{x}^*\in X is a local minimiser of ff if and only if there exists δ>0\delta>0 such that f(x‾∗)≤f(x‾)f(\underline{x}^*)\leq f(\underline{x}) for all x‾∈X\underline{x}\in X with ∥x‾−x‾∗∥<δ,\lVert\underline{x}-\underline{x}^*\rVert<\delta, a strict local minimiser if the inequality is strict for x‾≠x‾∗\underline{x}\neq\underline{x}^* and a global minimiser if and only if f(x‾∗)≤f(x‾)  ∀ x‾∈X.f(\underline{x}^*)\leq f(\underline{x})\,\,\forall\,\underline{x}\in X. A global minimiser is a local minimiser, but a local minimiser need not be global unless ff is convex.

By the Heine–Borel theorem a set X⊆RnX\subseteq\mathbb{R}^n is compact if and only if it is closed and bounded, and a continuous function on a non-empty compact set attains its minimum and maximum, so a global minimiser exists. For an unconstrained problem on Rn\mathbb{R}^n a global minimiser exists if ff is continuous and coercive, meaning that f(x‾)f(\underline{x}) grows without bound as ∥x‾∥\lVert\underline{x}\rVert does, since minimising over Rn\mathbb{R}^n then reduces to minimising over a compact sublevel set.

Let X⊆RnX\subseteq\mathbb{R}^n be open and f:X→Rf:X\rightarrow\mathbb{R} be differentiable at a local minimiser x‾∗.\underline{x}^*. The first-order necessary condition states that the gradient vanishes at x‾∗,\underline{x}^*, since otherwise ff decreases along −∇f(x‾∗).-\nabla f(\underline{x}^*).

∇f(x‾∗)=0‾\nabla f(\underline{x}^*)=\underline{0}

A point satisfying this condition is a stationary point of f,f, as in the univariate case. If f∈C2(X)f\in C^2(X) the second-order necessary condition states that the Hessian matrix at a local minimiser is positive semi-definite, and the second-order sufficient condition states that a stationary point at which the Hessian matrix is positive definite is a strict local minimiser. Both follow from the second-order Taylor expansion

f(x‾∗+h‾)=f(x‾∗)+12h‾⊺Hf(x‾∗) h‾+R2(h‾).f\left(\underline{x}^*+\underline{h}\right)=f(\underline{x}^*)+\frac{1}{2}\underline{h}^\intercal H_f(\underline{x}^*)\,\underline{h}+R_2(\underline{h}).

A stationary point whose Hessian matrix has both positive and negative eigenvalues, so is neither positive nor negative semi-definite, is a saddle point and is neither a local minimiser nor a local maximiser. A stationary point with a positive semi-definite Hessian matrix that is singular may be any of the three; for example, 00 is a minimiser of x4,x^4, a maximiser of −x4-x^4 and neither for x3.x^3.

Most optimisation problems cannot be solved by finding stationary points in closed form and are solved by an iterative method that generates a sequence of iterates x‾0,x‾1,…\underline{x}_0,\underline{x}_1,\ldots intended to converge to a minimiser. A line search method chooses at each iterate a search direction d‾k∈Rn\underline{d}_k\in\mathbb{R}^n and a step size αk>0\alpha_k>0 and updates

x‾k+1=x‾k+αkd‾k.\underline{x}_{k+1}=\underline{x}_k+\alpha_k\underline{d}_k.

A direction d‾\underline{d} is a descent direction of ff at x‾\underline{x} if and only if the directional derivative along it is negative, ∇f(x‾)⊺d‾<0,\nabla f(\underline{x})^\intercal\underline{d}<0, in which case f(x‾+αd‾)<f(x‾)f\left(\underline{x}+\alpha\underline{d}\right)<f(\underline{x}) for all sufficiently small α>0.\alpha>0. The method stops when ∥∇f(x‾k)∥\lVert\nabla f(\underline{x}_k)\rVert or the change in ff falls below a tolerance.

The step size may be fixed, chosen by exact line search as the minimiser of ff along the search direction,

αk=arg min⁡α>0f(x‾k+αd‾k),\alpha_k=\operatorname*{arg\,min}_{\alpha>0}f\left(\underline{x}_k+\alpha\underline{d}_k\right),

or chosen by backtracking line search, which starts from an initial step size and repeatedly multiplies it by a factor ρ∈(0,1)\rho\in\left(0,1\right) until the Armijo condition holds for some c∈(0,1),c\in\left(0,1\right), guaranteeing a decrease in ff proportional to the step size and directional derivative.

f(x‾k+αkd‾k)≤f(x‾k)+c αk∇f(x‾k)⊺d‾kf\left(\underline{x}_k+\alpha_k\underline{d}_k\right)\leq f(\underline{x}_k)+c\,\alpha_k\nabla f(\underline{x}_k)^\intercal\underline{d}_k

Let (x‾k)(\underline{x}_k) converge to x‾∗\underline{x}^* and ek=∥x‾k−x‾∗∥.e_k=\lVert\underline{x}_k-\underline{x}^*\rVert. The convergence is linear if there exist r∈(0,1)r\in\left(0,1\right) and KK with ek+1≤r ek  ∀ k≥K,e_{k+1}\leq r\,e_k\,\,\forall\,k\geq K, superlinear if ek+1ek→0\frac{e_{k+1}}{e_k}\rightarrow 0 and quadratic if there exist M>0M>0 and KK with ek+1≤M ek2  ∀ k≥K.e_{k+1}\leq M\,e_k^2\,\,\forall\,k\geq K. Convergence is sublinear if ek→0e_k\rightarrow 0 but no such r<1r<1 exists, for example ek=1k.e_k=\frac{1}{k}. Quadratic convergence roughly doubles the number of correct digits at each iteration.

Gradient descent or steepest descent is the line search method with search direction the negative gradient.

x‾k+1=x‾k−αk∇f(x‾k)\underline{x}_{k+1}=\underline{x}_k-\alpha_k\nabla f(\underline{x}_k)

The negative gradient is a descent direction whenever ∇f(x‾k)≠0‾,\nabla f(\underline{x}_k)\neq\underline{0}, and by the Cauchy-Schwarz inequality it is the direction d‾\underline{d} with ∥d‾∥=∥∇f(x‾k)∥\lVert\underline{d}\rVert=\lVert\nabla f(\underline{x}_k)\rVert that makes the directional derivative ∇f(x‾k)⊺d‾\nabla f(\underline{x}_k)^\intercal\underline{d} most negative. In the context of gradient descent the step size is also called the learning rate.

Let ff be differentiable with a gradient that is Lipschitz continuous with constant L>0,L>0, in which case ff is LL-smooth.

∥∇f(x‾)−∇f(y‾)∥≤L ∥x‾−y‾∥  ∀ x‾,y‾\lVert\nabla f(\underline{x})-\nabla f(\underline{y})\rVert\leq L\,\lVert\underline{x}-\underline{y}\rVert\,\,\forall\,\underline{x},\underline{y}

If ff is convex and LL-smooth with a global minimiser x‾∗\underline{x}^* then gradient descent with fixed step size αk=1L\alpha_k=\frac{1}{L} converges sublinearly in objective value,

f(x‾k)−f(x‾∗)≤L ∥x‾0−x‾∗∥22k,f(\underline{x}_k)-f(\underline{x}^*)\leq\frac{L\,\lVert\underline{x}_0-\underline{x}^*\rVert^2}{2k},

and if ff is additionally strongly convex with parameter μ\mu then it converges linearly,

∥x‾k−x‾∗∥2≤(1−μL)k∥x‾0−x‾∗∥2.\lVert\underline{x}_k-\underline{x}^*\rVert^2\leq\left(1-\frac{\mu}{L}\right)^k\lVert\underline{x}_0-\underline{x}^*\rVert^2.

The ratio κ=Lμ≥1\kappa=\frac{L}{\mu}\geq 1 is the condition number of the problem, and for a strongly convex quadratic objective it is the ratio of the largest to the smallest eigenvalue of the Hessian matrix. Gradient descent is slow when κ\kappa is large because the gradient points across the narrow valley of the objective rather than along it. A step size that is too large causes the iterates to diverge, and one that is too small makes progress slow.

Newton’s method chooses the search direction by minimising the second-order Taylor expansion of ff at the current iterate. If Hf(x‾k)H_f(\underline{x}_k) is positive definite this quadratic has the unique minimiser x‾k+d‾k\underline{x}_k+\underline{d}_k where the Newton direction d‾k\underline{d}_k solves

Hf(x‾k) d‾k=−∇f(x‾k)H_f(\underline{x}_k)\,\underline{d}_k=-\nabla f(\underline{x}_k)

so that the Newton step with step size αk=1\alpha_k=1 is

x‾k+1=x‾k−Hf(x‾k)−1∇f(x‾k).\underline{x}_{k+1}=\underline{x}_k-H_f(\underline{x}_k)^{-1}\nabla f(\underline{x}_k).

Newton’s method is equivalently the method for solving the stationarity equation ∇f(x‾)=0‾\nabla f(\underline{x})=\underline{0} by repeatedly solving its linear approximation, which for a univariate equation g(x)=0g(x)=0 is the iteration xk+1=xk−g(xk)g′(xk).x_{k+1}=x_k-\frac{g(x_k)}{g'(x_k)}. If x‾∗\underline{x}^* is a stationary point with positive definite Hf(x‾∗)H_f(\underline{x}^*) and HfH_f is Lipschitz continuous near x‾∗,\underline{x}^*, then Newton’s method converges quadratically to x‾∗\underline{x}^* from any sufficiently close starting point, and it minimises a strongly convex quadratic function exactly in one step. The Newton direction is a descent direction only when the Hessian matrix is positive definite, so far from the minimiser the method is combined with backtracking line search, giving the damped Newton method, or the Hessian matrix is modified to be positive definite. Each iteration requires the Hessian matrix and the solution of an n×nn\times n linear system, which is prohibitive for large n.n.

Quasi-Newton methods replace the inverse Hessian matrix with a positive definite approximation BkB_k that is updated at each iteration using only gradient differences, giving the search direction d‾k=−Bk∇f(x‾k)\underline{d}_k=-B_k\nabla f(\underline{x}_k) and a cost per iteration comparable to gradient descent. The update is chosen so that the new approximation satisfies the secant condition

Bk+1(∇f(x‾k+1)−∇f(x‾k))=x‾k+1−x‾k,B_{k+1}\left(\nabla f(\underline{x}_{k+1})-\nabla f(\underline{x}_k)\right)=\underline{x}_{k+1}-\underline{x}_k,

which the true inverse Hessian matrix satisfies approximately by the mean value theorem, and the most widely used update is the Broyden–Fletcher–Goldfarb–Shanno (BFGS) update. Quasi-Newton methods with line search converge superlinearly under the conditions that give Newton’s method quadratic convergence.