Hubbry Logo
Constrained optimizationConstrained optimizationMain
Open search
Constrained optimization
Community hub
Constrained optimization
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Constrained optimization
Constrained optimization
Constrained optimization
View on Wikipedia
from Wikipedia

In mathematical optimization, constrained optimization (in some contexts called constraint optimization) is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables. The objective function is either a cost function or energy function, which is to be minimized, or a reward function or utility function, which is to be maximized. Constraints can be either hard constraints, which set conditions for the variables that are required to be satisfied, or soft constraints, which have some variable values that are penalized in the objective function if, and based on the extent that, the conditions on the variables are not satisfied.

Relation to constraint-satisfaction problems

[edit]

The constrained-optimization problem (COP) is a significant generalization of the classic constraint-satisfaction problem (CSP) model.[1] COP is a CSP that includes an objective function to be optimized. Many algorithms are used to handle the optimization part.

General form

[edit]

A general constrained minimization problem may be written as follows:[2]

where and are constraints that are required to be satisfied (these are called hard constraints), and is the objective function that needs to be optimized subject to the constraints.

In some problems, often called constraint optimization problems, the objective function is actually the sum of cost functions, each of which penalizes the extent (if any) to which a soft constraint (a constraint which is preferred but not required to be satisfied) is violated.

Solution methods

[edit]

Many constrained optimization algorithms can be adapted to the unconstrained case, often via the use of a penalty method. However, search steps taken by the unconstrained method may be unacceptable for the constrained problem, leading to a lack of convergence. This is referred to as the Maratos effect.[3]

Equality constraints

[edit]

Substitution method

[edit]

For very simple problems, say a function of two variables subject to a single equality constraint, it is most practical to apply the method of substitution.[4] The idea is to substitute the constraint into the objective function to create a composite function that incorporates the effect of the constraint. For example, assume the objective is to maximize subject to . The constraint implies , which can be substituted into the objective function to create . The first-order necessary condition gives , which can be solved for and, consequently, .

Lagrange multiplier

[edit]
Main article: Lagrange multipliers

If the constrained problem has only equality constraints, the method of Lagrange multipliers can be used to convert it into an unconstrained problem whose number of variables is the original number of variables plus the original number of equality constraints. Alternatively, if the constraints are all equality constraints and are all linear, they can be solved for some of the variables in terms of the others, and the former can be substituted out of the objective function, leaving an unconstrained problem in a smaller number of variables.

Inequality constraints

[edit]

With inequality constraints, the problem can be characterized in terms of the geometric optimality conditions, Fritz John conditions and Karush–Kuhn–Tucker conditions, under which simple problems may be solvable.

Linear programming

[edit]

If the objective function and all of the hard constraints are linear and some hard constraints are inequalities, then the problem is a linear programming problem. This can be solved by the simplex method, which usually works in polynomial time in the problem size but is not guaranteed to, or by interior point methods which are guaranteed to work in polynomial time.

Nonlinear programming

[edit]

If the objective function or some of the constraints are nonlinear, and some constraints are inequalities, then the problem is a nonlinear programming problem.

Quadratic programming

[edit]

If all the hard constraints are linear and some are inequalities, but the objective function is quadratic, the problem is a quadratic programming problem. It is one type of nonlinear programming. It can still be solved in polynomial time by the ellipsoid method if the objective function is convex; otherwise the problem may be NP hard.

KKT conditions

[edit]

Allowing inequality constraints, the KKT approach to nonlinear programming generalizes the method of Lagrange multipliers. It can be applied under differentiability and convexity.

Branch and bound

[edit]

Constraint optimization can be solved by branch-and-bound algorithms. These are backtracking algorithms storing the cost of the best solution found during execution and using it to avoid part of the search. More precisely, whenever the algorithm encounters a partial solution that cannot be extended to form a solution of better cost than the stored best cost, the algorithm backtracks, instead of trying to extend this solution.

Assuming that cost is to be minimized, the efficiency of these algorithms depends on how the cost that can be obtained from extending a partial solution is evaluated. Indeed, if the algorithm can backtrack from a partial solution, part of the search is skipped. The lower the estimated cost, the better the algorithm, as a lower estimated cost is more likely to be lower than the best cost of solution found so far.

