Active Constraints

Standing anywhere in a feasible region, some restrictions are pressing against you and the rest have room to spare. Which is which is a property of where you are standing, not of the program.

This is a small idea that a great deal rests on. The account of a corner as a point that is 'pinned down' is really a statement about how many independent constraints are active there. Degeneracy is an excess of active constraints at one point. Adjacency is two corners whose active sets differ by one. None of those can be stated precisely until activity is a thing you can compute rather than see.

Up to now the word has been used informally. A constraint is 'tight', or 'binding'. This unit makes it a definition with a test attached.

This unit assumes you can evaluate a linear constraint at a point and distinguish a half-space from its bounding hyperplane.

At a feasible point, some constraints hold with equality and the rest have slack. Which do is a property of the point.

In the interior of the region every constraint has slack, so a small step in any direction stays feasible and the active set is empty.

On a flat face one constraint holds with equality. Steps that would increase $a_i^{\mathsf{T}}x$ beyond $b_i$ leave the region; steps along the face, and steps back into the interior, remain feasible.

At a vertex of a two-variable region, two active constraints have independent normals. No direction keeps both equalities and stays feasible, but feasible directions still exist: moving along an incident edge relaxes one of the two active constraints while keeping the other tight.

So a vertex is not a point from which nothing can move. It is a point at which the active normals span ${\mathbb{R}}^n$, so the set obtained by holding all active constraints at equality is a single point rather than a line or a plane. Keeping every active constraint tight fixes the point; relaxing some of them gives the edges leaving it.

This is why rank, not count, does the classifying. Let $r$ be the rank of the active normals at $\overline{x}$. The set of points keeping all active constraints tight is an affine subspace of dimension $n-r$: dimension $n$ in the interior, a face when $r=1$, an edge when $r=n-1$, and a single point when $r=n$. Three active constraints in two variables with two parallel normals have rank $1$ and do not give a vertex.

The active set converts this into arithmetic that works in any dimension. Evaluate each constraint at the point, collect those holding with equality, and compute the rank of their normals.

A constraint inactive at one point is not removable. It may be active elsewhere in the region, and deleting it changes the feasible set.

Let the feasible region be given by $a_i^{\mathsf{T}}x\le b_i$ for $i\in I$, $a_i^{\mathsf{T}}x=b_i$ for $i\in E$, and $x_j\ge 0$ for each $j$.

At a feasible point $\overline{x}$, a constraint is active, equivalently tight or binding, when it holds with equality there. The active set is

A constraint holding strictly, with or , is inactive at $\overline{x}$.

Three consequences follow at once.

Equality constraints are active everywhere. Every $i\in E$ is in $A(\overline{x})$ for every feasible $\overline{x}$, because feasibility is equality on those rows. They therefore never distinguish one feasible point from another.

Nonnegativity restrictions are constraints. A component sitting at zero is active exactly as a resource limit reached exactly is active. In standard form, where the structural rows are all equalities, the nonnegativity restrictions are the only constraints whose activity varies from point to point.

What makes a point a vertex. $\overline{x}$ is a vertex when the normals of its active constraints span ${\mathbb{R}}^n$, counting a nonnegativity row $x_j\ge 0$ as the unit vector $e_j$. It is the rank of the active normals that decides this, not how many there are.

Confirm the point is feasible first. Evaluate every constraint. If any is violated, stop: the active set is not defined at an infeasible point, and asking which constraints are tight there confuses violation with equality.

Evaluate each inequality constraint and record equality or slack. For each $i\in I$, compute $a_i^{\mathsf{T}}\overline{x}$ and compare with $b_i$. Equal means active; strictly less means inactive. Write the verdict down rather than carrying it mentally, because the count is what the later steps use.

Include every equality constraint. Each $i\in E$ is active by definition. List them, but note that they contribute nothing to any comparison between two feasible points.

Include the nonnegativity restrictions. For each component, active exactly when ${\overline{x}}_j=0$. In standard form these are usually the majority of the active set and are the easiest to overlook, since they are not written among the numbered constraints.

