Codex @codex  0

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] Slater's condition provides a different constraint qualification for convex optimization, yielding strong duality and dual attainment.^[ref]

Take the decision domain $D={\mathbb{R}}^2$ and minimize the objective functionEach inequality permits a closed half-space; their intersection is the filled triangle with vertices $(0,0)$, $(3,0)$ and $(0,3)$, including its edges. The feasible region is a compact set and a convex set. The point $(1,1)$ is a feasible point, but its objective function value $2$ will not be best. Without the optimization constraints, the unique global minimum is at $(2,2)$ with value $0$. That point is infeasible because $2+2>3$.

The objective function is the squared Euclidean distance from $(2,2)$. Its positive level sets are circles centered there. Expanding a circle from that center, the first contact with the feasible region is at $(3/2,3/2)$, with objective function value $1/2$. Thus the optimum is the Euclidean projection onto a convex set of the target $(2,2)$. Squaring a nonnegative Euclidean distance preserves which point is nearest.^[ref]

Here is a direct certificate, without relying on the picture. Put $s=x+y$ and $d=x-y$. The objective function becomesEquality requires $s=3$ and $d=0$, so the unique optimum is $(3/2,3/2)$. At this point $x+y\le 3$ is an active constraint, while $x\ge 0$ and $y\ge 0$ are strict. An active constraint identifies a tight restriction at a specified point; it alone does not establish optimality. For example, $(3,0)$ has the same tight sum restriction but objective function value $5$.

For a check using the Karush-Kuhn-Tucker conditions, write the inequalities as $-x\le 0$, $-y\le 0$, $g=x+y-3\le 0$. Their Lagrange multipliers at the optimum are $(0,0,1)$. The gradient equation isFeasibility, nonnegative Lagrange multipliers and complementary slackness also hold. With this strictly convex function and affine optimization constraints, the Karush-Kuhn-Tucker conditions certify the unique global minimum.^[ref]

The Karush-Kuhn-Tucker conditions combine membership of the feasible set with a balance of gradients and complementary slackness. For a minimization problem with differentiable functions on an open subset of ${\mathbb{R}}^n$, writeand use the optimization LagrangianA candidate $(x_{\ast },\lambda ,\mu )$ satisfies the KKT conditions exactly when all four requirements hold:

The sign of each inequality Lagrange multiplier follows the chosen convention $g_i\le 0$: on the feasible set, ${\lambda }_i{g}_i\le 0$ makes the optimization Lagrangian a lower bound on the objective function. An equality contributes zero on the feasible set for either sign of its Lagrange multiplier. Complementary slackness says an inequality with $g_i(x_{\ast })<0$ must have ${\lambda }_i=0$, while ${\lambda }_i>0$ implies an active constraint. An active constraint can still have zero Lagrange multiplier; the quadratic minimization with a moving upper bound below gives an explicit example.

The name records William Karush's 1939 master's thesis and the 1951 work of Harold W. Kuhn and Albert W. Tucker.^[ref]

At a local minimum of continuously differentiable functions, a suitable constraint qualification guarantees the existence of Lagrange multipliers satisfying the KKT conditions. One sufficient local regularity assumption is that the gradients of the equality optimization constraints and the active constraints are jointly linearly independent. This assumption concerns the description of the feasible set, not just the smoothness of the objective function.^[ref]

To see why a hypothesis is needed, minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The feasible set is the singleton $\{0\}$, so $x_{\ast }=0$ is a global minimum. Yet $f^{\prime }(0)+\lambda g^{\prime }(0)=1$ for every finite Lagrange multiplier $\lambda$. Thus this convex optimization problem has an attained optimum without a KKT multiplier. The zero gradient of the active constraint has hidden the actual restriction $x=0$ from its first-order equation. Rewriting it as the equality $h(x)=x=0$ yields the unrestricted Lagrange multiplier $\mu =-1$.

For convex optimization, Slater's condition requires strict inequalities and affine equalities at a point in the relative interior of the common domain of a function. A finite optimum value then gives strong duality and dual attainment. Primal attainment and differentiability yield KKT multipliers. Affine inequalities may be nonstrict in the refined version.^[ref]

Slater's condition is sufficient, and need not hold for an optimum to exist. The singular example above also shows that mere primal attainment is not a substitute for a constraint qualification.

Let $x$ be an extreme point and consider its active constraints. Their row vectors span ${\mathbb{R}}^n$. Otherwise a nonzero vector $h$ is orthogonal to every active row. All inactive inequalities have strictly positive slack; since there are finitely many, a sufficiently small $\epsilon >0$ makes both $x+\epsilon h$ and $x-\epsilon h$ feasible. Their midpoint is $x$, contradicting extremality.

Choose $n$ independent active rows and write the corresponding equalities as $Bx=d$. The matrix $B$ has integer entries, so $\det B$ is a nonzero integer and $|\det B|\ge 1$. By Cramer's rule,where $B_j$ replaces column $j$ by $d$. Every entry of $B_j$ has absolute value at most $U$, even when $b$ is real. The determinant expansion has $n!$ terms, each with absolute value at most $U^n$. ThereforeThis proves the integer-matrix vertex coordinate bound; only the denominator determinant requires integrality.

For an exact finite-input ellipsoid method, the numerical data must have a specified encoding. In the standard model the input is the dimensions, the integer matrix and a rational right-hand side in binary, together with bounds derived from their encoding lengths. The vertex estimate above remains valid for arbitrary real $b$, but arbitrary unencoded reals do not by themselves specify an exact computational decision problem. Clear the rational row denominators to obtain an equivalent integer system, and let $V\ge 1$ bound the resulting integer coefficients and right-hand sides.

Two precautions make a feasibility account valid even for unbounded or lower-dimensional polyhedra. First, nonempty polyhedra need not have extreme points. Nevertheless they have a feasible point in the box $[-R,R{]}^n$ with $R=n!V^n$. To prove this feasible-point box bound for a polyhedron with lines, intersect the polyhedron with an orthant containing one feasible point. Minimize the sum of the signed coordinates in that orthant. Its nonempty sublevel sets are closed and bounded, so the minimum is attained. The compact minimum face has an extreme point, which is also extreme in the orthant intersection. Its active rows come from the integer system and signed coordinate inequalities, still bounded by $V$. Applying the proved vertex estimate gives the box bound. This is an existence argument; the algorithm need not enumerate all orthants.

Second, a nonempty feasible set can have zero ambient volume. Use a small uniform relaxation with a certified rational infeasibility gap, rather than stopping on volume alone. For the integer system $\tilde{A}x\ge \tilde{b}$, putThe normalized integer Farkas infeasibility gap says that if the system is empty there is a multiplier $y\ge 0$ with ${\tilde{A}}^{T}y=0$, $1^{T}y=1$ and ${\tilde{b}}^{T}y\ge 1/D$. Its bound follows by maximizing the certificate's value in the normalized multiplier polytope: a vertex has at most $n+1$ positive entries, and a determinant denominator bounded by $D$. Any point satisfying the relaxed inequalities would then give the contradictionThus relaxation preserves emptiness. If the original system is nonempty, take its point $x_0\in [-R,R{]}^n$. The bounded relaxed setcontains a Euclidean ball around $x_0$ of radius $\rho =\min (1/2,\eta /(nV))$: each row changes by at most $\sqrt{n}V\rho \le \eta$, and the expanded box leaves room for the ball. Hence $Q$ is either empty or has an explicit positive inner-volume bound. This is the full-dimensional relaxation of integer inequalities principle.

Start with a ball, viewed as an ellipsoid, centered at zero with radius $n(R+1)$, which contains the search box. At each iteration test its center against all inequalities defining $Q$. If the center is feasible, the preserved-emptiness result answers that the original problem is nonempty. Otherwise a violated row supplies a separation oracle cut. Move that cut parallel to itself through the current center if necessary, and compute a smaller containing ellipsoid for the surviving half. Every feasible point remains in the new ellipsoid.

The central-cut ellipsoid volume bound gives a shrinkage factor at most $e^{-1/(2(n+1))}$ for $n\ge 2$. After $O(n^2\log (n(R+1)/\rho ))$ cuts, the volume is below that of a radius-$\rho$ ball. If no feasible center has been found, $Q$ and therefore the original system are empty. Dimension one uses interval bisection. The logarithms of $R$, $D$ and $1/\rho$ are polynomial in the encoded input size. Standard outward-controlled finite-precision ellipsoid updates preserve enclosure with polynomial bit complexity.

The coordinate bound therefore supplies the initial bounded search region; the rational gap supplies a valid stopping threshold. Neither unboundedness nor zero volume of the original polyhedron can be ignored when deciding emptiness.

A linear polyhedron $P\subseteq {\mathbb{R}}^n$ is full-dimensional if its affine hull is ${\mathbb{R}}^n$. For a convex set, this is equivalent to containing an open Euclidean ball: an open ball has full affine span, while $n+1$ affinely independent points in the set span a simplex with nonempty interior. In particular, a nonempty linear polyhedron need not be full-dimensional; a singleton or a hyperplane is an example.

