Wednesday, March 2, 2011

Is it safe to move lower bounds to zero?

Assume we have the problem

  min c'x
  st.   A x = b        (P0)
         x >= l

where l is large in absolute value say l_j=-1000 for all js. (l is short for lower bounds). The dual problem is


   max b'y + l's
   st.    A'y + s = c  (D0)
           s >= 0

 It is very common to transform the problem to

  min c'x + c'l
  st.   A x = b- A l  (P1)
         x >= 0

for efficiency reasons. Indeed all interior-point optimizers will do that.

The dual problem is

   max b'y + c'l
   st.    A'y + s = c  (D1)
           s >= 0


Let us say we solve (P1) and (D1). Moreover,

   A'y + s =  c

holds only approximate which definitely be the case for interior-point methods. To be precise we have

   A'y + s =  c + e

holds exactly where 0 < |e|| << 1.


This implies if (y,s) from (D1) is reported as an optimal solution to (D0) then there can be a big error in the dual objective value. Note that is not the case if l=0. Now if instead we report (y,c-A'y) as the optimal dual solution to (D0) then objective value will be correct but then s>=0 might be violated.

The question is that which dual solution to report. I guess the answer is that it depends on your priorities.

I will leave it as an exercise to the interested reader to construct a small example demonstrating this. Since I just spend all day figuring out that happening on instance with 100K variables.