Optimization
Algorithms that search for better or best solutions.
Optimization algorithms improve decisions, parameters, schedules, or designs according to a goal and constraints.
Gradient Descent
Minimizes an objective by repeatedly moving parameters opposite the gradient.
Newton's Method
Finds a root or optimum by repeatedly using local derivative information to form a better approximation.
Simulated Annealing
Searches for good solutions while sometimes accepting worse moves early on.
Genetic Algorithm
Evolves a population of candidate solutions through selection and variation.
Adam Optimizer
Adapts gradient updates using moving averages of gradients and squared gradients.
Branch and Bound
Searches solution branches while pruning branches that cannot improve the best result.
Coordinate Descent
Optimizes one parameter or coordinate at a time.
Linear Programming Simplex Method
Optimizes a linear objective by moving between vertices of a feasible region.
Nelder-Mead
Optimizes without derivatives by moving a simplex through the search space.
Stochastic Gradient Descent
Updates parameters using gradients from one example or a small batch at a time.
BFGS
Optimizes smooth functions by updating an approximation of second-order curvature.
L-BFGS
Runs BFGS-style optimization while storing only a limited history of curvature updates.
Levenberg-Marquardt
Solves nonlinear least-squares problems by blending Gauss-Newton steps with damping.
Interior Point Method
Solves constrained optimization problems by moving through the interior of the feasible region.
Gradient Clipping
Limits gradient size so optimization updates do not become unstable.
Proximal Gradient Method
Optimizes objectives with a smooth part and a nonsmooth regularization term.
Hill Climbing
Improves a solution by repeatedly moving to a better neighboring solution.
Beam Search
Keeps only the best few partial solutions while exploring a large search space.
Particle Swarm Optimization
Searches for good solutions by moving particles according to personal and group best positions.
Ant Colony Optimization
Solves combinatorial problems by reinforcing paths that produce good solutions.
Tabu Search
Improves solutions with local moves while forbidding recently visited moves or states.
Differential Evolution
Optimizes continuous parameters by combining differences between population members.
CMA-ES
Optimizes continuous functions by adapting a Gaussian search distribution.
Bayesian Optimization
Optimizes expensive black-box functions using a surrogate model and acquisition rule.
Golden Section Search
Finds the minimum of a unimodal one-dimensional function by shrinking an interval efficiently.
Powell's Method
Minimizes a function by performing line searches along evolving directions.
ADMM
Solves constrained optimization problems by alternating primal updates and dual correction.
Expectation-Maximization
Fits latent-variable models by alternating expected assignments and parameter updates.
RANSAC
Fits a model by repeatedly sampling small subsets and keeping the model with the most inliers.
Constraint Satisfaction Backtracking
Solves constraint problems by assigning variables recursively and undoing inconsistent choices.
Momentum Gradient Descent
Momentum Gradient Descent improves candidate solutions according to an objective function.
RMSProp
RMSProp improves candidate solutions according to an objective function.
Nesterov Accelerated Gradient
Nesterov Accelerated Gradient improves candidate solutions according to an objective function.
FISTA
FISTA improves candidate solutions according to an objective function.
Trust Region Method
Trust Region Method improves candidate solutions according to an objective function.
Augmented Lagrangian Method
Augmented Lagrangian Method improves candidate solutions according to an objective function.
Cutting Plane Method
Cutting Plane Method improves candidate solutions according to an objective function.
Subgradient Method
Subgradient Method improves candidate solutions according to an objective function.
Mirror Descent
Mirror Descent improves candidate solutions according to an objective function.
Frank-Wolfe Algorithm
Frank-Wolfe Algorithm improves candidate solutions according to an objective function.
DPLL
DPLL uses recursively assigning variables with unit propagation and backtracking for satisfiability.
CDCL
CDCL uses learning conflict clauses from implication graphs and backjumping to useful decision levels for satisfiability.
WalkSAT
Searches for a satisfying assignment by flipping variables in unsatisfied clauses.
Davis-Putnam Algorithm
Davis-Putnam Algorithm addresses satisfiability by eliminating variables by resolution before checking the remaining formula.
Unit Propagation
Simplifies SAT formulas by repeatedly assigning literals forced by unit clauses.
Pure Literal Elimination
Pure Literal Elimination handles satisfiability simplification by assigning variables that appear with only one polarity.
2-SAT Implication Graph
Solves 2-SAT by turning binary clauses into implications and checking strongly connected components.
0/1 Knapsack Dynamic Programming
Solves 0/1 knapsack by tabulating the best value for each item prefix and capacity.
Knapsack FPTAS
Knapsack FPTAS addresses knapsack approximation by scaling item values so dynamic programming runs in polynomial time.
Meet-in-the-Middle Knapsack
Meet-in-the-Middle Knapsack addresses knapsack optimization by enumerating half-instance sums and combining compatible partial solutions.
Branch-and-Bound Knapsack
Branch-and-Bound Knapsack uses pruning item-choice subtrees whose optimistic bound cannot beat the incumbent for knapsack optimization.
Hungarian Algorithm
Solves the assignment problem by maintaining dual labels and improving a minimum-cost matching.
Min-Cost Max-Flow
Finds a maximum feasible flow whose shipped units have minimum total cost.
Vertex Cover 2-Approximation
Vertex Cover 2-Approximation uses choosing both endpoints of uncovered edges to build a bounded cover for vertex cover approximation.
Branch-and-Bound Vertex Cover
Branch-and-Bound Vertex Cover addresses vertex cover by branching on uncovered edges and pruning covers that cannot improve the incumbent.
Greedy Set Cover
Approximates set cover by repeatedly choosing the set that covers the most uncovered elements per cost.
Algorithm X
Algorithm X uses choosing a constraint column and recursively trying rows that satisfy it for exact cover search.
Dancing Links
Dancing Links handles exact cover search by using linked-list removal and restoration to implement Algorithm X efficiently.
Branch-and-Bound Set Packing
Branch-and-Bound Set Packing addresses set packing by branching on compatible sets and bounding the best possible packing.
Local Search Set Packing
Local Search Set Packing addresses set packing by swapping sets in and out of a packing to improve objective value.
Held-Karp TSP
Solves exact TSP by dynamic programming over visited-city subsets and the current last city.
Christofides Algorithm
Builds a metric TSP tour within 3/2 of optimum using a tree, matching, and shortcutting.
Nearest Neighbor TSP
Nearest Neighbor TSP uses repeatedly visiting the nearest unvisited city for traveling salesperson heuristic.
2-Opt
2-Opt uses reversing crossing tour segments when the swap shortens the tour for traveling salesperson improvement.
Lin-Kernighan
Lin-Kernighan addresses traveling salesperson improvement by adaptively choosing k-edge exchanges that improve a tour.
Branch-and-Bound Maximum Clique
Branch-and-Bound Maximum Clique addresses maximum clique by branching on candidate vertices while bounding clique size with coloring.
Tomita Clique Algorithm
Tomita Clique Algorithm addresses maximum clique by using greedy coloring bounds to prune maximum-clique search.
Dreyfus-Wagner Steiner Tree
Dreyfus-Wagner Steiner Tree addresses steiner tree by combining terminal subsets with shortest-path distances.
Feedback Vertex Set Branching
Feedback Vertex Set Branching addresses feedback vertex set by branching on cycle vertices until the remaining graph is acyclic.
Minimum Feedback Arc Set Heuristic
Minimum Feedback Arc Set Heuristic addresses feedback arc set by ordering vertices to reduce backward edges in a directed graph.
Karmarkar's Algorithm
Karmarkar's Algorithm uses following a projective interior path toward an optimal linear-programming solution for linear programming.
Revised Simplex Method
Solves linear programs by updating a compact basis representation instead of a full tableau.
Chinese Postman Algorithm
Finds a minimum-cost closed walk that traverses every edge of a graph.
Kernighan-Lin Algorithm
Improves a graph bisection by swapping vertex pairs to reduce cut cost.
Fiduccia-Mattheyses Algorithm
Refines network or graph partitions with efficient single-vertex moves.