Active constraint set 2026-10-31
For inequalities , the active constraints at a feasible point are those holding with equality. Inactive constraints remain strictly satisfied in a sufficiently small neighborhood and do not restrict first-order feasible velocities there. The active gradients determine the linearized tangent cone and appear in the linear independence constraint qualification. At a KKT point, inactive constraints have zero Lagrange multipliers by complementary slackness.
Active-set clipping in cost-weighted baseline-tolerance allocation enforces the reference caps that an interior solution of cost-weighted allocation of baseline-response tolerances may violate. Keep the parent's stipulated logarithmic effort modelHere is a physical bias contribution in the common units of . If , no tightening is needed. Otherwise the budget binds, and the Karush-Kuhn-Tucker conditions giveThe positive Lagrange multiplier prices scarce bias budget. For a set of capped components and remaining free set , stationarity givesprovided the denominator is positive and the resulting choices agree with the proposed capped/free status. The monotonicity of the multiplier equation for capped tolerances permits a scalar search; strict convexity of the objective gives a unique allocation.
For an original cap-activating version of the parent's apparatus example, let , , , , and . Set reference bias contributions and . The unconstrained shares and violate the first cap. Capping it leaves for the second component, soMerely clipping the first share and leaving the second at wastes of permitted bias and unnecessarily increases the chosen effort. Reallocation lowers that effort by units.
The physical motivation remains leakage from residual offset and drift in a pulsed-radiometer baseline, documented in NIST's calibration apparatus.[ref]
Calibration Service for Low-level Pulsed-Laser Radiometers at 1.06 µm: Pulse Energy and Peak Power by Rodney W. Leonhardt. §3.5, printed p. 8; §7.2, Leakage Effect
The logarithmic cost and the numerical caps here are illustrative assumptions, not reported apparatus constants. Albert W. Tucker Created 2026-10-14 Updated 2026-11-05
Albert W. Tucker worked in topology, game theory and nonlinear optimization. With Harold W. Kuhn he helped formulate the conditions now called the Karush-Kuhn-Tucker conditions, which extend the use of Lagrange multipliers to inequality constraints. He also supplied the familiar name and narrative for the prisoner's dilemma.[ref]
https://mathshistory.st-andrews.ac.uk/Biographies/Tucker_Albert/. University of St Andrews biography, nonlinear programming and the prisoner's-dilemma interpretation
That example makes a mathematical distinction memorable: individually advantageous choices can lead to an outcome both players prefer less than a coordinated alternative. The payoff inequalities, rather than the story alone, define the strategic conflict.Portrait of Albert W. Tucker
. Unknown photographer; First International Topology Conference, Moscow, 1935; ETH Library source; extraction by Jochen Burghardt. Public domain asserted by Commons in origin and life-plus-70 jurisdictions. Source usage terms, via Wikimedia Commons. Source. Augmented Lagrangian method 2026-10-31
For smooth constraints , minimizeapproximately in , then update the nonnegative Lagrange multipliers by the displayed projected rule. Equality constraints instead contribute and use the unprojected update . The construction combines Lagrangian duality with a quadratic penalty method.
For an inequality, the exact identity is . Its unshifted negative part satisfies . On a violated constraint, accurate new multipliers therefore give violation of the order of times the multiplier error. This can achieve high feasibility accuracy without a vanishingly small , reducing condition number difficulties. The negative-part qualification is essential if an iterate approaches a binding constraint from the feasible side.
Bounded barrier multipliers under Slater's condition Created 2026-10-25 Updated 2026-10-31
Let be concave and continuously differentiable, and let a strict feasible point satisfy . Suppose , , , and the logarithmic barrier residuals tend to zero, where . By concavity,The right-hand side is bounded when is continuous near . Thus the nonnegative Lagrange multiplier estimates are bounded. A convergent subsequence gives ; passing to the limit in stationarity and proves the Karush-Kuhn-Tucker conditions at . An inactive optimization constraint has and hence even without selecting a subsequence. With a convex objective function, these conditions certify a global minimum. This result is conditional on the stated residual and primal convergence assumptions; it does not assert that every barrier subproblem has a minimizer.
Cobb–Douglas production function 2026-10-13
For positive constants , a Cobb–Douglas production function describes output in terms of capital and labour . It is homogeneous of degree . Under with , its unique nonnegative-input optimum is and , obtained by maximizing the strictly concave logarithm along the budget line. The optimized output has derivative , equal to its budget Lagrange multiplier. When , the unconstrained Lagrangian supremum over the positive orthant is infinite for every finite multiplier, despite the finite constrained optimum; the global dual representation must not be presumed in this case.
Conjugate-power constrained product maximum 2026-10-31
For conjugate exponents , the constraint set is compact, so the continuous product has a maximum. Boundary endpoints have product zero, while is feasible with product one. An interior maximum therefore satisfies the Lagrange multiplier equations and . Multiplying by and respectively gives , since the multiplier is nonzero. Substitution in the constraint makes both powers equal one. Thus the maximum is one, attained uniquely at . The boundary check and compactness are what turn the necessary multiplier equations into a global conclusion.
Constrained Kaplan–Meier estimator 2026-10-14
The Kaplan–Meier estimator constrained to have survivor function value at maximizes the right-censoring log-likelihood subject to the displayed constraint. Here is the discrete hazard, the event count and the risk set size. In an interior event-time solution, a Lagrange multiplier gives before the constrained time, with afterwards. The multiplier is chosen to satisfy the product constraint. It is essential to allow a zero-event jump at the constrained time or another relevant cell boundary: a constraint can require mass outside observed event times. A general implementation instead maximizes the concave probability-mass log-likelihood with total mass one and mass above equal to , allowing all relevant cells and a terminal tail. This also handles unobserved tails and boundary solutions without imposing unjustified event-only support.
Constrained optimization Created 2026-09-24 Updated 2026-11-05
Constrained optimization minimizes or maximizes an objective function over a feasible set defined by equality or inequality constraints. In subject to and , a feasible optimum must balance improvement of the objective against the permitted directions of motion.
For example, minimizing subject to gives , since . The unrestricted minimizer is infeasible. Lagrange multipliers and the Karush-Kuhn-Tucker conditions generalize this balancing argument; necessity requires appropriate hypotheses, and sufficiency needs extra structure such as convexity.[ref]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. Chapters 4–5, optimization problems and optimality conditions
Constraint qualification Created 2026-10-14 Updated 2026-10-20
A constraint qualification is a regularity hypothesis on optimization constraints that guarantees a specified optimality or duality conclusion. For the necessity of Karush-Kuhn-Tucker conditions, an appropriate constraint qualification ensures that a local minimum admits suitable Lagrange multipliers; linear independence of the gradients of equality optimization constraints and active constraints is one sufficient hypothesis in KKT regularity at a local minimum.[ref]
Lecture 7: Lagrange Multipliers and KKT Conditions. Lecture 7, §L7.1.3, Theorem L7.3, printed p. 4: independent active gradients
Slater's condition provides a different constraint qualification for convex optimization, yielding strong duality and dual attainment.[ref]Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §5.2.3, printed pp. 226–227: Slater's condition, strong duality and dual attainment
Constraint reaction in hyperelastic stress 2026-10-14
For a regular material constraint , admissible rates of the deformation gradient lie in the kernel of . The difference between the nominal stress and the derivative of the strain energy density annihilates that tangent space by virtual work, so it is a Lagrange multiplier times . For incompressibility, the derivative of the determinant is its cofactor matrix, and the material-first reaction is when .
Convex KKT optimality certificate 2026-10-14
For differentiable functions that are convex functions on an open convex set and affine functions , the KKT conditions certify a global minimum. Once Lagrange multipliers satisfy them, no extra Slater condition is needed.[ref]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. §5.5.3, printed p. 244: sufficiency under convexity and affine equalities
The certificate is a short chain of inequalities. Nonnegative Lagrange multipliers and affine equalities make a convex function. Its zero gradient gives a global minimum at by the first-order optimality condition. For every feasible point ,The first equality uses feasibility and complementary slackness; the last inequality uses and . Equivalently, the Lagrange dual function attains the same value as the primal objective function, proving strong duality. A strictly convex function makes the primal optimum unique, although the Lagrange multipliers need not be unique.
Affine equality optimization constraints matter: an arbitrary signed multiple of a nonlinear equality can destroy convexity of the optimization Lagrangian. For example, minimizing subject to the affine equality gives and for . This equality Lagrange multiplier is positive for , zero at , and negative for . Completing the square gives the certificate for every real number .
Outside convex optimization, KKT stationarity alone does not certify an optimum: minimizing with no optimization constraints gives the stationary candidate , which is a global maximum. The Lagrangian sufficiency theorem remains applicable whenever a global minimum of the optimization Lagrangian can be proved directly.
Convex optimization Created 2026-09-24 Updated 2026-10-13
Convex optimization is a minimization problem with a convex function as its objective function and a convex set of feasible points. For a finite-valued , the problem is to find with for every . The displayed infimum describes its value even when no minimizing point exists. The two convexity requirements concern different objects: the allowed decisions and the scores assigned to them.
A convex set contains the whole line segment between any two of its points:A convex function lies below the interpolation of its endpoint values:Thus mixing two allowed decisions preserves feasibility, and the mixed score is no worse than the same mixture of endpoint scores. The objective function may have flat regions or corners. For a strictly convex function, the second inequality is strict when and .
A useful constraint representation iswhere are convex functions on a common convex set , and the equalities are affine functions. Each inequality defines a convex sublevel set; their intersection with and the equality set is a convex set. An equality involving a general convex function need not preserve this geometry: allows and but excludes their midpoint . See Boyd and Vandenberghe, Convex Optimization (2004), §4.2.1 for the standard problem form.
Why local information can certify a global answer. Every local minimum of a convex optimization problem is a global minimum, including minima on the boundary. If a feasible point had , points would remain feasible and have value strictly below for every . Taking arbitrarily small contradicts a local minimum at . This argument explains the special power of convexity: a better distant decision would reveal an improving direction immediately nearby.
If a minimizer exists and the objective function is strictly convex on , it is unique. Two distinct minimizers of value would have a feasible midpoint with value strictly below . Existence is a separate question: the exponential function is strictly convex on , but its infimum is approached only as . Even a bounded convex set need not suffice: on also has unattained infimum . A continuous function on a nonempty compact set attains its minimum by the extreme value theorem.
Nor does strict convexity imply differentiability. For , the squared term gives the strict inequality while the triangle inequality gives the weak inequality for the absolute value. At zero the left and right derivatives are and , so no derivative exists there, although zero is the unique minimizer. Such objectives require subgradients or proximal operators rather than an ordinary gradient at every point.
For a differentiable convex function on an open convex set containing , the constrained first-order condition isIndeed, the subgradient inequality makes this sufficient; taking the one-sided derivative along feasible line segments makes it necessary. At an interior minimizer, both directions are feasible and the gradient must vanish. At a boundary minimizer it can be nonzero: it only needs to make every feasible direction nondecreasing. See Boyd and Vandenberghe, §§3.1.3 and 4.2.3.
A fully computed nearest-point problem. Project onto the half-space by minimizing half the squared Euclidean distance:The Hessian matrix is the identity matrix, so the objective function is strictly convex. The unconstrained minimizer violates the inequality. With the convention , the optimization Lagrangian is , where the Lagrange multiplier satisfies . Its Karush-Kuhn-Tucker conditions areThe last two equations give , . The choice is infeasible, so complementary slackness forces . Consequently , giving , and . The Euclidean distance is , rather than the objective function value . The gradient at the answer balances ; the displacement from to is a normal vector to the boundary.
There is an exact certificate independent of numerical search. Completing squares givesFor every feasible point, implies . Thus every feasible objective is at least , and attains this bound. More generally the Lagrangian dual problem has objective for . Its maximum is also , illustrating strong duality through matching computed bounds. This makes the example a model for Euclidean projection onto a convex set and the projection step in projected gradient descent.
What the multiplier conditions require. For differentiable convex functions on an open convex set and equalities defined by affine functions, the KKT conditions combine feasibility, , complementary slackness , and stationaritywith unrestricted equality Lagrange multipliers . They suffice to certify a global minimum without an additional regularity assumption: the optimization Lagrangian is convex, stationarity minimizes it, and feasibility with complementary slackness gives the same certificate as above. To guarantee their necessity at an attained finite optimum, a regularity hypothesis suffices: Slater's condition requires some with and . The projection example has the strictly feasible point . See Boyd and Vandenberghe, §§5.2.3 and 5.5.3. This hypothesis guarantees suitable multipliers, not existence of a primal minimizer.
Without regularity, necessity can fail even for convex functions: minimize subject to . The sole feasible point is optimal, but stationarity would require . No Lagrange multiplier works. There is no strictly feasible point, and the gradient of the constraint vanishes at the answer.
The nonconvex contrast. The polynomial has derivative and second derivative . Numerically solving the cubic gives stationary points , , and . Their objective values are respectively , , and , with second derivatives , , and . Hence both outer points are local minima, and the middle point is a local maximum. Since at both ends, its global minimum exists and must be one of the stationary minima: it is the left one. A method stopping at the right local minimum misses a better value by approximately .
A strictly convex quadratic has one minimum; a tilted quartic has two local minima with different values
. Details. The practical appeal of convex optimization is the ability to check an answer globally using geometry and matching Lagrangian duality bounds. The projection certificate certifies every feasible alternative at once; the tilted quartic shows why a zero gradient alone cannot do that for general nonlinear optimization.
Historically, an early landmark is Kuhn and Tucker's [ref]
https://digicoll.lib.berkeley.edu/record/112776/files/math_s2_article-35.pdf. Nonlinear Programming, Second Berkeley Symposium (1951), pp. 481–492
. Its §3 explicitly states a regularity hypothesis for inequality-constrained Lagrange multipliers; its discussion of saddle points explains how concave functions support global conclusions for maximization. This documents an early formulation of the multiplier approach; it does not establish sole discovery of today's KKT conditions or of convex optimization as a whole. Convex Optimization by Stephen Boyd and Lieven Vandenberghe Created 2026-10-13 Updated 2026-11-05
Publisher: Cambridge University Press.
Online text: www.seas.ucla.edu/~vandenbe/cvxbook/bv_cvxbook.pdf
Cited passages: Appendix A.5.2, pp. 646–647: symmetric eigenvalue decomposition and definiteness; §2.2.2, p. 30, equation (2.3): ellipsoids and semi-axis lengths; the book uses the inverse quadratic coefficient matrix; §3.1.4, Example 3.2, p. 71: a quadratic function is strictly convex exactly when its symmetric coefficient matrix is positive definite.
Online text: stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
Cited passages: Appendix A.5.5, printed p. 650: block inversion and minimized quadratic form; §C.4.1, printed pp. 672–675: block elimination, Algorithm C.4, factor-solve interpretation and dense complexity.
Online text: web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
The front matter states first publication in 2004 and a seventh printing with corrections in 2009. The title page credits Stephen Boyd and Lieven Vandenberghe as whole-book coauthors; no separate appendix byline is supplied. Cambridge University Press publishes the book; the Stanford author website hosts this copy.
Additional cited passage: §2.1.4, printed p. 24 (PDF page index 37), convex combinations and the definition and minimality of the convex hull. The title-page whole-book credits and the separately recorded 2004 first publication and 2009 corrected seventh printing apply to this copy.
Additional cited passages: §5.6.3, printed pp. 251–253, especially equation (5.58), local sensitivity of the optimal value to equality-constraint perturbations. The sign of the Lagrange multiplier depends on the chosen sign for the equality term. The title page and front matter retain the whole-book authorship, 2004 first publication and 2009 corrected seventh printing recorded above.
Additional cited passage: §4.4.2, printed p. 157, equation (4.37), robust linear programming imposes each inequality for every parameter in the chosen uncertainty set. The illustrated set is an ellipsoid, and its worst-case linear contribution is a Euclidean norm; a box or finite sign model has a different support calculation. [ref]
https://www.seas.ucla.edu/~vandenbe/cvxbook/bv_cvxbook.pdf. Printed p. 157, robust linear programming
Let be a real positive-definite matrix and let the columns of be an orthonormal basis of a two-dimensional linear subspace in three-dimensional Euclidean space. Points in that central plane are , with . Restricting the ellipsoid gives . The compressed matrix is a positive-definite matrix, and its extreme eigenvalues give the distance formulas in the title by the Rayleigh quotient. The two extremal axes are the images under of the corresponding eigenvectors. This restriction reduces a problem with two Lagrange multipliers to a two-dimensional quadratic form.
Distance extrema on a real quadratic surface Created 2026-10-18 Updated 2026-10-20
For a real symmetric matrix , every stationary squared distance on occurs in a positive-eigenvalue eigenspace. The Lagrange multiplier equation is ; multiplying by gives , hence . If is a positive-definite matrix, the nearest and farthest squared distances are and . With a repeated eigenvalue, the stationary set may contain an entire sphere within its eigenspace. For an indefinite or singular form the surface may be unbounded, and a stationary point need not be a global extremum.
Dual attainment 2026-10-18
Dual attainment means that a feasible choice of Lagrange multipliers achieves the optimal value of the Lagrangian dual problem. Equality of primal and dual optimal values alone does not imply dual attainment.
Elastic incompressibility Created 2026-10-25 Updated 2026-11-05
Volume preservation by the elastic accommodation in morphoelasticity. If , elastic incompressibility imposes , and hence . Total volume can increase through growth while the elastic response remains incompressible. A hydrostatic pressure acts as a Lagrange multiplier enforcing this constraint in the Cauchy stress tensor.
Envelope theorem 2026-10-14
For a smooth constrained maximum subject to , suppose smooth optimizers and multipliers satisfy . Differentiating the constraint gives , and the chain rule gives . Thus a Lagrange multiplier measures the marginal value of relaxing its corresponding constraint. A global supporting Lagrangian duality representation implies the needed stationarity, but local stationarity and smoothness alone suffice for this derivative identity.
Equality slice of a feasible triangle 2026-10-14
Keep the feasible triangle with a squared-distance objective, but add the equation . An equality requires an exact relation, whereas an inequality allows a range. Here the equality selects a line, and intersecting that line with the original feasible region leaves just the line segment from to :The lower bound comes from ; the upper bound comes from . This is a nonempty closed set even though it has empty interior in the plane. An equality can reduce the dimension of the allowed decisions without making the feasible region empty.
The old optimum violates the added equality. On the surviving line segment, the objective function isThe derivative shows that the unique global minimum is at , giving and value . The nearest point on the entire equality line would be , at with value , but it violates . Both the equality and the original inequalities must hold simultaneously.
Equality slice of a feasible triangle: the allowed line segment ends at the optimum (2,1), while the nearest point on the entire line is infeasible
. Details. Use and to fix the multiplier sign convention in the optimization Lagrangian ; the Lagrange multipliers of and are again zero. At , Karush-Kuhn-Tucker conditions hold with and :The Lagrange multiplier of an equality has no nonnegativity restriction. For an independent global certificate, completing the square gives . On the feasible set, and , so , with equality exactly at .