Collect the normals of the active constraints. For a row constraint the normal is $a_i$; for the restriction $x_j\ge 0$ it is the unit vector $e_j$.

Take the rank of that collection, not its size. Reduce the collected normals and count the pivots. This is the number of independent equalities the active constraints impose at the point.

Read off the point's position. The directions that keep every active constraint tight are those orthogonal to all the active normals, and they form a subspace of dimension $n$ minus the rank. Rank $n$ leaves none of them, so the active equalities determine the point uniquely and it is a vertex. Rank $n-1$ leaves a one-dimensional set: an edge. Rank $0$ means nothing is active and the point is interior.

Note what this does and does not say. It counts directions preserving the active set, not directions you may travel: from a vertex you can still move along an incident edge or into the region by releasing an active constraint. Rank $n$ says the point is pinned by its equalities, not that it is immobile.

Take the region

with $n=2$, and label the constraints $C_1,C_2$ and the restrictions $N_1,N_2$.

The point $(1,1)$. $C_1$: , slack. $C_2$: , slack. Both components positive. Active set empty, rank $0$, two free directions. Interior.

The point $(3,0.5)$. $C_1$: , slack. $C_2$: $3=3$, active. $N_2$: , slack. Active set $\{C_2\}$, normal $(1,0)$, rank $1$, one free direction. On a face.

The point $(3,1)$. $C_1$: $4=4$, active. $C_2$: $3=3$, active. Normals $(1,1)$ and $(1,0)$ are independent, rank $2=n$. No free direction. A vertex.

The point $(0,4)$. $C_1$: $4=4$, active. $C_2$: , slack. $N_1$: $x_1=0$, active. Normals $(1,1)$ and $e_1=(1,0)$, independent, rank $2$. A vertex, and note that one of the two constraints pinning it is a nonnegativity restriction, not a numbered constraint.

The same four constraints throughout. What varies is which are active, and that is what distinguishes the four positions.

Problem. For the standard-form system

determine the active set at $\overline{x}=(4,2,0,0)$ and say whether the point is a vertex.

Goal. The active set, its rank, and the classification.

Relevant principle. In standard form the structural rows are active everywhere; the nonnegativity restrictions are what vary.

Step 1: confirm feasibility. $4+2+0=6$ and $4+0=4$: both equalities hold. Every component is nonnegative. The point is feasible, so the active set is defined.

Step 2: the structural rows. Both are equality constraints, so both are active, as they are at every feasible point of this system. They contribute their normals $(1,1,1,0)$ and $(1,0,0,1)$.

Step 3: the nonnegativity restrictions. , inactive. , inactive. $x_3=0$, active. $x_4=0$, active. These contribute $e_3=(0,0,1,0)$ and $e_4=(0,0,0,1)$.

Step 4: collect and take the rank. Four normals in ${\mathbb{R}}^4$:

Reducing: using $e_3$ and $e_4$ to clear the third and fourth entries of the first two leaves $(1,1,0,0)$ and $(1,0,0,0)$, which are independent of each other. Four independent normals, so the rank is $4=n$.

Step 5: classify. Rank $n$ means no direction is free. The point is a vertex.

Check against the basis reading. The positive components are $x_1$ and $x_2$, whose columns are $(1,1{)}^{\mathsf{T}}$ and $(1,0{)}^{\mathsf{T}}$, independent, and exactly $m=2$ of them. So this is a basic feasible solution, which is the same verdict reached through the corner correspondence.

What did the work. Counting the active nonnegativity restrictions. In standard form, with $m$ equality rows always active, a vertex needs $n-m$ components at zero, and here $n-m=2$ matches the two zero components exactly.

Not active: a constraint that is merely close. At $(2.99,1)$ in the earlier region, $C_2$ gives . Nearly tight is inactive. There is no tolerance in the definition, and introducing one turns a rank computation into a judgement call.

