Duality

Question 1

How many ways do we have that we can use to derive the dual problem?

Answer 1

There are two ways

Question 2

Assume we want to find an upper bound of the optimal objective funciton value z-star. How can we do this?

Answer 2

We can examine one of the constraints that possess the same variables as the objective function, and multiply the constraint (on both side) by a value that makes each of the coefficients of the variables in the constraint LARGER than their corresponding objective function coefficients. when we then look at the new b-side value, we know that this value will always be smaller larger than any z-value. This is because regardless what value our variables are, the z-value coefficents will just never reach the same value before infeasible.

This gives us a rough estimate of upper bound z-score.

it can be even better to combine different constraints in a linear way and create a new constraint that provides an even better bound.

Question 3

How can we guess the best combinaiton of constraints that yield the best bound?

Answer 3

Instead of guessing, we can formulate an LP problem that solve this for us.

We need the coefficients of the constraints, and we need a set of weights (variables) that we want to solve for and find out how much of each constraint to use.

For instance:

7v1 + 16v2 >= 20
10v1 + 12v2 >= 18

We also demand that the weights are non-negative.

Then we need the objective function:

min w = 3600v1 + 5400v2

This is a dual problem to the primal problem.

Question 4

Can the dual problem always be given an interpretation economically?

Answer 4

No, but we always interpret the dual variables as shadow prices/marginal price.

we can never guarantee that the dual problem solve some sort of practical scenario. It may be purely theoretical problem with no other meaning.

Question 5

Elaborate on the process of deriving the dual problem

Answer 5

We start with the idea of finding a good bound for the z-value.

We can find an upper bound by considering how we can combine constraints.

We want to consider every constraint.
We consider a linear combinaiton of each coefficient in ONE of the columns in the constraint matrix.
This linear combination MUST be larger than this column’s corresponding objective function coefficient in order to make sure that the constraint value multiplier make the final result larger than or equal to the z-bound we want.

We have to do this for every coefficient in the objective function, which means that we transpose the constraint matrix and make linear combinations.

We take each column in the constraint matrix, and multiply it by a weight. This weight is a single-valued variable called the dual variable for this corresponding column.

Question 6

Why is duality important?

Answer 6

Duality is apparantly very important for developing new methods for various types of difficult optimziation problems.

Question 7

Give the six relationships between primal and dual problem

Answer 7

Firstly, we refer to “normal form”. Normal form is how we typically want things to be.
A variable is in normal form if it is defined as non-negative.

A constraint is in normal form if it is a <= constraint in a max problem, and a >= in a min problem.

1) A variable in normal form i nthe primal problem gives a constraint in nromal form in the dual problem

2) A constraint in normal form in the primal problem gives a variable in normal form in the dual problem

3) A variable defined as xj <= 0 in the primal gives a constraint in the dual of reverse type compared to normal form.

4) A constraint in the primal of reverse type compared to normal form gives a variable defined as vi <= 0 in the dual

5) A free variable in the primal gives an equality cnstraint in the dual

6) An equality constraint in the primal gives a free variable in the dual

Question 8

Elaborate on weak duality

Answer 8

Weak duality says that if we have a feasible solution in one of the problems, this solution is an upper bound for the other problem.

Or, not necessarily upper bound, but rather: A feasible solution to one of hte problems provides an optimistic estimation of the optimal objective function value to the other problem.

cx <= bv

Question 9

What is the theorem that follows from the weak duality theorem?

Answer 9

If x and v are feasible solutions to the primal and dual problem, and we have that cx = bv, we know that x and v are optimal solutions.

Question 9

Elaborate on strong duality

Answer 9

If either primal or dual problem has a bounded optimal solution, the same holds for the other problem, and the two objective function values are equal at optimum.

cx = bv

Question 10

elaborate on the dual theorem

Answer 10

The dual theorem says that if xb=B^(-1)b is an optimal basic solution to (P), then v=cbB^(-1) is optimal solution to (D) and that z-star = w-star.

What we need to prove is that solving simplex, and looking at the slack-portion in objective function row, which holds the values of cbB^(-1), will yield the optimal values of the dual problem.

how do we prove this? The proof consists of 3 steps:

1) Prove that v is feasible in (D).
2) Show that objective function values for xb and v are the same
3) Since xb is feasible in (P) nad v is feasible in (D), and the objective function values are equal, we use the theorem of weak duality to state that v = cbB^(-1) is an optimal solution to (D).