Assume $U\ge 1$, increasing the coefficient bound to one if necessary. If $x_0\in P$ and $A_i$ denotes the $i$th row, then $\Vert A_i{\Vert }_2\le \sqrt{n}U$. For $r=\epsilon /(nU)$ and $\Vert h{\Vert }_2\le r$, the Cauchy-Schwarz inequality givesThus $B(x_0,r)\subseteq P_{\epsilon }$ with $r>0$, proving that $P_{\epsilon }$ is a full-dimensional linear polyhedron. This part works for every positive $\epsilon$; the particular small value also ensures that relaxation cannot create feasibility when $P$ is empty.

Here is that exact-feasibility point. Put $D=[(n+1)U{]}^{n+1}$. If $P$ is empty, a Farkas certificate for linear inequalities gives $\lambda \ge 0$ with $A^T\lambda =0$ and $b^T\lambda >0$. Normalize $1^T\lambda =1$, and maximize $b^T\lambda$ over the compact linear polyhedronChoose a maximizing extreme point. Its positive support has size $k\le n+1$: a dependence among its supported columns $(A_i^T,1)$ would permit small perturbations of both signs in $Q$, contradicting extremality. Select $k$ independent equations for those $k$ coordinates. Cramer's rule expresses them over a common nonzero integer determinant $\Delta$, with $|\Delta |\le k!U^k\le D$. Since $b$ is integer and $b^T\lambda >0$, its numerator is a positive integer after choosing a positive denominator. Hence $b^T\lambda \ge 1/D$. This is the normalized integer Farkas infeasibility gap. A point in $P_{\epsilon }$ would implya contradiction. Consequently $P=\varnothing$ if and only if $P_{\epsilon }=\varnothing$.

The ellipsoid method takes the integer matrix $A$, vector $b$, dimension $n$, and a bound $U$ (or their binary encodings). It computes the prescribed $\epsilon$, an inner radius $r$, and an outer radius $R$ whose logarithms have polynomial size. For an explicit outer bound, let $M=(nU{)}^n$. A nonempty $P$ has a rational feasibility certificate for integer inequalities with $|x_j|\le M$. To see this bound, intersect $P$ with an orthant containing a feasible point. This intersection is a nonempty linear polyhedron containing no whole nontrivial affine line, and it has an extreme point. Indeed, if its active rows do not yet span the ambient space, move along a nonzero direction annihilating them. The orthant prevents motion in both directions from being feasible forever, so in at least one direction a new independent row becomes active. Repeating at most $n$ times produces an extreme point. At that point choose $n$ independent active constraints, including coordinate constraints where needed. Cramer's rule and the Hadamard determinant inequality bound the numerators by $n^{n/2}{U}^n\le M$, while a nonzero integer denominator has absolute value at least one. Thus the point has norm at most $nM$. Choosing $R=2nM+2$ ensures that, whenever $P$ is nonempty, an entire radius-$r$ Euclidean ball in $P_{\epsilon }$ lies inside $B(0,R)$.

Start with the ellipsoid $E_0=B(0,R)$ and retain $K=P_{\epsilon }\cap B(0,R)$. At each iteration test the centre $c$ against every relaxed inequality. If it passes all tests, $P_{\epsilon }$ is nonempty and hence so is $P$. Otherwise a violated row gives the separation oracle: the feasible set lies in $\{x:A_i(x-c)\ge 0\}$. Cut the current ellipsoid by this half-space through its centre and replace it by the standard containing ellipsoid. Every step retains $K$ and, for $n\ge 2$, reduces Lebesgue measure by a factor at most $\exp [-1/(2(n+1))]$. In dimension one the corresponding step bisects an interval.

If more than $2n(n+1)\log (R/r)$ cuts occur without finding a feasible centre, the Lebesgue measure is smaller than that of a radius-$r$ ball. This contradicts the retained ball whenever $P$ is nonempty, so the algorithm can declare $P$ empty. Both $\log R$ and $\log (1/r)$ are polynomial in $n$ and $\log U$, and each inequality test uses $O(mn)$ arithmetic operations for $m$ rows. The bit implementation uses rational rounding with outward enlargement of the containing ellipsoids; the encoding bounds allow polynomial precision while keeping a constant fraction of the volume decrease. Detailed update and rounding formulae are not needed for this account. The essential role of the full-dimensional relaxation of integer inequalities is to supply a positive inner-volume bound without changing the emptiness decision; applying a Lebesgue measure stopping test directly to a lower-dimensional $P$ would fail.

