Doubly stochastic matrix in linear programming

5 次查看（过去 30 天）
Xia
Xia 2015-1-16
评论： Matt J 2015-1-16
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?

请先登录，再回答此问题。

采纳的回答

Torsten
Torsten 2015-1-16
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 个评论
显示 1更早的评论
Matt J
Matt J 2015-1-16
The first constraint looks like it should be an inequality,
A*x-Z*y<=0
Xia
Xia 2015-1-16
编辑：Xia 2015-1-16
No, and actually just the opposite. It’s an application of Investment test. However, your answer and codes are helpful and inspiring. Thank you so much Matt, for your time and kindness. Again, thanks Torsten. Merci guys.

请先登录，再进行评论。

更多回答（1 个）

Matt J
Matt J 2015-1-16
编辑：Matt J 2015-1-16
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 个评论
Matt J
Matt J 2015-1-16
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);

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Linear Programming and Mixed-Integer Linear Programming 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by