Constrained optimization

1 Problem formulation

1.1 Objective functions and decision variables

Constrained optimization begins by selecting a set of decision variables—unknown quantities to be chosen—and an objective function that measures performance. The aim is to find a variable vector that minimizes (or maximizes) the objective while meeting specified constraints. In mathematical terms, a typical continuous formulation seeks an optimum of a function \(f(x)\) over a domain of candidate solutions \(x\in\mathbb{R}^n\), subject to restrictions.

Decision variables may represent design parameters, control inputs over time, latent model parameters, or allocations of limited resources. The objective can be smooth (differentiable), nonsmooth, or even discontinuous, which influences which algorithms are appropriate.

1.2 Types of constraints

1.2.1 Equality and inequality constraints

Constraints are commonly expressed as:

• Equality constraints: \(h_i(x)=0\), requiring exact satisfaction.
• Inequality constraints: \(g_j(x)\le 0\), restricting the solution to a permissible region.

Equality constraints often arise from conservation laws, exact matching requirements, or structural relationships. Inequalities are used for feasibility margins, limits, or safety conditions. In practice, algorithms must cope with the fact that boundary points (where some inequalities are tight) are often where optima occur.

1.2.2 Bound and box constraints

Bounds restrict variables individually, such as \(l_i \le x_i \le u_i\). When all bounds are specified simultaneously, the feasible region can be a box (an axis-aligned hyper-rectangle). Box constraints are particularly common because they encode simple physical or numerical limits, such as actuator ranges, parameter bounds, or normalization restrictions. Many algorithms exploit this separable structure to simplify projection and update steps.

1.3 Feasible sets and feasibility concepts

1.3.1 Interior vs. boundary feasibility

Feasible solutions are those satisfying all constraints. Feasibility can be categorized by location relative to the boundary of the allowed region. An interior feasible point satisfies all inequality constraints strictly (e.g., \(g_j(x)<0\) for every inequality), whereas a boundary point has at least one active inequality constraint with \(g_j(x)=0\). Interior points often enable stronger theoretical guarantees and smoother numerical behavior, while boundary optima may require careful treatment of constraint activation.

1.3.2 Convex vs. non-convex feasibility

A feasible set is convex if any line segment between two feasible points remains feasible. Convexity affects not only the geometry but also the behavior of algorithms and the structure of optimality conditions. Non-convex feasible sets can contain multiple disconnected regions, leading to local optima that are not globally optimal. Even when the feasible set is non-convex, constraints can still be structured so that local methods perform well in practice.

2 Solution notions and optimality

2.1 Global vs. local optima

An optimum can be defined globally or locally. A global optimum is best among all feasible points. A local optimum is best within some neighborhood: no feasible point sufficiently close to it improves the objective. In constrained problems, the neighborhood must respect feasibility, so “close” refers to feasible perturbations rather than arbitrary changes in variables.

Algorithms may target global solutions in special cases (e.g., certain convex problems) or settle for local solutions when the problem is general and potentially non-convex.

2.2 Stationarity and first-order conditions

Stationarity captures the idea that the objective cannot be improved by a small feasible move. For unconstrained optimization, stationarity reduces to vanishing gradient (for smooth objectives). With constraints, the concept generalizes: the gradient of the objective must be balanced by directions associated with the constraints.

First-order optimality conditions are often expressed using Lagrange multipliers or related notions, and they depend on which constraints are active at the candidate point. For inequality constraints, stationarity must account for feasible directions that do not violate constraints.

2.3 Second-order considerations

When first-order conditions are satisfied, second-order checks refine the classification of a point as a minimum, saddle, or maximum. For smooth problems, the curvature of the objective and constraints—captured by Hessians and their restrictions to feasible directions—determines whether the stationary point is locally optimal.

Second-order sufficient conditions provide criteria that guarantee a point is a strict local minimum, while second-order necessary conditions help detect when a stationary point cannot be optimal.

