Primal-Dual Scheme

• The primal is the original form of a linear program. It is of the form

• The dual is another LP derived from the original. The objective is inversed (i.e., if the primal maximizes, the dual minimizes)

  That is, the constraints become variables and the variables become constraints.

  • The above is the symmetric form of the dual.

  • The asymmetric form is one where we get rid of the non-negativity constraints. That is

Theorems §

• The weak duality theorem states that the objective value of the dual LP at any feasible solution is bound on the objective of the primal LP at any feasible solution. More formally if the primal LP has a maximization objective ¹

• The strong duality theorem states that the optima of the primal, if it exists, is equal to the optima of the dual. That is, for a maximization objective

• Consider a linear program in canonical form with an optimal basic feasible solution corresponding to the basis . The vector is an optimal solution to the dual

Complementary Slack Theory §

• Intuition: If we interpret the primal as a resource allocation problem, the dual LP is a resource valuation problem. It has similarities to pricing for supply and demand

  • On the consumer side, we have the primal problem. We want to mix good dictated by the ’s . The value of the mixing of these goods is governed by their marginal prices . The constraints are determined by the material available, the , and the amount of each material to produce each good (). The constraint is stated as as we have constraints on the raw materials. The consumer’s goal is to maximize profit.
  • On the producer side, we have the dual problem. We control the price of one unit of each material . Each good that can be made derives from these materials and the relation is captured by . It should be the case that since otherwise, the producer can just produce and sell the goods directly. dictates the overall target level of manufactured raw material. The producer’s goal is to minimize the production cost

• Consider the linear program

  Let be the optimal basis with solution , where . The corresponding dual solution is

  If we perturb by , the solution becomes . The corresponding increment in the cost function is called the sensitivity which is calculated as

• The sensitivity of the optimal cost to small changes in the constraints is given by the solution of the dual.

• The Complementary Slack Theorem of the Symmetric Form states the following: is the -th column of . Let and be feasible solutions for the primal and dual. A necessary and sufficient condition that they both be optimal is that

  • .

• The Complementary Slack Theorem of the Asymmetric Form states the following: is the -th column and is the -th row of . Let and be feasible solutions for the primal and dual. A necessary and sufficient condition that they both be optimal is that

• Another way to say the Complementary Slack Theorem is that:

  • If a dual variable is greater than (slack), then the corresponding primal constraint must be an equality (tight).
  • If a primal variable is greater than (slack), then the corresponding dual constraint must be an equality (tight).
  • Variables in one problem are complementary to constraints in another
  • A constraint is slack if the slack variable is positive. A variable constrained to be non-negative has slack if it is positive. There cannot be slack in both a constraint and the associated dual variable

Links §

• Linear and Nonlinear Programming by Luenberger and Ye - Ch. 4

Footnotes §

1. See Luenberger and Ye 4.2 for the proof. ↩