Why do we need duality in linear programming or convex optimization?

Question

I'm learning convex optimization, just get started with linear programming, and there is such a thing as duality in linear programming.

Here is my problems, why there is a dual problem for a linear program, how to prove it? And why do we need the dual problem when solving the primal problem ?

Answer 1

I hope my post answers your question. I'm afraid my english is not that good, but i hope you'll get what i mean

How to get the dual problem:

Let $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^{m}$, $c \in \mathbb{R}^{n}$ for my whole post.

Let $x \in \mathbb{R}^{n}$. Then the following statements hold: \begin{equation} \min \{(b-Ax)y : y\in\mathbb{R}^{m} \}= \begin{cases} - \infty & \text{if } Ax = b \\ 0 & \text{if } Ax \neq b \end{cases} \\ \end{equation} If $Ax=b$, then $b-Ax = 0$ and hence $(b-Ax)y = 0$ for each $y \in \mathbb{R}^{m}$. If $b-Ax = r \neq 0$, $y$ can be choosen arbitrarily small.

Let $y \in \mathbb{R}^{m}$. Then the following statement holds: \begin{equation} \max \{(c-A^{T}y)x : x \in\mathbb{R}^{n}\} = \begin{cases} + \infty & \text{if } c-A^{T}y \nleq 0 \\ 0 & \text{if } c-A^{T}y \leq 0 \end{cases} \end{equation} If $c-A^{T}y \leq 0$, then for each $x \geq x$ the term $c-A^{T}y$ is lesser than, or equal zero, which leads to the maximum being $0$. If $c-A^{T}y \nleq 0$, then at least one component $(c-A^{T}y)_{i} > 0$. By setting $x_{i} = t$, and all other components of x to $0$, the whole term goes to $+\infty$ for $t \rightarrow +\infty$.

This prooves following lemma: \begin{equation} max\{c^{T}x : x \geq 0,b-Ax=0\}=\max_{x\geq 0}\min_{y} c^{T}x+(b-A^{T}y) \\ \min_{y}\max_{x \geq 0}b^{T}y+(c-A^{T}y)^{T}x = \min_{A^{T}y \geq c} b^{T}y \end{equation}

Lemma (Minimax Lemma): Let $X,Y$ be two sets, $f: X \times Y \rightarrow \mathbb{R}, (x,y) \mapsto f(x,y)$. Then the following holds: \begin{equation} \max_{x \in X}\min_{y \in Y} f(x,y) \leq \min_{y \in Y}\max_{x \in X} f(x,y) \end{equation} Proof: \begin{equation} f(x,y) \leq \max_{x\in X}f(x,y) =: g(y) \\ h(x) := \min_{y \in Y}f(x,y) \leq \min_{y \in Y} g(y) := \bar g \\ \max_{x \in X}h(x) \leq \bar g \end{equation}

The following theorem is called weak duality and leads to the dual problem: \begin{align} \max \{c^{T}x : x \geq 0, Ax-b = 0\} & = \max_{x \geq 0} \min_{y} c^{T}x+(b-Ax)^{T}y \\ & \leq \min_{y}\max_{x \geq 0} b^{T}y-(A^{T}y-c)^{T}x & \text{(Minimax Lemma)} \\ & = \min \{b^{T}y : A^{T}x - c \geq 0 \} \end{align}

To sum things up: (P) is called primal problem, (D) is called dual problem: \begin{align} (P) & \max c^{T}x, Ax=b, x \geq 0 \\ (D) & \min b^{T}y, A^{T}y \geq c \end{align}

Answer 2

This is only a partial answer but, in my opinion, one of the best consequences of having a duality is the following:

A linear programming P has an optimal solution if and only if P* has
an optimal solution and the values of both optimal solutions are the
same.

Moreover if z is the value of some feasible solution of P and z* is
the value of some feasible solution of P* then z<=z*.

This can be used to show the optimality of some solutions and, in fact, is one of the main steps in the proof of the convergence of the Simplex algorithm.