2.4 Constraint qualifications

Constraint qualifications are technical assumptions that ensure the optimality conditions derived from multipliers are valid. Intuitively, they prevent pathological situations where gradients of constraints fail to describe the feasible geometry near a candidate point. Common constraint qualifications influence whether KKT-style conditions (discussed later) are necessary at an optimum.

In numerical practice, inadequate constraint qualification can lead to instability, misleading multiplier estimates, or failure of theoretical guarantees.

3 Lagrangian and duality

3.1 Lagrangian formulation

A foundational tool for constrained optimization is the Lagrangian, which combines the objective and constraints using multipliers. For a problem with inequality constraints \(g_j(x)\le 0\) and equality constraints \(h_i(x)=0\), the Lagrangian typically takes the form \[ \mathcal{L}(x,\lambda,\nu)= f(x)+\sum_j \lambda_j g_j(x)+\sum_i \nu_i h_i(x), \] with \(\lambda_j\ge 0\) for inequality constraints. The Lagrangian transforms feasibility and optimality into a combined stationarity and multiplier framework.

This formulation is useful both for analysis and for algorithms that estimate multipliers alongside primal variables.

3.2 KKT conditions

The Karush–Kuhn–Tucker (KKT) conditions generalize first-order optimality to constrained problems under suitable assumptions. They typically include:

1. Stationarity: the derivative of the Lagrangian with respect to \(x\) vanishes (or satisfies an appropriate subdifferential condition).
2. Primal feasibility: \(h(x)=0\) and \(g(x)\le 0\).
3. Dual feasibility: multipliers associated with inequalities are nonnegative.
4. Complementary slackness: each inequality constraint either is inactive or has a zero multiplier.

3.2.1 Complementary slackness

Complementary slackness encodes the interaction between a constraint and its multiplier. For each inequality \(g_j(x)\le 0\), either the constraint is strictly satisfied (so \(g_j(x)<0\)) and the multiplier \(\lambda_j\) must be zero, or the constraint is tight (\(g_j(x)=0\)) and \(\lambda_j\) may be positive. This relationship helps identify which constraints “drive” the optimum.

3.2.2 Primal-dual feasibility

Primal-dual feasibility requires simultaneously that the primal variables satisfy constraints and that multipliers satisfy sign conditions. Together with stationarity and complementary slackness, these yield a structured set of equations and inequalities characterizing optimality in many smooth settings.

3.3 Dual problems and weak/strong duality

Duality constructs an optimization problem over multipliers. The dual objective is defined by minimizing the Lagrangian with respect to the primal variables, yielding a function of multipliers alone. Weak duality states that, under general conditions, the dual optimum provides a bound on the primal optimum (the direction depends on whether the primal is a minimization or maximization problem). When stronger relationships hold, such as strong duality, the optimal values coincide.

Strong duality is particularly common in convex problems under appropriate regularity assumptions, and it often enables certificates of optimality and gap-based stopping criteria.

3.4 Saddle points and dual variables interpretation

At points satisfying KKT conditions, the primal-dual pair can often be interpreted as a saddle point of the Lagrangian: the objective cannot be improved by adjusting the primal variables while respecting multipliers, and the multipliers cannot improve the dual objective given the primal. Dual variables can also be interpreted as marginal values or “prices” of constraints—measuring how much the objective would change for infinitesimal relaxation of constraints—though this interpretation is most reliable under smoothness and regularity.

4 Algorithmic approaches

4.1 Penalty and barrier methods

4.1.1 Exterior penalty methods

Penalty methods convert a constrained problem into an unconstrained (or less constrained) one by adding a term that grows when constraints are violated. In exterior penalty formulations, violations are penalized directly, and iteratively increasing penalty parameters encourages feasibility. The method can be attractive because it reduces constraint handling to objective modifications.

However, large penalty parameters can cause ill-conditioning, leading to slower convergence or numerical difficulties, especially for second-order methods.

