Solving Matrix equation with contraints
in [Matlab]
|
Prev: HELP PLEASE!!
Next: remove black bar outline in bar3
From: monalisa sen on 7 May 2010 16:25 Hi: I am trying to solve AX=B; where X,A, B are n by n matrices; subject to the constraints: a) x(i,i)=0 (ie all the diagonal element of X matrix shd be 0) b) each of the row sum of X should be 1, ie, sum[x(i,j)]=1 when summing over all the columns for each row i. c) each x(i,j)>=0; Can any of you please help? Thnaks a lot.
From: John D'Errico on 7 May 2010 17:20 "monalisa sen" <msen1981(a)gmail.com> wrote in message <hs1svg$84u$1(a)fred.mathworks.com>... > Hi: > > I am trying to solve AX=B; where X,A, B are n by n matrices; subject to the constraints: > a) x(i,i)=0 (ie all the diagonal element of X matrix shd be 0) > b) each of the row sum of X should be 1, ie, sum[x(i,j)]=1 when summing over all the columns for each row i. > c) each x(i,j)>=0; > > Can any of you please help? > Thnaks a lot. Formulate this as a linear system of equations in n^2 unknowns. If you do so, then we find a system of 1. n^2 equations for the equality A*X = B. 2. n equations that correspond to the diagonal elements being zero. 3. n row sum equations. In general, this system will not have an exact solution, since we have n^2 + 2*n equations in n^2 unknowns. It is an overdetermined problem. The inequality constraints merely serve to reduce the probability that a solution exists. However, if you know that a solution exists, it is easy enough. n = 4; A = [ 16 2 3 13; 5 11 10 8; 9 7 6 12;4 14 15 1]; B = [4.78082343328984 9.22416092385747 11.3133835756658 8.68163206718693; ... 8.71780822242756 5.02919066456483 8.44394288910161 11.809058223906; ... 7.34746997932943 7.70521084234125 9.64129536853806 9.30602380979126; ... 8.89183816258422 1.19610039052821 7.7213261373564 16.1907353095312]; A A = 16 2 3 13 5 11 10 8 9 7 6 12 4 14 15 1 Can we solve for X? We will need lsqlin from the optimization toolbox. M = kron(eye(n),A); Meq = [sparse(1:n,1:(n+1):n^2,1,n,n^2);kron(ones(1,n),speye(n))]; X = lsqlin(M,B(:),[],[],Meq,[zeros(n,1);ones(n,1)],zeros(n^2,1)); X = reshape(X,n,n) X = 0 0.14366 0.49293 0.36341 0.50342 0 0.39621 0.10037 0.1052 0.0060072 0 0.88879 0.26603 0.53135 0.20262 0 Test that it worked, to within the floating point precision available in matlab. A*X - B ans = 1.7764e-15 1.7764e-15 1.7764e-15 0 0 0 1.7764e-15 -1.7764e-15 2.6645e-15 0 0 0 -1.7764e-15 -1.3323e-15 1.7764e-15 3.5527e-15 I'll let the interested student figure out how I built the matrices M and Meq, and why they were appropriate. HTh, John
From: Bruno Luong on 8 May 2010 03:46 "monalisa sen" <msen1981(a)gmail.com> wrote in message <hs1svg$84u$1(a)fred.mathworks.com>... > Hi: > > I am trying to solve AX=B; where X,A, B are n by n matrices; subject to the constraints: > a) x(i,i)=0 (ie all the diagonal element of X matrix shd be 0) > b) each of the row sum of X should be 1, ie, sum[x(i,j)]=1 when summing over all the columns for each row i. > c) each x(i,j)>=0; > > Can any of you please help? I have a doubt if the problem is well described, since if A is full-rank matrix (likely for square), then X = A\B is the unique solution of first equation, and you cal only pray it to meet the other constraints. If A in singular matrix, you could also formalize X(:) as an element of a polytope (hopefully non empty), by finding an element of a feasible set using a dummy linear-programming. Just call LINPROG with a dummy cost coefficients with all above constraints and maximum of 1 iteration. The solution returned is what you are looking for. Use similar Kron trick as John's has showed to build the linear constraint matrix to pass to LINPROG. Bruno
From: John D'Errico on 8 May 2010 04:48 "Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <hs34rs$5ue$1(a)fred.mathworks.com>... > "monalisa sen" <msen1981(a)gmail.com> wrote in message <hs1svg$84u$1(a)fred.mathworks.com>... > > Hi: > > > > I am trying to solve AX=B; where X,A, B are n by n matrices; subject to the constraints: > > a) x(i,i)=0 (ie all the diagonal element of X matrix shd be 0) > > b) each of the row sum of X should be 1, ie, sum[x(i,j)]=1 when summing over all the columns for each row i. > > c) each x(i,j)>=0; > > > > Can any of you please help? > > I have a doubt if the problem is well described, since if A is full-rank matrix (likely for square), then X = A\B is the unique solution of first equation, and you cal only pray it to meet the other constraints. I agree completely with Bruno here. The example I supplied was explicitly chosen to have an exact solution, but most systems will not be so lucky. John
From: Bruno Luong on 8 May 2010 08:05
Actually since all the equation are equalities, no simple linear inversion (no need fancy toolbox) should do: % John's example n = 4; A = [ 16 2 3 13; 5 11 10 8; 9 7 6 12; 4 14 15 1]; B = [4.78082343328984 9.22416092385747 11.3133835756658 8.68163206718693; ... 8.71780822242756 5.02919066456483 8.44394288910161 11.809058223906; ... 7.34746997932943 7.70521084234125 9.64129536853806 9.30602380979126; ... 8.89183816258422 1.19610039052821 7.7213261373564 16.1907353095312]; Aeq = [kron(speye(size(A)),A); sparse(1:n,1:n+1:n^2,1,n,n*n); kron(ones(1,n),speye(n))]; beq = [B(:); zeros(n,1); ones(n,1)]; X = reshape(Aeq\beq,[n n]); disp(X) % Bruno |