Skip to content

Latest commit

 

History

History
700 lines (599 loc) · 27.7 KB

optimization.md

File metadata and controls

700 lines (599 loc) · 27.7 KB
Raw

Problems

Sparse approximation

Logic optimization

Convex optimization

Unconstrained nonlinear optimization without derivatives

Unconstrained nonlinear optimization with first derivative

Combinatorial optimization

Nonlinear dimensionality reduction

-- Model + Loss

Ordinary least squares

Constrained linear least squares

  • solved by (libraries): 'scipy.optimize.lsq_linear'

Non-negative linear least-squares problem

Bounded-variable least squares

  • also called: 'BVLS'
  • variant of: 'Ordinary least squares'
  • specialization of: 'Quadratic programming'

Orthogonal regression

Total least squares

Non-linear least squares

Linear programming

  • also called: 'LP', 'Linear optimization', 'Constrained linear optimization'
  • https://en.wikipedia.org/wiki/Linear_programming
  • implemented by: 'Mathematica LinearProgramming'
  • implemented by: 'Mathematica FindMinimum(Method->"LinearProgramming")' (what is the algorithm here?)
  • implemented by: 'Artelys Knitro', 'GNU Linear Programming Kit'

Quadratic programming

Quadratically constrained quadratic program

Integer linear programming

Mixed Integer Linear Programming

  • also called: 'MILP'
  • implemented by: 'lp_solve', 'APOPT', 'GNU Linear Programming Kit'

Nonlinear programming

Integer Nonlinear Programming

  • also called: 'INLP'

Mixed Integer Nonlinear Programming

Optimization algorithms

Iteratively reweighted least squares

Sequential Minimal Optimization

SMO-type decomposition method

Cutting-plane method

Branch and bound

Branch and cut

Branch and reduce

  • paper: 'A branch-and-reduce approach to global optimization (1996)'
  • domain: 'Optimization'

Quesada Grossman algorithm

  • solves: 'Mixed Integer Nonlinear Programming'
  • implemented in: 'Artelys Knitro', 'AIMMS'
  • domain: 'Optimization'

Outer approximation algorithm

  • solves: 'Mixed Integer Nonlinear Programming'
  • domain: 'Optimization'

Karmarkar's algorithm

Simplex algorithm

Revised simplex method

Powell's method

  • https://en.wikipedia.org/wiki/Powell%27s_method
  • paper: 'An efficient method for finding the minimum of a function of several variables without calculating derivatives (1964)'
  • type: 'Unconstrained nonlinear without derivatives'
  • is a: 'Optimization method'
  • implemented in: 'Python scipy.optimize.minimize(method="Powell")' (modified variant)
  • input: 'Real-valued function of several real variables'
  • domain: 'Optimization'

Luus–Jaakola

  • https://en.wikipedia.org/wiki/Luus–Jaakola
  • paper: 'Optimization by direct search and systematic reduction of the size of search region'
  • is a: 'Heuristic'
  • type: 'Unconstrained nonlinear without derivatives'
  • becomes 'Iterative method' for 'twice continuously differentiable functions', however for this problem 'Newton's method' is usually used
  • applications: 'optimal control', 'transformer design', 'metallurgical processes', 'chemical engineering'
  • input: 'Real-valued function of several real variables'
  • implemented in: 'Python osol.extremum'
  • approximates: 'Global extremum'
  • domain: 'Optimization'

Pattern search

  • https://en.wikipedia.org/wiki/Pattern_search_(optimization)
  • paper: '"Direct Search" Solution of Numerical and Statistical Problems'
  • type: 'Unconstrained nonlinear without derivatives'
  • is a: 'Optimization method'
  • is a: 'Heuristic' or 'Iterative method', depending on the class of function WHICH CLASSES?
  • input: 'Function'
  • domain: 'Optimization'

Golden-section search

Successive parabolic interpolation

Line search

Differential evolution

  • https://en.wikipedia.org/wiki/Differential_evolution
  • paper: 'Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces'
  • type: 'Unconstrained nonlinear without derivatives'
  • implemented in: 'Mathematica NMinimize(Method->"DifferentialEvolution")', 'scipy.optimize.differential_evolution'
  • is a: 'Metaheuristic', 'Stochastic algorithm'
  • input: 'Real-valued function of several real variables'
  • domain: 'Optimization'

