In this below, we make a brief introduction on Linear Programing in finite dimension.
Consider following optimization problem: For a given matrix and two column vectors
and
maximize linear cost
over the constarints
For the notational convenience, let’s denote this in the following succinct way:
The value of the problem (LP) is closely connected to the value of the dual problem given as below:
In the above, is the transpose of
.
The two important facts reveal the relation of the value functions of the above dual problems: one is called weak duality theorem and the other strong duality theorem.
Weak duality gives upper bound of the value without any assumption, and its proof is short. This result also holds under inifinite dimensional linear programing.
Proposition 1 (Weak duality)
.
Proof: For arbitrary adimissible for (LP), and
adimissible for (LP’), we have
Strong duality gives sufficient condition for the equality in Weak duality, and the proof is more involved.
Proposition 2 (Strong duality) Assume (LP) has a finite value
, then
.
Proof: later.