Not active: a violated constraint. At $(4,1)$, $C_2$ gives . That constraint is not active; the point is infeasible and the active set is not defined there at all. Violation and equality are different relations, and only one of them is activity.

Not a reason to count it: an equality constraint distinguishing points. In standard form both structural rows are active at every feasible point. Citing them to explain why this point is a vertex rather than that one explains nothing, since they are equally active at both.

Not enough for a vertex: three active constraints in two variables. If two of the three normals are parallel, say $x_1\le 3$ and $2x_1\le 6$, whose normals are $(1,0)$ and $(2,0)$, then three active constraints have rank $2$ at best, and possibly less. It is the rank that decides, and counting is not a substitute for it.

Not removable: an inactive constraint. Dropping $C_1$ from the region because it is slack at $(1,1)$ changes the region: $(3,3)$ then becomes feasible, and the vertex at $(3,1)$ disappears. The constraint was inactive at one point, not inert.

The word 'inactive' suggests a constraint that is not doing anything, and the suggestion is wrong in a way that has consequences.

The tempting move. Solving a program, you observe that the constraint $x_1+x_2\le 4$ has slack at the point you are examining, and conclude it can be dropped to simplify the problem.

Why it fails. Activity is a property of a point. Take the region $x_1+x_2\le 4$, $x_1\le 3$, $x_1,x_2\ge 0$, and examine $(1,1)$, where the first constraint indeed has slack. Now drop it. The region was a quadrilateral with vertices $(0,0)$, $(3,0)$, $(3,1)$ and $(0,4)$; without that constraint it becomes an unbounded strip running upward between $x_1=0$ and $x_1=3$. The vertex $(3,1)$ is gone and so is the bound on $x_2$. Maximise $x_2$ over each and the answers are $4$ and no finite optimum. A different problem with a different verdict.

The general statement. A constraint's job is to exclude points, and a constraint inactive at $\overline{x}$ is excluding points elsewhere. What can be dropped without changing the region is a redundant constraint, one whose removal leaves the feasible set unchanged, and redundancy is a property of the constraint against the whole system, decided globally, not by inspecting one point.

The confusion this actually causes. In the simplex method a learner who has conflated the two expects the algorithm to discard slack constraints as it goes. It does not. Every constraint remains in the system for every iteration; what changes is which are active at the current basic feasible solution, and a constraint slack at this corner may be exactly the one that limits the step at the next.

1. For the region $2x_1+x_2\le 8$, $x_1+3x_2\le 9$, $x_1,x_2\ge 0$, give the active set at $(4,0)$, at $(3,2)$, and at $(1,1)$, and classify each point.

2. At a point where three constraints are active in two variables, what must be true of the normals for the point to be a vertex? Give a case where three are active and the point is still not a vertex.

3. In the standard-form system $x_1+x_2+x_3=5$, $x_1,x_2,x_3\ge 0$, how many nonnegativity restrictions must be active for a point to be a vertex? Name one such point.

4. A colleague says: 'The third constraint has slack at our current solution, so I removed it from the model and re-solved.' What could go wrong, and what would have justified the removal?

5. Explain why, in standard form, the structural equality constraints never help to distinguish a vertex from an interior point.

A constraint is active at a feasible point when it holds with equality there. The active set collects all of them, and it includes equality constraints, active everywhere, and nonnegativity restrictions, active wherever a component is zero.

Activity belongs to the point, not to the constraint. The same inequality is active at some feasible points and inactive at others, so 'this constraint is binding' is incomplete without saying where.

What classifies a point is the rank of the active normals, not their number. Rank $n$ blocks every direction and the point is a vertex; each unit of shortfall leaves one more free direction, down to an interior point where nothing is active.

An inactive constraint is not removable. Removal is licensed by redundancy, which is a global property of the constraint against the whole system, and the two are routinely confused.

This vocabulary is what the next three ideas are stated in. A degenerate corner has more active constraints than it needs; two corners are adjacent when their active sets differ by one; and the simplex method's step is one constraint released and another acquired.