Exercise 4.7 (Duality in piecewise linear convex optimization} Con- sider the problem of minimizing mam-=1 ,,,,, m (ax bi) over all x e 3?\". Let 1; be the value of the optimal cost, assumed nite. Let A be the matrix with rows in, . . . ,am, and let b be the vector with components in, . .. , bm. (51) Consider any vector p E 3?\" that satises p'A = 0', p 2 0, and 2:1 19" = 1. Show that p'b S 1). (b) In order to obtain the best possible lower bound of the form considered in part (a), we form the linear programming problem maximize p"b subject to p'A p'6 P where e is the vector with all components equal to 1. Show that the optimal cost in this problem is equal to v. or 1 0, 1V