Duality Theory

Claudio Arbib

Università di L’Aquila

Operations Research

Duality Theory

Content

• Compatible systems of linear inequalities

• Theorems of the alternative

• Gale’s Theorem

• Fàrkas’ Lemma

• Duality theory in Linear Programming

• Strong Duality Theorem

• The dual of a linear program

• Weak Duality Theorem and other corollaries

• Rules to construct the dual problem

Compatible systems of linear inequalities

• By Fourier’s Theorem a system of linear inequalities Ax < b with x ∈ IRⁿ, A ∈ IR^m×n, b ∈ IR^m

is compatible if and only if another linear system A’x < b’, obtained by conic combination of the given inequalities, with

A’ = [0, A°] ∈ IR^p×n, b’ ∈ IR^p, is in turn compatible.

Theorems of the alternative

• Iterating n times Fourier’s Theorem, one has that Ax < b is compatible if and only if there exist specific conic combinations of its inequalities that produce a compatible system A⁽ⁿ⁾x < b⁽ⁿ⁾, where

A⁽ⁿ⁾ = [0, …, 0] ∈ IR^q×n, b⁽ⁿ⁾ ∈ IR^q

• But [0, …, 0]x < b⁽ⁿ⁾ is compatible if and only if b⁽ⁿ⁾ > 0.

• So in order to have Ax < b incompatible it must be possible to find a vector of multipliers y > 0 that combines

– the rows of A so as to obtain the null row 0

– the components of b so as to obtain a real b_i⁽ⁿ⁾ < 0

Gale’s Theorem

The previous discussion is summarized by

Theorem (Gale): The linear system Ax < b is compatible if and only if the system y > 0, yA = 0, yb < 0 is incompatible.

• Gale’s Theorem is called the first theorem of the alternative, because it expresses the compatibility of one system in terms of the incompatibility of another.

• We call Ax < b the primal system, and y > 0, yA = 0, yb < 0 the dual system.

• With a primal system of the form Ax > b, the dual writes y > 0, yA = 0, yb > 0.

P

Example

Primal system P) 2x₁ + 4x₂ < 5

x₁ – 3x₂ < 6

Dual system D) 2y₁ + y₂ = 0

4y₁ – 3y₂ = 0 5y₁ + 6y₂ < 0

y₁, y₂ > 0

x₂

x₁

(0, 5/4)

(5/2, 0) (0, –2)

(6, 0) (0, 0)

y₁ y₂

D is clearly incompatible (1, –2)

(3, 4)

Fàrkas’ Lemma

Gale’s Theorem is not the only theorem of the alternative:

Theorem (Fàrkas): The linear system (standard primal) Ax = b, x > 0 is compatible if and only if the system

yA > 0, yb < 0

(or, equivalently, the system yA < 0, yb > 0) is incompatible.

Proof: Ax = b, x > 0 ⇔ Ax < b, –Ax < –b, –x < 0 compatible iff (Gale):

z –A = 0, z > 0, z –b < 0.

A –I

b 0

Set z = [u, v, w]. To write uA – vA – w = 0 with w > 0 means (u – v)A > 0.

Calling y = (u – v) the thesis follows.

(Observe that y can have negative components).

x₃

x₁

x₂

Example

Primal system P) x₁ + 3x₂ – 2x₃ = 6 x₁, x₂ , x₃ > 0 Dual system D) y < 0, y > 0, 3y > 0

6y < 0

y

(0, 0, –3)

(6, 0, 0) (0, 2, 0)

P

intersection = {0}

D is clearly incompatible

Comment

• The theorems of the alternative provide us with an important mean to tackle the problem of deciding whether a polyhedron is empty or not

• They allow us to transform a problem with a universal quantifier (∀) in one with an existence quantifier (∃).

In fact a polyhedron Ax < b is empty if for all x ∈ IRⁿ there exists a row i such that a_ix > b_i.

