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 ff over XX and the points at which it is attained.

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

The function ff is the objective function and the set XX is the feasible set of the problem. A point of XX is feasible. Maximising ff is equivalent to minimising −f,-f, so only minimisation is considered.

Let min⁡x‾∈Xf(x‾)\min_{\underline{x}\in X}f(\underline{x}) be an optimisation problem. The optimal value of the problem is the infimum of ff over X.X.

p∗:=inf⁡x‾∈Xf(x‾)p^*:=\inf_{\underline{x}\in X}f(\underline{x})

The optimal value is −∞-\infty if ff is unbounded below on XX and ∞\infty if XX is empty.

Let min⁡x‾∈Xf(x‾)\min_{\underline{x}\in X}f(\underline{x}) be an optimisation problem with optimal value p∗.p^*. A minimiser or optimal solution of the problem is a point x‾∗∈X\underline{x}^*\in X with f(x‾∗)=p∗.f(\underline{x}^*)=p^*. 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\}.

Let min⁡x‾∈Xf(x‾)\min_{\underline{x}\in X}f(\underline{x}) be an optimisation problem. The problem is unconstrained if and only if the feasible set XX is Rn\mathbb{R}^n or an open subset of it, so that every point near a feasible point is feasible. The problem is constrained if and only if it is not unconstrained.

Let X⊆Rn,X\subseteq\mathbb{R}^n, f:X→Rf:X\rightarrow\mathbb{R} be a function and x‾∗∈X.\underline{x}^*\in X. The point x‾∗\underline{x}^* is a strict local minimiser of ff if and only if there exists δ>0\delta>0 such that f(x‾∗)<f(x‾)f(\underline{x}^*)<f(\underline{x}) for all x‾∈X\underline{x}\in X with x‾≠x‾∗\underline{x}\neq\underline{x}^* and ∥x‾−x‾∗∥<δ.\lVert\underline{x}-\underline{x}^*\rVert<\delta. A global minimiser is a local minimiser, but a local minimiser need not be global unless ff is convex.

Let X⊆RnX\subseteq\mathbb{R}^n be a non-empty compact set and f:X→Rf:X\rightarrow\mathbb{R} be continuous. By the Heine–Borel theorem XX is closed and bounded, and ff attains its minimum and maximum, so a global minimiser exists.

Let f:Rn→Rf:\mathbb{R}^n\rightarrow\mathbb{R} be a function. The function ff is coercive if and only if f(x‾)f(\underline{x}) grows without bound as ∥x‾∥\lVert\underline{x}\rVert does. If ff is continuous and coercive then a global minimiser of ff over Rn\mathbb{R}^n exists, since minimising over Rn\mathbb{R}^n 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}^*.

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

The condition holds since otherwise ff decreases along −∇f(x‾∗).-\nabla f(\underline{x}^*). A point satisfying the first-order necessary condition is a stationary point of f,f, as in the univariate case.

Let X⊆RnX\subseteq\mathbb{R}^n be open and f∈C2(X).f\in C^2(X). The second-order necessary condition states that the Hessian matrix of ff at a local minimiser is positive semi-definite. The second-order sufficient condition states that a stationary point at which the Hessian matrix is positive definite is a strict local minimiser. Both conditions follow from the second-order Taylor expansion at a stationary point.

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})

Let X⊆RnX\subseteq\mathbb{R}^n be open, f∈C2(X)f\in C^2(X) and x‾∗\underline{x}^* be a stationary point of f.f. The point x‾∗\underline{x}^* is a saddle point of ff if and only if the Hessian matrix at x‾∗\underline{x}^* has both positive and negative eigenvalues. A saddle point is neither a local minimiser nor a local maximiser. A stationary point with a positive semi-definite Hessian matrix that is singular may be a minimiser, a maximiser or neither; 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. An iterative method is a method that generates a sequence of iterates x‾0,x‾1,…\underline{x}_0,\underline{x}_1,\ldots intended to converge to a minimiser.

Let f:Rn→Rf:\mathbb{R}^n\rightarrow\mathbb{R} be differentiable. A line search method is an iterative method that 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 the iterate by moving along the search direction.

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

A line search method stops when ∥∇f(x‾k)∥\lVert\nabla f(\underline{x}_k)\rVert or the change in ff falls below a tolerance.

Let f:Rn→Rf:\mathbb{R}^n\rightarrow\mathbb{R} be differentiable at x‾\underline{x} and d‾∈Rn.\underline{d}\in\mathbb{R}^n. The 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

If d‾\underline{d} is a descent direction then f(x‾+αd‾)<f(x‾)f\left(\underline{x}+\alpha\underline{d}\right)<f(\underline{x}) for all sufficiently small α>0.\alpha>0.

Let ff be differentiable, x‾k\underline{x}_k be an iterate and d‾k\underline{d}_k be a descent direction. Exact line search is the choice of step size that minimises 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)

Let ff be differentiable, x‾k\underline{x}_k be an iterate, d‾k\underline{d}_k be a descent direction and c∈(0,1).c\in\left(0,1\right). The Armijo condition is the condition that the step size αk\alpha_k gives a decrease in ff proportional to the step size and the 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 ff be differentiable, x‾k\underline{x}_k be an iterate, d‾k\underline{d}_k be a descent direction and ρ∈(0,1).\rho\in\left(0,1\right). Backtracking line search is the choice of step size that starts from an initial step size and repeatedly multiplies it by ρ\rho until the Armijo condition holds.

Let (x‾k)(\underline{x}_k) be a sequence that converges to x‾∗\underline{x}^* and ek=∥x‾k−x‾∗∥.e_k=\lVert\underline{x}_k-\underline{x}^*\rVert. The convergence is linear if and only if there exist r∈(0,1)r\in\left(0,1\right) and KK with ek+1≤r eke_{k+1}\leq r\,e_k for all k≥K.k\geq K. The convergence is superlinear if and only if ek+1ek→0.\frac{e_{k+1}}{e_k}\rightarrow 0. The convergence is quadratic if and only if there exist M>0M>0 and KK with ek+1≤M ek2e_{k+1}\leq M\,e_k^2 for all k≥K.k\geq K. The convergence is sublinear if and only 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.

Let f:Rn→Rf:\mathbb{R}^n\rightarrow\mathbb{R} be differentiable. Gradient descent or steepest descent is the line search method whose search direction is 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)

In the context of gradient descent the step size is also called the learning rate. Gradient descent has the following properties:

  • the negative gradient is a descent direction whenever ∇f(x‾k)≠0‾;\nabla f(\underline{x}_k)\neq\underline{0};
  • by the Cauchy-Schwarz inequality the negative gradient 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.

Let f:Rn→Rf:\mathbb{R}^n\rightarrow\mathbb{R} be differentiable and L>0.L>0. The function ff is LL-smooth if and only if its gradient is Lipschitz continuous with constant L.L.

∥∇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}

Let ff be convex and LL-smooth with a global minimiser x‾∗.\underline{x}^*. Gradient descent with fixed step size αk=1L\alpha_k=\frac{1}{L} has the following convergence properties:

  • it 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};
  • 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.

Let ff be strongly convex with parameter μ\mu and LL-smooth. The condition number of the problem is the ratio κ=Lμ≥1.\kappa=\frac{L}{\mu}\geq 1. For a strongly convex quadratic objective the condition number 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.

Let f∈C2f\in C^2 and x‾k\underline{x}_k be an iterate at which Hf(x‾k)H_f(\underline{x}_k) is positive definite. The Newton direction at x‾k\underline{x}_k is the vector d‾k\underline{d}_k that solves the linear system

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

The Newton direction minimises the second-order Taylor expansion of ff at x‾k,\underline{x}_k, which has the unique minimiser x‾k+d‾k\underline{x}_k+\underline{d}_k when the Hessian matrix is positive definite.

Let f∈C2.f\in C^2. Newton’s method is the line search method with the Newton direction and step size αk=1.\alpha_k=1.

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)}. Newton’s method has the following properties:

  • 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;
  • 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;
  • each iteration requires the Hessian matrix and the solution of an n×nn\times n linear system, which is prohibitive for large n.n.

The damped Newton method is Newton’s method combined with backtracking line search, which is used far from the minimiser. Alternatively the Hessian matrix is modified to be positive definite.

Let ff be differentiable. A quasi-Newton method is a line search method that replaces the inverse Hessian matrix with a positive definite approximation BkB_k 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.

Let Bk+1B_{k+1} be the approximate inverse Hessian matrix of a quasi-Newton method. The secant condition is the condition that Bk+1B_{k+1} maps the change in gradient to the change in iterate.

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

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