KKT Conditions for Inequality-Constrained Quadratics

From Equality Constraints to Inequality Constraints

With equality constraints, a feasible point must satisfy every constraint exactly. Inequalities allow more possibilities: a constraint may hold with equality or may have room to spare. The Karush–Kuhn–Tucker (KKT) conditions account for this distinction by pairing each inequality with a nonnegative multiplier and requiring a complementary-slackness relationship between the two.

We study a quadratic objective over a set described by linear inequalities. The objective is convex when its Hessian is positive semidefinite. In this setting, the KKT conditions do more than identify plausible candidates: they characterize global minimizers.

Definition: Let \(x\in\mathbb{R}^p\), let \(Q\) be a symmetric positive-semidefinite \(p\times p\) matrix, let \(c\in\mathbb{R}^p\), let \(A\) be an \(m\times p\) matrix, and let \(b\in\mathbb{R}^m\). The inequality-constrained quadratic problem is

\min_{x\in\mathbb{R}^p} f(x)=\frac{1}{2}x^TQx+c^Tx \quad\text{subject to}\quad Ax\le b.

The vector inequality means that each of the \(m\) component inequalities holds: \(a_i^Tx\le b_i\), where \(a_i^T\) is row \(i\) of \(A\). The slack of constraint \(i\) at \(x\) is \(b_i-a_i^Tx\), which is nonnegative at a feasible point.

The factor \(1/2\) makes the gradient especially simple. Since \(Q\) is symmetric, \(\nabla f(x)=Qx+c\). Introduce one multiplier \(\lambda_i\) for each inequality and use the minimization convention \(a_i^Tx-b_i\le 0\). The Lagrangian is

\mathcal{L}(x,\lambda) =f(x)+\lambda^T(Ax-b), \qquad \lambda\ge 0.

The multiplier sign is tied to this convention: for constraints written as \(Ax-b\le 0\), the multipliers must be nonnegative. Reversing the inequality convention without adjusting the Lagrangian changes the sign rule.

The KKT Conditions

A point is primal feasible if it satisfies the original inequalities. A multiplier vector is dual feasible if all its components are nonnegative. The remaining conditions are stationarity and complementary slackness.

Theorem: For the quadratic problem above, a feasible point \(x^*\) is a global minimizer if and only if there is a vector \(\lambda^*\in\mathbb{R}^m\) satisfying all four KKT conditions:

\begin{aligned} &\text{Primal feasibility:} && Ax^*\le b,\\ &\text{Dual feasibility:} && \lambda^*\ge 0,\\ &\text{Stationarity:} && Qx^*+c+A^T\lambda^*=0,\\ &\text{Complementary slackness:} && \lambda_i^*(a_i^Tx^*-b_i)=0,\quad i=1,\ldots,m. \end{aligned}

These conditions apply when the feasible set is nonempty. For affine inequalities, no strict-feasibility assumption is needed for the necessity statement.

Complementary slackness says that for each constraint, at least one of its two factors is zero. If a constraint is strictly slack, its multiplier must be zero. If its multiplier is positive, the constraint must hold with equality. An active constraint—one holding with equality—does not have to have a positive multiplier.

Worked Example: A Scalar Bound Becomes Active

Minimize \(f(x)=\frac12(x-3)^2\) subject to \(0\le x\le 1\). Write the inequalities as \(x\le1\) and \(-x\le0\), so \(Q=1\), \(c=-3\), and the constraint rows are \(1\) and \(-1\).

The objective decreases as \(x\) moves toward \(3\), so the feasible minimizer is \(x^*=1\). To verify it with KKT, assign multipliers \(\lambda_1\) to \(x\le1\) and \(\lambda_2\) to \(-x\le0\). Stationarity requires

x^*-3+\lambda_1-\lambda_2=0.

At \(x^*=1\), the first constraint is active and the second is strictly slack: \(1-1=0\), while \(-1-0=-1<0\). Complementary slackness therefore requires \(\lambda_2=0\). Stationarity becomes \(-2+\lambda_1=0\), giving \(\lambda_1=2\ge0\). The point is feasible, the multipliers are nonnegative, and all KKT conditions hold. The objective value is \(f(1)=\frac12(1-3)^2=2\).

Why the Conditions Characterize a Minimum

The sufficiency argument uses convexity. For a differentiable convex function, the first-order inequality gives \(f(y)\ge f(x^*)+\nabla f(x^*)^T(y-x^*)\) for every \(y\). For this quadratic, convexity follows from \(Q\succeq0\): the difference between the two sides is \(\frac12(y-x^*)^TQ(y-x^*)\), which is nonnegative.

Suppose the KKT conditions hold and take any feasible \(y\). Stationarity and complementary slackness give

\begin{aligned} \nabla f(x^*)^T(y-x^*) &=-(\lambda^*)^TA(y-x^*)\\ &=-\sum_{i=1}^m\lambda_i^* \bigl(a_i^Ty-a_i^Tx^*\bigr)\ge0. \end{aligned}

To see the last inequality term by term, if \(\lambda_i^*=0\), the term is zero. If \(\lambda_i^*>0\), complementary slackness makes constraint \(i\) active at \(x^*\), so \(a_i^Tx^*=b_i\). Feasibility of \(y\) then gives \(a_i^Ty-b_i\le0\), making the displayed term nonnegative. The convex first-order inequality now yields \(f(y)\ge f(x^*)\). Since this holds for every feasible \(y\), \(x^*\) is a global minimizer.

