Exercise 4.2 (Self-dual problems)

Consider the primal problem

minimize c ′ x subject to A x ≥ 0 x ≥ 0 .

Form the dual problem and convert it into an equivalent minimization problem. Derive a set of conditions on the matrix A and the vectors b , c , under which the dual is identical to the primal, and construct an example in which these conditions are satisfied.

Answers

The primal problem

minimize c′x subject toAx≥ b x ≥0 		(1)

results in the following dual:

maximize p′b subject top ≥0 p′A ≤c′.

Our goal is to find a choice of A,b and c under which the above two optimization problems become one and the same. To make this task visually easier, notice that p′A ≤c′ is equivalent to A′p ≤c and transform the maximization problem into an equivalent minimization problem:

minimize −p′b subject to −A′p ≥−c p ≥0. 		(2)

Comparing the primal (1) and its dual (2), we see that both become the same whenever A is a skew symmetric matrix (i.e., −A′ = A) and b = −c.

Example 1. Consider the following primal parameters:

A := [ 0 1 −1 −1 0 2 1 −2 0 ]c := [ 1 −1 1 ]b := [ −1 1 −1 ].

The primal problem is then

minimizex1 − x2 + x3 subject tox2 − x3 ≥−1 − x1 + 2x3 ≥ 1 x1 − 2x2 ≥−1 x1,x2,x3 ≥ 0, 		(3)

whereas the corresponding dual problem is

maximize − p1 + p2 − p3 subject to − p2 + p3 ≤ 1 p1 − 2p3 ≤−1 − p1 + 2p2 ≤ 1 p1,p2,p3 ≥ 0. 		(4)

An equivalent transformation into a minimization problem yields

minimizep1 − p2 + p3 subject top2 − p3 ≥−1 − p1 + 2p3 ≥ 1 p1 − 2p2 ≥−1 p1,p2,p3 ≥ 0. 		(5)

Thus, the dual and the primal problems are practically identical.

User profile picture
2022-03-15 19:20
Comments