Graphical understanding of the primal and dual problem

Question

I have a relatively simple question. Assuming we have a simple numerical example of an LP with two decision variables and two constraints (non-negativity excluded), how can I visualize the graphical relationship between the dual and primal problem? How do both lead to the same solution?

Answer 1

Given a real function of $n$ real variables

$ {\displaystyle \Phi:A \subset \mathbb{R^n} \to \mathbb{R}} $

defined on the open set $A$ and conditioned by constraints on the manifold $M$ of $\mathbb{R^n} $, we wish searching for the maximum or minimum points of $\Phi $ restricted to $M$.

The variety $M$ is thus assigned by means of a system of $m$ equations $F_i (\mathbf x )=0$ where $ {\displaystyle F_i: \mathbb{R^n} \to \mathbb{R}} $ for $i=1, \cdots , m $ under the the hypothesis that the rank of the Jacobian matrix $J$ is equal to $m$ at an appropriate point $\mathbf x_0 $. The manifold $M$ is an m-dimensional surface. If Implicit function theorem (Dini's theorem) holds, then the m equations defining the variety $M$

$F_i(x_1, \cdots, x_r, x_{r+1}, \cdots , x_{r+m})=0 $ for $i=1, 2, \cdots , m$

can be represented by m functions $ {\displaystyle f_i: A \subset \mathbb{R^r} \to \mathbb{R}} $ as graph of functions (explicit forms for $F_i$) in the neighbourhood of point $\mathbf x_0 $. As consequence, the manifold $M$ can be defined implicitly for every point $\mathbf x \in A $ as an r-dimensional surface

$M=\{ \mathbf x \in U(\mathbf x_0) \quad | \quad x_{r+k}=f_k(x_1 , x_2 , \cdots , x_r ) \quad k=1, 2, \cdots , m \}$

The $r$ local variables $ x_1 , x_2 , \cdots , x_r $ provide the parametric representation of the surface for each $\mathbf x$ falling inside the neighbourhood of the point $\mathbf x_0$.

The variables $x_{r+1} , x_{r+2} , \cdots , x_{r+m}$ can be regarded as slack/surplus variables.

To each point of the manifold $M$ of dimension $r$ it is possible to associate the tangent space $T(\mathbf x)$.

The dimension of the tangent plane at one of its points $\mathbf x_0 \in M$ is equal to the dimension of the surface $M$ or the number of $r$ parameters if $M$ is defined parametrically. If the $M$ surface is defined by a system of equations $r=n-m$, the dimension of the tangent plane is equal to the dimension $n$ of the space decreased by the number $m$ of equations.

The normal space to $M$ in $\mathbf x_0$ is defined as $N(\mathbf x_0)= \{ \mathbf u \in \mathbb{R^n} \quad | \quad < \mathbf u, \mathbf v> =0 \quad \forall \mathbf v \in T(\mathbf x_0)\}$

Identifying $\mathbf u =\mathbf F $ we obtain $ \operatorname J_{F} ( \mathbf x_0 ) \cdot \mathbf v = 0 $ for every $ \mathbf v \in T(\mathbf x_0)$.

It follows that $ \nabla F_i (\mathbf x_0) \in N(\mathbf x_0)$ with $i=1, \cdots , \cdots , m$.

Since the rank of $ \operatorname J_{F} ( \mathbf x_0 ) $ is equal to $m$, we have that $ \nabla F_1 (\mathbf x_0), \cdots , \nabla F_m (\mathbf x_0)$ are linearly independent. Therefore $N(\mathbf x_0)$ is generated by these vectors: the gradient of $F$ at $\mathbf x_0$ is perpendicular to the manifold $M$.

If $N(\mathbf x_0)$ is generated by $ \nabla F_1 (\mathbf x_0), \cdots , \nabla F_m (\mathbf x_0)$ then there exist m scalars $ \lambda_1, \cdots , \lambda_m$ called Lagrange multipliers such that $ \nabla \Phi (\mathbf x_0)$ can be expressed as a linear combination of the gradients of $\mathbf F$ at $\mathbf x_0$.

If $\Phi$ has a maximum/minimum at $\mathbf x_0$, the gradient of the objective function $\Phi$ is perpendicular to the manifold $M$.

Once the reader sees $\Phi$ as a dot product $\Phi = < \mathbf c, \mathbf x >$ with $\mathbf c$ constant, it is easy to visualize the graphical relationship between the dual and primal problem.

Primal

$\mathbf x’ \in \mathbb{R^r} $, $\mathbf c’ \in \mathbb{R^r}$, $\mathbf b \in \mathbb{R^m} $

$z=< \mathbf c’, \mathbf x’ >=c’_1x’_1 + c’_2x’_2 + \cdots + c’_rx’_r$

$A’\mathbf x \leq \mathbf b$

$A’$ $m$x$n$ matrix having rank equals to $m$

Let $n=r+m$, we can write $\mathbf c = (c’_1, \cdots , c’_r, 0, \cdots , 0)$ and we can introduce the $\Phi$ as

objective function

$\Phi := < \mathbf c, \mathbf x >=c’_1x_1 + \cdots + c’_rx_r + 0s_1 + 0s_m = z$

$ \mathbf x $ subject to be in $= \overline{\Omega} $

Feasible Region, $\overline{\Omega} = \overset{\circ}{\Omega} \cup \partial \Omega$

$\sum_{j=1}^r a_{ij} x’_j – b_i + s_i$ for $i=1, \cdots , m$

It is sufficient to write the matrix $A$ like $A=(A’|I)$ where $I$ is the $m$x$m$ Identity matrix.

The manifold $M$ is defined through $m$ equations of following type $F_i (\mathbf x)=0$:

$F_i(x_1, \cdots, x_r, s_1, \cdots , s_m)= f_i(x_1, \cdots, x_r)+s_i = g_i(x_1, \cdots, x_r)-b_i+s_i=0 $ for $i=1, 2, \cdots , m$

once slack/surplus variables are introduced like

$s_i = |b_i - \sum_{j=1}^r a_{ij} x_j | \geq 0 $ for $i=1, \cdots , m$

The manifold $M$ is implicitly defined as an r-dimensional surface $M=\{ \mathbf x \in \overset{\circ}{\Omega} \quad | \quad s_k=g_k(x_1 , x_2 , \cdots , x_r ) – b_k \quad k=1, 2, \cdots , m \}$

Lagrangian function

$\mathcal{L}(\mathbf x, \mathbf \lambda)= < \mathbf c, \mathbf x > + < \mathbf \lambda, \mathbf b – A \mathbf x >= < \mathbf \lambda, \mathbf b > + < \mathbf c – A^t \lambda, \mathbf x >$