Doubly stochastic matrix in linear programming

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?

Answer 1

[Torsten]

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.

[Xia]

Firstly, thanks a lot Torsten for your anwer. Yes, it is exactly the formulation of optimization. So how can I use linprog() function to solve x and Z?

[Matt J]

The first constraint looks like it should be an inequality,

   A*x-Z*y<=0

[Xia]

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.

Answer 2

[Matt J]

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);

[Matt J]

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);