On the other hand, this estimated cost cannot be lower than the effective cost that can be obtained by extending the solution, as otherwise the algorithm could backtrack while a solution better than the best found so far exists. As a result, the algorithm requires an upper bound on the cost that can be obtained from extending a partial solution, and this upper bound should be as small as possible.

A variation of this approach called Hansen's method uses interval methods.[5] It inherently implements rectangular constraints.

First-choice bounding functions

[edit]

One way for evaluating this upper bound for a partial solution is to consider each soft constraint separately. For each soft constraint, the maximal possible value for any assignment to the unassigned variables is assumed. The sum of these values is an upper bound because the soft constraints cannot assume a higher value. It is exact because the maximal values of soft constraints may derive from different evaluations: a soft constraint may be maximal for while another constraint is maximal for .

[edit]

This method[6] runs a branch-and-bound algorithm on problems, where is the number of variables. Each such problem is the subproblem obtained by dropping a sequence of variables from the original problem, along with the constraints containing them. After the problem on variables is solved, its optimal cost can be used as an upper bound while solving the other problems,

In particular, the cost estimate of a solution having as unassigned variables is added to the cost that derives from the evaluated variables. Virtually, this corresponds on ignoring the evaluated variables and solving the problem on the unassigned ones, except that the latter problem has already been solved. More precisely, the cost of soft constraints containing both assigned and unassigned variables is estimated as above (or using an arbitrary other method); the cost of soft constraints containing only unassigned variables is instead estimated using the optimal solution of the corresponding problem, which is already known at this point.

There is similarity between the Russian Doll Search method and dynamic programming. Like dynamic programming, Russian Doll Search solves sub-problems in order to solve the whole problem. But, whereas Dynamic Programming directly combines the results obtained on sub-problems to get the result of the whole problem, Russian Doll Search only uses them as bounds during its search.

Bucket elimination

[edit]

The bucket elimination algorithm can be adapted for constraint optimization. A given variable can be indeed removed from the problem by replacing all soft constraints containing it with a new soft constraint. The cost of this new constraint is computed assuming a maximal value for every value of the removed variable. Formally, if is the variable to be removed, are the soft constraints containing it, and are their variables except , the new soft constraint is defined by:

Bucket elimination works with an (arbitrary) ordering of the variables. Every variable is associated a bucket of constraints; the bucket of a variable contains all constraints having the variable has the highest in the order. Bucket elimination proceed from the last variable to the first. For each variable, all constraints of the bucket are replaced as above to remove the variable. The resulting constraint is then placed in the appropriate bucket.

See also

[edit]

References

[edit]

Further reading

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Constrained optimization

View on Grokipedia
from Grokipedia
Constrained optimization is a fundamental area of that involves finding the maximum or minimum value of an objective function subject to a set of constraints defining the for the decision variables. These constraints typically take the form of equality conditions, such as hi(x)=0h_i(\mathbf{x}) = 0, or inequality conditions, such as gi(x)≤0g_i(\mathbf{x}) \leq 0, where x\mathbf{x} represents the vector of variables, limiting the domain over which the optimization occurs. Unlike unconstrained optimization, where the objective function is optimized over all possible values without restrictions, constrained optimization requires accounting for these boundaries to ensure solutions remain feasible, often leading to optima at the edges of the feasible set. The general formulation of a constrained optimization problem can be stated as minimizing (or maximizing) f(x)f(\mathbf{x}) subject to gj(x)≤0g_j(\mathbf{x}) \leq 0 for j=1,…,mj = 1, \dots, m and hk(x)=0h_k(\mathbf{x}) = 0 for k=1,…,pk = 1, \dots, p, assuming the functions are sufficiently differentiable, such as continuously differentiable (C1C^1). For problems with equality constraints, the method of Lagrange multipliers provides a key theoretical and computational tool, introduced by in his 1788 work Mécanique Analytique to solve problems in the and mechanics. This approach constructs the Lagrangian L(x,λ)=f(x)+∑λkhk(x)\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum \lambda_k h_k(\mathbf{x}), setting its partial derivatives to zero to yield the system ∇f(x∗)=−∑λk∇hk(x∗)\nabla f(\mathbf{x}^*) = -\sum \lambda_k \nabla h_k(\mathbf{x}^*) at a local optimum x∗\mathbf{x}^*. For inequality constraints, the Karush-Kuhn-Tucker (KKT) conditions generalize this framework, incorporating complementary slackness (λjgj(x∗)=0\lambda_j g_j(\mathbf{x}^*) = 0, λj≥0\lambda_j \geq 0) alongside stationarity and primal/dual feasibility; these necessary conditions under suitable constraint qualifications were first fully articulated in a 1951 publication by and , building on earlier work by William Karush in 1939. Constrained optimization problems arise across diverse fields, including for under budget limits, for structural design with material constraints, and for scheduling with capacity restrictions. In services, it aids in optimizing intervention packages given competing demands, such as in programs.30082-7/fulltext) Numerical methods, including interior-point algorithms and , have evolved to solve large-scale instances efficiently, often leveraging convexity assumptions for global optimality guarantees.

