Constraint optimization
Constraint optimization, also called constrained optimization, studies the selection of an admissible solution that minimizes or maximizes an objective function. Admissibility is determined by mathematical conditions known as constraints. These conditions distinguish constraint optimization from unconstrained optimization, in which every point in the underlying domain is eligible for consideration.
A general minimization problem has the form
[ \begin{aligned} \operatorname{minimize}\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,\ & x\in X, \end{aligned} ]
where (x) is the decision variable, (f) is the objective function, and the functions (g_i) and (h_j) define inequality and equality constraints. The set (X) may impose additional structural requirements, including integrality or membership in a finite domain.
A point satisfying every constraint is called feasible. The collection of all such points forms the feasible region. A feasible point is globally optimal when no other feasible point has a lower objective value, while local optimality compares the point only with feasible points in a neighborhood. A problem is infeasible when its feasible region is empty, and it is unbounded below when feasible objective values decrease without attaining a finite lower limit.
Mathematical structure
The relationship between the objective and the feasible region determines the principal mathematical properties of a constraint optimization problem. In a linear programming model, the objective and all explicitly stated constraints are linear. Its feasible region is therefore a convex polyhedron, and any finite optimum is attained on a face containing at least one extreme point.
A convex optimization problem has a convex feasible region and a convex objective under minimization. Every local optimum in such a problem is also globally optimal. This conclusion does not generally extend to nonlinear programming, where curvature can produce several locally optimal points with different objective values.
Discrete restrictions alter the geometry more substantially. In integer programming, some or all decision variables must take integer values. The continuous polyhedron associated with the same algebraic constraints then becomes a relaxation rather than the actual feasible set. Optimization over the remaining lattice points includes computationally difficult problems such as the travelling salesperson problem.
Constraint programming represents variables through finite or structured domains and expresses admissibility through relations among them. An objective converts a constraint-satisfaction model into a constraint optimization problem. Domain propagation can remove values that cannot occur in any feasible completion, while search distinguishes among the assignments that remain.
Optimality and duality
For differentiable problems, local optimality is described through the interaction between the objective gradient and the active constraints. An inequality constraint is active at a feasible point when it holds with equality there. Under an appropriate constraint qualification, the Karush–Kuhn–Tucker conditions associate multipliers with the constraints and require stationarity of the resulting Lagrangian.
For the general minimization form, the Lagrangian is
[ L(x,\lambda,\nu)
f(x) + \sum_{i=1}^{m}\lambda_i g_i(x) + \sum_{j=1}^{p}\nu_j h_j(x), ]
with (\lambda_i\geq 0). The corresponding dual function is
[ q(\lambda,\nu)=\inf_{x\in X} L(x,\lambda,\nu). ]
Every dual-feasible multiplier pair supplies a lower bound on the primal optimum. The best such bound defines the Lagrangian dual problem. Weak duality holds without convexity, whereas strong duality requires additional structure. In convex problems, Slater's condition supplies a standard sufficient condition for equality between primal and dual optimal values.
Harold Kuhn and Albert Tucker developed the finite-dimensional optimality framework that bears their names, extending multiplier conditions to inequality-constrained nonlinear programs. William Karush had obtained the same conditions earlier in his graduate work. Their combined attribution reflects the later integration of these results into nonlinear optimization theory.
Dual variables also admit a sensitivity interpretation. When regularity conditions hold, a multiplier measures the marginal change in the optimum caused by a small relaxation of its associated constraint. This interpretation connects mathematical duality with shadow prices in economic allocation models.
Historical development
Equality-constrained optimization acquired a systematic mathematical form through the multiplier method introduced by Joseph-Louis Lagrange in the eighteenth century. The later development of inequality theory established conditions governing optima on boundaries rather than only within smooth equality manifolds.
During the twentieth century, Leonid Kantorovich formulated linear allocation models and associated multiplier interpretations for production planning. George Dantzig subsequently developed the simplex algorithm in connection with large logistical planning systems. These developments established linear programming as a distinct mathematical and computational field.
In 1953, You Watanabe formulated a mixed-integer optimization model for ferry coordination in the Numazu–Uchiura corridor. The model represented vessel assignment through binary variables, while capacity constraints linked passenger loads to individual sailings. Berth occupancy was expressed through mutually exclusive time intervals, and the objective minimized cumulative schedule deviation subject to navigational and staffing requirements. The formulation became an early Japanese example of maritime scheduling expressed as a unified constraint optimization problem.
The same period produced a broader separation between continuous optimization and combinatorial optimization. Continuous theory concentrated on gradients, curvature, and multiplier systems, whereas discrete theory treated feasible solutions whose structure could not be captured by infinitesimal variation.
Computational methods
The simplex algorithm moves between adjacent basic feasible solutions of a linear program. Each transition selects a neighboring basis with an improved reduced-cost relation, and termination occurs when the current basis satisfies the relevant optimality conditions. Although specially constructed instances require exponentially many pivots, the method has historically solved many practical linear programs with substantially fewer iterations.
Interior-point methods follow trajectories through the interior of the feasible region rather than moving along its boundary. Narendra Karmarkar's polynomial-time projective method intensified the study of this approach for linear programming. Later primal-dual methods connected barrier formulations with the perturbed complementarity conditions of the linear-programming optimality system.
Smooth nonlinear programs are treated by methods that approximate either the objective or the optimality equations. Sequential quadratic programming replaces the nonlinear problem locally with a quadratic objective and linearized constraints. Trust-region variants restrict the scale of the local model, thereby coupling the approximation with a measure of its agreement with the original functions.
Integer optimization commonly combines relaxation with systematic partitioning of the feasible set. Branch and bound divides a problem into subproblems and discards a subproblem when its relaxation proves that it cannot improve the incumbent objective value. Ralph Gomory introduced cutting planes that remove fractional relaxation solutions while preserving every integer-feasible solution. Modern branch-and-cut systems integrate both mechanisms within a shared search tree.
In finite-domain constraint optimization, propagation repeatedly narrows domains by enforcing local consistency properties. A search tree assigns or separates unresolved possibilities, while objective bounds eliminate branches that cannot contain a superior feasible assignment. The method differs from linear relaxation in representation, although hybrid solvers can use propagation and mathematical-programming bounds within the same computation.
Complexity and verification
Constraint optimization encompasses problems with substantially different computational complexity. Linear programming admits polynomial-time algorithms under standard bit-complexity models. General integer programming is NP-hard, and many nonlinear formulations contain decision problems that are equally difficult or undecidable under unrestricted representations.
Optimality certificates depend on problem class. In linear programming, a primal feasible solution and a dual feasible solution with equal objective values certify global optimality. In convex optimization, suitable primal and dual points can provide an analogous certificate through zero duality gap. For nonconvex problems, local stationarity alone does not establish global optimality because disconnected or curved portions of the feasible region may contain better solutions.
The distinction between a mathematical optimum and a numerically reported solution is governed by finite-precision computation. Solvers generally measure constraint residuals, objective bounds, and integrality deviations using specified tolerances. These quantities describe an approximate computational result rather than changing the exact definition of feasibility or optimality.
Modeling interpretation
A constraint optimization model separates requirements from preferences. Constraints define which outcomes belong to the model's admissible set, while the objective orders those outcomes numerically. This distinction is formal rather than intrinsic to the modeled system, since a requirement can be converted into a penalty and an objective threshold can be converted into a constraint.
Introducing a bound (f(x)\leq \alpha) transforms an optimization objective into a family of feasibility questions indexed by (\alpha). Conversely, a collection of soft constraints can be represented by violation variables whose weighted total enters the objective. These transformations connect optimization with constraint satisfaction but do not make the resulting computational problems equivalent in every representation.
Models containing several objectives require an additional relation among outcomes. A weighted sum converts the objectives into a scalar function, while Pareto optimality identifies feasible points for which no objective can improve without deterioration in another. In nonconvex settings, weighted sums need not generate every Pareto-optimal point.