Question 11

Elaborate on the proof of the dual theorem

Answer 11

The dual theorem says that the solution to the dual problem is actually found in the portion of the final simplex tableau of the primal problem that corresponds to the slack-variable section in the objective function row.

In order to prove that this is the case, we need to do 3 steps:
1) Prove that if this happens to be the case, the solution v is feasible in (D).
2) Show that the values of both objective functions are the same when this is the case.
3) Conclude with weak duality that this is how it is.

We start with the primal problem, and split it using matrix notation.

max z = cbxb + cnxn
s.t. Bxb + Nxn = b
xb, xn >= 0

This gives us the following dual problem:

min w = bv
s.t.
B^(T)v >= cb
N^(T)v >= cn
v free

We assume that xb = B^(-1)b is an optimal basic solution, and that v = cbB^(-1) is optimal solution to dual.

We want to prove feasibility in (D). We look at the two types of constraints in (D).

First we have B^(T)v >= cb
We interchange B^(T) and v, which leads to a swap in transposes:

v^(T)B >= cb

Now we replace v^(T) with the assumed value of cb^(T)B^(-1), which gives us:

cb^(T) >= cb^(T), which of course applies.

Now, onto the next set of constraints, which are the non-basic related ones.

We have that N^(T)v >= cn
We swap the position and thus their transpose like before:

v^(T) N >= cn^(T)

Now we enter our assumes result of v^(T) = cb^(T)B^(-1), which gives us:

cb^(T)B^(-1) N >= cn^(T)

This is the same as:

cn^(T) - cb^(T)B^(-1) N <= 0

We recognize this LHS as the identity of reduced cost in optimal tableau. Since we assume optimality, we know that this is indeed smaller than or equal to 0.

Now we have proved that v=cb^(T)B^(-1) is indeed feasible in (D).

The next step is to show that the objective function values are identical as well.

We know that in (P), obj func value is cb^(T)B^(-1)b

Since we have shown that v = cb^(T) B^(-1) is feasible in (D), we can find its value:

w = b^(T)v = v^(T)b = cb^(T)B^(-1)b, which is the same as the (P).

Since xb is feasible in P, and v is feasible in D, and the objective function values are equal for the two solutions, we can use the theorem of weak duality and state that v^(T) = cb^(T) B^(-1) is an otpimal solution to D.

This entire proof is simple to understand if the proof of weak duality is understood. to be clear, it is actually really simple. We know that the solution to (D) is optimistic in regards to (P) if x and v are feasible in their respective problems. Since we have showed that the bound offered by (D) is the same as the same as the objective function value from (P), we can conclude with the fact that the solution to the dual problem is provided by the slack-coefficeints in objective row.

IMPORTANT: Recall the objective here. We want to show that if xb = B^(-1)b is an optimal basic solution, then v^(T) = cb^(T) B^(-1) AND z star = w star.

this proof use WEAK duality. This means that we can only make assumptions from primal to dual, and not from dual to primal.

Question 12

What does weak duality say, in a sentence?

Answer 12

Solving the dual problem provides an upper (or lower if minimization primal problem) bound to the primal, as long as there is a feasible solution.

Question 13

What is the complementary slackness constraint?

Answer 13

A relationship between a primal constraint “i” and the corresponding dual variable vi:

vi (bi - ∑aij xj [j=1, n]) = 0

This says that either the dual variable is 0, or the slack variable has value 0. If the slack variable has value 0, it would mean that the constraint is binding.

There is also a complementary slackness constraint that relates a primal variable and a constraint in the dual:

xj (∑aij vi - cj) = 0

Indicates that either the primal variable has the value 0, or the const

Question 14

what is the complementary slackness theorem?

Answer 14

Assume x and v are feasible solutions in P and D respectively. Then x and v are optimal solutions to respective problem if and only if the complementary slackness constraints

v(b - Ax) = 0

and

x(Av - c) = 0

are satisfied

Question 15

Define strong duality

Answer 15

If either P or D has a bounded optimal solution, the same holds for the other problem, and the two objective function values are equal at optimum, i.e.

cx = bv

Question 16

Informally, what does the strong duality theorem “say”?

Answer 16

It says that if one problem has an optimal solution, so does the other one problem.

