Consider the inequality form LP:
minimize c^(T)x
subject to Ax <= b
with A in R^(m x n), b in R^(m).
Let w in R_(+)^(m). If x is feasible for the LP, i.e., satisfies Ax <= b, then it also satisfies the inequality
w^(T)Ax <= w^(T)b.
Geometrically, for any w >= 0, the halfspace H_(w) = {x | w^(T)Ax <= w^(T)b} contains the feasible set for the LP. Therefore, if we minimize the objective c^(T)x over the halfspace H_(w), we get a lower bound on p^(**).
(a) Derive an expression for the minimum value of c^(T)x over the halfspace H_(w) (which will depend on the choice of w).
(b) Formulate the problem of finding the best such bound by maximizing the lower bound over w >= 0.
(c) Relate the results of (a) and (b) to the Lagrange dual of the LP.
Hint:
(a) When minimizing a linear function over a halfspace, the minimum will be -infty unless the halfspace is aligned with the linear function.
(b) maximize_(w) -alpha w^(T)b
subject to alpha w^(T)A + c^(T) = 0
w >= 0 (element-wise), alpha > 0
(c) Use w' = alpha w.