The theorems of the alternative make it unnecessary to check that for all x by looking for just one y such that yb < 0 which belongs to another polyhedron (the dual of Ax < b).

• As a matter of fact, the difference between an “easy” and a “difficult” problem is often marked by the possibility or impossibility of such a practice. For

instance, the very definition of the class NP is based on this distinction.

Duality Theory in LP

• Consider an LP problem in standard form:

P) min cx

Ax = b x > 0

Theorem (strong duality): A feasible solution x* of problem P is optimal if and only if thare exists a y* belonging to

D = {y ∈ IR^m: yA < c}

such that y*b > cx*

x₃

x₁

x₂

Example

Problem P) min x₁ – 2x₂ + 4x₃

x₁ + 3x₂ – 2x₃ = 6 x₁, x₂ , x₃ > 0

D = {y∈IR: y < 1, 3y < –2 , –2y < 4}

i.e., D = {y∈IR: y < 1, y < –2/3 , y > –2}

y P

x* = (6, 0, 0) cx* = +6

y* = –2/3 y*b = –4

x* non optimal

>

x₃

x₁

x₂

Example

Problem P) min x₁ – 2x₂ + 4x₃

x₁ + 3x₂ – 2x₃ = 6 x₁, x₂ , x₃ > 0

D = {y∈IR: y < 1, 3y < –2 , –2y < 4}

i.e., D = {y∈IR: y < 1, y < –2/3 , y > –2}

y P

x* = (0, 2, 0) cx* = –4

y* = –2/3 y*b = –4

x* optimal

<

Strong duality

Proof:

Let x* be feasible for problem P and assume y*b > cx* for some y* ∈ D.

Then the system yA < c

–yb < –cx* namely y[A, –b] < [c, –cx*]

turns out to be compatible.

If we apply Gale’s Theorem to such a system we see that the system [A, –b][ ] = 0, [ ] > 0, [c, –cx*][ ] < 0

is necessarily incompatible.

x λ

x λ x

λ

Strong duality

Proof (contd.):

In other words no x, λ > 0 fulfils

Ax = λb, cx < λcx*

and this is true, in particular, for λ = 1, which implies that no feasible x for P exists which fulfils

cx < cx*

and so x* is optimal for P.

Strong duality

Proof (contd.):

Conversely, if the dual system y[A, –b] < [c, –cx*] is incompatible, then the primal Ax = λb, cx < λcx* has a solution x°, λ° > 0.

– If λ° > 0, x°/ λ° is P-feasible and better than x*.

– If λ° = 0, one hasAx° = 0, x° > 0 and cx° < 0, hence x* + x° is feasible and better than x*.

Therefore, x* is not optimal.

End proof

The dual problem

• The theorem just proved justifies the introduction of a new problem

D) max yb

yA < c

• This is called the dual of problem P.

In turn, P is called the primal problem.

• The dual of a linear program (in standard form) is still a linear program (in general form).

• The dual problem has

– a variable for each constraint of the primal, – a constraint for each variable of the primal.

Proprieties of the dual

Theorem (reciprocity): Problem P is the dual of problem D.

Theorem (weak duality or dominance): For any pair x ∈ P, y ∈ D of solutions one has yb < cx.

Proof: Reciprocity is readily seen by rewriting D in standard form adding non- negative slack variables, and then writing the dual of the problem so obtained.

To see dominance it suffices to combine the columns of yA < c (constraints of D) using the components of x as multipliers. Since the combination is conic, the inequality is preserved:

yAx < cx

The thesis is obtained by the associative property (y(Ax) < cx) and by observing that Ax = b.

A few corollaries

Corollary: x* ∈ P and y* ∈ D are optimal if and only if y*b = cx*

Proof: by combining weak and strong duality.

Corollary (complementary slackness): x* ∈ P and y* ∈ D are optimal if and only if

(c – y*A)·x* = y*·(Ax* – b) = 0

Proof: this corollary says that optimal dual (primal) slacks are orthogonal to any optimal primal (duale) solution.

