Graphical understanding of the primal and dual problem

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?

• Please, take a look at this and this links. Commented Apr 27 at 4:57
• Dear Derd, if you want I can show you in my answer how relates part of slack/surplus variables and part of variables (free parameters) to positive dual variables. Commented Apr 27 at 12:08
• If you're hoping to plot the primal and the dual feasible regions on the one set of 2D axes and see some sort of relationship then you are going to be disappointed. Commented May 26 at 15:29

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 >$$