Random search

  • https://en.wikipedia.org/wiki/Random_search
  • paper: 'The convergence of the random search method in the extremal control of a many parameter system'
  • is a: 'Randomized algorithm'
  • implemented in: 'Mathematica NMinimize(Method->"RandomSearch")'
  • type: 'Unconstrained nonlinear without derivatives'
  • related: 'Random optimization'
  • input: 'Real-valued function of several real variables'
  • domain: 'Optimization'

Random optimization

  • https://en.wikipedia.org/wiki/Random_optimization
  • paper: 'Random optimization (1965)'
  • type: 'Unconstrained nonlinear without derivatives'
  • is a: 'Randomized algorithm'
  • related: 'Random search'
  • input: 'Real-valued function of several real variables'
  • domain: 'Optimization'

Nelder–Mead method

Genetic algorithm

  • https://en.wikipedia.org/wiki/Genetic_algorithm
  • book: 'Adaptation in natural and artificial systems (1975)'
  • type: 'Unconstrained nonlinear without derivatives'
  • is a: 'Metaheuristic', 'Randomized search method', 'Evolutionary algorithm'
  • used for: 'Integer Nonlinear Programming'
  • input: 'Genetic representation', 'Fitness function'
  • domain: 'Optimization'

Principal Axis Method

Newton's method

Broyden–Fletcher–Goldfarb–Shanno algorithm

  • https://en.wikipedia.org/wiki/Broyden–Fletcher–Goldfarb–Shanno_algorithm
  • is a: 'Quasi-Newton method', 'Iterative method'
  • implemented in: 'Python scipy.optimize.minimize(method="BFGS")', 'Mathematica FindMinimum(Method->"QuasiNewton")'
  • implemented in: 'gsl_multimin_fdfminimizer_vector_bfgs2', 'Ceres Solver'
  • type: 'Unconstrained nonlinear with first derivative'
  • input: 'Differentiable real-valued function of several real variables and its gradient'
  • domain: 'Optimization'

Limited-memory BFGS

  • https://en.wikipedia.org/wiki/Limited-memory_BFGS
  • is a: 'Quasi-Newton method'
  • variant of: 'BFGS' (for large systems with memory optimizations)
  • implemented in: 'Mathematica FindMinimum(Method->"QuasiNewton")', 'Python scipy.minimize(method="L-BFGS-B")' (L-BFGS-B variant)
  • implemented in: 'Ceres Solver'
  • applications: 'Maximum entropy models', 'CRF'
  • input: 'Differentiable real-valued function of several real variables and its gradient'
  • domain: 'Optimization'

Basin-hopping algorithm

  • https://en.wikipedia.org/wiki/Basin-hopping
  • paper: 'Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms'
  • implemented in: 'scipy.optimize.basinhopping'
  • input: 'smooth scalar function of one or more variables'
  • applications: 'Physical Chemistry'
  • works good if there are lots of local extrema
  • is a: 'stochastic algorithm', 'sampling algorithm'
  • type: 'Unconstrained nonlinear without derivatives'
  • depends on any: 'local optimization algorithm'
  • approximates: 'Global extremum'
  • domain: 'Optimization'

Levenberg–Marquardt algorithm

  • also called: 'LMA'
  • https://en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_algorithm
  • http://mathworld.wolfram.com/Levenberg-MarquardtMethod.html
  • paper: 'A Method for the Solution of Certain Non-Linear Problems in Least Squares (1944)'
  • type: 'Unconstrained nonlinear with first derivative'
  • solves: 'Non-linear least squares', 'Orthogonal non-linear least squares'
  • is a: 'iterative method'
  • applications: 'generic curve-fitting problems'
  • output: 'local extermum'
  • implemented in: 'Mathematica FindMinimum(Method->"LevenbergMarquardt")', 'Python scipy.optimize.least_squares(method="lm"), scipy.optimize.root(method="lm")', 'scipy.optimize.leastsq', 'MINPACK', 'R ONLS'
  • implemented in: 'Ceres Solver'
  • input: 'Sum of squares function and data pairs'
  • variant of: 'Gauss–Newton'
  • domain: 'Optimization'

