Practice: Active Constraints

Label the constraints $C_1:3x_1+x_2\le 9$, $C_2:x_1+x_2\le 5$, and the restrictions $N_1,N_2$. Here $n=2$.

(a) $(1,1)$. $C_1$: , slack. $C_2$: , slack. $N_1$: , slack. $N_2$: , slack. Active set empty, rank $0$. Two free directions, so the point is interior.

(b) $(2,3)$. $C_1$: $6+3=9=9$, active. $C_2$: $2+3=5=5$, active. Both components positive, so neither restriction is active. Normals $(3,1)$ and $(1,1)$: not multiples of one another, so rank $2=n$. No free direction, so the point is a vertex.

(c) $(0,5)$. $C_1$: , slack. $C_2$: $0+5=5=5$, active. $N_1$: $x_1=0$, active. $N_2$: , slack. Normals $(1,1)$ and $e_1=(1,0)$: independent, rank $2=n$. A vertex.

What (c) illustrates. One of the two constraints pinning this vertex is a nonnegativity restriction rather than a numbered constraint. A learner who counts only $C_1$ and $C_2$ finds one active constraint, concludes the point is on a face, and is wrong. The restriction is doing half the work of holding the point in place.

The error. Activity is a property of a point, not of a constraint. A constraint inactive at $(1,1)$ is excluding points elsewhere, and the region is defined by all of its constraints, not by whichever happen to be tight at one solution.

The consequence, concretely. With $x_1+x_2\le 4$ present, the region is a quadrilateral with vertices $(0,0)$, $(3,0)$, $(3,1)$ and $(0,4)$, bounded. Remove it and the region becomes the unbounded strip $0\le x_1\le 3$, $x_2\ge 0$, running upward forever. The vertex $(3,1)$ disappears and $x_2$ loses its bound entirely.

Why this is not a small difference. Maximise $x_2$ over each. On the true region the answer is $4$, at $(0,4)$. On the reduced region there is no finite optimum at all. The removal changed the verdict from a number to unbounded.

What would have justified a removal. Redundancy. A constraint whose removal leaves the feasible set unchanged. That is a global property, decided against the whole system, not by inspecting one point. Here $x_1+x_2\le 4$ is plainly not redundant, since removing it demonstrably enlarges the region.

The confusion to name. 'Inactive here' and 'unnecessary' are different claims, and only the second licenses deletion. A constraint slack at the current corner may be exactly the one that limits the step at the next, which is why the simplex method keeps every constraint in the system for every iteration.

The structural constraints. All $30$ equality rows are active, as they are at every feasible point of a standard-form system. Feasibility is equality on those rows, so they contribute nothing that distinguishes this point from any other.

The nonnegativity restrictions. Active exactly where a component is zero. With $30$ components positive out of $75$, there are $45$ components at zero, so $45$ restrictions are active.

The total. $30+45=75$ active constraints.

Is it a vertex? The test is whether the active normals have rank $n=75$. The $45$ active restrictions contribute unit vectors $e_j$ for the zero components, which are independent of one another. The $30$ structural rows, assuming $A$ has full row rank, supply $30$ more independent directions covering the remaining coordinates. Rank $75=n$, so yes, a vertex, and the count $n-m=75-30=45$ zero components is exactly what a vertex of such a system requires.

What would make it degenerate. More than $45$ components at zero, equivalently, fewer than $m=30$ strictly positive. Then a basic variable sits at zero, more than $75$ constraints are active, and several bases describe the same point.

Why the procedure transfers unchanged. Nothing above required a picture, and nothing referred to the dimension except to count. Evaluate every constraint, collect the active ones, take the rank. In two variables that procedure is confirmable by looking; in $75$ it is the only thing available, and it is the same procedure.