Duality Theory Flashcards
Primal Problem in standard form
min cᵀx
s.t. Ax=b , x≥0
primal problem in canonical form
min cᵀx
s.t. Ax≥b , x≥0
dual problem in canonical form
max bᵀy
s.t. Aᵀy≤c y≥0
dual problem in standard form
max bᵀy
s.t. Aᵀy≤c y∈ℝᵐ
dimensions of A
mxn matrix
m rows
n columns
How to find the dual problem
- find the matrix form of the primal problem
- make sure the primal is in standard or canonical form
- find the dual using the known ‘formula’
proposition. The dual of the dual.
The dual of the dual is primal.
Weak Duality Theorem
Let x be any feasible point of the primal problem x∈Fp and assume y to be any feasible point of the dual problem (y,s)∈Fd. Then,
cᵀx ≥ bᵀy
Primal feasible region
Fp = {x: Ax = b, x≥0}
Dual feasible region
Fd = {(y,s): Aᵀy + s = c, s≥0}
(we introduced slack variables into the dual problem.
Duality gap
cᵀx - bᵀy
corollary. Unbounded primal.
If the primal Lp is unbounded (cᵀx-> - infinity) then the dual LP must be infeasible
corollary. Unbounded Dual.
If the dual LP is unbounded, then the primal LP is infeasible.
Corollary. Optimal in dual/primal
if x is feasible to the primal LP and y is feasible to the dual LP and cᵀx = bᵀy then x must be optimal to the primal LP and y must be optimal to the dual LP
Strong Duality Theorem
If both the primal and the dual problems have feasible solutions x,y respectively, then they both have optimal solutions and for any y primal optimal solution x* and dual optimal solution y* we have that cᵀx* = bᵀy*
P optimal <=>
D optimal
P unbounded =>
D unfeasible
D unbounded =>
P infeasible
P infeasible =>
D unbounded or infeasible
D infeasible =>
P unbounded or infeasible
Theorem. Optimality Conditions.
Consider the standard LP problem: min cᵀx s.t. Ax=b , x≥0 where b∈Rᵐ, c∈Rⁿ, A∈Rᵐˣⁿ. Then x* is an optimal solution to the LP iff there exists y* s.t. the following three conditions hold (1) Aᵀy*≤c (2) Ax* = b, x*≥0 (3) bᵀy* = cᵀx*
Theorem. Optimality Conditions (reformulated)
Consider the standard LP problem: min cᵀx s.t. Ax=b , x≥0 where b∈Rᵐ, c∈Rⁿ, A∈Rᵐˣⁿ. Then x* is an optimal solution to the LP iff there exists y* s.t. the following three conditions hold (1) Aᵀy*+s* = c, s*≥0 (2) Ax* = b, x*≥0 (3) x*ᵀs* = 0
How to use the optimality conditions to find an optimal solution
- Put the primal into standard form and find the feasibility of the primal
- Find the Dual. Determine the feasibility of the dual
- find the complementary slackness condition.
Since x,s≥0 the only way xᵀs = 0 is if xᵢsᵢ=0 - By complementary slackness find that since some x*ᵢ not equal to 0, then some slacks equal 0
- Solve the dual feasibility equations simultaneously using the fact that the slacks are equal to 0.
- Calculate the final slack/ check if it is zero.
- If it is not equal to 0 then corresponding x is 0 => primal feasibility can now be solved (simultaneously) to get optimal solution
- if it is equal to 0 optimal solution = 0
Strictly Complementary Solution
A solution is called a strictly complementary solution if the solution satisfies that (x)ᵀs = 0 and x* + s* > 0
How to check if (a,b) is a solution to an LP problem.
- write the problem in standard form (and find the feasibility of the primal)
- Write the LP problem in matrix form
- Find the dual (and find the feasibility of the dual)
- Find the complementary slackness condition (objective function of primal=objective function of the dual)
- consider the point (a,b) check it satisfies the primal (input into the feasibility of the primal to find values of the slack)
- compute the complementary slackness with (a,b) to find the ys.
- check if the ys satisfy the dual feasibility
- if they satisfy then (a,b) is a solution
- if they don’t satisfy then (a,b) is not a solution
Theorem. optimal solution optimality conditions.
x and (y,s) are optimal solutions to primal and dual problems respectively iff they satisfy the primal feasibility, dual feasibility and the completementary slackness condition
Theorem Strict Complementarity
If primal and dual problems both have feasible solutions, then both problems have a pair of strict complementary solutions x≥ and s≥0 which satisfy the complementary slackness condition
