0
$\begingroup$

I want to implement the following optimization problem from the following paper Randomized Gossip Algorithms, Page 10 Eq 53: \begin{align} \text{minimize} &\qquad s\\ \text{subject to} & \qquad \begin{cases} W - \mathbf{11}^T/n \preceq sI\\ W = \sum_{i,j=1}^n\frac1n P_{ij}W_{ij}\\ P_{ij}\geq 0,\quad P_{ij}=0\text{ if }\{i,j\}\not\in E\\ \sum_{j} P_{ij} = 1,\quad \forall i \end{cases} \end{align}

  1. In this problem, $W$, $P$, and $P_{ij}$ are $n\times{n}$ matrices. I would appreciate if you help me with implementing the following constraint in CVX. \begin{equation} W=\frac{1}{n}\sum_{i,j=1}^{n}P_{i,j}W_{i,j} \end{equation}

  2. Also, in this problem, $E$ is a set of neighbors of a node $i$. Constraint "$P_{ij}=0$ if $\{i,j\}\not\in E$" means that $P_{ij}$ is zero if nodes $i$ and $j$ are not neighbors. Does anyone can help with how to implement this neighborhood relationship?

For $n=3$, neighbors.xlsx can look like:

screenshot of neighbors.xlsx

This means node 1 is neighbor with node 2, node 2 is neighbor with node 1 and 3, and node 3 is neighbor with node2.

I have the written the following piece of code for that in Matlab. It does not work. Any help is greatly appreciated.

cvx_begin sdp
    agt = struct([]);
    neighbors = readcell('neighbors.xlsx');
    N = 2;
    for i = 1:N
      agt(i).neighbors = neighbors{i};
    end
    variable s
    variable P(N,N) symmetric
    variable W_ij(N,N) symmetric
    expression W
    
    minimize (s)
    
subject to     

P(:) >= 0;

    j = 1;
    for i = 1:N
        D =[i,j];
        if ~ismember(D,agt(i).neighbors)
            P(i,j)== 0;
        end
        j = j+1;
    end


    for i = 1:N
        for j = 1:N
            W = P(i,j).*W_ij;
        end    
    end
    W = (1/N).*W;
    W-(1/N)*ones(N,1)*ones(1,N) - s*eye(N) == semidefinite(N);

cvx_end
$\endgroup$
7
  • 1
    $\begingroup$ I think a Matlab forum might be what you are looking for, sorry. $\endgroup$
    – David Roberts
    Commented Jan 19, 2022 at 0:47
  • $\begingroup$ @DavidRoberts You have a point. I just posted it here in case someone familiar with this optimization concept could help. $\endgroup$ Commented Jan 19, 2022 at 0:54
  • 1
    $\begingroup$ CVX has help forums: ask.cvxr.com $\endgroup$ Commented Jan 19, 2022 at 0:55
  • $\begingroup$ @Spring no probs. Even so, it's probably a little questionable if it's on-topic, since MathOverflow is for research questions or those that come up in research. It's tricky to place more applied topics, since for them research is often about applying known techniques to a new or novel problem, which is not what the general culture is here. Best of luck! $\endgroup$
    – David Roberts
    Commented Jan 19, 2022 at 0:57
  • $\begingroup$ @DavidRoberts I apologize if I seemed to disrespect the forum here. I had no intentions to do so. $\endgroup$ Commented Jan 19, 2022 at 0:59

0

You must log in to answer this question.