For necessity, suppose \(x^*\) is a minimizer and let \(I\) be the indices of constraints active there. Consider the cone \(C=\{A_I^T\mu:\mu\ge0\}\), generated by the active constraint normals. This finitely generated cone is closed and convex. If \(-\nabla f(x^*)\) were not in \(C\), the separating-hyperplane theorem for a point and a closed convex cone would give a direction \(d\) such that

d^T(-\nabla f(x^*))>0 \quad\text{and}\quad d^Tz\le0\ \text{for every }z\in C.

Taking \(z=A_I^T\mu\) for each nonnegative \(\mu\) implies \(A_Id\le0\). Also, \(d^T(-\nabla f(x^*))>0\) means \(\nabla f(x^*)^Td<0\). For sufficiently small \(t>0\), the point \(x^*+td\) remains feasible: active constraints do not increase, and each inactive constraint has positive slack that a sufficiently small step preserves. Differentiability and the negative directional derivative imply \(f(x^*+td)<f(x^*)\) for sufficiently small positive \(t\), contradicting optimality. Thus \(-\nabla f(x^*)\in C\). Its representation by nonnegative coefficients supplies multipliers for active constraints; set the multipliers of inactive constraints to zero. These choices satisfy dual feasibility, stationarity, and complementary slackness, proving necessity. \(\square\)

Worked Example: A Two-Dimensional Boundary Solution

Minimize \(f(x_1,x_2)=\frac12[(x_1-2)^2+(x_2-1)^2]\) subject to \(x_1+x_2\le2\), \(-x_1\le0\), and \(-x_2\le0\). The unconstrained minimum is \((2,1)\), which violates the first inequality.

Consider \(x^*=(1.5,0.5)\). It is feasible because \(1.5+0.5=2\) and both coordinates are positive. The first constraint is active; the two nonnegativity constraints are slack. The gradient is

\nabla f(x^*)=(1.5-2,\;0.5-1)^T=(-0.5,-0.5)^T.

Set the multiplier for \(x_1+x_2\le2\) to \(\lambda_1=0.5\), and those for the other two constraints to \(\lambda_2=\lambda_3=0\). Then \(A^T\lambda=(0.5,0.5)^T\), so stationarity holds:

\nabla f(x^*)+A^T\lambda=(-0.5,-0.5)^T+(0.5,0.5)^T=(0,0)^T.

All multipliers are nonnegative. The active constraint has zero slack, and the two slack constraints have zero multipliers, so complementary slackness holds. The theorem therefore confirms global optimality. The objective value is \(\frac12[(-0.5)^2+(-0.5)^2]=0.25\).

Reading Multipliers and Active Constraints

The conditions are a system of equations and inequalities that must hold together. Stationarity balances the objective gradient against a nonnegative combination of active constraint normals. Geometrically, if the objective gradient points toward a direction that would improve the objective, the active constraints must block that direction at an optimum.

A zero multiplier does not prove that a constraint is slack. It can be active with a zero multiplier, for example when the constraint is redundant or its normal is unnecessary to balance the objective gradient. Multipliers can also fail to be unique. Neither situation invalidates the KKT test: the requirement is that some multiplier vector satisfies all four conditions.

Worked Example: An Active Constraint with a Zero Multiplier

Minimize \(f(x)=\frac12x^2\) subject to \(-x\le0\) and \(-2x\le0\). Both constraints express \(x\ge0\), so the minimizer is \(x^*=0\), with objective value zero. At this point both inequalities are active.

Let their multipliers be \(\lambda_1\) and \(\lambda_2\). Stationarity gives

x^*-\lambda_1-2\lambda_2=0, \quad\text{so}\quad \lambda_1+2\lambda_2=0.

Because both multipliers must be nonnegative, this equation forces \(\lambda_1=\lambda_2=0\). Thus both constraints are active even though both multipliers are zero. Feasibility, stationarity, dual feasibility, and complementary slackness all hold. The example shows why “active” and “positive multiplier” are not interchangeable.

Common Mistakes and Practical Use

Using the wrong multiplier sign. For \(Ax-b\le0\) in a minimization problem, use \(\mathcal{L}=f+\lambda^T(Ax-b)\) with \(\lambda\ge0\). The sign rule follows from this chosen form.
Checking stationarity alone. A stationary point may violate the inequalities or have negative multipliers. Verify primal feasibility, dual feasibility, stationarity, and complementary slackness.
Demanding positive multipliers for every active constraint. Complementary slackness requires a product to be zero, not a positive multiplier whenever a constraint is active.
Calling a KKT point a minimum without convexity. Here \(Q\succeq0\) makes the objective convex, and the feasible set is convex because its constraints are affine. Outside this setting, KKT conditions alone need not certify a global minimum.

For a strictly convex quadratic, \(Q\) is positive definite and the objective has at most one minimizer on a convex feasible set. With only positive semidefiniteness, multiple minimizers may occur. In either case, the KKT conditions provide a precise way to verify an optimum without guessing which inequalities will be active in advance.

Check Your Understanding

Use the KKT conditions to reason through each question.

For constraints written \(Ax\le b\), what Lagrangian sign convention leads to nonnegative multipliers?
If constraint \(i\) has positive slack at a KKT point, what must be true of \(\lambda_i\)?
Does an active inequality necessarily have a positive multiplier? Explain using complementary slackness.
Why do KKT conditions suffice for global optimality when \(Q\) is positive semidefinite?
For a candidate point and multiplier vector, list the four separate checks needed to verify the KKT conditions.