Fundamentals

Definition and Scope

Constrained optimization refers to the mathematical of finding the minimum or maximum of an objective function subject to equality or inequality constraints on the decision variables, which define a for potential solutions. This approach is fundamental in mathematical programming, where the goal is to achieve an optimal value within the boundaries imposed by the constraints, rather than searching unrestricted space. In contrast to unconstrained optimization, where the objective can be evaluated over the entire domain without restrictions, constrained optimization limits the search to the , which may be bounded or unbounded and can introduce local optima due to the geometry of the constraints. This distinction highlights how constraints model real-world limitations, such as resource availability or regulatory requirements, potentially altering the nature of the solution landscape. The scope of constrained optimization extends to continuous problems with real-valued variables, discrete problems involving integer decisions, and mixed-integer formulations that combine both types. It finds widespread applications in for modeling under , in for subject to physical limits, and in for solving and scheduling challenges. A basic illustrative example involves a manufacturer seeking to minimize the total production cost of two while adhering to fixed limits on raw materials, where the quantities of each good must collectively not exceed the available supply. Understanding constrained optimization assumes foundational knowledge of calculus for handling function behaviors and linear algebra for representing constraints and variables efficiently.

Historical Development

The roots of constrained optimization trace back to the 17th and 18th centuries, when mathematicians began addressing problems involving extrema under constraints through the emerging field of . Leonhard Euler laid foundational work in 1744 with his publication Methodus inveniendi lineas curvas maximi minimive proprietate gaudentes, where he derived necessary conditions for optimizing functionals, introducing what became known as the Euler-Lagrange equation for variational problems with equality constraints. This approach was pivotal in handling tasks, such as finding curves of minimal length or maximal area, and influenced subsequent developments in and physics. Joseph-Louis Lagrange built upon Euler's ideas in the late 18th century, formalizing the multiplier method in 1762 by simplifying optimality conditions for constrained variational problems and fully articulating it in his 1788 treatise Mécanique Analytique. Lagrange's technique introduced auxiliary variables—now called Lagrange multipliers—to incorporate equality constraints directly into the objective function, enabling the solution of static equilibrium problems in mechanics without explicit substitution. This method marked a significant advancement for equality-constrained optimization, providing a systematic analytical framework that persisted into the 19th century amid growing applications in engineering and economics. In the early , attention shifted toward inequality constraints, with contributing key insights in 1935 through his theorem on the properties of the inverse of the bordered Hessian in constrained optimization problems. 's work extended variational methods to handle inequalities more robustly, laying groundwork for and . This was followed by William Karush's 1939 master's thesis at the , which independently derived necessary optimality conditions for nonlinear problems with both equality and inequality constraints, though it remained unpublished at the time. The mid-20th century saw formalization and broader adoption, as and published their extension of Lagrange multipliers to inequality constraints in 1951, introducing the Kuhn-Tucker conditions as necessary for local optima in . Their work, building on Karush's earlier formulation, provided a cornerstone for modern constrained optimization theory. Post-World War II, George B. Dantzig's 1947 invention of the simplex method for revolutionized computational approaches to constrained problems, offering an efficient iterative algorithm that influenced the shift from analytical to numerical methods across optimization. The modern era integrated constrained optimization with computing advancements, exemplified by Narendra Karmarkar's 1984 development of an , a polynomial-time for that traversed the interior of the rather than boundaries, dramatically improving scalability for large-scale problems. This innovation spurred widespread adoption of interior-point techniques in the and beyond, bridging theoretical guarantees with practical efficiency in fields like .

