Unconstrained Optimisation
Let be a set and be a function. An optimisation problem is the problem of finding the smallest value of over and the points at which it is attained.
The function is the objective function and the set is the feasible set of the problem. A point of is feasible. Maximising is equivalent to minimising so only minimisation is considered.
Let be an optimisation problem. The optimal value of the problem is the infimum of over
The optimal value is if is unbounded below on and if is empty.
Let be an optimisation problem with optimal value A minimiser or optimal solution of the problem is a point with The set of minimisers is written
Let be an optimisation problem. The problem is unconstrained if and only if the feasible set is 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 be a function and The point is a strict local minimiser of if and only if there exists such that for all with and A global minimiser is a local minimiser, but a local minimiser need not be global unless is convex.
Let be a non-empty compact set and be continuous. By the Heine–Borel theorem is closed and bounded, and attains its minimum and maximum, so a global minimiser exists.
Let be a function. The function is coercive if and only if grows without bound as does. If is continuous and coercive then a global minimiser of over exists, since minimising over reduces to minimising over a compact sublevel set.
Let be open and be differentiable at a local minimiser The first-order necessary condition states that the gradient vanishes at
The condition holds since otherwise decreases along A point satisfying the first-order necessary condition is a stationary point of as in the univariate case.
Let be open and The second-order necessary condition states that the Hessian matrix of 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.
Let be open, and be a stationary point of The point is a saddle point of if and only if the Hessian matrix at 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, is a minimiser of a maximiser of and neither for
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 intended to converge to a minimiser.
Let be differentiable. A line search method is an iterative method that chooses at each iterate a search direction and a step size and updates the iterate by moving along the search direction.
A line search method stops when or the change in falls below a tolerance.
Let be differentiable at and The direction is a descent direction of at if and only if the directional derivative along it is negative.
If is a descent direction then for all sufficiently small
Let be differentiable, be an iterate and be a descent direction. Exact line search is the choice of step size that minimises along the search direction.
Let be differentiable, be an iterate, be a descent direction and The Armijo condition is the condition that the step size gives a decrease in proportional to the step size and the directional derivative.
Let be differentiable, be an iterate, be a descent direction and Backtracking line search is the choice of step size that starts from an initial step size and repeatedly multiplies it by until the Armijo condition holds.
Let be a sequence that converges to and The convergence is linear if and only if there exist and with for all The convergence is superlinear if and only if The convergence is quadratic if and only if there exist and with for all The convergence is sublinear if and only if but no such exists, for example Quadratic convergence roughly doubles the number of correct digits at each iteration.
Let be differentiable. Gradient descent or steepest descent is the line search method whose search direction is the negative gradient.
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
- by the Cauchy-Schwarz inequality the negative gradient is the direction with that makes the directional derivative most negative.
Let be differentiable and The function is -smooth if and only if its gradient is Lipschitz continuous with constant
Let be convex and -smooth with a global minimiser Gradient descent with fixed step size has the following convergence properties:
- it converges sublinearly in objective value,
- if is additionally strongly convex with parameter then it converges linearly,
Let be strongly convex with parameter and -smooth. The condition number of the problem is the ratio 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 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 and be an iterate at which is positive definite. The Newton direction at is the vector that solves the linear system
The Newton direction minimises the second-order Taylor expansion of at which has the unique minimiser when the Hessian matrix is positive definite.
Let Newton’s method is the line search method with the Newton direction and step size
Newton’s method is equivalently the method for solving the stationarity equation by repeatedly solving its linear approximation, which for a univariate equation is the iteration Newton’s method has the following properties:
- if is a stationary point with positive definite and is Lipschitz continuous near then Newton’s method converges quadratically to 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 linear system, which is prohibitive for large
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 be differentiable. A quasi-Newton method is a line search method that replaces the inverse Hessian matrix with a positive definite approximation updated at each iteration using only gradient differences, giving the search direction and a cost per iteration comparable to gradient descent.
Let be the approximate inverse Hessian matrix of a quasi-Newton method. The secant condition is the condition that maps the change in gradient to the change in iterate.
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.