Davidon–Fletcher–Powell formula

Symmetric rank-one

  • https://en.wikipedia.org/wiki/Symmetric_rank-one
  • also called: 'SR1'
  • is a: 'Quasi-Newton method'
  • advantages for sparse or partially separable problems
  • implemented in: 'Python scipy.optimize.SR1'
  • type: 'Unconstrained nonlinear with first derivative'
  • input: 'Function and its gradient'
  • domain: 'Optimization'

Berndt–Hall–Hall–Hausman algorithm

Nonlinear conjugate gradient method

  • https://en.wikipedia.org/wiki/Nonlinear_conjugate_gradient_method
  • type: 'Unconstrained nonlinear with first derivative'
  • implemented in: 'Mathematica FindMinimum(Method->"ConjugateGradient")'
  • implemented in: 'Python scipy.optimize.minimize(method="Newton-CG")'
  • implemented in: 'Python scipy.optimize.minimize(method="trust-ncg")' (Trust region variant)
  • domain: 'Optimization'

Truncated Newton method

  • https://en.wikipedia.org/wiki/Truncated_Newton_method
  • type: 'Unconstrained nonlinear with first derivative'
  • implemented in: 'Python scipy.optimize.minimize(method="TNC")'
  • input: 'Differentiable real-valued function of several real variables and its gradient'
  • domain: 'Optimization'

Gauss–Newton algorithm

Trust region method

Trust Region Reflective

Bounded-variable least-squares algorithm

  • paper: 'Bounded-Variable Least-Squares: an Algorithm and Applications' (1995)
  • implemented in: 'scipy.optimize.lsq_linear(method="bvls")'
  • solves: 'Linear least squares'

Proximal gradient method

Coordinate descent

  • also called: 'CDN'
  • https://en.wikipedia.org/wiki/Coordinate_descent
  • application: 'L1-regularized classification'
  • input: 'Real-valued function of several real variables'
  • input: 'Differentiable real-valued function of several real variables and its gradient' (variant)
  • domain: 'Optimization'

Gradient descent

  • also called: 'Steepest descent'
  • https://en.wikipedia.org/wiki/Gradient_descent
  • type: 'Unconstrained nonlinear with first derivative'
  • will converge to a global minimum if the function is convex
  • stochastic approximation: 'Stochastic gradient descent'
  • applications: 'Convex optimization'
  • implemented in: 'gsl_multimin_fdfminimizer_steepest_descent'
  • input: 'Differentiable real-valued function of several real variables and its gradient'
  • domain: 'Optimization'

Stochastic gradient descent

Momentum method for stochastic gradient descent

  • paper: 'Learning representations by back-propagating errors (1986)'
  • implemented in: 'tf.train.MomentumOptimizer, keras.optimizers.SGD'
  • domain: 'Optimization'

Adam

  • also called: 'Adaptive moment estimation optimization algorithm'
  • paper: 'Adam: A Method for Stochastic Optimization (2014)'
  • implemented in: 'tf.train.AdamOptimizer, keras.optimizers.Adam'
  • variant of: 'Stochastic gradient descent'
  • domain: 'Optimization'

RAdam

  • also called: 'Rectified Adam'
  • paper: 'On the Variance of the Adaptive Learning Rate and Beyond' (2019)
  • variant of: 'Adam'
  • domain: 'Optimization'

RMSProp

  • also called: 'Root Mean Square Propagation'
  • implemented in: 'tf.train.RMSPropOptimizer, keras.optimizers.RMSprop'
  • domain: 'Optimization'

ADADELTA

  • paper: 'ADADELTA: An Adaptive Learning Rate Method (2012)'
  • implemented in: 'tf.train.AdadeltaOptimizer, keras.optimizers.Adadelta'
  • domain: 'Optimization'

AdaGrad

  • also called: 'Adaptive gradient algorithm'
  • paper: 'Adaptive Subgradient Methods for Online Learning and Stochastic Optimization (2011)'
  • implemented in: 'tf.train.AdagradOptimizer, keras.optimizers.Adagrad'
  • domain: 'Optimization'

Interior-point method

