• 写在前面
• 问题描述
• 论文1算法
  • 算法设计
  • 收敛性证明

写在前面

原论文1：Distributed Continuous-Time Algorithms for Resource Allocation Problems over Weight-Balanced Digraphs.

原论文2：Distributed Resource Allocation over Directed Graphs via Continuous-Time Algorithms.

本文是Deng 2018^[1]和Zhu 2021^[2]的笔记，从形如$\sum_{i=1}^nx=\sum_{i=1}^nd_i$的资源分配问题入手，主要探讨一下带有耦合约束的分布式优化问题在有向图（拉普拉斯矩阵不对称）条件下如何求解。

问题描述

考虑多智能体系统的通信拓扑由一个有向图$\mathcal G$表示，其中节点集为$\mathcal V=\{1,2,\cdots,N\}$，有向边集为$\mathcal E\subseteq\mathcal V\times \mathcal V$。定义资源分配问题

$\begin{aligned} \min_{x\in\mathbb R^{nN}}&\quad f(x),\quad f(x)=\sum_{i=1}^Nf_i(x_i)\\ \operatorname{s.t.}&\quad \sum_{i=1}^N x_i=\sum_{i=1}^N d_i,\quad x_i\in\mathcal C_i,\quad i\in\mathcal V \end{aligned}\qquad (1)$

其中，$N$是智能体的个数，$n$ 是智能体状态的维度，$f_i:\mathcal C_i\to \mathbb R$是局部非光滑的凸函数，$\mathcal C_i\subset \mathbb R^n$称为局部可行集，是仅能被自身获得的闭凸集合。

论文1算法

本节中考虑通信拓扑图$\mathcal G$ 为一个强连通的有向平衡图。

假设1：

1）Slater条件满足（解的存在性）；

2）局部代价函数$f_i$是$\omega$-强凸的（解的唯一性）。

算法设计

分布式算法

$\left\{ \begin{aligned} \dot x_i&\in \Pi_{\mathcal C_i}(x_i,-\partial f_i(x_i)-y_i),\quad x_i(0)\in\mathcal C_i,\\ \dot y_i&=k_1\left(\sum_{j=1}^N a_{ij}(z_i-z_j)-d_i+x_i\right)-k_2\sum_{j=1}^N a_{ij}(y_i-y_j),\\ \dot z_i&=-\left(\sum_{j=1}^N a_{ij}(z_i-z_j)-d_1+x_i\right), \end{aligned} \right.\qquad (2)$

其中，$\Pi_{\mathcal C_i}(x_i,\cdot)=P_{\mathcal T_{C_i}(x_i)}(\cdot)$，即某点对集合$\mathcal C_i$在$x_i$处的切锥的投影，

$k_1>\frac{2}{\hat \lambda_2\omega},\quad k_2>4\frac{\|L\|^2k_1^2}{\hat \lambda_2^2}.$

算法(2)中包含三个部分：

• $\partial f_i(x_i)$用来优化代价函数；
• $z_i$用来满足资源分配约束；
• $y_i$用来保证任务信息的一致性。

收敛性证明

将算法(2)写成矩阵形式

$\left\{ \begin{aligned} \dot x&\in \Pi_{\mathcal C}(x,) \end{aligned} \right.$