Subject: Optimisation and Financial Mathematics

Topic: Non-standard Linear Programming Programmings and Duality

5. Consider the following pair of primal-dual linear programs: maximise cu minimise by (primal) subject to Ar 20 y > 0 for c, 2 ER", b, Y E RM and A Rmx (a) Prove the Complementary Slackness Theorem: Assume that the primal LP has a feasible solution x and the dual LP has a feasible solution y. Then, x is an optimal solution of the primal LP and y is an optimal solution of the dual LP if and only if (1) either I; = 0 or 1 dijYi = c; or both for j = 1, 2, ..., n, and (2) either yi = 0 or 11 dij; = b; or both for i = 1,2, Hint: Use the Fundamental Duality Theorem. 7 m. (b) By introducing slack or surplus variables, rewrite the primal LP into the following form: max s.t. Dz = b z > 0 Write out d, z and D explicitly. (c) Let P = {z : Dz = b, z>0} be non-empty. We say that z is a verter of P if there does not exist a non-zero y such that z + y, z - Y EP. For z e P, define the index set J = {j : Zj >0}. Let B be a submatrix of D formed by selecting column j of D for je J (correspond to positive zj's). Show that z is a vertex if and only if the columns of B are linearly independent by the following steps. (i) If z P is not a vertex, show that there exists a non-zero y such that Dy = 0 and Y; = 0 whenever zj = 0. (ii) By part (i), if z P is not a vertex, show that B has linearly dependent columns. Hint: consider columns of D that correspond to non-zero components of the y in part (i). (iii) If B has linearly dependent columns, show that there exists a non-zero y such that Dy = 0 and yj = 0 whenever z; = 0, and show that z is not a vertex of P. Hint: we can add 0 components to "extend a vector