Formulations

General Problem Statement

Constrained optimization problems involve finding values of decision variables that minimize (or maximize) an objective function while satisfying a set of constraints defining the . The standard mathematical formulation is to minimize a function f:Rn→Rf: \mathbb{R}^n \to \mathbb{R} subject to equality constraints gi(x)=0g_i(x) = 0 for i=1,…,mi = 1, \dots, m and inequality constraints hj(x)≤0h_j(x) \leq 0 for j=1,…,pj = 1, \dots, p, where x∈Rnx \in \mathbb{R}^n represents the vector of decision variables. This general form encompasses both equality-constrained and inequality-constrained problems as special cases, with the latter arising when all equalities are absent and vice versa. The feasible set Ω\Omega is defined as Ω={x∈Rn∣gi(x)=0, i=1,…,m; hj(x)≤0, j=1,…,p}\Omega = \{ x \in \mathbb{R}^n \mid g_i(x) = 0, \, i=1,\dots,m; \, h_j(x) \leq 0, \, j=1,\dots,p \}, which must be nonempty for the problem to be well-posed. In many practical settings, assumptions such as convexity of ff, gig_i, and −hj-h_j ensure that local optima are global, while regularity conditions like the linear independence constraint qualification (LICQ)—requiring the gradients of active constraints to be linearly independent—facilitate the application of optimality conditions. The objective function ff can be linear, quadratic, or nonlinear, and the variables may be continuous or discrete, though classical methods typically assume continuous domains. Maximization problems are equivalently formulated by minimizing −f(x)-f(x), preserving the structure of the constraints. Multi-objective extensions replace the scalar ff with a vector of objectives, seeking the —a set of nondominated solutions where no objective can improve without degrading another—subject to the same constraints. Stochastic variants arise when ff, gig_i, or hjh_j involve expectations over random variables, as in risk-averse or data-driven optimization. For solution methods to apply, functions are often assumed differentiable, with twice-differentiability aiding second-order analyses.

Equality-Constrained Form

In equality-constrained optimization, the problem is formulated as minimizing an objective function f:Rn→Rf: \mathbb{R}^n \to \mathbb{R} subject to mm equality constraints gi(x)=0g_i(x) = 0 for i=1,…,mi = 1, \dots, m, where each gi:Rn→Rg_i: \mathbb{R}^n \to \mathbb{R} is typically smooth, and m<nm < n to ensure the system is underdetermined with a nontrivial feasible set. This setup contrasts with unconstrained problems by restricting the search space to the solution set of the constraints, often leading to a lower-dimensional feasible region. Geometrically, the feasible set {x∈Rn∣g(x)=0}\{ x \in \mathbb{R}^n \mid g(x) = 0 \}, where g(x)=(g1(x),…,gm(x))Tg(x) = (g_1(x), \dots, g_m(x))^T, forms a smooth manifold of dimension n−mn - m under suitable regularity conditions, embedded in Rn\mathbb{R}^n. Optimal points occur at critical points of ff restricted to this manifold, where the gradient of ff is orthogonal to the tangent space of the constraint surface, ensuring no descent direction lies within the feasible set. To guarantee the existence of optimal solutions and the validity of necessary conditions, constraint qualifications are imposed on the equality constraints. The linear independence constraint qualification (LICQ) requires that the gradients ∇gi(x∗)\nabla g_i(x^*) for i=1,…,mi = 1, \dots, m are linearly independent at a point x∗x^* in the feasible set. For equality-only problems, the Mangasarian-Fromovitz constraint qualification (MFCQ) simplifies to LICQ, as it demands linear independence of the equality gradient vectors without additional inequality considerations. Duality in equality-constrained optimization introduces the Lagrangian function L(x,λ)=f(x)+∑i=1mλigi(x)\mathcal{L}(x, \lambda) = f(x) + \sum_{i=1}^m \lambda_i g_i(x), where λ∈Rm\lambda \in \mathbb{R}^m are Lagrange multipliers. This formulation encodes the constraints into an unconstrained saddle-point problem, with the dual function providing a lower bound on the primal objective under strong duality conditions such as convexity and a constraint qualification like the linear independence constraint qualification (LICQ). A simple example is minimizing f(x,y)=x2+y2f(x, y) = x^2 + y^2 subject to x+y=1x + y = 1. The feasible set is the line y=1−xy = 1 - x, and substituting yields f(x,1−x)=2x2−2x+1f(x, 1 - x) = 2x^2 - 2x + 1, with minimum at x=1/2x = 1/2, y=1/2y = 1/2, and f=1/2f = 1/2. Equality-constrained forms provide foundational building blocks for extending to inequality constraints, where active inequalities mimic equalities at optima.

