How to write an optimization constraint related to neighbors of a node in a graph

Question

Nasim 2022-1-19

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1631975-how-to-write-an-optimization-constraint-related-to-neighbors-of-a-node-in-a-graph

编辑： Nasim 2022-1-22

Hello All,

I am trying to implement an SDP optimzation problem in CVX. The language is Matalb. My question is mainly related to Matlab coding.

Here is the optimization problem (from the paper, Randomized Gossip Algorithms, P. 10 Eq. 54):

In this problem, W, P, and P_{ij} are n-by-n matrices. 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? Any help is greatly appreiciated.

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

I wrote this piece of code:

agt = struct([]);
    neighbors = readcell('neighbors.xlsx');
    N = 2;
    for i = 1:N
      agt(i).neighbors = neighbors{i};
    end
    j = 1;
    for i = 1:N
        D =[i,j];
        if ~ismember(D,agt(i).neighbors)
            W(i,j)== 0;
        end
        j = j+1;
    end

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Matt J 2022-1-19

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1631975-how-to-write-an-optimization-constraint-related-to-neighbors-of-a-node-in-a-graph#answer_877535

编辑：Matt J 2022-1-19

在 MATLAB Online 中打开

You can get the graph adjacency matrix A from the adjacency() command,

https://www.mathworks.com/help/matlab/ref/graph.adjacency.html

Then, the constraints are:

P>=0,
dot(1-A(:),P(:))=0;
sum(P.*A,2)=1;

3 个评论
显示 1更早的评论隐藏 1更早的评论

Matt J 2022-1-19

编辑：Matt J 2022-1-19

在 MATLAB Online 中打开

A is the adjacency matrix of the graph. I recommended that you generate it using the adjacency() command.

The second constraint is implied by the two constraints,

P>=0
dot(1-A(:),P(:))=0;

because Q=1-A is a matrix such that Q(i,j)=1 if

and zero otherwise. Therefore dot(1-A(:),P(:))=0 is the same as

. Because we have applied the additional constraint

, the constraint

follows.

Nasim 2022-1-19

Thanks a lot!

请先登录，再进行评论。

How to write an optimization constraint related to neighbors of a node in a graph

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

3 个评论
显示 1更早的评论隐藏 1更早的评论

更多回答（0 个）

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

How to write an optimization constraint related to neighbors of a node in a graph

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

3 个评论 显示 1更早的评论隐藏 1更早的评论

更多回答（0 个）

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

3 个评论
显示 1更早的评论隐藏 1更早的评论