Why do we need duality in linear programming or convex optimization? 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 ?
 A: 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}
A: 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 factible solution of P and z* is
the value of some factible 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.
