Linear Programming

Linear Programming Problem 1 (4 points, Exer. 41 in Linear Programming Exercises): Let P 2 Rn×n be a matrix with the following two properties: • all elements of P are nonnegative: pij ≥ 0 for i = 1; · · · ; n and j = ...

Linear Programming Problem 1 (4 points, Exer. 41 in Linear Programming Exercises): Let P 2 Rn×n be a matrix with the following two properties: • all elements of P are nonnegative: pij ≥ 0 for i = 1; · · · ; n and j = 1; · · · ; n. • the columns of P sum to one: Pn i=1 pij = 1 for j = 1; · · · ; n. Show that there exists a y 2 Rn such that P y = y; y ≥ 0; nX i =1 yi = 1: Remark (the following are not related to the probem solution). This result has the following application. We can interpret P as the transition probability matrix of a Markov chain with n states: if s(t) is the state at time t (i.e., s(t) is a random variable taking values in f1; · · · ; ng), then pij is defined as pij = Pr(s(t + 1) = ijs(t) = j): Let y(t) 2 Rn be the probability distribution of the state at time t, i.e., yi(t) = Pr(s(t) = i): Then the distribution at time t + 1 is given by y(t + 1) = P y(t). The result in this problem states that a finite state Markov chain always has an equilibrium distribution y. Solution: Suppose there exists no such y. From Farkas’s Lemma, there exist z 2 Rn and w 2 R such that (P − I)T z + w1 ≥ 0; w < 0; i.e., PT z > z:Since the elements of P are nonnegative with unit column sums, we must have (PT z)i ≤ max j zj; which contradicts z < PT z. Problem 2 (4 points, Exer. 46 in Linear Programming Exercises): For the following two LPs, check (and prove whether) the proposed solution is optimal, by using duality: 1. For the LP minimize 47x1 + 93x2 + 17x3 − 93x4 subject to 26666664 −1 −6 1 3 −1 −2 7 1 0 3 −10 −1 −6 −11 −2 12 1 6 −1 −3 37777775 266664 x1 x2 x3 x4 377775 ≤ 26666664 −3 5 −8 −7 4 37777775 Is x = (1; 1; 1; 1) optimal? 2. For the LP maximize 7x1 + 6x2 + 5x3 − 2x4 + 3x5 subject to 266664 1 3 5 −2 3 4 2 −2 1 1 2 4 4 −2 5 3 1 2 −1 −2 377775 26666664 x1 x2 x3 x4 x5 37777775 ≤ 266664 4 3 5 1 377775 ; xi ≥ 0; i = 1 : : : 5 Is x = (0; 4=3; 2=3; 5=3; 0) optimal? Solution: 1. Clearly, x∗ = (1; 1; 1; 1) is feasible: it satisfies the first four constraints with equality and the fifth constraint with strict inequality. To prove that x∗ is optimal, we construct a dual optimal z∗ as a certificate of the optimality. z∗ must satisfy: AT z∗ + c = 0; z∗ ≥ 0; zk∗(bk − aT k x∗) = 0; k = 1; : : : ; 5: From the complementarity conditions we see that z5∗ = 0, and the dual equality constraints reduce to a set of four equations in four variables 266664 −1 −1 0 −6 −6 −2 3 −11 1 7 −10 −2 3 1 −1 12 377775 266664 z∗ 1 z∗ 2 z∗ 3 z∗ 4 377775 + 266664 47 93 17 −93 377775 = 0:These equations have a unique solution (3; 2; 2; 7; 0). Therefore, z∗ = (3; 2; 2; 7; 0): This implies that the optimality condition holds, and x∗ = (1; 1; 1; 1) is optimal. 2. We consider the given problem as the dual problem and we can form the primal problem as minimize cT y subject to Ay ≤ b y ≤ 0; where A = 26666664 1 4 2 3 3 2 4 1 5 −2 4 2 −2 1 −2 −1 3 1 5 −2 37777775 ; b = 26666664 −7 −6 −5 2 −3 37777775 ; c = 266664 −4 −3 −5 −1 377775 : Let us suppose ~ x = (0; 4=3; 2=3; 5=3; 0)T is dual optimal, and ~ y is primal optimal. Then according to the optimality condition, we have x~i(b − Ay~)i = 0; i = 1; : : : ; 5; cT y~ = −bT x; ~ where the first constraints are according to the complementary slackness and the second constraint is due to the strong duality. We can solve the above equations, which contain four equations and four variables. Then we can get the solution: ~ y = (−1; −1; 0; −1)T . Obviously, ~ y is not primal feasible, since the last constraint of Ay ≤ b is not satisfied. Therefore, ~ x = (0; 4=3; 2=3; 5=3; 0)T is not optimal. Problem 3 (4 points, Exer. 47 in Linear Programming Exercises) Consider the polyhedron P = fx 2 R4jAx ≤ b; Cx = dg where A = 266664 −1 −1 −3 −4 −4 −2 −2 −9 −8 −2 0 −5 0 −6 −7 −4 377775 ; b = 266664 −8 −17 −15 −17 377775 andC = h13 11 12 22i ; d = 58 1. Prove that ^ x = (1; 1; 1; 1) is an extreme point of P. 2. Prove that ^ x is optimal for the LP minimize cT x subject to Ax ≤ b Cx = d with c = (59; 39; 38; 85). 3. (Bonus)(1 point) is ^ x the only optimal point? if not, describe the entire optimal set. You can use any software, but you have to justify your answers analytically. Solution: (a) We have b − Ax^ = (1; 0; 0; 0); i.e., all inequalities except the first one are active. We therefore have to examine the rank of the matrix 266664 −4 −2 −2 −9 −8 −2 0 −5 0 −6 −7 −4 13 11 12 22 377775 The rank is four. Hence ^ x is an extreme point. (b) To prove ^ x is optimal, we have to find a z 2 R4 and y 2 R satisfying z ≥ 0; A~T z + CT y + c = 0; zi(~bi − a~T i x^) = 0; i = 1; :::; 4: The complementary slackness conditions imply that z1 = 0, so the optimality conditions reduce to zi ≥ 0, i = 2; :::; 4, and 266664 −4 −8 0 13 −2 −2 −6 11 −2 0 −7 12 −9 −5 −4 22 377775 266664 z2 z3 z4 y 377775 = 266664 −59 −39 −38 −85 377775 This is a set of four equations in four variables, with an invertible coefficient matrix. It has a unique solution z2 = 1; z2 = 2; z3 = 0; y = −3:From this we conclude that the optimality conditions at ^ x are solvable and that there is a unique dual solution z^ = (0; 1; 2; 0); y = −3: (c) Any primal optimal x must satisfy the complementary slackness conditions with the dual optimal solution found in part (b). Conversely, any x that is primal feasible and complementary with ^ z is optimal. This yields the following conditions on x: Ax ≤ b; Cx = d; ~bi − a~T i x = 0; i = 2; 3: This leaves only one possibility for an extreme point other than ^ x to be optimal: it is possible that there is an optimal extreme point at which the first inequality is active. To see if this yields a feasible point, we have to solve the set of equations 266664 −1 −1 −3 −4 −4 −2 −2 −9 −8 −2 0 −5 13 11 12 22 377775 266664 x1 x2 x3 x4 377775 = 266664 −8 −17 −15 58 377775 The solution is ~ x = (0:7542; 1:8375; 0:3917; 1:0583). To verify that ~ x is feasible, we plug it in in the fourth inequality. We find h−8 −2 0 −5i x~ = −18 ≤ −17: (1) Therefore ~ x is feasible. We conclude that there are two optimal extreme points, ^ x and ~ x. Any convex combination of ^ x and ~ x is also optimal, i.e., the optimal set is Xopt = fθx^ + (1 − θ)~ xjθ 2 [0; 1]g : (2) Problem 4 (3 points, Exer. 50 in Linear Programming Exercises): A matrix A 2 R(mp)×n and a vector b 2 Rmp are partitioned in m blocks of p rows: A = 266664 A1 A2 ... Am 377775 ; b = 266664 b1 b2 ... bm 377775 ; with Ak 2 Rp×n, bk 2 Rp. (a) Express the optimization problem minimize mP k=1 jjAkx − bkjj1 (3) as an LP.(b) Suppose rank(A) = n and Axls − b 6= 0, where xls is the solution of the least-squares problem minimize jjAx − bjj2: Derive the dual program and show that it can be simplified as maximize Pm k=1 bT k zk subject to Pm k=1 AT k zk = 0 jjzkjj1 ≤ 1; k = 1; : : : ; m (c) For the setup of (b), show that the optimal value of (3) is bounded below by Pm k=1 jjrkjj2 maxk=1;··· ;m jjrkjj1 where rk = Akxls − bk for k = 1; · · · ; m. Solution: (a) The problem is equivalent to the LP minimize 1T y subject to −yk1 ≤ Akx − bk ≤ yk1; k = 1; : : : ; m; with an auxiliary variable y 2 Rm. (b) The dual problem can be written as maximize mP k=1 bT k (uk − vk) subject to mP k=1 AT k (uk − vk) = 0 1T (uk + vk) = 1; k = 1; : : : ; m uk ≥ 0; vk ≥ 0; with variables uk; vk 2 Rp. We can derive the simplified equivalent problem maximize mP k=1 bT k zk subject to mP k=1 AT k zk = 0 jjzkjj1 ≤ 1; k = 1; : : : ; m: This can be testified as follows (see, page 6-16). If uk, vk are feasible for the first problem, then zk = uk − vk is feasible for the second problem. If zk is feasible for the second problem, then (uk)i = maxf(zk)i; 0g+αk and (vk)i = maxf−(zk)i; 0g+αk are feasible for the first problem, where αk = (1 − jjzkjj1)=(2p). (c) For the least square solution xls, we have the following property: (AT A)xls = AT b: