1
$\begingroup$

Main Question

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

enter image description here

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?

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ This makes it extremely clear, thank you! (+1) $\endgroup$ – Clarinetist Jun 26 '18 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.