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 ?


2 Answers 2


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}


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

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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .