Problem 1 (Strict Complementarity in Linear Programming) (100 pts): In the lecture, we mentioned that there is strict complementarity property that holds for LP, without giving a proof. We will prove this property in this problem. Let us formally state this property first. Consider the following primal/dual L.P problem: (P)minxRcxs.t.Ax=b(D)maxyRbyx0s.t.Ayc In the discussion that follows, we will assume both problems (P) and (D) are feasible. By weak duality. we know that both primal and dual optimal solutions exist. And by strong duality, for any pair of primal and dual optimal solutions (x,y), we have: cx=by. As an immediate consequence, complementarity slackness holds and we have: s=cAy0,(s)x=0 The above complementarity slackness can be equivalently written as the following: si>0xi=0,xi>0si=0,i=1,2,,n. In the complementarity slackness, it is possible that xi=si=0 for some 1in. However, for linear programming, in fact there exists a primal optimal solution x and a dual optimal solution s (and y ) such that the strict complementarity holds. That is, exactly one of xi or si equals 0 but not both, for all i=1,,n, or equivalently the following holds: si>0xi=0,xi>0si=0,i=1,2,,n. We formally state it as the following theorem: Theorem 1. Suppose both (P) and (D) are feasible. Then there exists a primal optimal solution x and a dual optimal solution (y,s) with s=cAy, such that the strict complementarify (1) holds. To prove Theorem 1, we will need to use the next Lemma, whose proof will be constructed in this problem step by step. Lemma 1. Suppose both (P) and (D) are feasible. Then for any index 1in, either there exists a primal optimal solution x such that xi>0, or there exists a dual optimal solution s such that si>0. Note that we can not have both xi>0 and si>0 for some i, otherwise the (weak) complementa be violated, which is supposed to hold for any optimal solution x and s. Answer the following questions in order to prove Lemma 1. (d) Following part (c) for the case when the optimal value of (P) is 0 , but consider now the case when the (an) optimal solution (y,y0) to (D) is such that y0=0. Let y be any optimal solution to (D) and define y=y+y. Answer the next three questions. - Show that y is feasible to (D). - Show that y is an optimal solution to (D). - In this case, we have s:=cAy is such that si>0. Explain why. (e) Finally, we are left with the case when the optimal value of (P) is less than 0 . This means that there is a feasible solution to (P) with negative objective value. Give an explanation of why this fact indicates that there exists an optimal solution x to the primal problem (P) such that xj>0. Note the following relations: 1n=1n.1TE=1.1A=(1)1n. maxcx=bminbys.t.Ax=0mins.by=Ayc0x0. xx1nnx1 ise x0, The interpretation of exch quantity of the primal problem is as following - Each peimal wariable x1 is the action frequency of action jA, or the expected present value of number of times in which an individual is in state 1 and takes action i. - b=1m means there is one individual in each state. Specifically P is a columa wochustic matrix, meaning each column taking action jt at state i). - Ax=1m is the contervatiog law, which ensures that for each itate 1 , the expected present value of mumber of individuals entering state i equals the expected present value of number of individuats leaving ig (EP)=b - The primal problem is to find action frequencies that maximize the expected present reward cx. Interpretation of the LP Formulation (Dual) Policy and Basic Feasible Solution A polic x= in the original MDP, containing exactly one action in di for each state, t. corresponds to m basic variable indices of a. base feasible colution of the primal problem in the L.P formulation. Let An,Pm,EnRm be the columng of A,P,E, with indices in rolution for policy $. Denote y= (o) y= be the remaining indices that are not in . The interpretation of each quantity of the dual problem is as following: - Each dual variable y assigns a value to each state i. is then x rend intoriale - The optimal dual variable y, satisfying A7yc, is the optimal walue function satisfying the Bellman ootimality equation. - Note that there exists a unique optimal value function v+=y4 such that y is the maximum-expected retum at state f. - The minimum value of the duat problem br y, is in fact the largest sum of the total state values for all possible pollicies . xyx=0,A2x0=1,x1 The corresponding dual basic solution y2 is the unique solution to Axy>C A17y=c4 and is 5 Teasible solution if. A17yc4) AYA=G X The primal dual basic solution pair (x,y) is optimal if and only if both are fegsible, In such case, = is an optimal policy and yn=v is the optimat value function. The duat constraints exactly describe the (matrox form) Bellman optimality equations. Policy and Basic Feasible Solution Lemma There is a one-to-one correspondence between a policy of the original MDP and a basic feasible solution of the primal problem (P). Primal and Dual Basic Solutions Given any policy , which is also a basis of (P), we can compute An=1{Pn and the primal/dual basic solution pair x and (y,s) as: y2=(A2)1c As we have seen in the dual simplex method, the primal/dual basic solution pair is always complementary. Here, the primal basic solution xn is always feasible (xn0), indicating dual optimality. On the other hand, the primal optimality is only achieved at dual feasibility, In particular, when sy0. Policy and Basic Feasible Solution (Proof) Proof The logic is to show that every basic feasible solution of (P) must contain one index in each of state set Ai,i=1,,m, which corresponds to one action in each state, thus a policy. Let be the basis set of any basic feasible solution for (P). Consider the coefficients of the i-th row of A. We can see that ay0 for all j/Ai. If we assume for some i, no basic variable is chosen from Ai, of simply Ai=, then we have: which is a contradiction. That is, there must be at least one basic variable in each A,i=1,,m. However, since is a basis, =m. Then must contain exactly one (action) index in Ai for each state i=1,,m. In other words, is a policy. Strict Complementarity Lemma If both LP(P) and (D) are feasible, then there is a unique partition B{1,2,,n} and N{1,2,,n}, such that for each optimal solution pair (x,s). x^j=0,vjN1andsj=0,vjB, and there is at lesst one optimal solution pair (x,s) that is strictly complementary: xj>0,VjB1,andsj>0,VjN. In particular, every optimal policy B so that Bm and Nnm. The existence of strictly complementary optimal solution follow from the strict complementarity result of general L.P. We may call B the optimal (super) basic variable set and N the optimal non-basic variable set. The cardinality result follows from the fact that there must be an optimal basic feasible solution (or optimal policy) where the basic variables (optimal action frequencies) are all strictly positive, so their indices must belong to B. There may exist multiple optimal policies for an MDP, B contains actions, each of which appears in at least one optimal policy, and N contains the remaining actions, none of which appears in any optimal policy. The total number of non-optimal actions in N should not exceed nm for any MDP. The optimal dual basic feasible solution pair (y,5) is unique and invariant among the multiple optimal policies. Therefore, if j is a non-optimal action, then its optimal dual slack value s j must be positive. The LP Formulation (Basic/Non-Basic) maxs.t.cxAx=bx0,minbys.t.s=Ayc0 Given a policy and let denote the remaining indices not in . the primal problem can be expressed in the equivalent form: where c is the reduced cost and cn=0,cr=cyAyr and yn=(An+)1cn The LP Formulation (Basic/Non-Basic) Given a policy and let y denote the remaining indices not in , the primal problem can be expressed in the equivalent form: maxixi+cx0maxci(Am)1m+CyxnArx2+Axxn=1s.t.Axxr+Axr=1mx=(xr;x)0 The dual problem can be written as min15ys.A4y+s4=c4A1y+s2=c2s=(5,;,sn)0.