This is a list of numerical analysis topics.
General Validated numerics Iterative method Rate of convergence — the speed at which a convergent sequence approaches its limit Order of accuracy — rate at which numerical solution of differential equation converges to exact solution Series acceleration — methods to accelerate the speed of convergence of a series Aitken's delta-squared process — most useful for linearly converging sequences Minimum polynomial extrapolation — for vector sequences Richardson extrapolation Shanks transformation — similar to Aitken's delta-squared process, but applied to the partial sums Van Wijngaarden transformation — for accelerating the convergence of an alternating series Abramowitz and Stegun — book containing formulas and tables of many special functions Digital Library of Mathematical Functions — successor of book by Abramowitz and Stegun Curse of dimensionality Local convergence and global convergence — whether you need a good initial guess to get convergence Superconvergence Discretization Difference quotient Complexity: Computational complexity of mathematical operations Smoothed analysis — measuring the expected performance of algorithms under slight random perturbations of worst-case inputs Symbolic-numeric computation — combination of symbolic and numeric methods Cultural and historical aspects: History of numerical solution of differential equations using computers Hundred-dollar, Hundred-digit Challenge problems — list of ten problems proposed by Nick Trefethen in 2002 Timeline of numerical analysis after 1945 General classes of methods: Collocation method — discretizes a continuous equation by requiring it only to hold at certain points Level-set method Level set (data structures) — data structures for representing level sets Sinc numerical methods — methods based on the sinc function, sinc(x) = sin(x) / x ABS methods
Error Error analysis (mathematics)
Approximation Approximation error Catastrophic cancellation Condition number Discretization error Floating point number Guard digit — extra precision introduced during a computation to reduce round-off error Truncation — rounding a floating-point number by discarding all digits after a certain digit Round-off error Numeric precision in Microsoft Excel Arbitrary-precision arithmetic Interval arithmetic — represent every number by two floating-point numbers guaranteed to have the unknown number between them Interval contractor — maps interval to subinterval which still contains the unknown exact answer Interval propagation — contracting interval domains without removing any value consistent with the constraints See also: Interval boundary element method, Interval finite element Loss of significance Numerical error Numerical stability Error propagation: Propagation of uncertainty Residual (numerical analysis) Relative change and difference — the relative difference between x and y is |x − y| / max(|x|, |y|) Significant figures Artificial precision — when a numerical value or semantic is expressed with more precision than was initially provided from measurement or user input False precision — giving more significant figures than appropriate Sterbenz lemma Truncation error — error committed by doing only a finite numbers of steps Well-posed problem Affine arithmetic
Elementary and special functions Unrestricted algorithm Summation: Kahan summation algorithm Pairwise summation — slightly worse than Kahan summation but cheaper Binary splitting 2Sum Multiplication: Multiplication algorithm — general discussion, simple methods Karatsuba algorithm — the first algorithm which is faster than straightforward multiplication Toom–Cook multiplication — generalization of Karatsuba multiplication Schönhage–Strassen algorithm — based on Fourier transform, asymptotically very fast Fürer's algorithm — asymptotically slightly faster than Schönhage–Strassen Division algorithm — for computing quotient and/or remainder of two numbers Long division Restoring division Non-restoring division SRT division Newton–Raphson division: uses Newton's method to find the reciprocal of D, and multiply that reciprocal by N to find the final quotient Q. Goldschmidt division Exponentiation: Exponentiation by squaring Addition-chain exponentiation Multiplicative inverse Algorithms: for computing a number's multiplicative inverse (reciprocal). Newton's method Polynomials: Horner's method Estrin's scheme — modification of the Horner scheme with more possibilities for parallelization Clenshaw algorithm De Casteljau's algorithm Square roots and other roots: Integer square root Methods of computing square roots nth root algorithm hypot — the function (x2 + y2)1/2 Alpha max plus beta min algorithm — approximates hypot(x,y) Fast inverse square root — calculates 1 / √x using details of the IEEE floating-point system Elementary functions (exponential, logarithm, trigonometric functions): Trigonometric tables — different methods for generating them CORDIC — shift-and-add algorithm using a table of arc tangents BKM algorithm — shift-and-add algorithm using a table of logarithms and complex numbers Gamma function: Lanczos approximation Spouge's approximation — modification of Stirling's approximation; easier to apply than Lanczos AGM method — computes arithmetic–geometric mean; related methods compute special functions FEE method (Fast E-function Evaluation) — fast summation of series like the power series for ex Gal's accurate tables — table of function values with unequal spacing to reduce round-off error Spigot algorithm — algorithms that can compute individual digits of a real number Approximations of π: Liu Hui's π algorithm — first algorithm that can compute π to arbitrary precision Leibniz formula for π — alternating series with very slow convergence Wallis product — infinite product converging slowly to π/2 Viète's formula — more complicated infinite product which converges faster Gauss–Legendre algorithm — iteration which converges quadratically to π, based on arithmetic–geometric mean Borwein's algorithm — iteration which converges quartically to 1/π, and other algorithms Chudnovsky algorithm — fast algorithm that calculates a hypergeometric series Bailey–Borwein–Plouffe formula — can be used to compute individual hexadecimal digits of π Bellard's formula — faster version of Bailey–Borwein–Plouffe formula List of formulae involving π
Numerical linear algebra Numerical linear algebra — study of numerical algorithms for linear algebra problems
Basic concepts Types of matrices appearing in numerical analysis: Sparse matrix Band matrix Bidiagonal matrix Tridiagonal matrix Pentadiagonal matrix Skyline matrix Circulant matrix Triangular matrix Diagonally dominant matrix Block matrix — matrix composed of smaller matrices Stieltjes matrix — symmetric positive definite with non-positive off-diagonal entries Hilbert matrix — example of a matrix which is extremely ill-conditioned (and thus difficult to handle) Wilkinson matrix — example of a symmetric tridiagonal matrix with pairs of nearly, but not exactly, equal eigenvalues Convergent matrix — square matrix whose successive powers approach the zero matrix Algorithms for matrix multiplication: Strassen algorithm Coppersmith–Winograd algorithm Cannon's algorithm — a distributed algorithm, especially suitable for processors laid out in a 2d grid Freivalds' algorithm — a randomized algorithm for checking the result of a multiplication Matrix decompositions: LU decomposition — lower triangular times upper triangular QR decomposition — orthogonal matrix times triangular matrix RRQR factorization — rank-revealing QR factorization, can be used to compute rank of a matrix Polar decomposition — unitary matrix times positive-semidefinite Hermitian matrix Decompositions by similarity: Eigendecomposition — decomposition in terms of eigenvectors and eigenvalues Jordan normal form — bidiagonal matrix of a certain form; generalizes the eigendecomposition Weyr canonical form — permutation of Jordan normal form Jordan–Chevalley decomposition — sum of commuting nilpotent matrix and diagonalizable matrix Schur decomposition — similarity transform bringing the matrix to a triangular matrix Singular value decomposition — unitary matrix times diagonal matrix times unitary matrix Matrix splitting — expressing a given matrix as a sum or difference of matrices
Solving systems of linear equations Gaussian elimination Row echelon form — matrix in which all entries below a nonzero entry are zero Bareiss algorithm — variant which ensures that all entries remain integers if the initial matrix has integer entries Tridiagonal matrix algorithm — simplified form of Gaussian elimination for tridiagonal matrices LU decomposition — write a matrix as a product of an upper- and a lower-triangular matrix Crout matrix decomposition LU reduction — a special parallelized version of a LU decomposition algorithm Block LU decomposition Cholesky decomposition — for solving a system with a positive definite matrix Minimum degree algorithm Symbolic Cholesky decomposition Iterative refinement — procedure to turn an inaccurate solution in a more accurate one Direct methods for sparse matrices: Frontal solver — used in finite element methods Nested dissection — for symmetric matrices, based on graph partitioning Levinson recursion — for Toeplitz matrices SPIKE algorithm — hybrid parallel solver for narrow-banded matrices Cyclic reduction — eliminate even or odd rows or columns, repeat Iterative methods: Jacobi method Gauss–Seidel method Successive over-relaxation (SOR) — a technique to accelerate the Gauss–Seidel method Symmetric successive over-relaxation (SSOR) — variant of SOR for symmetric matrices Backfitting algorithm — iterative procedure used to fit a generalized additive model, often equivalent to Gauss–Seidel Modified Richardson iteration Conjugate gradient method (CG) — assumes that the matrix is positive definite Derivation of the conjugate gradient method Nonlinear conjugate gradient method — generalization for nonlinear optimization problems Biconjugate gradient method (BiCG) Biconjugate gradient stabilized method (BiCGSTAB) — variant of BiCG with better convergence Conjugate residual method — similar to CG but only assumed that the matrix is symmetric Generalized minimal residual method (GMRES) — based on the Arnoldi iteration Chebyshev iteration — avoids inner products but needs bounds on the spectrum Stone's method (SIP — Strongly Implicit Procedure) — uses an incomplete LU decomposition Kaczmarz method Preconditioner Incomplete Cholesky factorization — sparse approximation to the Cholesky factorization Incomplete LU factorization — sparse approximation to the LU factorization Uzawa iteration — for saddle node problems Underdetermined and overdetermined systems (systems that have no or more than one solution): Numerical computation of null space — find all solutions of an underdetermined system Moore–Penrose pseudoinverse — for finding solution with smallest 2-norm (for underdetermined systems) or smallest residual Sparse approximation — for finding the sparsest solution (i.e., the solution with as many zeros as possible)
Eigenvalue algorithms Eigenvalue algorithm — a numerical algorithm for locating the eigenvalues of a matrix
Power iteration Inverse iteration Rayleigh quotient iteration Arnoldi iteration — based on Krylov subspaces Lanczos algorithm — Arnoldi, specialized for positive-definite matrices Block Lanczos algorithm — for when matrix is over a finite field QR algorithm Jacobi eigenvalue algorithm — select a small submatrix which can be diagonalized exactly, and repeat Jacobi rotation — the building block, almost a Givens rotation Jacobi method for complex Hermitian matrices Divide-and-conquer eigenvalue algorithm Folded spectrum method LOBPCG — Locally Optimal Block Preconditioned Conjugate Gradient Method Eigenvalue perturbation — stability of eigenvalues under perturbations of the matrix
Other concepts and algorithms Orthogonalization algorithms: Gram–Schmidt process Householder transformation Householder operator — analogue of Householder transformation for general inner product spaces Givens rotation Krylov subspace Block matrix pseudoinverse Bidiagonalization Cuthill–McKee algorithm — permutes rows/columns in sparse matrix to yield a narrow band matrix In-place matrix transposition — computing the transpose of a matrix without using much additional storage Pivot element — entry in a matrix on which the algorithm concentrates Matrix-free methods — methods that only access the matrix by evaluating matrix-vector products
Interpolation and approximation Interpolation — construct a function going through some given data points
Nearest-neighbor interpolation — takes the value of the nearest neighbor
Polynomial interpolation Polynomial interpolation — interpolation by polynomials
Linear interpolation Runge's phenomenon Vandermonde matrix Chebyshev polynomials Chebyshev nodes Lebesgue constants Different forms for the interpolant: Newton polynomial Divided differences Neville's algorithm — for evaluating the interpolant; based on the Newton form Lagrange polynomial Bernstein polynomial — especially useful for approximation Brahmagupta's interpolation formula — seventh-century formula for quadratic interpolation Extensions to multiple dimensions: Bilinear interpolation Trilinear interpolation Bicubic interpolation Tricubic interpolation Padua points — set of points in R2 with unique polynomial interpolant and minimal growth of Lebesgue constant Hermite interpolation Birkhoff interpolation Abel–Goncharov interpolation
Spline interpolation Spline interpolation — interpolation by piecewise polynomials
Spline (mathematics) — the piecewise polynomials used as interpolants Perfect spline — polynomial spline of degree m whose mth derivate is ±1 Cubic Hermite spline Centripetal Catmull–Rom spline — special case of cubic Hermite splines without self-intersections or cusps Monotone cubic interpolation Hermite spline Bézier curve De Casteljau's algorithm composite Bézier curve Generalizations to more dimensions: Bézier triangle — maps a triangle to R3 Bézier surface — maps a square to R3 B-spline Box spline — multivariate generalization of B-splines Truncated power function De Boor's algorithm — generalizes De Casteljau's algorithm Non-uniform rational B-spline (NURBS) T-spline — can be thought of as a NURBS surface for which a row of control points is allowed to terminate Kochanek–Bartels spline Coons patch — type of manifold parametrization used to smoothly join other surfaces together M-spline — a non-negative spline I-spline — a monotone spline, defined in terms of M-splines Smoothing spline — a spline fitted smoothly to noisy data Blossom (functional) — a unique, affine, symmetric map associated to a polynomial or spline See also: List of numerical computational geometry topics
Trigonometric interpolation Trigonometric interpolation — interpolation by trigonometric polynomials
Discrete Fourier transform — can be viewed as trigonometric interpolation at equidistant points Relations between Fourier transforms and Fourier series Fast Fourier transform (FFT) — a fast method for computing the discrete Fourier transform Bluestein's FFT algorithm Bruun's FFT algorithm Cooley–Tukey FFT algorithm Split-radix FFT algorithm — variant of Cooley–Tukey that uses a blend of radices 2 and 4 Goertzel algorithm Prime-factor FFT algorithm Rader's FFT algorithm Bit-reversal permutation — particular permutation of vectors with 2m entries used in many FFTs. Butterfly diagram Twiddle factor — the trigonometric constant coefficients that are multiplied by the data Cyclotomic fast Fourier transform — for FFT over finite fields Methods for computing discrete convolutions with finite impulse response filters using the FFT: Overlap–add method Overlap–save method Sigma approximation Dirichlet kernel — convolving any function with the Dirichlet kernel yields its trigonometric interpolant Gibbs phenomenon
Other interpolants Simple rational approximation Polynomial and rational function modeling — comparison of polynomial and rational interpolation Wavelet Continuous wavelet Transfer matrix See also: List of functional analysis topics, List of wavelet-related transforms Inverse distance weighting Radial basis function (RBF) — a function of the form ƒ(x) = φ(|x−x0|) Polyharmonic spline — a commonly used radial basis function Thin plate spline — a specific polyharmonic spline: r2 log r Hierarchical RBF Subdivision surface — constructed by recursively subdividing a piecewise linear interpolant Catmull–Clark subdivision surface Doo–Sabin subdivision surface Loop subdivision surface Slerp (spherical linear interpolation) — interpolation between two points on a sphere Generalized quaternion interpolation — generalizes slerp for interpolation between more than two quaternions Irrational base discrete weighted transform Nevanlinna–Pick interpolation — interpolation by analytic functions in the unit disc subject to a bound Pick matrix — the Nevanlinna–Pick interpolation has a solution if this matrix is positive semi-definite Multivariate interpolation — the function being interpolated depends on more than one variable Barnes interpolation — method for two-dimensional functions using Gaussians common in meteorology Coons surface — combination of linear interpolation and bilinear interpolation Lanczos resampling — based on convolution with a sinc function Natural neighbor interpolation PDE surface Transfinite interpolation — constructs function on planar domain given its values on the boundary Trend surface analysis — based on low-order polynomials of spatial coordinates; uses scattered observations Method based on polynomials are listed under Polynomial interpolation
Approximation theory Approximation theory
Orders of approximation Lebesgue's lemma Curve fitting Vector field reconstruction Modulus of continuity — measures smoothness of a function Least squares (function approximation) — minimizes the error in the L2-norm Minimax approximation algorithm — minimizes the maximum error over an interval (the L∞-norm) Equioscillation theorem — characterizes the best approximation in the L∞-norm Unisolvent point set — function from given function space is determined uniquely by values on such a set of points Stone–Weierstrass theorem — continuous functions can be approximated uniformly by polynomials, or certain other function spaces Approximation by polynomials: Linear approximation Bernstein polynomial — basis of polynomials useful for approximating a function Bernstein's constant — error when approximating |x| by a polynomial Remez algorithm — for constructing the best polynomial approximation in the L∞-norm Bernstein's inequality (mathematical analysis) — bound on maximum of derivative of polynomial in unit disk Mergelyan's theorem — generalization of Stone–Weierstrass theorem for polynomials Müntz–Szász theorem — variant of Stone–Weierstrass theorem for polynomials if some coefficients have to be zero Bramble–Hilbert lemma — upper bound on Lp error of polynomial approximation in multiple dimensions Discrete Chebyshev polynomials — polynomials orthogonal with respect to a discrete measure Favard's theorem — polynomials satisfying suitable 3-term recurrence relations are orthogonal polynomials Approximation by Fourier series / trigonometric polynomials: Jackson's inequality — upper bound for best approximation by a trigonometric polynomial Bernstein's theorem (approximation theory) — a converse to Jackson's inequality Fejér's theorem — Cesàro means of partial sums of Fourier series converge uniformly for continuous periodic functions Erdős–Turán inequality — bounds distance between probability and Lebesgue measure in terms of Fourier coefficients Different approximations: Moving least squares Padé approximant Padé table — table of Padé approximants Hartogs–Rosenthal theorem — continuous functions can be approximated uniformly by rational functions on a set of Lebesgue measure zero Szász–Mirakyan operator — approximation by e−n xk on a semi-infinite interval Szász–Mirakjan–Kantorovich operator Baskakov operator — generalize Bernstein polynomials, Szász–Mirakyan operators, and Lupas operators Favard operator — approximation by sums of Gaussians Surrogate model — application: replacing a function that is hard to evaluate by a simpler function Constructive function theory — field that studies connection between degree of approximation and smoothness Universal differential equation — differential–algebraic equation whose solutions can approximate any continuous function Fekete problem — find N points on a sphere that minimize some kind of energy Carleman's condition — condition guaranteeing that a measure is uniquely determined by its moments Krein's condition — condition that exponential sums are dense in weighted L2 space Lethargy theorem — about distance of points in a metric space from members of a sequence of subspaces Wirtinger's representation and projection theorem Journals: Constructive Approximation Journal of Approximation Theory
Miscellaneous Extrapolation Linear predictive analysis — linear extrapolation Unisolvent functions — functions for which the interpolation problem has a unique solution Regression analysis Isotonic regression Curve-fitting compaction Interpolation (computer graphics)
Finding roots of nonlinear equations See #Numerical linear algebra for linear equations Root-finding algorithm — algorithms for solving the equation f(x) = 0
General methods: Bisection method — simple and robust; linear convergence Lehmer–Schur algorithm — variant for complex functions Fixed-point iteration Newton's method — based on linear approximation around the current iterate; quadratic convergence Kantorovich theorem — gives a region around solution such that Newton's method converges Newton fractal — indicates which initial condition converges to which root under Newton iteration Quasi-Newton method — uses an approximation of the Jacobian: Broyden's method — uses a rank-one update for the Jacobian Symmetric rank-one — a symmetric (but not necessarily positive definite) rank-one update of the Jacobian Davidon–Fletcher–Powell formula — update of the Jacobian in which the matrix remains positive definite Broyden–Fletcher–Goldfarb–Shanno algorithm — rank-two update of the Jacobian in which the matrix remains positive definite Limited-memory BFGS method — truncated, matrix-free variant of BFGS method suitable for large problems Steffensen's method — uses divided differences instead of the derivative Secant method — based on linear interpolation at last two iterates False position method — secant method with ideas from the bisection method Muller's method — based on quadratic interpolation at last three iterates Sidi's generalized secant method — higher-order variants of secant method Inverse quadratic interpolation — similar to Muller's method, but interpolates the inverse Brent's method — combines bisection method, secant method and inverse quadratic interpolation Ridders' method — fits a linear function times an exponential to last two iterates and their midpoint Halley's method — uses f, f' and f''; achieves the cubic convergence Householder's method — uses first d derivatives to achieve order d + 1; generalizes Newton's and Halley's method Methods for polynomials: Aberth method Bairstow's method Durand–Kerner method Graeffe's method Jenkins–Traub algorithm — fast, reliable, and widely used Laguerre's method Splitting circle method Analysis: Wilkinson's polynomial Numerical continuation — tracking a root as one parameter in the equation changes Piecewise linear continuation
Optimization Mathematical optimization — algorithm for finding maxima or minima of a given function
Basic concepts Active set Candidate solution Constraint (mathematics) Constrained optimization — studies optimization problems with constraints Binary constraint — a constraint that involves exactly two variables Corner solution Feasible region — contains all solutions that satisfy the constraints but may not be optimal Global optimum and Local optimum Maxima and minima Slack variable Continuous optimization Discrete optimization
Linear programming Linear programming (also treats integer programming) — objective function and constraints are linear
Algorithms for linear programming: Simplex algorithm Bland's rule — rule to avoid cycling in the simplex method Klee–Minty cube — perturbed (hyper)cube; simplex method has exponential complexity on such a domain Criss-cross algorithm — similar to the simplex algorithm Big M method — variation of simplex algorithm for problems with both "less than" and "greater than" constraints Interior point method Ellipsoid method Karmarkar's algorithm Mehrotra predictor–corrector method Column generation k-approximation of k-hitting set — algorithm for specific LP problems (to find a weighted hitting set) Linear complementarity problem Decompositions: Benders' decomposition Dantzig–Wolfe decomposition Theory of two-level planning Variable splitting Basic solution (linear programming) — solution at vertex of feasible region Fourier–Motzkin elimination Hilbert basis (linear programming) — set of integer vectors in a convex cone which generate all integer vectors in the cone LP-type problem Linear inequality Vertex enumeration problem — list all vertices of the feasible set
Convex optimization Convex optimization
Quadratic programming Linear least squares (mathematics) Total least squares Frank–Wolfe algorithm Sequential minimal optimization — breaks up large QP problems into a series of smallest possible QP problems Bilinear program Basis pursuit — minimize L1-norm of vector subject to linear constraints Basis pursuit denoising (BPDN) — regularized version of basis pursuit In-crowd algorithm — algorithm for solving basis pursuit denoising Linear matrix inequality Conic optimization Semidefinite programming Second-order cone programming Sum-of-squares optimization Quadratic programming (see above) Bregman method — row-action method for strictly convex optimization problems Proximal gradient method — use splitting of objective function in sum of possible non-differentiable pieces Subgradient method — extension of steepest descent for problems with a non-differentiable objective function Biconvex optimization — generalization where objective function and constraint set can be biconvex
Nonlinear programming Nonlinear programming — the most general optimization problem in the usual framework
Special cases of nonlinear programming: See Linear programming and Convex optimization above Geometric programming — problems involving signomials or posynomials Signomial — similar to polynomials, but exponents need not be integers Posynomial — a signomial with positive coefficients Quadratically constrained quadratic program Linear-fractional programming — objective is ratio of linear functions, constraints are linear Fractional programming — objective is ratio of nonlinear functions, constraints are linear Nonlinear complementarity problem (NCP) — find x such that x ≥ 0, f(x) ≥ 0 and xT f(x) = 0 Least squares — the objective function is a sum of squares Non-linear least squares Gauss–Newton algorithm BHHH algorithm — variant of Gauss–Newton in econometrics Generalized Gauss–Newton method — for constrained nonlinear least-squares problems Levenberg–Marquardt algorithm Iteratively reweighted least squares (IRLS) — solves a weighted least-squares problem at every iteration Partial least squares — statistical techniques similar to principal components analysis Non-linear iterative partial least squares (NIPLS) Mathematical programming with equilibrium constraints — constraints include variational inequalities or complementarities Univariate optimization: Golden section search Successive parabolic interpolation — based on quadratic interpolation through the last three iterates General algorithms: Concepts: Descent direction Guess value — the initial guess for a solution with which an algorithm starts Line search Backtracking line search Wolfe conditions Gradient method — method that uses the gradient as the search direction Gradient descent Stochastic gradient descent Landweber iteration — mainly used for ill-posed problems Successive linear programming (SLP) — replace problem by a linear programming problem, solve that, and repeat Sequential quadratic programming (SQP) — replace problem by a quadratic programming problem, solve that, and repeat Newton's method in optimization See also under Newton algorithm in the section Finding roots of nonlinear equations Nonlinear conjugate gradient method Derivative-free methods Coordinate descent — move in one of the coordinate directions Adaptive coordinate descent — adapt coordinate directions to objective function Random coordinate descent — randomized version Nelder–Mead method Pattern search (optimization) Powell's method — based on conjugate gradient descent Rosenbrock methods — derivative-free method, similar to Nelder–Mead but with guaranteed convergence Augmented Lagrangian method — replaces constrained problems by unconstrained problems with a term added to the objective function Ternary search Tabu search Guided Local Search — modification of search algorithms which builds up penalties during a search Reactive search optimization (RSO) — the algorithm adapts its parameters automatically MM algorithm — majorize-minimization, a wide framework of methods Least absolute deviations Expectation–maximization algorithm Ordered subset expectation maximization Nearest neighbor search Space mapping — uses "coarse" (ideal or low-fidelity) and "fine" (practical or high-fidelity) models
Optimal control and infinite-dimensional optimization Optimal control
Pontryagin's minimum principle — infinite-dimensional version of Lagrange multipliers Costate equations — equation for the "Lagrange multipliers" in Pontryagin's minimum principle Hamiltonian (control theory) — minimum principle says that this function should be minimized Types of problems: Linear-quadratic regulator — system dynamics is a linear differential equation, objective is quadratic Linear-quadratic-Gaussian control (LQG) — system dynamics is a linear SDE with additive noise, objective is quadratic Optimal projection equations — method for reducing dimension of LQG control problem Algebraic Riccati equation — matrix equation occurring in many optimal control problems Bang–bang control — control that switches abruptly between two states Covector mapping principle Differential dynamic programming — uses locally-quadratic models of the dynamics and cost functions DNSS point — initial state for certain optimal control problems with multiple optimal solutions Legendre–Clebsch condition — second-order condition for solution of optimal control problem Pseudospectral optimal control Bellman pseudospectral method — based on Bellman's principle of optimality Chebyshev pseudospectral method — uses Chebyshev polynomials (of the first kind) Flat pseudospectral method — combines Ross–Fahroo pseudospectral method with differential flatness Gauss pseudospectral method — uses collocation at the Legendre–Gauss points Legendre pseudospectral method — uses Legendre polynomials Pseudospectral knotting method — generalization of pseudospectral methods in optimal control Ross–Fahroo pseudospectral method — class of pseudospectral method including Chebyshev, Legendre and knotting Ross–Fahroo lemma — condition to make discretization and duality operations commute Ross' π lemma — there is fundamental time constant within which a control solution must be computed for controllability and stability Sethi model — optimal control problem modelling advertising Infinite-dimensional optimization
Semi-infinite programming — infinite number of variables and finite number of constraints, or other way around Shape optimization, Topology optimization — optimization over a set of regions Topological derivative — derivative with respect to changing in the shape Generalized semi-infinite programming — finite number of variables, infinite number of constraints
Uncertainty and randomness Approaches to deal with uncertainty: Markov decision process Partially observable Markov decision process Robust optimization Wald's maximin model Scenario optimization — constraints are uncertain Stochastic approximation Stochastic optimization Stochastic programming Stochastic gradient descent Random optimization algorithms: Random search — choose a point randomly in ball around current iterate Simulated annealing Adaptive simulated annealing — variant in which the algorithm parameters are adjusted during the computation. Great Deluge algorithm Mean field annealing — deterministic variant of simulated annealing Bayesian optimization — treats objective function as a random function and places a prior over it Evolutionary algorithm Differential evolution Evolutionary programming Genetic algorithm, Genetic programming Genetic algorithms in economics MCACEA (Multiple Coordinated Agents Coevolution Evolutionary Algorithm) — uses an evolutionary algorithm for every agent Simultaneous perturbation stochastic approximation (SPSA) Luus–Jaakola Particle swarm optimization Stochastic tunneling Harmony search — mimicks the improvisation process of musicians see also the section Monte Carlo method
Theoretical aspects Convex analysis — function f such that f(tx + (1 − t)y) ≥ tf(x) + (1 − t)f(y) for t ∈ [0,1] Pseudoconvex function — function f such that ∇f · (y − x) ≥ 0 implies f(y) ≥ f(x) Quasiconvex function — function f such that f(tx + (1 − t)y) ≤ max(f(x), f(y)) for t ∈ [0,1] Subderivative Geodesic convexity — convexity for functions defined on a Riemannian manifold Duality (optimization) Weak duality — dual solution gives a bound on the primal solution Strong duality — primal and dual solutions are equivalent Shadow price Dual cone and polar cone Duality gap — difference between primal and dual solution Fenchel's duality theorem — relates minimization problems with maximization problems of convex conjugates Perturbation function — any function which relates to primal and dual problems Slater's condition — sufficient condition for strong duality to hold in a convex optimization problem Total dual integrality — concept of duality for integer linear programming Wolfe duality — for when objective function and constraints are differentiable Farkas' lemma Karush–Kuhn–Tucker conditions (KKT) — sufficient conditions for a solution to be optimal Fritz John conditions — variant of KKT conditions Lagrange multiplier Lagrange multipliers on Banach spaces Semi-continuity Complementarity theory — study of problems with constraints of the form ⟨u, v⟩ = 0 Mixed complementarity problem Mixed linear complementarity problem Lemke's algorithm — method for solving (mixed) linear complementarity problems Danskin's theorem — used in the analysis of minimax problems Maximum theorem — the maximum and maximizer are continuous as function of parameters, under some conditions No free lunch in search and optimization Relaxation (approximation) — approximating a given problem by an easier problem by relaxing some constraints Lagrangian relaxation Linear programming relaxation — ignoring the integrality constraints in a linear programming problem Self-concordant function Reduced cost — cost for increasing a variable by a small amount Hardness of approximation — computational complexity of getting an approximate solution
Applications In geometry: Geometric median — the point minimizing the sum of distances to a given set of points Chebyshev center — the centre of the smallest ball containing a given set of points In statistics: Iterated conditional modes — maximizing joint probability of Markov random field Response surface methodology — used in the design of experiments Automatic label placement Compressed sensing — reconstruct a signal from knowledge that it is sparse or compressible Cutting stock problem Demand optimization Destination dispatch — an optimization technique for dispatching elevators Energy minimization Entropy maximization Highly optimized tolerance Hyperparameter optimization Inventory control problem Newsvendor model Extended newsvendor model Assemble-to-order system Linear programming decoding Linear search problem — find a point on a line by moving along the line Low-rank approximation — find best approximation, constraint is that rank of some matrix is smaller than a given number Meta-optimization — optimization of the parameters in an optimization method Multidisciplinary design optimization Optimal computing budget allocation — maximize the overall simulation efficiency for finding an optimal decision Paper bag problem Process optimization Recursive economics — individuals make a series of two-period optimization decisions over time. Stigler diet Space allocation problem Stress majorization Trajectory optimization Transportation theory Wing-shape optimization
Miscellaneous Combinatorial optimization Dynamic programming Bellman equation Hamilton–Jacobi–Bellman equation — continuous-time analogue of Bellman equation Backward induction — solving dynamic programming problems by reasoning backwards in time Optimal stopping — choosing the optimal time to take a particular action Odds algorithm Robbins' problem Global optimization: BRST algorithm MCS algorithm Multi-objective optimization — there are multiple conflicting objectives Benson's algorithm — for linear vector optimization problems Bilevel optimization — studies problems in which one problem is embedded in another Optimal substructure Dykstra's projection algorithm — finds a point in intersection of two convex sets Algorithmic concepts: Barrier function Penalty method Trust region Test functions for optimization: Rosenbrock function — two-dimensional function with a banana-shaped valley Himmelblau's function — two-dimensional with four local minima, defined by f ( x , y ) = ( x 2 + y − 11 ) 2 + ( x + y 2 − 7 ) 2 {\displaystyle f(x,y)=(x^{2}+y-11)^{2}+(x+y^{2}-7)^{2}}
Rastrigin function — two-dimensional function with many local minima Shekel function — multimodal and multidimensional Mathematical Optimization Society
Numerical quadrature (integration) Numerical integration — the numerical evaluation of an integral
Rectangle method — first-order method, based on (piecewise) constant approximation Trapezoidal rule — second-order method, based on (piecewise) linear approximation Simpson's rule — fourth-order method, based on (piecewise) quadratic approximation Adaptive Simpson's method Boole's rule — sixth-order method, based on the values at five equidistant points Newton–Cotes formulas — generalizes the above methods Romberg's method — Richardson extrapolation applied to trapezium rule Gaussian quadrature — highest possible degree with given number of points Chebyshev–Gauss quadrature — extension of Gaussian quadrature for integrals with weight (1 − x2)±1/2 on [−1, 1] Gauss–Hermite quadrature — extension of Gaussian quadrature for integrals with weight exp(−x2) on [−∞, ∞] Gauss–Jacobi quadrature — extension of Gaussian quadrature for integrals with weight (1 − x)α (1 + x)β on [−1, 1] Gauss–Laguerre quadrature — extension of Gaussian quadrature for integrals with weight exp(−x) on [0, ∞] Gauss–Kronrod quadrature formula — nested rule based on Gaussian quadrature Gauss–Kronrod ru