Exercise 4.5 Consider a linear programming problem in standard form and assume that the rows of A are linearly independent. For each one of the following statements, provide either a proof or a counterexample. (a) Let x* be a basic feasible solution. Suppose that for every basis correspond- ing to x*, the associated basic solution to the dual is infeasible. Then, the optimal cost must be strictly less that c'x*. (b) The dual of the auxiliary primal problem considered in Phase I of the simplex method is always feasible. (c) Let pi be the dual variable associated with the ith equality constraint in the primal. Eliminating the ith primal equality constraint is equivalent to introducing the additional constraint p; = 0 in the dual problem.Exercise 4.7 (Duality in piecewise linear convex optimization) Con- sider the problem of minimizing max;1,... n(ajx b;) over all x R". Let v be the value of the optimal cost, assumed finite. Let A be the matrix with rows ai,...,am, and let b be the vector with components b1, ..., bn. (a) Consider any vector p R that satisfies p'A =0, p>0,and ) ;" p; = 1. Show that p'b 0. Let x* be an optimal solution, assumed to exist, and let p* be an optimal solution to the dual. (a) Let X be an optimal solution to the primal, when c is replaced by some . Show that ( )'(x x*)