Return to the LP of Exercise 7-18 and consider solving by Primal-Dual Interior Algorithm 7C.

(a) Derive the corresponding dual formulation over variables v and place it in standard form by adding slack variables s as needed.

(b) Show that Algorithm 7C could appropriately start with solutions x = 12, 3, 2, 3, 1>32, v = 11>2, 1>22, and the corresponding values of s in your dual standard form of (a).

(c) State all relevant complementary slackness conditions between primal and dual.

(d) Demonstrate that the primal solution value and the dual solution value of

(a) are separated by a duality gap equal to the total complementary slackness violation.

(e) Now suppose we want to derive move directions to change primal and dual solutions in a way that will move each complementary slackness violation closer to m = 5. Write, but do not solve the system of equation that must be solved to compute values of x, v, and s. Those 3 directions should be left as symbols, but all other elements of the equations should be detailed numerically for the given example and starting points.

(f) Build upon your analysis of

(e) to conduct up to 3 iterations Primal-Dual Interior Point Algorithm 7C (fewer if optimality is reached earlier) to move toward an optimal solution. At each step show the parameter m, change directions for x, v, and v, step size l, and new solutions, as well as the complementary-slackness/

duality gap between primal and dual.