4.1.2 Barrier (interior-point) methods

Barrier methods handle inequalities by adding a barrier term to the objective that becomes large near constraint boundaries. The iterate remains strictly within the feasible interior, often ensuring iterates satisfy \(g_j(x)<0\) for all \(j\). As the algorithm progresses, the barrier parameter decreases, gradually allowing the solution to approach the boundary where the optimum typically resides.

Interior-point methods are widely used for large-scale problems because their structure enables efficient linear algebra and strong convergence properties in convex settings.

4.2 Augmented Lagrangian methods

4.2.1 Update rules for multipliers

Augmented Lagrangian methods combine Lagrangian terms with penalty-like corrections, mitigating some drawbacks of pure penalty methods. They maintain an estimate of multipliers and update them using information from constraint violations. The penalty component helps stabilize primal updates while the multiplier updates refine the dual representation.

A key advantage is balancing feasibility and objective improvement without requiring extremely large penalty parameters.

4.2.2 Handling infeasibility

Infeasible iterates can occur, especially in algorithms that do not enforce strict feasibility at each step. Augmented Lagrangian schemes aim to drive constraint violations down while continuing to improve the objective. Handling infeasibility effectively depends on how updates respond to violation magnitude and on choices of step sizes, penalty parameters, and stopping thresholds.

4.3 Projected methods

4.3.1 Projected gradient descent

Projected methods take an unconstrained update step and then project back onto the feasible set (or onto a constraint-compatible subset). For instance, projected gradient descent performs:

1. Compute a descent direction using the gradient of the objective.
2. Take a step in that direction.
3. Project the result onto the feasible set according to an appropriate norm.

When the feasible set is simple (e.g., a box or a convex set with efficient projection), projected methods are straightforward and can converge reliably for convex problems.

4.3.2 Feasible vs. inexact projection

Exact projection may be expensive or impossible for complicated constraints. Inexact projection replaces the exact projection with an approximation, such as using iterative solvers or relaxed updates. Theoretical convergence depends on how the approximation error is controlled. In practice, inexact projection is often used to reduce computation while preserving acceptable progress toward feasibility.

4.4 Active-set and constraint handling

4.4.1 Identifying active constraints

Active-set methods maintain an estimate of which inequality constraints are active at the solution. Active constraints are treated as equalities in subproblems, while inactive constraints are ignored locally. The method iteratively updates the active set as the solution moves.

Correctly identifying active constraints can accelerate convergence, but misidentification can lead to extra iterations.

4.4.2 Subproblem strategies (e.g., quadratic models)

At each iteration, the algorithm solves a subproblem—often using a local model of the objective (such as a quadratic approximation) together with the current active constraints. The subproblem solution proposes a search direction and a step length that must also respect changes in the active set. These local models allow use of Newton-like ideas when curvature information is available.

4.5 Constraint reduction and variable elimination

Some formulations can be simplified by removing variables or substituting constraints. If equality constraints define a reduced parameterization, the problem can be expressed in fewer variables. Similarly, when constraints have special structure (such as linear dependencies), they can be eliminated to reduce dimension and improve conditioning.

Constraint reduction is particularly useful because it can convert a constrained problem into a smaller constrained or even unconstrained one, though it requires careful algebra and attention to feasibility preservation.

5 Convex constrained optimization

5.1 Convexity in objectives and constraints

In convex constrained optimization, the objective is convex, and the feasible set is described by convex constraints. For a minimization problem, convex objectives satisfy \[ f(\theta x+(1-\theta)y) \le \theta f(x)+(1-\theta)f(y), \] and convex inequality constraints define convex regions. Under these conditions, any local minimum is also a global minimum, and the optimization landscape avoids spurious local minima.

Convexity is not only a theoretical condition; it dictates which algorithms can provide strong performance guarantees.

5.2 KKT sufficiency in convex settings