Inequality-Constrained Form

In inequality-constrained optimization, the problem is typically formulated as finding the minimum of an objective function over a feasible region defined by inequality constraints: min⁡x∈Rn f(x)subject tohj(x)≤0,j=1,…,p,\min_{x \in \mathbb{R}^n} \, f(x) \quad \text{subject to} \quad h_j(x) \leq 0, \quad j=1,\dots,p, where f:Rn→Rf: \mathbb{R}^n \to \mathbb{R} is the objective function (often assumed differentiable), and each hj:Rn→Rh_j: \mathbb{R}^n \to \mathbb{R} is a constraint function. This setup contrasts with unconstrained optimization by restricting the search space to the intersection of sublevel sets {x∣hj(x)≤0}\{x \mid h_j(x) \leq 0\}. At a local optimum x∗x^*, constraints are classified as active if hj(x∗)=0h_j(x^*) = 0 or inactive if hj(x∗)<0h_j(x^*) < 0; active constraints bind the solution, effectively reducing the dimensionality of the problem, while inactive ones do not influence the local behavior. The feasible region X={x∈Rn∣hj(x)≤0, j=1,…,p}\mathcal{X} = \{x \in \mathbb{R}^n \mid h_j(x) \leq 0, \, j=1,\dots,p\} is a closed convex set if the hjh_j are convex; for linear inequalities hj(x)=aj⊤x−bj≤0h_j(x) = a_j^\top x - b_j \leq 0, X\mathcal{X} forms a convex polyhedron bounded by hyperplanes. A key conceptual aspect involves complementarity, where at the optimum, each constraint is either inactive (hj(x∗)<0h_j(x^*) < 0) with zero associated multiplier, or active with a non-negative multiplier, satisfying hj(x∗)⋅μj=0h_j(x^*) \cdot \mu_j = 0 for multiplier μj≥0\mu_j \geq 0; this ensures that inactive constraints do not penalize the objective unduly. For convex problems (where ff and hjh_j are convex), Slater's condition guarantees strong duality: if there exists a strictly feasible point x~\tilde{x} such that hj(x~)<0h_j(\tilde{x}) < 0 for all jj, then the primal and dual optimal values coincide, and the dual problem attains its optimum. This condition ensures that local minima are global and facilitates efficient solvability, as the duality gap vanishes under mild assumptions. Equality constraints can be incorporated by converting each gi(x)=0g_i(x) = 0 into a pair of inequalities gi(x)≤0g_i(x) \leq 0 and −gi(x)≤0-g_i(x) \leq 0, transforming the problem into a purely inequality-constrained form; however, this requires constraint qualifications (such as linear independence of gradients) to preserve optimality conditions and avoid ill-posedness. A representative example is resource allocation in linear programming, formulated as min⁡ c⊤x\min \, c^\top x subject to Ax≤bA x \leq b and x≥0x \geq 0, where x∈Rnx \in \mathbb{R}^n represents allocations, A∈Rm×nA \in \mathbb{R}^{m \times n} captures resource limits, and b∈Rmb \in \mathbb{R}^m are bounds; here, nonnegativity constraints xk≥0x_k \geq 0 (or −xk≤0-x_k \leq 0) model physical limits, and the feasible region is a polyhedron. When the objective or constraints are nonconvex, the feasible region X\mathcal{X} may be nonconvex, leading to multiple local optima where active sets vary across basins of attraction; in such cases, distinguishing local from global optima is challenging, often requiring global search techniques, as local methods may converge to suboptimal points.

