Doubly stochastic matrix in linear programming
3 views (last 30 days)
Show older comments
How may I get the vector x by using linprog(f,A,b), where b=Wy(y is a known vector) and W is all possible doubly stochastic matrix? Or other methods will work for lp given constraints involve doubly stochastic matrix, especially if W is high dimensional and enumeration seems infeasible?
0 Comments
Accepted Answer
Torsten
on 16 Jan 2015
You mean how you can formulate the above problem for linprog ?
min: f'x
s.c.
A*x-Z*y=0
sum_i z_ij = 1
sum_j z_ij = 1
0 <= z_ij <= 1
Or what exactly are you asking for ?
Best wishes
Torsten.
3 Comments
Matt J
on 16 Jan 2015
The first constraint looks like it should be an inequality,
A*x-Z*y<=0
More Answers (1)
Matt J
on 16 Jan 2015
Edited: Matt J
on 16 Jan 2015
This assumes that A will always be non-empty.
[m,n]=size(A);
p=m^2+n; %all unknowns
fwx=f; fwx(p)=0;
Awx=[kron(-y.',speye(m)), A];
bwx=zeros(m,1);
C= kron(speye(m), ones(1,m));
R= kron(ones(1,m), speye(m));
Aeq=[C;R]; Aeq(end,p)=0;
beq= ones(2*m,1);
lb=-inf(1,p); lb(1:m^2)=0;
ub=+inf(1,p; lb(1:m^2)=1;
WX=linprog(fwx,Awx,bwx,Aeq,beq,lb,ub);
W=reshape(WX(1:m^2),m,[]);
x=WX(m^2+1:p);
1 Comment
Matt J
on 16 Jan 2015
No, and actually just the opposite.
You mean you definitely want equality in
A*x-Z*y=0
If so, modify the call to linprog as follows
WX=linprog(fwx,[],[],[Aeq;Awx], [beq; bwx ],lb,ub);
See Also
Categories
Find more on Dynamic System Models in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!