For many convex problems under standard regularity assumptions, KKT conditions become not just necessary but also sufficient for optimality. This means that verifying KKT conditions at a candidate point can certify that it is globally optimal. The sufficiency result is central to convex optimization because it converts a numerical solution into a verifiable certificate.

5.3 Regularization and smoothing

Some convex objectives are difficult to optimize directly due to nonsmoothness or ill-conditioning. Regularization adds a stabilizing term, often increasing curvature or making the function more amenable to gradient-based methods. Smoothing replaces nonsmooth components with smooth approximations, trading exactness for computational tractability in a controlled way.

These techniques can improve convergence rates and robustness, especially when gradients are noisy or when constraints create steep regions.

5.4 Examples: quadratic programming and linear programming

Two canonical convex classes are:

• Linear programming (LP): linear objective with linear inequality/equality constraints.
• Quadratic programming (QP): quadratic objective with linear constraints, or equivalently constraints yielding a convex quadratic form.

LPs and QPs appear across engineering, operations research, and data-driven modeling. Their structure enables specialized interior-point methods, active-set strategies, and efficient decomposition approaches.

6 Numerical methods and practical considerations

6.1 Scaling and conditioning

Real-world problems often suffer from poor scaling: variables and constraints may differ drastically in magnitude. Scaling transforms the problem to improve numerical conditioning, which reduces error amplification and can substantially accelerate convergence. Poor conditioning can also cause line search or Newton steps to behave unpredictably.

Practical implementations frequently include automated scaling heuristics and careful choice of tolerances.

6.2 Stopping criteria

Stopping criteria determine when an iterative method terminates. Typical measures include:

• Objective improvement being sufficiently small.
• Constraint violation norms falling below thresholds.
• Stationarity residuals (e.g., gradient-related quantities or KKT residuals) being small.
• Step sizes becoming negligible relative to variable magnitudes.

Choosing tolerances involves balancing computational cost against solution quality, especially when constraint satisfaction is critical.

6.3 Handling constraints with noise or approximate gradients

Many applications provide noisy gradients or approximate derivatives. When constraint evaluations or gradient estimates contain errors, algorithms must be resilient: they may use safeguarded step sizes, robust merit functions, or stochastic approximations. Constraint handling becomes more challenging because feasibility checks can be affected by estimation noise.

Robust variants often rely on averaging, smoothing, or adaptive strategies to maintain progress while controlling violation.

6.4 Sensitivity to initialization and feasibility

Initialization can strongly affect convergence, particularly for non-convex problems or for methods that rely on local models. Some algorithms require feasible starting points, while others allow infeasible initialization with subsequent correction. Sensitivity to starting points manifests as different convergence paths or termination outcomes.

Even in convex settings, poor initialization can slow early progress, so feasible or near-feasible starts can be beneficial.

7 Regularization and constrained variants

7.1 Regularized constrained formulations

Regularization modifies an optimization problem by adding terms that improve numerical behavior or incorporate prior preferences. For constrained problems, regularization may penalize excessive curvature, encourage sparsity (in a convex manner), or stabilize ill-posedness. The constraints remain, but the modified objective can make the problem easier to solve and the solution more stable.

Regularization strength is typically tuned through validation, model selection criteria, or problem-specific heuristics.

7.2 Relaxations and reformulations

7.2.1 Slack variables and epigraph forms

Reformulation can simplify constraint structures. Slack variables convert inequality constraints into equality constraints by introducing additional nonnegative variables. Epigraph forms represent a function minimization problem as a constrained problem over the epigraph of the objective, which is useful when the objective is convex and can be represented through constraints.

These transformations often enable using standard solvers and exploiting convex structure.

7.2.2 Relaxing equalities/inequalities

Relaxation replaces strict constraints with approximate or softened versions. For equalities, one may allow small deviations within a tolerance, yielding an approximate feasibility requirement. Inequality relaxations may enlarge the feasible region or replace difficult constraints with easier surrogates.

