- Atlas
- Mathematics
- Mathematical Optimization
Mathematical Optimization
Mathematical optimization is the study of how to make the best possible choice among the options available.
15 frameworks, from 1744 to today · Applied Mathematics · Mathematics
- Calculus of Variations 1744-1900
- Linear Programming 1947-Present
- First-Order and Stochastic Gradient Methods 1951-Present
- Nonlinear Programming 1951-Present
- Stochastic Programming 1955-Present
- Optimal Control 1956-Present
- Dynamic Programming 1957-Present
- Combinatorial optimization 1958-Present
- Global and Derivative-Free Optimization 1960-Present
- Regularization and Statistical Learning Optimization 1970-Present
- Complexity and Approximation Theory 1971-Present
- Metaheuristic 1975-Present
- Interior-point method 1984-Present
- Convex Optimization 1990-Present
- Robust Optimization 1998-Present
Overview
Mathematical optimization is the study of how to make the best possible choice among the options available1. Given a set of possible decisions and a way of measuring how good each one is, the optimizer's job is to find the decision that scores highest—or, in the usual formulation, minimizes a cost1. The field matters because almost every practical question of design, planning, and inference can be phrased this way: how to route a fleet at least cost, how to shape a wing for maximum lift, how to set prices to maximize revenue, how to fit a model to data. What makes optimization a mathematical discipline rather than a bag of tricks is that it asks when a best choice exists, how to recognize it, and how to compute it reliably. Its history is a long movement from special problems solved by clever calculus toward general methods that work on enormous problems a computer can attack.
The calculus of variations: optimizing over curves
The oldest strand concerns problems where the thing to be chosen is not a number but a function—a curve, a path, a shape. The founding example is the brachistochrone: the curve down which a bead slides fastest under gravity between two points. Galileo had studied related questions in the 1600s, but the problem was posed sharply by Johann Bernoulli in 1696, and solved independently by him, by his brother Jakob, by Newton, and by Leibniz. The answer is a cycloid, and the episode announced a new kind of mathematics.
The general method came from Euler and Lagrange in the mid-1700s2. If you want to minimize an integral that depends on an unknown function and its derivative, the optimum must satisfy a differential equation now called the Euler–Lagrange equation32. This is the calculus of variations, and it reframed mechanics: Lagrange's Mécanique analytique (1788) derived the laws of motion from a principle of least action. The tradition continued through Legendre, Jacobi, and Weierstrass, who in the later 1800s sharpened the question of when a stationary curve is genuinely a minimum rather than merely a critical point. The field's central limitation was that it gave necessary conditions—equations the answer must satisfy—but not always a constructive way to find the answer.
Linear programming: the simplex method and duality
The decisive modern turn came from wartime logistics. In the 1940s, George Dantzig, working on US Air Force planning problems, formulated the linear program: minimize a linear cost subject to linear constraints14. The feasible region is a polytope (a many-sided solid), and the key insight is that an optimum, if it exists, occurs at a corner—a vertex. Dantzig's simplex method (developed around 1947) walks from vertex to vertex along edges, improving the objective at each step. It was fast in practice and, crucially, programmable.
Around the same time, the theory of duality gave linear programming its conceptual depth15. Every minimization problem has a companion maximization problem, and the two have equal optimal values under mild conditions. John von Neumann formulated duality in the late 1940s, and the result connects to his earlier minimax theorem for games. Duality is not a curiosity: it supplies certificates of optimality and, in economics, shadow prices—the marginal value of relaxing a constraint. Tjalling Koopmans applied linear programming to allocation problems, and Leonid Kantorovich had independently developed related ideas in the Soviet Union in the late 1930s for production planning. The field's reach was demonstrated when Dantzig and others applied it to diet problems, transportation, and scheduling.
Nonlinear programming and optimality conditions
Linear models are a special case. The general problem—minimize a nonlinear function subject to nonlinear constraints—needed its own theory. In 1951, Harold Kuhn and Albert Tucker published conditions characterizing an optimum of a constrained nonlinear program, now called the Karush–Kuhn–Tucker (KKT) conditions; the same conditions had appeared in William Karush's 1939 master's thesis6. The KKT conditions generalize Lagrange multipliers to inequality constraints: at an optimum, the gradient of the objective is a nonnegative combination of the gradients of the active constraints. They are the workhorse of the field, the nonlinear analogue of the Euler–Lagrange equation.
The 1950s and 1960s produced a family of algorithms. The gradient method—step in the direction of steepest descent—is the simplest, and its slow convergence on ill-conditioned problems motivated Newton's method and quasi-Newton methods such as the Davidon–Fletcher–Powell update (1959 onward). For constrained problems, sequential quadratic programming and penalty and barrier methods were developed. A parallel strand, convex optimization, studied problems where the objective and feasible set are convex—bowl-shaped—so that any local optimum is global. This structure makes problems tractable, and it underlies much of what followed.
Optimal control and dynamic programming
A distinct tradition grew from engineering. Optimal control asks how to steer a system—a rocket, a chemical plant—over time to minimize a cost7. The Pontryagin maximum principle, developed by Lev Pontryagin and colleagues in the Soviet Union in the 1950s, gives necessary conditions in the form of a Hamiltonian system, generalizing the calculus of variations to problems with control constraints. It was applied to trajectory optimization and became standard in aerospace.
Independently, Richard Bellman developed dynamic programming in the 1950s8. The idea is a principle of optimality: an optimal policy has the property that whatever the initial decision, the remaining decisions must be optimal for the state that results. This turns a multi-stage problem into a recursion, solved backward from the end. Dynamic programming handles discrete and stochastic problems that the maximum principle does not, and it underlies reinforcement learning. Its weakness is the "curse of dimensionality": the number of states grows explosively with the number of variables.
Integer programming and combinatorial optimization
Many real decisions are discrete—build a plant or not, assign a driver to a route. Integer programming adds the requirement that some variables be whole numbers, and combinatorial optimization studies problems over finite structures such as graphs and networks. The field's landmark is the traveling salesman problem: find the shortest tour visiting a set of cities9. It is easy to state and famously hard to solve exactly.
The 1950s and 1960s brought foundational algorithms. Ford and Fulkerson's work on network flows (1956) solved transportation and assignment problems efficiently. The branch-and-bound method, developed by Ailsa Land and Alison Doig in 1960, systematically partitions the feasible set and prunes regions that cannot beat the best known solution10. Cutting planes, introduced by Ralph Gomory in 1958, tighten the linear relaxation of an integer program by adding valid inequalities. Modern solvers combine both in branch-and-cut11.
The theoretical reckoning came with computational complexity. In 1971 Stephen Cook proved that the satisfiability problem is NP-complete, and Richard Karp in 1972 showed that the traveling salesman problem and many other combinatorial problems are NP-hard—no known polynomial-time algorithm solves them, and none is expected. This reframed the field's ambitions. Exact solution of large instances may be impossible, so attention turned to approximation algorithms, which guarantee solutions within a known factor of optimal, and to heuristics—practical rules that find good solutions without guarantees12. Metaheuristics such as simulated annealing (Kirkpatrick, Gelatt, and Vecchi, 1983), genetic algorithms (Holland, 1970s), and tabu search (Glover, 1980s) search broadly and escape local optima. The question of whether P equals NP remains open13.
Interior-point methods and the convex revolution
For decades the simplex method dominated linear programming, and its worst-case behavior was poorly understood. In 1979 Leonid Khachiyan showed that the ellipsoid method solves linear programs in polynomial time—a theoretical breakthrough, though slow in practice. Then in 1984 Narendra Karmarkar introduced a projective interior-point method that was both polynomial-time and competitive in practice. Interior-point methods approach the optimum from inside the feasible region rather than traveling along its boundary, following a central path. They were soon generalized, and by the 1990s they had become the standard for large-scale convex problems.
The 1990s and 2000s saw convex optimization mature into a unifying framework. The recognition that many problems—least squares, linear programming, semidefinite programming, geometric programming—share convex structure made them solvable by common machinery. Stephen Boyd and Lieven Vandenberghe's textbook Convex Optimization (2004) codified the field and spread it widely. Semidefinite programming, with interior-point solvers, found applications in control and combinatorial approximation.
Stochastic, robust, and data-driven optimization
Real problems involve uncertainty. Stochastic programming, developed from the 1950s by Dantzig, Beale, and others, optimizes expected cost over random parameters. Robust optimization instead hedges against the worst case within an uncertainty set, a framework formalized by Ben-Tal and Nemirovski and by Bertsimas and Sim in the late 1990s and 2000s. Stochastic gradient methods, which estimate the gradient from random samples, date to Robbins and Monro's 1951 stochastic approximation and became central to machine learning.
The rise of statistical learning reshaped the field's center of gravity. Training a model means minimizing a loss over data, often with a regularization term that penalizes complexity to prevent overfitting—ridge regression (Hoerl and Kennard, 1970) and the lasso (Tibshirani, 1996) are canonical examples. The lasso's L1 penalty produces sparse solutions, and its optimization is a convex problem. Support vector machines (Cortes and Vapnik, 1995) cast classification as a convex quadratic program. The scale of modern data made first-order methods—gradient descent and its variants—dominant, since they need only gradient evaluations. Stochastic gradient descent and its adaptive variants (AdaGrad, 2011; Adam, 2014) train deep networks with millions of parameters. Derivative-free optimization handles objectives with no usable gradient, and global optimization attacks nonconvex problems where local methods fail.
The present
Optimization today is a sprawling, active field. Convex methods and interior-point solvers are mature and embedded in engineering and finance. Mixed-integer programming solvers handle industrial problems of millions of variables through branch-and-cut and sophisticated presolve. First-order and stochastic methods drive machine learning, where nonconvexity is the norm and theory lags practice. Open questions include the complexity of nonconvex optimization, the design of methods that scale to massive distributed data, the interface between optimization and statistical generalization, and the foundations of integer programming, where the gap between what solvers achieve and what theory guarantees remains wide. The field's history is one of widening scope: from curves chosen by calculus, to numbers chosen by algorithms, to models chosen by machines from data.
References
- Mathematical optimization (introduction, Optimization problems, History), Wikipedia
- Euler–Lagrange equation (introduction, History), Wikipedia
- Calculus of variations, Wikipedia
- Simplex algorithm (History), Wikipedia
- Duality (optimization) (History), Wikipedia
- Karush–Kuhn–Tucker conditions, Wikipedia
- Optimal control, Wikipedia
- Dynamic programming, Wikipedia
- Combinatorial optimization, Wikipedia
- Branch and bound, Wikipedia
- Branch and cut, Wikipedia
- Approximation algorithm, Wikipedia
- NP-hardness, Wikipedia
The frameworks of Mathematical Optimization
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1744-1900
- 1947-Present
Linear Programming
How to optimize a linear objective under linear constraints?
About Linear Programming
Linear programming is a method for determining the best possible outcome—such as maximum profit or lowest cost—in a mathematical model whose requirements are represented by linear relationships. It is a specific, and historically pivotal, case of mathematical optimization. The framework's power lies in its balance of simplicity and utility: the problems it solves are simple enough to be understood geometrically, yet general enough to address complex logistical, economic, and engineering challenges.The core problem of linear programming is to optimize a linear objective function, subject to a set of linear equality and inequality constraints. The decision variables represent the quantities you are free to choose, the objective function measures the quality of a choice, and the constraints define the boundaries of what is permissible. The set of all permissible points is known as the feasible region. The goal is to find a point in this region that maximizes or minimizes the objective function.The distinctive organizing idea of linear programming is that the optimal solution, if it exists, will be found at a vertex, or corner, of the feasible region. Because the objective function is linear, its level sets are parallel lines (or hyperplanes in higher dimensions). As you move the objective function in the direction of improvement, the last point of contact with the feasible region will always be a corner. This geometric insight is the foundation for the most famous algorithm in the field: the simplex method, developed by George Dantzig in 1947. The simplex method is an efficient, systematic way to move from one vertex of the feasible region to an adjacent one, always improving the objective function, until no further improvement is possible.To understand linear programming, it is helpful to learn its essential concepts in a logical order. First, one must learn to formulate a problem, translating a real-world scenario into a set of variables, constraints, and an objective function. Second, one must understand the geometry of the solution space, including the concepts of convexity, the feasible region, and vertices. Third, one must learn the mechanics of a solution algorithm, with the simplex method being the standard starting point. Finally, one must understand the concept of duality, which is the idea that every linear program has a corresponding "dual" problem. The dual has deep implications for sensitivity analysis, allowing you to understand how changes in the constraints affect the optimal solution.The intellectual history of linear programming is a story of independent discovery and convergence. In 1939, Soviet mathematician Leonid Kantorovich formulated the problem of linear programming to aid in the planning of manufacturing schedules, but his work was not widely recognized in the West for many years. The field truly took off during World War II, when the need for efficient resource allocation became critical. In 1947, George Dantzig, working for the U.S. Air Force, formalized the general problem and invented the simplex method to solve it. This work was so foundational that the year 1947 marks the beginning of linear programming as a distinct field. John von Neumann, a contemporary of Dantzig, contributed the theory of duality, and the first practical applications were quickly found in military logistics and, later, in the operations of large corporations.Linear programming differs from other optimization frameworks in its strict requirement of linearity. Unlike nonlinear programming, which handles smooth, curved functions, or combinatorial optimization, which deals with discrete choices, linear programming is limited to problems that can be modeled with straight lines and flat planes. However, this limitation is also its greatest strength. The linear structure guarantees that any local optimum is also the global optimum, a property that does not hold for more general problems. This makes linear programming a remarkably robust and reliable tool. While it is a special case of convex optimization, it predates and helped inspire that broader field.The prerequisites for understanding linear programming are modest. A solid grasp of high-school algebra, particularly the ability to solve systems of linear equations, is essential. An introductory course in linear algebra, covering matrices, vectors, and matrix multiplication, is highly recommended, as it provides the language for expressing and solving problems with many variables. No prior knowledge of optimization is required, as the core concepts are built from the ground up. The field is remarkably accessible, and its immediate practical applications make it a compelling entry point into the broader world of mathematical optimization.The 8 concepts its tower teaches
- Linear Programming Formulation
- Feasible Region
- Convexity
- Vertices
- Optimality at Vertices
- Simplex Method
- Duality
- Sensitivity Analysis
- 1951-Present
First-Order and Stochastic Gradient Methods
How to minimize a function by following its gradient?
- 1951-Present
Nonlinear Programming
What conditions characterize an optimum of a nonlinear program?
- 1955-Present
- 1956-Present
- 1957-Present
Dynamic Programming
How to solve multi-stage decision problems recursively?
- 1958-Present
Combinatorial optimization
How to find the best solution among discrete options?
- 1960-Present
Global and Derivative-Free Optimization
How to find global optima without derivatives?
- 1970-Present
Regularization and Statistical Learning Optimization
How to fit models to data by minimizing regularized loss?
- 1971-Present
Complexity and Approximation Theory
How hard is it to solve an optimization problem?
- 1975-Present
Metaheuristic
How to search broadly for good solutions without guarantees?
- 1984-Present
Interior-point method
How to solve linear programs from inside the feasible region?
- 1990-Present
Convex Optimization
Which optimization problems are tractable because of convexity?
About Convex Optimization
Convex optimization is a subfield of mathematical optimization that studies a specific, remarkably tractable class of problems: minimizing a convex function over a convex set. Equivalently, one may maximize a concave function over a convex set. The field’s central insight is that this geometric structure—the "bowl-shaped" landscape of the objective and the "bulging" shape of the feasible region—guarantees that any local solution is also the global solution. This single property transforms the often-daunting task of finding a best-possible answer into a problem that can be solved reliably and, in many important cases, in polynomial time.The formal setting is simple. A problem is defined by a real-valued convex objective function f over a convex feasible set C. The goal is to find a point x* in C that attains the infimum of f over C. The standard form writes this as minimizing f(x) subject to inequality constraints gᵢ(x) ≤ 0, where each gᵢ is convex, and equality constraints hᵢ(x) = 0, where each hᵢ is affine (a linear function plus a constant). Because the feasible set is the intersection of convex sets (the sublevel sets of the convex functions and the hyperplanes defined by the affine equalities), it is itself convex dove. This compact formalism covers an enormous range of practical problems, from fitting lines to data to balancing investment portfolios.The field’s practical power rests on a second property, one that the mathematical definition alone does not reveal: algorithmic tractability. While general mathematical optimization is NP-hard in the worst case, many classes of convex problems can be solved in polynomial time. This was not always obvious. For much of the history of optimization, convexity was treated as a useful but incidental feature of certain problems. Linear programming, developed in the late 1940s, already exploited a special kind of convexity, but the generalization to nonlinear convex objectives and constraints came into its own starting in the 1970s. The development of polynomial-time interior-point methods in the 1980s, following Narendra Karmarkar's projective algorithm for linear programming and its later extension to nonlinear convex problems by Yurii Nesterov and Arkadi Nemirovski in the early 1990s, cemented convex optimization as a cornerstone of applied mathematics and machine learning commun.To understand what convex optimization is, it helps to place it among its neighbors. Linear programming, dominant since the 1940s, handles problems where the objective and constraints are all linear—a special, extremely tractable case. Nonlinear programming, which developed alongside convex optimization, deals with the general case where functions may have multiple local minima Wax, twists, and saddle points; there, finding a global optimum is generically hardcisely, and no algorithm can guarantee success without strong assumptions. Convex optimization sits between these: it allows nonlinearity but restricts it to the specific, structured form where every local optimum is global. This restriction is not a weakness but the key to its power—it is the boundary where optimization problems become tractable in a deep, structural sense.The Organizing IdeaThe framework’s distinctive contribution is the recognition that a broad, practically important class of problems—far broader than linear programming—can be solved with the same guarantees of global optimality that make linear programming so attractively clean. A convex problem is defined by two ingredients: a convex objective function and a convex feasible set. A set is convex if the line segment between any two of its points lies entirely inside it. A function is convex if its graph lies below the chord connecting any two points on it—roughly, the function curves upward. The equality constraints in a convex problem must be affine (linear plus a constant), which keeps the feasible region convex; the inequality constraints must be convex functions of the variable. When all these conditions hold, the problem has a defining property: every local minimum is a global minimum. There are no treacherous valleys or false peaks; a descent method that finds any stationary point has, in fact, found the best possible solution.Essential Concepts in Learning Order1. Convex Sets and Convex FunctionsThe foundation is geometric. A set C is convex if, for any two points x and y in C, the entire segment tx + (1−t)y for t in [0,1] lies in C. A function f is convex if for all such points, f(tx + (1−t)y) ≤ t f(x) + (1−t) f(y). The inequality says that the function’s value along any chord lies below or on the chord itself. Convex functions have second-order characterizations when differentiable: the Hessian must be positive semidefinite throughout the domain.2. The Standard FormA convex optimization problem is conventionally written in standard form: minimize f(x) subject to gᵢ(x) ≤ 0 for convex gᵢ, and hᵢ(x) = 0 for affine hᵢ. The objective f must be convex)Skip. This compact notation is powerful because it exposes the structure that algorithms exploit: the feasible region bulges outward, and the objective never bends downward in a way that would create traps.3. DualityOne of the most powerful ideas in the framework is Lagrangian duality. To every convex problem one can attach a dual problem whose optimal value provides a lower bound on the original (primal) optimum. Under mild conditions called constraint qualifications, the two optima coincide—this is strong duality. Duality is not merely a theoretical curiosity. It underpins sensitivity analysis, gives certificates of optimality, and leads to decomposition methods for large problems. The associated Karush–Kuhn–Tucker (KKT) conditions characterize optimality for differentiable convex problems and form the backbone of many algorithms.4. AlgorithmsThe history of solution methods for convex problems traces a revealing arc. Early work in the 1940s and 1950s on linear programming produced the simplex method, which is efficient in practice but has worst-case exponential behavior. In the 1970s, Leonid Khachiyan's ellipsoid method proved that linear programming is solvable in polynomial time—a landmark theoretical result, though slow in practice. The decisive breakthrough for convex optimization came with Narendra Karmarkar's 1984 interior-point method, which was both polynomial-time and practically fast for linear programs. Nesterov and Nemirovski extended these ideas to general convex problems in the late 1980s and early 1990s with the theory of self-concordant barrier functions, creating a unified algorithmic framework. Today, primal-dual interior-point methods and first-order methods such as the proximal gradient method form the workhorses of the field.5. Modeling and ApplicationsA crucial practical skill is recognizing when a real-world problem can be cast in convex form—or when a slight reformulation makes it convex. This is often the hard part. Many problems from engineering, statistics, and finance are naturally convex. Least-squares regression, linear and quadratic programming, and geometric programming are standard examples. Special classes such as semidefinite programming and cone programming extend the framework further)Skip and have become central in control theory, combinatorial optimization relaxations, and machine learning. The epigraph trick—moving the objective into an extra variable and an inequality constraint—shows that any convex problem can be put into a standard algorithmic form. The modeler's art lies in choosing formulations that are both accurate and computationally tractable.6. What Makes It DistinctiveCompared with general nonlinear programming, convex optimization has a unique status: it is the largest known class of problems for which a local optimum is guaranteed to be globalible, and for which efficient algorithms have a rigorous performance guarantee. Compared with linear programming, it sacrifices pure linearity but gains far greater expressive power while retaining the core guarantee of tractability. Compared with combinatorial optimization, it deals with continuous variables and can often provide relaxations that bound or even solve discrete problems. The framework's power lies precisely in this combination: a simple geometric condition that both describes an enormous range of real problems and enables reliable, efficient solution.History and LegacyWhile the concept of convexity has ancient mathematical roots, convex optimization as a coherent framework crystallized in the second half of the twentieth century. The immediate predecessor was linear programming, developed by George Dantzig in the 1940s with the simplex method. The 1950s and 1960s saw the emergence of nonlinear programming and increasingly sophisticated theory, but general nonlinear problems remained stubbornly difficult. The local period of convex optimization as a distinct framework begins in the 1970s. The polynomial-time solvability of convex problems was demonstrated in sequence: the ellipsoid method in the 1970s, then Karmarkar's interior-point breakthrough, then the self-concordant barrier theory of Nesterov and Nemirovski in the early 1990s. Throughout this period, the field absorbed and unified earlier work on duality (from linear programming), on the geometry of convex sets, and on descent methods. A landmark codification came with Stephen Boyd and Lieven Vandenberghe's 2004 textbook Convex Optimization, which established the modern pedagogical canon and made the subject accessible to a broad engineering audiencefication. The field also developed deep connections to the earlier framework of combinatorial optimization: many discrete problems admit convex relaxations whose solutions provide bounds or exact answers. As of the early 21st century, convex optimization is a mature discipline—a standard tool in control, signal processing, communications, finance, and, increasingly, in the training and analysis of machine learning models, where it provides the theoretical bedrock for understanding gradient-based methods even when the problems at hand are not themselves convex.Why It Matters NowThe continuing significance of convex optimization lies in its role as a guarantee in a world of approximate methods. Modern large-scale learning problems are rarely convex in their full form, but their core components often are, and convex relaxations provide certificates, bounds, and starting points that make tractable algorithms possible. The field also remains a rich source of new algorithmic ideas: first-order methods with accelerated convergence rates, distributed optimization schemes, and interior-point techniques continue to be refined and applied to problems with thousands or millions of variables. For a student of applied mathematics, convex optimization is the natural bridge between the clean theory of linear programming and the messy reality of general nonlinear optimization—a set of tools whose power and reliability have made it a standard ingredient in the modern computational toolbox.The 11 concepts its tower teaches
- Convex Sets and Functions
- Standard Form Convex Problem
- Local Minima Are Global
- Lagrangian Duality
- Strong Duality and Slater's Condition
- KKT Conditions
- Convex Modeling
- Epigraph Reformulation
- Interior-Point Methods
- First-Order Methods
- Convex Relaxation
- 1998-Present
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Optimal Control grew out of Calculus of Variations
Optimal control grew directly out of the calculus of variations: the Pontryagin maximum principle generalizes the Euler–Lagrange equation to problems with control constraints, treating the control as the unknown function.
Carried by Lev Pontryagin.
Combinatorial optimization grew out of Linear Programming
Integer and combinatorial optimization built on the linear programming formulation; Gomory's cutting planes (1958) and branch-and-bound (1960) work by tightening and partitioning the LP relaxation.
Carried by Ralph Gomory; Ailsa Land; Alison Doig.
Complexity and Approximation Theory influenced by Combinatorial optimization
Computational complexity theory took the combinatorial problems of integer programming, such as the traveling salesman problem, as its central examples of NP-hard problems, reframing the field's ambitions.
Carried by Stephen Cook; Richard Karp.
Nonlinear Programming influenced by Calculus of Variations
The KKT conditions for constrained nonlinear programs generalize Lagrange multipliers, the technique Lagrange introduced in the calculus of variations for equality constraints.
Carried by Harold Kuhn; Albert Tucker; William Karush.
Nonlinear Programming grew out of Linear Programming
Nonlinear programming extended the linear programming framework to nonlinear objectives and constraints, with the KKT conditions playing the role duality plays in linear programs.
Carried by Harold Kuhn; Albert Tucker.
Convex Optimization grew out of Linear Programming
Convex optimization absorbed linear programming as a special case, recognizing LP, least squares, and semidefinite programming as instances of a common convex structure solvable by shared methods.
Regularization and Statistical Learning Optimization grew out of First-Order and Stochastic Gradient Methods
Regularization and statistical learning optimization grew out of first-order gradient methods, applying them to regularized loss minimization in statistics and machine learning.
Global and Derivative-Free Optimization grew out of Nonlinear Programming
Global and derivative-free optimization developed as a branch of nonlinear programming for problems where gradients are unavailable or local methods fail to find global optima.
Interior-point method influenced by Nonlinear Programming
Interior-point methods for linear programming were soon generalized to nonlinear and convex programming, building on the barrier methods developed in nonlinear programming in the 1960s.
Convex Optimization grew out of Nonlinear Programming
Convex optimization emerged as the tractable special case of nonlinear programming, where the KKT conditions become sufficient and algorithms have global convergence guarantees.
Robust Optimization grew out of Nonlinear Programming
Robust optimization reformulated nonlinear programs to remain feasible under data uncertainty, growing out of the constrained optimization framework.
Robust Optimization grew out of Stochastic Programming
Robust optimization emerged as a worst-case counterpart to stochastic programming, replacing probabilistic uncertainty with deterministic uncertainty sets.
Dynamic Programming rival of Optimal Control
Optimal control and dynamic programming were developed contemporaneously as competing approaches to sequential decision problems, the maximum principle giving necessary conditions and dynamic programming a recursive solution.
Carried by Lev Pontryagin; Richard Bellman.
Metaheuristic grew out of Combinatorial optimization
Metaheuristics developed as practical search methods for combinatorial optimization problems that exact algorithms cannot solve, such as simulated annealing and genetic algorithms.
Carried by Scott Kirkpatrick; John Holland.
Metaheuristic influenced by Complexity and Approximation Theory
The NP-hardness results of complexity theory motivated the development of heuristics and metaheuristics that find good solutions without optimality guarantees.
Interior-point method influenced by Complexity and Approximation Theory
Khachiyan's polynomial-time ellipsoid method for linear programming was a complexity-theoretic result that spurred Karmarkar's polynomial-time interior-point method.
Carried by Leonid Khachiyan; Narendra Karmarkar.
Beyond the field
Where Mathematical Optimization's ideas came from in other fields, and what they led to there: the strongest 12 of 76 links.
Calculus of Variations led to Variational geometry and geometric analysis in Calculus Of Variations
Variational geometry and geometric analysis grew directly out of the classical calculus of variations, applying its variational principles to geometric functionals such as area and energy.
Calculus of Variations led to Regularity theory in Calculus Of Variations
Regularity theory is a direct descendant of the classical calculus of variations: Hilbert's nineteenth problem and the older question of whether minimizers of variational integrals are smooth carried over into the modern regularity program.
Carried by David Hilbert.
Calculus of Variations led to Direct method in the calculus of variations in Calculus Of Variations
The direct method grew out of the classical calculus of variations by replacing the Euler–Lagrange equation with minimization over a function space. Hilbert's and Tonelli's work turned the classical problem into an existence theory.
Carried by David Hilbert; Leonida Tonelli.
Calculus of Variations grew out of Calculus in Mathematical Analysis
The calculus of variations grew directly out of the differential and integral calculus: Euler and Lagrange treated the variation of an integral as a problem in the calculus itself, using the same differential notation and operations. Euler's Methodus inveniendi (1744) and Lagrange's later analytical treatment formalised this as a branch of analysis.
Carried by Leonhard Euler; Methodus inveniendi (1744); Joseph-Louis Lagrange.
Calculus of Variations led to Optimal control and the Pontryagin maximum principle in Calculus Of Variations
Optimal control and the Pontryagin maximum principle grew directly out of the calculus of variations: Pontryagin's maximum principle generalizes the Euler–Lagrange and Weierstrass conditions to control problems with constraints on the control.
Carried by Lev Pontryagin.
Calculus of Variations led to Global variational and minimax methods in Calculus Of Variations
Global variational and minimax methods grew directly out of the classical calculus of variations: Morse theory and the direct methods of the calculus of variations generalized the older search for extrema of functionals to global and topological settings.
Carried by Marston Morse.
Calculus of Variations led to Lagrange multiplier in Calculus Of Variations
The Lagrange multiplier arose inside the calculus of variations as the device for adjoining isoperimetric and holonomic constraints to the variation. It is a technique developed within that body of theory.
Carried by Joseph-Louis Lagrange.
Calculus of Variations led to Convex analysis and lower semicontinuity (Tonelli–Morrey existence theory) in Calculus Of Variations
Tonelli's lower semicontinuity and convexity conditions were developed to make the classical variational problem well posed, refining the older calculus of variations into an existence theory. The framework is a direct outgrowth of that classical problem.
Carried by Leonida Tonelli.
Calculus of Variations led to Calculus of Variations and Geometric Measure Theory in Partial Differential Equations
Calculus of variations and geometric measure theory grew directly out of the classical calculus of variations, extending its existence theory and its notion of minimiser to non-smooth objects. Hilbert's and Lebesgue's work around 1900 carried the classical variational problems into the modern framework.
Carried by David Hilbert; Henri Lebesgue.
Calculus of Variations led to Geometric measure theory and minimal surfaces in Calculus Of Variations
Geometric measure theory and minimal surfaces grew directly out of the classical calculus of variations: the Plateau problem and area minimization were the variational problems whose measure-theoretic treatment founded the field.
Linear Programming led to Integer and Mixed-Integer Programming in Combinatorial Optimization
Integer programming grew out of linear programming: Gomory's cutting-plane method (1958) and the branch-and-bound work of Land and Doig (1960) took the simplex method and LP duality as their starting machinery, adding integrality constraints on top.
Carried by Ralph Gomory; Ailsa Land; Alison Doig.
Linear Programming influenced by Linear algebra in Algebra
Linear programming is formulated entirely in linear algebra: Dantzig's simplex method operates on systems of linear inequalities and matrices, and duality is expressed through linear algebra.
Carried by George Dantzig.

Mathematical Optimization is a planet in Nousfarer
Its city has a tower for each of these 15 frameworks. Land, walk in, and climb one concept at a time.
Land on Mathematical OptimizationRelated fields
Fields its ideas are linked to
- Calculus Of Variations 12 links
- Applied Mathematics 8 links
- Algorithms 6 links
- Combinatorial Optimization 6 links
- Operations Research 6 links
- Reinforcement Learning 3 links
- Astrodynamics 2 links
- Approximation Algorithms 2 links
- Inverse Problems 2 links
- Numerical Analysis 2 links
- Resource Economics 2 links
- Geometry 2 links
More in Applied Mathematics
- Applied Mathematics
- Asymptotic Analysis
- Continuum Mechanics
- Control Theory
- Financial Mathematics
- Game Theory
- Inverse Problems
- Mathematical Biology
- Numerical Analysis
See where Mathematical Optimization sits on the Map of Human Knowledge