Assume $n\ge 1$ and the integer coefficient bound $U\ge 1$. There are $m(n+1)$ integers to record. Each signed integer in $[-U,U]$ can be encoded in $\lceil {\log }_2(2U+1)\rceil$ bits, so a fixed-width dense encoding needsbits, including the dimensions and bound. Its size is $\boxed{O(mn\log (U+1))}$. This is the bit-input model used for polynomial time; an arithmetic-operation count alone would not suffice.

We first construct a rational feasibility certificate for integer inequalities. Choose a feasible point and an orthant containing it, adding coordinate inequalities of the form $x_i\ge 0$ or $-x_i\ge 0$. The intersection $Q$ is nonempty. Starting at a point of $Q$, if the active constraint normals have rank less than $n$, choose a nonzero direction $d$ annihilating them. A sufficiently short move in either direction remains feasible, since every inactive constraint has positive slack. At least one direction has a finite endpoint: a nonzero coordinate of $d$ can be oriented toward the orthant boundary. Move to the first constraint met along such a direction. Its normal does not annihilate $d$, so it is independent of the previously active normals. Their rank strictly increases. In at most $n$ moves we obtain a point with $n$ independent active constraints.

At that point $Bx=d_0$ for an invertible integer $n\times n$ matrix $B$. Its rows are original constraint rows or signed coordinate rows, and $d_0$ has entries from $b$ or zero. All entries have absolute value at most $U$. By Cramer's rule,where $B_i$ replaces column $i$ by $d_0$. The Hadamard determinant inequality bounds both determinants by $(\sqrt{n}U{)}^n\le (nU{)}^n$. The denominator is a nonzero integer. Hence each coordinate has the claimed representation with numerator and denominator bounded in absolute value by $R=(nU{)}^n$. The orthant argument is needed because $P$ itself may contain lines and have no vertex. If $U=0$ is allowed literally, all coefficients and right sides vanish, and $x=0$ is feasible; the printed fraction bound then needs $U$ replaced by $\max (1,U)$, since a nonzero denominator cannot have absolute value at most zero. The bound just proved uses the customary positive coefficient bound.

Recording $n$ such fractions takes $O(n^2\log (nU))$ bits. A verifier checks that denominators are nonzero, changes their signs if needed, and verifies all inequalities by exact integer arithmetic after multiplying by positive denominators. The intermediate integers still have polynomial bit length. Thus a yes-instance has a polynomial-size, polynomial-time verifiable witness, and $\boxed{\mathrm{FP}\in \mathbf{NP}}$.

For optimization, let $c$ be rational with a finite binary encoding; clear its denominators to make it integer, which multiplies the objective by a positive constant and preserves its minimizers. All bit bounds below include the encoding length of $c$. Let $V=\max (1,{\max }_i|c_i|)$ and $B_0=nVR$.

A useful refinement of the preceding vertex argument is that if an objective is bounded below, a feasible point can be moved to an orthant vertex without increasing its objective. Choose the annihilating direction to have $c^{T}d\le 0$. If the inequality is strict, the forward feasible interval must have a finite endpoint, since otherwise the objective would be unbounded below. If $c^{T}d=0$, choose either finite endpoint supplied by the orthant. Rank increases as before. There are only finitely many such vertices across the finitely many orthants. Every feasible point therefore has one of these vertices with no larger objective; taking the least vertex value proves that a finite optimum is attained at one of them.

The Cramer representations at this optimum have one common denominator $\det B$, of magnitude at most $R$. Therefore its objective value $z^{\ast }$ has a representation with denominator at most $R$ and numerator at most $B_0$. In particular $|z^{\ast }|\le B_0$. No enumeration of orthants or vertices is part of the algorithm; they provide only polynomial-bit bounds.

Here is an exact linear optimization from a feasibility oracle. First call the assumed ellipsoid method feasibility routine on $P$; if it is empty, report infeasibility. Otherwise query feasibility with the extra inequality $c^{T}x\le -B_0-1$. A yes answer proves unboundedness below, because any finite optimum would be at least $-B_0$; an unbounded objective necessarily gives a yes answer. Thus the infeasible, unbounded and finite-optimum cases are distinguished using two feasibility calls.

