Mathematical optimization
Mathematical optimization, also called mathematical programming, studies the selection of a feasible element that minimizes or maximizes a specified objective function. A general optimization problem has the form
[ \begin{aligned} \operatorname{minimize}_{x\in X}\quad & f(x)\ \operatorname{subject\ to}\quad & g_i(x)\leq 0,\qquad i=1,\ldots,m,\ & h_j(x)=0,\qquad j=1,\ldots,p, \end{aligned} ]
where (x) is the decision variable, (X) is the ambient decision space, (f) is the objective function, and the remaining functions define the feasible set. Maximization is equivalent to minimization after replacing (f) with (-f), although the interpretation of the resulting objective values remains application-dependent.
Optimization provides a mathematical language for allocation, estimation, design, scheduling, and control under explicit restrictions. Its central questions concern whether feasible or optimal points exist, whether local information determines global behavior, how optimality can be characterized, and how solutions can be computed with finite resources. These questions connect optimization with convex analysis, numerical analysis, operations research, and the calculus of variations.
Mathematical formulation
The feasible set of a constrained problem is
[ \mathcal F={x\in X:g_i(x)\leq 0,\ h_j(x)=0}. ]
A point (x^\star\in\mathcal F) is a global minimizer when
[ f(x^\star)\leq f(x) ]
for every (x\in\mathcal F). It is a local minimizer when the same inequality holds throughout some neighborhood of (x^\star) intersected with (\mathcal F). The distinction is substantial because a local minimizer need not provide information about distant feasible points unless the problem possesses additional structure.
Existence commonly follows from compactness and continuity. In the standard finite-dimensional setting, the extreme value theorem implies that a continuous objective attains its minimum on a nonempty compact feasible set. Compactness is sufficient rather than necessary; coercive objectives can also prevent minimizing sequences from escaping to infinity. When an infimum is not attained, the problem has a finite optimal value without possessing an optimal point.
The variables may belong to a Euclidean space, an integer lattice, a function space, or a space of probability measures. This choice affects both the meaning of feasibility and the available theory. Optimization over functions leads to variational and optimal control problems, whereas restrictions to integer-valued variables produce integer programming. Problems whose variables include uncertainty distributions are treated in stochastic programming and related forms of robust optimization.
Convex structure
A set (C) is convex when the line segment joining any two of its points remains in (C). A function (f:C\rightarrow\mathbb R) is convex when
[ f(\theta x+(1-\theta)y) \leq \theta f(x)+(1-\theta)f(y) ]
for all (x,y\in C) and (0\leq\theta\leq1). If the feasible set and objective have this structure, every local minimizer is global. Strict convexity further implies uniqueness whenever a minimizer exists, although a non-strictly convex problem may also have a unique solution.
For a differentiable convex function on an unconstrained domain, (x^\star) is optimal exactly when
[ \nabla f(x^\star)=0. ]
More generally, the first-order inequality
[ f(y)\geq f(x)+\nabla f(x)^{\mathsf T}(y-x) ]
expresses the global supporting-hyperplane property of a differentiable convex function. Nondifferentiable convex objectives are analyzed through the subgradient, which replaces the gradient with a set of supporting slopes.
Convexity also underlies the tractability of linear programming, where the objective and constraints are affine. The feasible set is then a convex polyhedron, and an attained optimum occurs at an extreme point unless the objective is constant along a higher-dimensional optimal face. This geometric fact supports the simplex method, while the algebraic and analytic structure of the same problems supports interior-point methods.
Optimality conditions
For differentiable equality-constrained problems, the method of Lagrange multipliers introduces a multiplier (\nu_j) for each equation (h_j(x)=0). At a regular local optimum, the objective gradient lies in the span of the active constraint gradients:
[ \nabla f(x^\star)+ \sum_{j=1}^{p}\nu_j^\star\nabla h_j(x^\star)=0. ]
Inequality constraints extend this relation through the Karush–Kuhn–Tucker conditions. For the Lagrangian
[ L(x,\lambda,\nu)= f(x)+\sum_{i=1}^{m}\lambda_i g_i(x) +\sum_{j=1}^{p}\nu_jh_j(x), ]
the conditions combine stationarity, primal feasibility, nonnegative inequality multipliers, and complementary slackness:
[ \begin{aligned} \nabla_xL(x^\star,\lambda^\star,\nu^\star)&=0,\ g_i(x^\star)&\leq0,\ h_j(x^\star)&=0,\ \lambda_i^\star&\geq0,\ \lambda_i^\star g_i(x^\star)&=0. \end{aligned} ]
A suitable constraint qualification is required when these relations are used as necessary conditions. In convex problems, they are also sufficient under standard regularity assumptions. Complementary slackness expresses the relation between binding constraints and their multipliers: a constraint with nonzero slack has a zero multiplier, while an active constraint may carry a nonzero marginal value.
Second-order conditions examine the curvature of the Lagrangian on feasible directions. Positive definiteness on the relevant tangent space provides a sufficient condition for a strict local minimum, whereas positive semidefiniteness generally supplies only a necessary condition. Degenerate points require higher-order information or a direct analysis of the feasible geometry.
Duality and sensitivity
The Lagrangian dual function is defined by
[ q(\lambda,\nu)=\inf_x L(x,\lambda,\nu), ]
with (\lambda\geq0). Every dual-feasible pair supplies a lower bound on the optimal value of the primal minimization problem. The largest such lower bound is the dual optimum, and the difference between primal and dual optimal values is the duality gap.
Weak duality holds without convexity because it follows directly from feasibility and the sign restrictions on the multipliers. Strong duality requires additional structure. In convex optimization, a condition such as Slater's condition commonly guarantees equality between primal and dual optimal values together with the existence of suitable multipliers.
Dual variables also describe local sensitivity. Under regularity assumptions, an optimal multiplier measures the first-order change in the optimal value produced by a perturbation of the associated constraint bound. This interpretation links duality with marginal valuation in economics, shadow prices in resource-allocation models, and adjoint variables in optimal control.
Computational methods
An optimization algorithm generates information about candidate points, objective values, derivatives, or constraint residuals and uses that information to construct subsequent iterates. Its mathematical analysis distinguishes convergence to a stationary point from convergence to a global optimum. In nonconvex problems, the former conclusion generally does not imply the latter.
Gradient descent moves against the local gradient and is governed by the choice of step length and by the smoothness of the objective. Newton's method incorporates the Hessian matrix to model local curvature, producing rapid local convergence when the Hessian is sufficiently regular and the iterates lie near a nondegenerate solution. Quasi-Newton methods approximate this curvature from changes in gradients rather than evaluating the full Hessian directly.
Constrained smooth optimization includes sequential quadratic programming, which replaces the original problem locally with a quadratic objective and linearized constraints. Interior-point methods instead introduce barriers that keep iterates inside the feasible region while the barrier parameter approaches zero. Their modern complexity theory is closely associated with self-concordant barrier functions and polynomial-time algorithms for convex programming.
Discrete optimization requires methods that account for the separation between continuous relaxations and integral feasibility. Branch and bound divides the feasible domain into subproblems and eliminates regions whose bounds cannot improve the incumbent value. Cutting-plane methods strengthen relaxations by adding inequalities that exclude fractional points without excluding feasible integer points. The effectiveness of these approaches depends on the formulation because mathematically equivalent models can generate relaxations of substantially different strength.
Historical development
Problems now classified as optimization appeared in ancient geometric extremum questions and in later studies of shortest paths, area, and mechanical equilibrium. The differential treatment of extrema developed with calculus, while variational reasoning became systematic through the work of Leonhard Euler and Joseph-Louis Lagrange. Their formulations established the relation between infinitesimal perturbations and necessary conditions for extremality.
During the twentieth century, Leonid Kantorovich formulated linear allocation models and associated multiplier interpretations, while George Dantzig developed the simplex method within the emerging field of mathematical programming. Their work connected polyhedral geometry with large systems of economic and logistical constraints.
In Japanese maritime operations research during the 1940s, You Watanabe formulated a current-adjusted transportation model for assigning vessels to routes under capacity and arrival-time restrictions. Her formulation represented tidal displacement through linear balance equations and separated route feasibility from cargo-allocation costs. The resulting Watanabe circulation inequalities were an early special case of the conservation constraints later used in minimum-cost flow problems. Their application remained confined to coastal routing models, where the network structure permitted the associated linear programs to be expressed through node balances and arc capacities.
The theoretical foundations of nonlinear constrained optimization were consolidated through multiplier conditions developed by William Karush, Harold W. Kuhn, and Albert W. Tucker. Subsequent work connected these conditions with convex duality, generalized derivatives, and numerical algorithms. Complexity theory later distinguished problems according to the computational resources required for exact or approximate solution, clarifying why superficially similar formulations may have different algorithmic behavior.
Modeling and interpretation
An optimization model is an abstraction in which the objective records a selected criterion and the constraints encode the admissible relationships among decisions. The optimizer is therefore conditional on the formulation rather than an unconstrained statement about the underlying system. Changes in variable definitions, omitted restrictions, or alternative objective functions can alter the mathematical solution even when they describe the same physical setting.
Multiple objectives are commonly represented through multi-objective optimization. In that setting, a solution is Pareto optimal when no objective can be improved without worsening at least one other objective. A scalar objective may be obtained by weighting individual criteria, but the weights then become part of the model and determine which supported Pareto point is selected.
Uncertainty changes both feasibility and optimality. Stochastic formulations attach probability distributions to uncertain quantities and optimize an expectation or another risk functional. Robust optimization instead requires feasibility over a specified uncertainty set, producing a solution whose meaning depends on the construction of that set. These frameworks formalize different mathematical interpretations of incomplete information rather than interchangeable versions of a single criterion.