Mathematical optimization is the branch of mathematics concerned with finding values of decision variables that minimize or maximize an objective function, subject to specified restrictions. It provides both a language for expressing decision problems and methods for solving them. Applications range from resource allocation and engineering design to statistical estimation and machine learning. The alternative name mathematical programming refers to planning or selecting decisions, rather than specifically to writing computer programs. (stanford.edu)
Mathematical formulation
A common finite-dimensional formulation is
[ \begin{aligned} \operatorname{minimize}_{x\in X}\quad & f(x),\ \text{subject to}\quad & g_i(x)\leq 0,\quad i=1,\ldots,m,\ & h_j(x)=0,\quad j=1,\ldots,p. \end{aligned} ]
Here (x) represents the decision variables, (f) is the objective function, and the functions (g_i) and (h_j) express inequality and equality constraints. The domain (X) may impose additional restrictions, such as requiring some variables to be integers. The feasible set consists of all points satisfying these requirements. Maximizing (f) is equivalent to minimizing (-f). (stanford.edu)
A feasible point (x^\ast) is a global minimizer if (f(x^\ast)\leq f(x)) for every feasible (x). A local minimizer satisfies this comparison only within some neighborhood. A problem can be infeasible, unbounded below, or have a finite infimum that is never attained. For example, minimizing (x) over (x>0) has infimum zero but no minimizing point. (wiki.mcs.anl.gov)
Principal problem classes
Problems are classified by their variables, constraints, and objective:
- Continuous optimization permits variables to range over continuous domains, usually subsets of real coordinate space.
- Integer programming requires some or all variables to take integer values; mixed-integer problems combine integer and continuous variables.
- Linear programming uses a linear objective and affine equality or inequality constraints.
- Quadratic programming uses a quadratic objective with affine constraints.
- Nonlinear optimization allows more general functions.
- Unconstrained optimization has no explicit constraints beyond the variables’ domain; constrained optimization includes additional restrictions. (wiki.mcs.anl.gov)
These classifications overlap. In convex optimization, the objective is a convex function and the feasible set is convex. Every local minimizer is then globally optimal, although a minimizer need not exist or be unique. Nonconvex problems can have distinct local minima, making global certification more difficult. (stanford.edu)
Optimality conditions and duality
For a differentiable objective, an unconstrained local minimizer in the interior of its domain must have zero gradient. This condition is not sufficient: a stationary point can also be a maximum or a saddle point. Second-order conditions examine curvature through the Hessian matrix of second derivatives. A positive-definite Hessian at a stationary point establishes a strict local minimum. (wiki.mcs.anl.gov)
Constrained problems commonly use Karush–Kuhn–Tucker conditions, involving stationarity, feasibility, multiplier signs, and complementary slackness. Their necessity generally requires suitable constraint qualifications. Lagrangian duality constructs a related problem whose value provides a bound on the original minimization problem. Under appropriate conditions, including standard regularity assumptions in convex optimization, the optimal primal and dual values coincide. Such bounds can certify solution quality without directly comparing every feasible point. (mit.edu)
Solution methods
An optimization algorithm exploits the problem’s structure and the information available about its functions. Gradient descent repeatedly moves against the gradient, with a step size controlling each update. Line search procedures choose a step along a proposed direction. Newton’s method uses second-order information, while quasi-Newton methods build approximations to curvature rather than calculating the full Hessian at every iteration. (arxiv.org)
Linear programs are commonly solved by the simplex method or interior-point methods. Other constrained problems use projected-gradient, penalty, augmented-Lagrangian, or sequential quadratic programming methods. These approaches differ in how they enforce constraints or construct simpler subproblems. No single method is equally suitable for all problem classes. (neos-guide.org)
For large data-based objectives, stochastic gradient descent estimates gradients using sampled observations or small batches. This reduces work per update but introduces variability. Methods such as the Adam optimizer adapt updates using accumulated gradient statistics; their behavior depends on the objective, parameter settings, and sampling process. (arxiv.org)
Applications in learning and decision-making
In statistical learning, optimization selects model parameters by minimizing a loss function evaluated on training data. Empirical risk minimization formalizes this process using average observed loss. Regularization modifies the objective or admissible parameters to discourage particular forms of complexity. Neural-network training often combines sampled-gradient updates with derivative calculations through the model. (mit.edu)
In operations research and engineering, decision variables may describe production quantities, schedules, transportation choices, or electricity generation. Constraints encode capacities, conservation requirements, and other restrictions. Optimization models also appear in economics and game theory, including consumption planning and strategic interactions between firms. (neos-guide.org)
Modeling and numerical limitations
Optimality is always relative to the chosen model: changing the objective, constraints, or input data can change the preferred solution. A mathematically optimal result therefore does not establish that the model captures every relevant feature of the underlying situation. Practical analysis includes formulating the problem, solving it, and interpreting the result in its application context. (neos-guide.org)
Numerical methods typically return approximate solutions rather than exact symbolic answers. Their assessment distinguishes constraint violations, stationarity, and objective-value bounds. A small gradient alone does not certify global optimality for a general nonconvex problem, whereas an appropriate primal–dual bound can provide a quantitative certificate. (mit.edu)