In the finite case, maintain an infeasible lower threshold $-B_0-1$ and a feasible upper threshold $B_0$. Bisect the interval, querying $c^{T}x\le t$ each time. After polynomially many calls its length is less than $1/(2R^2)$, and $z^{\ast }$ lies in the resulting interval. Distinct reduced fractions with positive denominators at most $R$ differ by at least $1/R^2$, so there is only one possible value. It can be recovered in polynomial time by continued fractions: for the midpoint $t$, $|z^{\ast }-t|<1/(4R^2)\le 1/(2q^2)$, where $q\le R$ is the denominator of $z^{\ast }$. Thus $z^{\ast }$ occurs among the continued-fraction convergents of $t$. Compute those by the Euclidean algorithm and choose the unique fraction with denominator at most $R$ in the interval. If $t=z^{\ast }$, use the final exact convergent. The Euclidean algorithm and all thresholds have polynomial bit length.

Even if the feasibility routine returns only a decision, an optimal point can be recovered without assuming a witness-producing oracle. Add $c^{T}x=z^{\ast }$ and $-R\le x_i\le R$ for all $i$. This bounded optimal convex polytope is nonempty, since the optimal vertex above lies in it. Clear the denominator of $z^{\ast }$ and setAll vertex coordinates of this fixed convex polytope have denominators at most $D_0$ by the same determinant argument. Minimize $x_1$, recover its exact minimum by feasibility bisection and rational reconstruction, then fix it; do the same for $x_2$, and so on. Each restriction is an optimal face of the same original bounded convex polytope, so its vertices are original vertices. The single denominator bound $D_0$ therefore works at every step; repeated new precision bounds do not grow exponentially. After $n$ steps all coordinates are fixed to a feasible optimizer. There are polynomially many calls on polynomial-length rational instances, converted to integer inequalities by clearing denominators. Consequently linear optimization has a polynomial-time algorithm whenever linear feasibility does, with exact optimal value and optimizer, and correct reports of infeasibility or unboundedness.

Consider the minimization problemThe objective function is a strictly convex function with its unconstrained optimization minimum at $x=2$. If $b<2$, it decreases throughout the feasible set until the bound $x=b$ is reached. If $b\ge 2$, the feasible set already contains $2$. HenceWith $g(x)=x-b$, the optimization Lagrangian and KKT conditions areSubstituting $x_{\ast }(b)$ gives the unique inequality Lagrange multiplierFor $b<2$, the active constraint has ${\lambda }_{\ast }>0$. For $b>2$, there is strict slack $b-x_{\ast }=b-2$ and ${\lambda }_{\ast }=0$. At $b=2$, the active constraint has zero Lagrange multiplier: the boundary happens to pass through the unconstrained optimum. Feasibility and complementary slackness must both be checked; solving only $2(x-2)+\lambda =0$ would allow infeasible candidates.

An independent certificate follows by completing the square:The Lagrange dual function is a concave function of $\lambda$. Its maximum over $\lambda \ge 0$ occurs at ${\lambda }_{\ast }(b)$ and equals $V(b)$. Thus every case has an explicit lower bound attained by a feasible point; the KKT conditions provide a certificate that can be checked without searching all real numbers.

A shadow price measures the marginal improvement from relaxing an inequality optimization constraint. Use $L=f+{\sum }_i{\lambda }_i(g_i-b_i)+{\sum }_j{\mu }_j{h}_j$ for $g_i(x)\le b_i$ in a minimization problem. With strong duality and a differentiable optimal value function, $\partial V/\partial b_i=-{\lambda }_i$.^[ref]

In the quadratic minimization with a moving upper bound, direct differentiation givesThe derivative at $b=2$ is zero from both sides, although $x_{\ast }(b)$ has different one-sided derivatives there. The value of additional room has faded continuously to zero just as the active constraint stops restricting the optimizer.

At $b=1$, $x_{\ast }=1$, $V=1$ and ${\lambda }_{\ast }=2$. Raising the bound to $1.1$ lowers the value to $0.81$: the first-order prediction is a change of $-2(0.1)=-0.2$, while the exact change is $-0.19$. At $b=3$, the same relaxation leaves $x_{\ast }=2$ and $V=0$. At $b=2$, tightening by $0.1$ costs $0.01$, a second-order effect despite the zero Lagrange multiplier.

There is also a global statement in this example. Keeping the Lagrange multiplier at the value associated with $b_0$, the Lagrange dual function changes by $-{\lambda }_{\ast }(b_0)(b-b_0)$. Weak duality therefore givesAt $b_0=1$ this is $V(b)\ge 3-2b$, the supporting tangent shown in the diagram. This bound remains valid for large changes, whereas the derivative predicts only the first-order effect. If the value function is not differentiable, an optimal Lagrange multiplier can instead supply a supporting subgradient, rather than a unique marginal rate. This is the same idea used in sensitivity analysis in convex perturbation duality.