Solution Methods for Equality Constraints

Direct Substitution

The direct substitution method, also known as the elimination method, addresses equality-constrained optimization problems by solving the constraint equations explicitly for a subset of the decision variables and substituting these expressions into the objective function, thereby transforming the problem into an unconstrained minimization over the remaining free variables. This approach is particularly applicable when the number of equality constraints mm is small relative to the number of variables nn, assuming the constraints are independent and solvable for mm dependent variables in terms of n−mn-m free variables z∈Rn−mz \in \mathbb{R}^{n-m}. The resulting reduced objective function is then fred(z)=f(x(z))f_{\text{red}}(z) = f(x(z)), where x(z)x(z) denotes the full vector of variables after substitution, and optimization proceeds using standard unconstrained techniques such as gradient descent or Newton's method. The method follows a structured process: first, select and solve the mm equality constraints h(x)=0h(x) = 0 for the dependent variables, yielding explicit functions xd=g(z)x_d = g(z) under suitable regularity conditions; second, insert this into the objective to form fred(z)f_{\text{red}}(z); third, compute the minimum of fred(z)f_{\text{red}}(z) by setting its gradient to zero or applying iterative algorithms, ensuring the solution satisfies the original constraints. For linear constraints, this substitution is exact and preserves the problem's structure without approximation. This technique offers simplicity and computational efficiency in low-dimensional settings with few constraints, as it avoids introducing auxiliary variables and directly yields an unconstrained problem that can leverage well-established solvers. It is exact for linear equality constraints, where the substitution maintains convexity if the original objective is convex. However, explicit solvability of nonlinear constraints is often infeasible, limiting applicability to problems where closed-form expressions exist. Additionally, numerical instability arises for nonlinear cases if the implicit functions are poorly conditioned, potentially amplifying errors in constraint satisfaction during optimization. The validity of local substitution relies on the implicit function theorem, which guarantees the existence and differentiability of the implicit functions g(z)g(z) provided the Jacobian matrix of the constraints with respect to the dependent variables, ∂h∂xd\frac{\partial h}{\partial x_d}, is nonsingular (i.e., full rank mm) at the solution point. Violation or near-violation of this nonsingularity assumption—such as when the Jacobian determinant approaches zero—leads to high sensitivity: minor perturbations in the constraints or objective can cause substantial deviations in the substituted variables, resulting in ill-conditioned reduced problems and unreliable optima. This error amplification is particularly pronounced in numerical implementations, where floating-point precision exacerbates the instability, often necessitating regularization or alternative methods like Lagrange multipliers for robustness. A representative example illustrates the method's application. Consider minimizing f(x,y)=x2+y2f(x, y) = x^2 + y^2 subject to the linear equality constraint h(x,y)=x+y−1=0h(x, y) = x + y - 1 = 0. Solve the constraint for y=1−xy = 1 - x, yielding the reduced objective fred(x)=x2+(1−x)2=2x2−2x+1f_{\text{red}}(x) = x^2 + (1 - x)^2 = 2x^2 - 2x + 1. Differentiating gives fred′(x)=4x−2=0f_{\text{red}}'(x) = 4x - 2 = 0, so x=0.5x = 0.5 and y=0.5y = 0.5, with minimum value f(0.5,0.5)=0.5f(0.5, 0.5) = 0.5. Here, the linear constraint allows exact substitution without numerical concerns.

Lagrange Multiplier Method

