Duality Theory

Question 1

Primal Problem in standard form

Answer 1

min cᵀx

s.t. Ax=b , x≥0

Question 2

primal problem in canonical form

Answer 2

min cᵀx

s.t. Ax≥b , x≥0

Question 3

dual problem in canonical form

Answer 3

max bᵀy

s.t. Aᵀy≤c y≥0

Question 4

dual problem in standard form

Answer 4

max bᵀy

s.t. Aᵀy≤c y∈ℝᵐ

Question 5

dimensions of A

Answer 5

mxn matrix
m rows
n columns

Question 6

How to find the dual problem

Answer 6

1. find the matrix form of the primal problem
2. make sure the primal is in standard or canonical form
3. find the dual using the known ‘formula’

Question 7

proposition. The dual of the dual.

Answer 7

The dual of the dual is primal.

Question 8

Weak Duality Theorem

Answer 8

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

Question 9

Primal feasible region

Answer 9

Fp = {x: Ax = b, x≥0}

Question 10

Dual feasible region

Answer 10

Fd = {(y,s): Aᵀy + s = c, s≥0}

(we introduced slack variables into the dual problem.

Question 11

Duality gap

Answer 11

cᵀx - bᵀy

Question 12

corollary. Unbounded primal.

Answer 12

If the primal Lp is unbounded (cᵀx-> - infinity) then the dual LP must be infeasible

Question 13

corollary. Unbounded Dual.

Answer 13

If the dual LP is unbounded, then the primal LP is infeasible.

Question 14

Corollary. Optimal in dual/primal

Answer 14

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

Question 15

Strong Duality Theorem

Answer 15

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*

Question 16

P optimal <=>

Answer 16

D optimal

Question 17

P unbounded =>

Answer 17

D unfeasible

Question 18

D unbounded =>

Answer 18

P infeasible

Question 19

P infeasible =>

Answer 19

D unbounded or infeasible

Question 20

D infeasible =>

Answer 20

P unbounded or infeasible

Question 21

Theorem. Optimality Conditions.

Answer 21

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*

Question 22

Theorem. Optimality Conditions (reformulated)

Answer 22

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

Question 23

How to use the optimality conditions to find an optimal solution

Answer 23

1. Put the primal into standard form and find the feasibility of the primal
2. Find the Dual. Determine the feasibility of the dual
3. find the complementary slackness condition.
   Since x,s≥0 the only way xᵀs = 0 is if xᵢsᵢ=0
4. By complementary slackness find that since some x*ᵢ not equal to 0, then some slacks equal 0
5. Solve the dual feasibility equations simultaneously using the fact that the slacks are equal to 0.
6. 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

Question 24

Strictly Complementary Solution

Answer 24

A solution is called a strictly complementary solution if the solution satisfies that (x)ᵀs = 0 and x* + s* > 0

Question 25

How to check if (a,b) is a solution to an LP problem.

Answer 25

1. write the problem in standard form (and find the feasibility of the primal)
2. Write the LP problem in matrix form
3. Find the dual (and find the feasibility of the dual)
4. Find the complementary slackness condition (objective function of primal=objective function of the dual)
5. consider the point (a,b) check it satisfies the primal (input into the feasibility of the primal to find values of the slack)
6. compute the complementary slackness with (a,b) to find the ys.
7. 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

Question 26

Theorem. optimal solution optimality conditions.

Answer 26

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

Question 27

Theorem Strict Complementarity

Answer 27

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