Understanding binding constraints associated with points in $\mathbb{R}^3$

Question

Main Question

This is Figure 2.6 from Bertsimas and Tsitsiklis' Introduction to Linear Optimization:

To make this searchable, here is the text:

Figure 2.6: Let $P = \{(x_1, x_2, x_3) \mid x_1 + x_2 + x_3 = 1, x_1, x_2, x_3 \geq 0\}$. There are three constraints that are active at each one of the points $A$, $B$, $C$, and $D$. There are only two constraints that are active at point $E$, namely $x_1 + x_2 + x_3 = 1$ and $x_2 = 0$.

I don't understand this explanation of Figure 2.6 at all. It is entirely gibberish to me.

---

Context

Apparently Figure 2.6 is an illustration of the following definition:

Definition 2.8 If a vector $\mathbf{x}^{*}$ satisfies $\mathbf{a}_i^{\prime}\mathbf{x}^{*} = b_i$ for some $i$ in $M_1$, $M_2$, or $M_3$, we say that the corresponding constraint is active or binding at $\mathbf{x}^{*}$.

To explain what $M_1, M_2, M_3$ are, define a polyhedron as a set $\{\mathbf{x} \in \mathbb{R}^n \mid \mathbf{A}\mathbf{x} \geq \mathbf{b}\}$, where $\geq$ is componentwise inequality.

Let $P \subset \mathbb{R}^n$ be a polyhedron defined by the following system of inequalities and equality: \begin{align*} \mathbf{a}_i^{\prime}\mathbf{x} &\geq b_i\text{, } \qquad i \in M_1 \\ \mathbf{a}_i^{\prime}\mathbf{x} &\leq b_i\text{, } \qquad i \in M_2 \\ \mathbf{a}_i^{\prime}\mathbf{x} &= b_i\text{, } \qquad i \in M_3 \end{align*} where $M_1, M_2, M_3$ are index sets, $\mathbf{a}_i \in \mathbb{R}^n$, and $b_i \in \mathbb{R}$ for every $i$.

---

My Effort

From a lot of searching, I understand that an active/binding constraint is a constraint such that if the constraint were changed, the feasible region would change. But this idea of constraints active at a point makes no sense to me. Why is $x_2 = 0$ "active" at point $E$? I can't tell you why. Is it because $E$ is in the $x_1$-$x_3$ plane? How am I even supposed to tell?

Answer 1

The definition they provide is pretty obtuse. A constraint is active at a point $\mathbf{x}$ if $\mathbf{x}$ satisfies that constraint with equality. From Wikipedia:

Given a point $x$ in the feasible region, a constraint $$g(x)\geqslant0$$ is called active at $x$ if $g(x)=0$, and inactive at $x$ if $g(x)>0$. Equality constraints are always active.

You say that

I understand that an active/binding constraint is a constraint such that if the constraint were changed, the feasible region would change.

This isn't quite right. For example, consider the feasible region

\begin{align} x_1+x_2\leqslant1\\ x_1\leqslant1\\ x_1,x_2\geqslant0 \end{align}

At the point $\mathbf{x}=(1,0)$, the constraint $x_1\leqslant1$ is active. However, if you draw a picture you'll see that removing $x_1\leqslant1$ doesn't change the feasible region.

Regarding the picture, your intuition is correct: $x_2=0$ is active at $E$ because $E$ lies in the $x_1-x_3$ plane.

Similarly, the point $B$ has three active constraints. Looking at the picture, the point $B=(\beta,0,0)$ for some $\beta>0$. Hence $x_2\geq0$ and $x_3\geq0$ are binding, as is the constraint $x_1+x_2+x_3=1$ (so we can conclude $\beta=1$, even though the axes aren’t labeled).