The first condition rewrites cx* = y*Ax*, and since Ax* = b it is equivalent to the previous corollary.

The second one is true ∀y*, because Ax* = b.

Example

Primal problem P) min 4x₁ + 3x₂ + x₃

x₁ + 3x₂ – 2x₃ = 6 x₁, x₂ , x₃ > 0

Dual problem D) max 6y

y < 4, 3y < 3, –2y < 1

x₃

x₁

x₂

y 0

4 1

−1/2

dual optimum 6 primal optimum 6 P

(0, 2, 0)

A few corollaries

Corollary: if problem P (problem D) is unbounded from below (from above) then problem D (problem P) has no solution.

Proof: it directly derives from weak duality.

For example, suppose by contradiction that P is unbounded from below (i.e., for any x ^∈ P there exists an x° ^∈ P such that cx° < cx) and that, however, D is non-empty (i.e., there exists one y° ^∈ D).

This clearly contradicts weak duality, according to which one has y°b < cx,

∀x ^∈ P, and therefore it can’t be cx → –∞.

(A similar argument can be used for the case D unbounded).

Example

Primal problem P) min – 4x₁ – 3x₂ – x₃

x₁ + 3x₂ – 2x₃ = 6

x₁, x₂ , x₃ > 0

Dual problem D) max 6y

y < –4, 3y < –3, –2y < –1

y 0

–1 1/2 empty dual

x₃

x₁

x₂

P

–4 unbounded primal

Summarizing

×

×

×

×

impossible impossible

D has a finite optimum

impossible

× ?

×

×

×

D = Ø

impossible

×

×

×

×

impossible D unbounded

P has a finite optimum P = Ø

P unbounded

Rules to construct the dual

Rule 1: Write the primal as a minimization problem with > and/or =

constraints. The dual will then be a maximization problem with = and/or < constraints.

Rule 2: Add a dual variable y_i for any primal constraint: y_i will be

• > 0 if the primal constraint is > (loose constraint)

• free if the primal constraints is = (strict constraint)

Rule 3: The dual objective function is a linear combination of the y_i’s with the primal left-hand side b. The dual hand side is instead the primal cost vector c.

Rule 4: Add a dual constraint for any primal variable x_j: this constraint will have the form

• of < (loose constraint) if x_j is > 0

• of = (strict constraint) if x_j is free

Example 1

Primal problem P) max 5x₁ – x₂ + 2x₃

x₁ + 4x₂ – 6x₃ < 6 2x₁ – x₃ = 4 2x₁ + 3x2 > 5

x₂, x₃ > 0

Rewrite (Rule 1) P) min – 5x₁ + x₂ – 2x₃

– x₁ – 4x₂ + 6x₃ > –6 2x₁ – x₃ = 4 2x₁ + 3x2 > 5

x₂, x₃ > 0

Dual problem D) max – 6y₁ + 4y₂ + 5y₃

y₁, y₃ > 0

– y₁ + 2y₂ + 2y₃ = –5 – 4y₁ + 3y₃ < 1

6y₁ – y₂ < –2

x₃

x₁

x₂

P

Example 2

Primal problem P) min 4x₁ + 3x₂ + x₃

x₁ + 3x₂ – 2x₃ = 6 x₁, x₂ , x₃ > 0

primal optimum 39/5 = 7,8

What is the dual problem?

x₁ + x₂ + x₃ > 3

(0, 12/5, 3/5)

(3/2, 3/2, 0)

(6, 0, 0)

x₃

x₁

x₂

P

Example 3

Primal problem P) min 4x₁ + 3x₂ + x₃

x₁ + 3x₂ – 2x₃ = 6 x₁, x₂ , x₃ > 0 x₁ + x₂ + x₃ > 3 max

What is the dual optimum value?

What is the dual problem?

(0, 12/5, 3/5)

(3/2, 3/2, 0)

(6, 0, 0)