Relaxation can improve solvability but may require post-processing to ensure the final solution remains acceptable for the original problem.

7.3 Robust optimization under constraints

Robust optimization addresses uncertainty in constraints or problem data by optimizing against worst-case or probabilistic deviations. The constrained formulation then involves additional structure—often leading to conservatism or increased computational complexity. The objective becomes to find a decision that remains feasible (or nearly feasible) under uncertainty scenarios.

Robust constrained optimization is used when model inputs or measurements are uncertain and constraint violations carry significant cost.

8 Discrete and structured constrained optimization

8.1 Combinatorial constraints overview

Discrete constrained optimization arises when decision variables are combinatorial (e.g., integers or selections). Constraints can encode logical conditions, capacity limits, or structural requirements like network connectivity. The feasible set is typically non-convex and combinatorial, so classical continuous optimality notions must be adapted or replaced.

Algorithms often rely on search, cutting planes, dynamic programming, or heuristics coupled with bounds.

8.2 Mixed-integer constrained problems (MIP-style)

Mixed-integer programming combines integer variables with continuous ones and uses constraints to describe feasible combinations. A MIP typically includes linear constraints and objective functions, though more general forms exist. Branch-and-bound and branch-and-cut frameworks explore a tree of relaxations, using linear programming bounds to prune suboptimal branches.

In many practical settings, MIP solvers also include constraint-presolving, symmetry handling, and cutting plane generation to improve performance.

8.3 Constraint programming concepts (high-level)

Constraint programming (CP) focuses on representing constraints as relations over variables and using constraint propagation to prune domains. Rather than solving a numeric program directly, CP explores assignments consistent with constraints while repeatedly applying propagation rules to narrow possible values.

CP is often well-suited for scheduling, combinatorial design, and problems with complex logical constraints.

8.4 Scheduling and resource allocation with constraints

Scheduling and resource allocation frequently involve constrained decisions such as ordering tasks, allocating limited machines, meeting deadlines, and respecting precedence constraints. Models may be expressed using MIP, CP, or hybrid methods. Constraints can represent both feasibility (e.g., resource capacities) and preferences (e.g., minimizing delays or maximizing throughput).

The structure of these problems often enables decomposition: dividing time periods, resources, or task sets and then coordinating solutions.

9 Applications and use cases (survey)

9.1 Engineering design constraints

Engineers use constrained optimization to ensure designs meet physical and safety limitations while optimizing weight, efficiency, or performance. Constraints can include stress limits, geometric bounds, stability requirements, and manufacturability considerations. Many engineering tasks involve nonlinear objectives and constraints, motivating algorithms that balance feasibility and objective improvement.

9.2 Machine learning with constraints

Constrained optimization appears in machine learning when models must satisfy conditions beyond fitting data. Examples include enforcing monotonicity, fairness-related criteria in an abstract sense, resource limits during training, or keeping parameters within bounds for stability. These tasks can be formulated as constrained risk minimization or regularized constrained learning problems.

Algorithms range from projected methods and Lagrangian-based approaches to interior-point or augmented Lagrangian strategies depending on differentiability and structure.

9.3 Control systems and constrained dynamics

Control problems often require actions to remain within safe limits and system trajectories to respect constraints. Such constraints can include actuator saturation, state bounds, and safety envelopes. Formulations may involve optimal control with constraints over time, leading to optimization problems solved repeatedly in a receding-horizon manner.

The resulting constrained optimization must be computationally efficient to run in real-time or near real-time.

9.4 Economics-inspired constrained models (general, non-controversial)

Economics-inspired modeling frequently uses constrained optimization to represent trade-offs under limitations, such as budget constraints, production capacity, or demand-response relationships. While the modeling context varies, the mathematical structure typically mirrors constrained resource allocation: an objective represents an aggregate criterion, and constraints encode feasibility limits.

General constrained optimization techniques—penalties, multipliers, projections, and convex programming—often provide a computational toolkit for these models.