Answer Happy

Problem 5 (based on Exercise 7-27 from the textbook). Consider the following LP min 5x1 + 4x2 + 3x3 + 2x2 + 16x5 s.t. 2x1 + x3 + 6x5 = 8 X2 + x3 + 2x4 + 3x5 12 Vi Xi > 0 (a) Derive the corresponding dual formulation using dual variables v and place it in standard form using slack variables s. (6) Show that the Primal-Dual Interior-Point algorithm could appropriately start with solutions x = (2,3,2,3, 1/3), = (1/2, 1/2). V= 2 (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 u = 5. Write (but do not solve) the system of equations that must be solved to compute the values of Ax, Av and As.