If primal problem has unbounded optimal solution, the dual problem has no feasible solution.

If primal problem has no feasible solutions, the dual is unbounded OR infeasible as well.

Question 17

If a constraint is not active, its corresponding shadow price has …

Answer 17

The value 0

Question 18

if a variable is basic, its coefficient value in objective function row is …?

Answer 18

0

Question 19

Name an omportant fact about degeneracy`

Answer 19

We can have coefficents in the objective function row that are 0, and still represent non-basic variables.

Question 20

Recall degeneracy

Answer 20

Degeneracy means that we can change the basis and move to another solution, but keep the objective function value the same

Question 21

Is there a relationship between a primal constraint “i” and the corresponding dual variable “vi”?

Answer 21

Yes, it is given by the complementary slackness constraint:

vi (bi - ∑aij xj [j=1, n]) = 0

This is a relationship that tells us that either the constraint must be binding, or the corresponding shadow price/dual variable must be 0.

Intuition says that a shadow price of 0 means that the resource constraint is such that it does not influence us at the current optimal solution. For instance, it could be a production capacity constraint saying that our factory can only handle 1000 units per hour, but in the optimal solution, we find that it is better to produce 500 units per hour. In such a case, it makes no sense to see an increase in objective function value Z by relaxing the constraint. therefore, the shadow price/dual variable holds the value 0.
However, if we find that it is optimal to produce at the limit, 1000 units per hour, it is very likely that there is an interval that extends beyond 1000 units per hour that would be more optimal if we had the additional capacity. The exact amount of “how much better” an additional unit capacity would carry, is the shadow price/dual variable value. If we have the optimal solution, and this was the case, then it would also be represented as the reduced cost (since non-basic variable in type of slack as the constraint is binding) which is the amount that z increase by if we add a unit of capacity.

mean that the slack-variable that it is associated with happens to be a non-basic variable. Because of this, the same coefficient that represent shadow price, also represent reduced cost of z by increasing the slack variable one unit

Question 22

Soemthing slightly tricky about complementary slackness constriants…?

Answer 22

both parts can be zero. This would happen if the shadow price = 0 and the constraint is binding. This represent cases where we are “producing” (or doing something else) at the limit of the constraint, but relaxing the constraint actually serves no benefit. Very special case.

Question 23

what can we use complementary slackness constraints for?

Answer 23

the complementary slackness constraint works in a way that if we are given a non-zero shadow price, we automatically know that its corresponding constraint is binding, and vice versa, and can use this to establish constraint utilization/resource utilization of the primal problem if we are given the optimal solution to the dual problem

Question 24

is there a relation between a primal variable xj and a cosntraint in the dual problem?

Answer 24

Yes, it is a complementary slackness that applies here as well.

xj (∑aijvi[i=1, m] - cj ) = 0

This says that either the primal variable is 0, or the

Question 25

is there a difference between complementary slackness of the two types?

Answer 25

it works both ways, and it works exactly the same way. either the constraint is binding, and its corresponding additional benefit in relaxing the constraint is positive, or the constraint is not binding and there is no benefit in relaxing the constraint, or the constraint is binding and there is no relaxation benefit. 0 and nonzero, nonzero and 0, 0 and 0 cases

Question 26

What happens with complementary slackness conditions if constraints are not in normal form?

Answer 26

we can have complementary slackness cases where one of the parts, for instance the shadow price, is negative. For instance, a negative shadow price would indicate that relaxing the constraint actually makes our case worse. This happens if we do not actually “relax” the constraint, which would happen if the constraint is not in “normal form” (normal form as in <= constraints for max problems, >= for min problems). Flipped constraint sign would flip the shadow price sign

Question 27

Elaborate on the process of using complementary slackness for verification

Answer 27

Given a basic feasible solution, we can check with the dual problem whether this solution is optimal or not by using the complementary slackness conditions.

There are two sets of complementary slackness conditions: one for each type of problem. both say the same however, but apply to the opposite problem.

We use these conditions to figure out which constraints in the primal and dual that are binding, and which variables we know are zero (from the provided feasible solution to the primal), and find a system of equations that we can solve which gives us the values of the dual variables. Then we check if these variable values satisfy the dual problem, i.e. if the solution is dual feasible. If it is, we know from weak and strong duality and this is optimal solution. If not, we know that the solution is not optimal.