Successive linear programming

Sequential quadratic programming

Han–Powell

  • variant of: 'Sequential quadratic programming'
  • domain: 'Optimization'

NLPQL

  • paper: 'NLPQL: A fortran subroutine solving constrained nonlinear programming problems' (1986)
  • variant of: 'Sequential quadratic programming'
  • implemented in: 'Fortran NLPQL'
  • domain: 'Optimization'

NLPQLP

  • https://en.wikipedia.org/wiki/NLPQLP
  • report: 'NLPQLP: A Fortran implementation of a sequential quadratic programming algorithm with distributed and non-monotone line search'
  • variant of: 'Sequential quadratic programming'
  • solves: 'Nonlinear programming' for 'twice continuously differentiable functions'
  • implemented in: 'Fortran NLPQLP'
  • domain: 'Optimization'

Sequential Least SQuares Programming

  • also called: 'SLSQP'
  • implemented in: 'Python scipy.optimize.minimize(method="SLSQP")'
  • domain: 'Optimization'
  • uses: 'Han–Powell'
  • variant of: 'Sequential quadratic programming'

Frank–Wolfe algorithm

  • also called: 'conditional gradient method', 'reduced gradient algorithm', 'convex combination algorithm'
  • paper: 'An algorithm for quadratic programming (1956)'
  • https://en.wikipedia.org/wiki/Frank%E2%80%93Wolfe_algorithm
  • solves: 'Constrained convex optimization'
  • iterative first-order optimization algorithm
  • domain: 'Optimization'

Augmented Lagrangian method

Penalty method

Local search

Hill climbing

  • https://en.wikipedia.org/wiki/Hill_climbing
  • type: 'Local search', 'Heuristic search'
  • is a: 'Iterative method', 'Anytime algorithm', 'Metaheuristic'?
  • applications: 'Artificial intelligence'
  • output: 'Local extremum'
  • domain: 'Optimization'

Tabu search

  • https://en.wikipedia.org/wiki/Tabu_search
  • paper: 'Future Paths for Integer Programming and Links to Artificial Intelligence (1986)'
  • is a: 'Metaheuristic'
  • type: 'Local search'
  • applications: 'Combinatorial optimization', 'Travelling salesman problem'
  • domain: 'Optimization', 'Approximate global optimization'

Simulated annealing

Cuckoo search

Ant colony optimization algorithms

Fireworks algorithm

Estimation of distribution algorithms

Constrained Optimization BY Linear Approximation

  • also called: 'COBYLA'
  • https://en.wikipedia.org/wiki/COBYLA
  • paper: 'A Direct Search Optimization Method That Models the Objective and Constraint Functions by Linear Interpolation (1994)'
  • implemented in: 'Python scipy.optimize.minimize(method="COBYLA")'
  • type: 'Constrained optimization without derivatives'
  • input: 'Real-valued function of several real variables'
  • domain: 'Optimization'

Dogleg Method

Matching pursuit

  • paper: 'Matching pursuits with time-frequency dictionaries (1993)'
  • https://en.wikipedia.org/wiki/Matching_pursuit
  • solves: 'Sparse approximation'
  • properties: 'greedy'
  • variants: 'Orthogonal Matching Pursuit'
  • domain: 'Optimization'

Orthogonal Matching Pursuit

  • paper: 'Orthogonal Matching Pursuit: recursive function approximation with application to wavelet decomposition (1993)'
  • implemented in: 'sklearn.linear_model.OrthogonalMatchingPursuit' (Orthogonal variant)
  • variant of: 'Matching pursuit'
  • domain: 'Optimization'

Karnaugh map

Quine–McCluskey algorithm

Espresso algorithm

GLMNET

  • paper: 'Regularization Paths for Generalized Linear Models via Coordinate Descent' (2010)
  • applications: 'L1-regularized logistic regression'
  • Newton-type optimizer
  • implemented in: 'R glmnet'

newGLMNET

  • paper: 'An Improved GLMNET for L1-regularized LogisticRegression' (2012)
  • applications: 'L1-regularized logistic regression'
  • implemented in: 'LIBLINEAR'
  • improved variant of: 'GLMNET'

Practical theorems

No free lunch theorem