The Lagrange multiplier method provides a systematic approach to finding local optima of a function subject to equality constraints by transforming the constrained problem into an unconstrained one involving auxiliary variables known as Lagrange multipliers. Developed originally by in his 1788 work Mécanique Analytique to address problems in classical mechanics, the method has become a cornerstone of optimization theory for equality-constrained problems. It applies to nonlinear optimization problems where the objective function and constraints are differentiable, enabling the identification of stationary points that satisfy necessary conditions for optimality. Consider the equality-constrained optimization problem of minimizing a smooth objective function f:Rn→Rf: \mathbb{R}^n \to \mathbb{R} subject to mm equality constraints gi(x)=0g_i(x) = 0 for i=1,…,mi = 1, \dots, m, with m<nm < n. The Lagrangian function is formed as L(x,λ)=f(x)+∑i=1mλigi(x),\mathcal{L}(x, \lambda) = f(x) + \sum_{i=1}^m \lambda_i g_i(x), where λ=(λ1,…,λm)∈Rm\lambda = (\lambda_1, \dots, \lambda_m) \in \mathbb{R}^m are the Lagrange multipliers. The method seeks stationary points of the Lagrangian, satisfying the stationarity conditions ∇xL(x,λ)=0\nabla_x \mathcal{L}(x, \lambda) = 0 and ∇λL(x,λ)=0\nabla_\lambda \mathcal{L}(x, \lambda) = 0, which translate to the coupled nonlinear system ∇f(x)+∑i=1mλi∇gi(x)=0,gi(x)=0∀i=1,…,m.\nabla f(x) + \sum_{i=1}^m \lambda_i \nabla g_i(x) = 0, \quad g_i(x) = 0 \quad \forall i = 1, \dots, m. This system is solved simultaneously for xx and λ\lambda, avoiding explicit elimination of variables as in direct substitution methods. The derivation of these conditions can be obtained using the implicit function theorem applied to the constraint manifold. Near a regular point where the constraint gradients {∇gi(x)}i=1m\{\nabla g_i(x)\}_{i=1}^m are linearly independent, the feasible set is locally a smooth (n−m)(n-m)-dimensional manifold. Parameterizing this manifold implicitly and considering a Taylor expansion of ff along feasible directions yields that at a local optimum x∗x^*, the gradient ∇f(x∗)\nabla f(x^*) must lie in the span of the constraint normals {∇gi(x∗)}\{\nabla g_i(x^*)\}, leading to ∇f(x∗)=−∑i=1mλi∇gi(x∗)\nabla f(x^*) = -\sum_{i=1}^m \lambda_i \nabla g_i(x^*) for some multipliers λ\lambda. The signs in the Lagrangian convention account for minimization. Geometrically, the method interprets the optimum as the point where the level sets of the objective function are tangent to the constraint surface, implying that ∇f(x∗)\nabla f(x^*) is a linear combination of the ∇gi(x∗)\nabla g_i(x^*). The multipliers λi\lambda_i quantify the sensitivity of the optimal value to perturbations in the ii-th constraint; specifically, λi∗\lambda_i^* represents the rate of change of the optimal objective value with respect to a relaxation of gi(x)=0g_i(x) = 0 to gi(x)=ϵg_i(x) = \epsilon, often termed shadow prices in economic applications. Under suitable regularity, the envelope theorem confirms df∗/dϵ=λi∗df^*/d\epsilon = \lambda_i^* at ϵ=0\epsilon = 0. A key assumption for the existence and uniqueness of multipliers is the linear independence constraint qualification (LICQ), which requires that the gradients {∇gi(x∗)}i=1m\{\nabla g_i(x^*)\}_{i=1}^m are linearly independent at the candidate optimum x∗x^*. This ensures the constraint Jacobian has full row rank, guaranteeing a unique λ∗\lambda^* and that x∗x^* is a regular point on the feasible set. Without LICQ, multiple multipliers may exist or the conditions may fail to hold. To classify the stationary point as a local minimum, maximum, or saddle, second-order sufficient conditions involve the bordered Hessian of the Lagrangian, defined as the (n+m)×(n+m)(n+m) \times (n+m) matrix H~=[0∇g1T⋯∇gmT∇g1⋮∇xx2L∇gm],\tilde{H} = \begin{bmatrix} 0 & \nabla g_1^T & \cdots & \nabla g_m^T \\ \nabla g_1 & & & \\ \vdots & & \nabla_{xx}^2 \mathcal{L} & \\ \nabla g_m & & & \end{bmatrix},
Add your contribution
Related Hubs
User Avatar
No comments yet.