0

We are learning about the Geometry of Duality in Linear Programming, and my prof uses the terminology active hyperplane. I'm wondering what the formal definition of this is. I can't seem to find any other references to this online.

From my understanding if we have a linear program

maximize $c^Tx$ such that

$Ax\le b$, and $0\le x$

and are checking if some vector $x'= (x_1,x_2,...,x_n)^T$ solves this LP, we plug in $x'$ giving $Ax'\le b$. Then if for any of the inequalities evaluated with $x'$ gives an equality, or if we get a strict inequality then the corresponding $y$'s in the duel are equal to 0, then those are the active hyperplanes.

As an example suppose we have the following LP:

maximize $x_1+x_2-x_3+2x_4$ such that

$x_1+3x_2-2x_3+4x_4\le 3$

$0x_1+4x_2-2x_3+3x_4\le 1$

$0x_1-x_2+x_3-x_4\le 2$

$-x_1-x_2+2x_3-x_4\le 4$

and we want to see if $x'=(1,0,2,0)^T$ solves this LP, we can plug these values into each equation. The first gives $-3=-3$, the second $-4<1$ which means $y_2=0$ in the dual, the third gives $2=2$, and the last $3<4$ meaning that $y_4=0$ in the dual.

Giving us the active hyperplanes:

$$x_1+3x_2-2x_3+x_4=-3$$

$$-x_2+x_3-x_4=1$$

$$-x_2=0$$

$$-x_4=0$$

Is there a formal definition for this?

MITjanitor
  • 2,690

1 Answers1

1

In general, an inequality constraint $g(x) \le 0$ is considered active (at $x$) if $g(x) = 0$.

If we let $A=\begin{bmatrix} a_1^T \\ \vdots \\ a_m^T \end{bmatrix}$, then the constraint $Ax \le b$ is equivalent to the scalar constraints $a_k^T x \le b$.

If constraint $k$ is active at $x$ (that is, $a_k^T x = b_k$), then $x$ lies on the hyperplane $\{y | a_k^T y = b_k \}$. This, presumably, is what your professor means by an active hyperplane.

copper.hat
  • 172,524