在多智能体网络中, 分布式优化是决策和数据处理的重要研究方向, 近年来得到广泛研究^[1-3]. 每个智能体都有一个局部目标函数, 通过各智能体与其邻居进行信息交互, 共同协作实现由局部目标函数之和构成的全局目标函数最小. 随着近年来互联网、大数据等新兴技术的发展, 资源分配在网络系统中得到广泛的应用, 如电力系统中的经济调度、机器人研究、智能交通、能源制造、无线网络利用率最大化等^[4-8], 使系统具有更高的功能效率、稳定性、安全性和可靠性.

分布式优化是通过各智能体间协调合作来实现优化任务, 每个智能体只能访问自己的局部目标函数和局部约束集, 与优化问题相关信息分别存储在各智能体中, 这充分保证了信息的隐私安全^[2]. 其次, 各智能体与其邻居节点进行信息交换即可, 不必将数据信息传递到中心节点, 更加节约了通信成本, 也避免了集中式算法会引入的通信单点故障和传感器故障等, 极大地提高了系统的鲁棒性, 也避免了对于处理大规模的复杂优化问题时, 集中式算法会由于智能体之间的通信、计算等限制变得低效^[9].

大多数的分布式算法是基于无向通信网络实现的, 如文献[10]提出的分布式精确收敛的一阶算法是通过前两次迭代的状态和梯度信息来更新节点的状态. 分布式不精确梯度方法和梯度跟踪算法中每个节点采用相同的步长, 变量的更新规则中并未用到动态一致性算法, 最终跟踪的梯度不是全局平均梯度. 之后有研究提出在无向图网络下, 改进分布式不精确梯度方法和梯度跟踪技术, 使其在不同节点采用不同步长, 加速优化算法^[11-12].

而许多实际问题中的通信网络往往是有向的, 如无线电传感器网络、手机通讯网络等^[13]. 有向图中算法收敛是一项具有挑战性的工作, 如文献[12]中所提算法只适用于无向网络, 在有向网络下其算法不具备收敛性. 文献[14]考虑在强连通加权平衡有向图上智能体的资源分配问题. 当局部目标函数强凸时, 其满足等式路径约束和局部凸集的约束条件下, 分布式连续时间投影算法的输出状态可渐近收敛到资源配置问题的最优解. 对局部凸集约束条件进行松弛并提出可以在强连通加权不平衡有向图上的自适应连续时间梯度算法, 其中局部目标函数及其梯度分别满足强凸性和Lipachitz条件, 并证明其指数收敛到问题的最优解. 文献[15]结合Push-Sum算法的核心思想, 提出满足一致强连通时变有向图网络下有效收敛的Subgradient-Push算法. 假设每个节点知道其对应的出度信息, 在次梯度有界的标准假设下使每个节点收敛并且都能找到最优值.

在实际应用中, 当系统对实时优化有较高要求时, 通常会考虑有向网络下的分布式连续时间算法, 其对系统的稳定性及灵活性的高要求可以用来解决资源分配问题^[16-19]. 文献[20-21]中提出的分布式投影算法分别用于解决无向图和加权平衡有向图的资源分配问题. 文献[20]在满足线性等式约束和局部可行集约束的前提下, 基于差分投影提出的连续时间算法, 可以不通过初始化对无向网络下的各智能体进行决策分配. 文献[21]考虑了满足局部可行集约束的非光滑代价函数在强连通加权平衡有向网络下的分布式资源分配问题. 利用微分包含和LaSalle集值不变性原理, 证明了解的唯一性和算法的收敛性. 但文献[20-21]所提的连续时间算法对于分布式资源分配仍存在一定的局限性. 文献[20]的算法对加权平衡有向图的有效性仍需探索; 文献[21]中算法在运行前需计算智能体在切锥上的投影, 增加了各智能体之间的交互和计算时间.

分布式优化问题中最简单的情况是无约束优化^[22-23]. 如文献[22]通过构造李雅普诺夫函数并进行稳定性分析, 使提出的连续时间分布式算法能够指数收敛到全局最小值. 在无向网络下的分布式连续时间非光滑凸优化问题中^[24], 只考虑局部可行集约束, 通过算法在切锥上的投影, 使其在满足局部可行集的约束条件下使算法收敛. 此外, 文献[25]中提出了一种分布式连续时间多智能体系统, 使目标函数在满足不等式路径约束、等式路径约束和局部可行集的约束下算法收敛, 找到全局目标函数的最小值. 上述研究中大多没有考虑耦合约束, 然而耦合路径约束出现在许多实际应用中, 具有重大研究价值.

具有耦合约束的分布式优化, 其中各个智能体的决策变量的可行域会受到其他智能体的影响. 然而在实际应用中, 网络拓扑图中没有中心点时, 耦合约束并不能够满足对各个智能体的资源分配^[26]. 在文献[26]中考虑具有耦合的非线性约束, 提出一个改进的拉格朗日函数, 引入局部乘子来解耦约束, 并使用非光滑罚函数保证算法的正确性, 使其鞍点不仅能得到优化问题的最优解, 其原对偶次梯度的算法也是完全分布的. 文献[27]研究解决不等式约束的优化问题, 通过Caratheodory意义上原始对偶动力学的解的存在的唯一性和连续性, 建立在原始对偶动力学下全局渐近收敛的分布式算法.

本文基于文献[28]中提出的分布式连续时间投影算法进行延展, 通过投影的定义及性质, 结合线性代数理论分析, 找到了证明算法的平衡解为分布式优化问题最优解的充分必要条件, 并且可以适用于强连通加权平衡有向通信网络拓扑图. 在满足耦合不等式约束和局部可行集约束的情况下使非光滑全局目标函数最小, 找到分布式优化问题的最优解. 大多数分布式优化问题考虑的是无约束、等式约束或不等式约束^{[23-25, 29-31]}, 与文献[24]中的局部可行集约束相比, 我们考虑的耦合不等式路径约束更具有通用性, 难度更高且计算更复杂, 适用范围更广. 本文研究了分布式优化在强连通有向通信拓扑图下的连续时间投影算法, 和文献[12]中无向网络下的离散时间系统相比, 可以实现实时优化, 稳定性更高. 本文通过Moreau-Yosida正则化近似函数解决非光滑目标函数最优问题, 比文献[24]和文献[26]中提出的方法更易于实现. 结合文献[28]中所提算法找到在强连通加权平衡网络下, 满足耦合不等式路径约束和局部可行集约束的最优解.

本文结构安排如下. 第1节介绍本文考虑的分布式优化问题和预备知识; 第2节提出应用在强连通有向图的分布式连续时间投影算法, 并分析证明算法的平衡解为优化问题最优解的充分必要条件; 第3节通过数值实验验证理论结果; 第4节总结本文的主要结论和未来研究方向.

符号说明: $ {\bf R} $表示实数集, $ {\bf R}^{m} $和$ {\bf R}^{mn} $分别表示$ m $维列向量集和$ m\times n $矩阵空间. ${{I}}_{m}$是$ m $维单位方阵. $ \mathbf{0}_{m} $是一组元素为0的$ m $维列向量, $ \mathbf{1}_{m} $是一组元素为1的$ m $维列向量. $ \|\cdot\| $是欧几里德范数. $ T_{S}(x) $是$ x $在集合$ S $上的切锥. $ N_{i}=\{j:(j,i)\in \mathcal{E}\} $是节点$ i $的邻居集合. 给定一个矩阵$ A $, $ {\rm range}(A) $表示矩阵$ A $的像, $ {\rm ker}(A) $表示矩阵$ A $的核. $ \lambda_{\rm max}(A) $表示矩阵$ A $的最大特征值. $ A\otimes B $表示矩阵$ A $和$ B $之间的Kronecker积. 矩阵$ A\geq0 $ ($ A>0 $) 时, $ A $为半正定(正定)矩阵, $ A\in {\bf R}^{mm} $. $ d_{i}^{\rm in} $是智能体$ i $的入度, $ d_{i}^{\rm out} $是智能体$ i $的出度.

1.   问题描述与预备知识

1.1   问题描述

考虑如下分布式优化问题^[14]

通信网络是由$ M $个智能体组成, $x_i\in {\bf R}^{m}$是全局决策变量, $ X_{i}\in {\bf R}^{m} $是各智能体的局部可行集, 每个智能体$i\in \mathcal{I}=\{1,\cdots,M\}$对应一个局部决策变量$ x_{i}\in X_{0}=\bigcap_{i=1}^{M}X_{i}\in {\bf R}^{m} $, 其中, $ X_{0} $是各智能体局部可行集的交集. 其对应的局部目标函数和局部耦合不等式约束分别是$ f_{i}(x_{i}):{\bf R}^{m}\rightarrow {\bf R} $和$g_{i}(x_{i}): {\bf R}^{m}\rightarrow {\bf R}^{n}$, 各智能体只能访问自己的局部目标函数$f_i$和不等式约束$g_i$, 其中, $ x={\rm col}(x_{1},x_{2},\cdots, x_{M}) $. 通过分布式连续时间投影算法让各智能体与邻居节点信息交互协同合作, 在满足耦合不等式约束和局部可行集约束下, 使各智能体状态收敛到全局最优解, 全局目标函数值最小.

本文对目标函数、耦合不等式约束和拓扑图等作出以下假设.

假设 1. $ f_{i} $和$ g_{i} $是局部可行集$ X_{i} $上的非光滑凸函数, 其中$ X_{i} $是闭凸集且$ \forall i\in \mathcal{I} $.

假设 2. 考虑的信息交换图$ \mathcal{G} $是强连通加权平衡有向图.

假设 3. 问题 (1) 至少存在一个有界的解.

注 1. 若局部Lipschitz函数$ g $是凸函数, 则$ \partial g(x) $在$x $处的次微分满足: $\partial g(x)=\{s\in {\bf{R}}^n : g(y)\geq g(x)+s^{\rm T}(x-x_{0})\}, \; \forall x\in {\bf R}^{m}$, $s $称为次梯度.

注 2. 在假设1的条件下, 函数非光滑是指目标函数和约束函数均为非连续可微函数. 我们通过Moreau-Yosida近似函数, 使非光滑函数转化为连续可微函数^[28], 即

其中, $ \gamma>0 $, 函数$ f_{\gamma}(x) $, $ g_{\gamma}(x) $分别是非光滑凸函数$ f(x) $, $ g(x) $的Moreau-Yosida近似函数. 根据文献[28]和文献[32]可知, 近似后的函数$ f_{\gamma}(x) $, $ g_{\gamma}(x) $为连续可微的凸函数, 并且满足关系式${\rm sup}_{\gamma > 0}f_{\gamma}(x)= {\rm lim}_{\gamma\rightarrow 0}f_{\gamma}(x)=f(x)$, ${\rm sup}_{\gamma > 0}g_{\gamma}(x)={\rm lim}_{\gamma\rightarrow 0}g_{\gamma}(x)= g(x)$. 值得注意的是, $ f(x) $, $ g(x) $是凸函数, 那么存在唯一的$ y $使 $f_{\gamma}(x)={\rm min}_{y\in {\bf R}^{mM}}\{f(y)+ \frac{1}{2\gamma}\|x\,- y\|^{2}\}$, 其中$ y $称为$ f $在$ x $处的近似算子.

1.2   预备知识

本节首先介绍图论的基本知识^{[2, 14]}. 包含$ M $个智能体的有向图为$ \mathcal{G(V,E,A)} $, 其中, $\mathcal{V}=\{1,2,\cdots, M\}$是各节点的集合, $ \mathcal{E}\subset \mathcal{V}\times \mathcal{V} $是边的集合. $\mathcal{A}= (a_{ij})\in {\bf R}^{MM}$是$ \mathcal{G} $的邻接矩阵, 当$ (i,j)\in \mathcal{E} $ ($ i\neq j $) 时, 表示节点$ j $可以传递信息给节点$ i $, $ a_{ij}>0 $; 当$(i,j)\notin \mathcal{E}$, $ a_{ij}=0 $. 任意的智能体之间均存在有向路径时, 称其为强连通有向图. $ D $是$ \mathcal{G} $的度矩阵, 智能体$ i $ 的入度和出度分别表示为: $ d_{i}^{\rm in}=\sum_{j=1}^{M}a_{ij} $, $d_{i}^{\rm out}= \sum_{j=1}^{M}a_{ji}$. $ L=(l_{i,j})\in {\bf R}^{MM} $是有向图的拉普拉斯矩阵, $ L=D^{\rm in}-\mathcal{A} $, $D^{\rm in}={\rm diag}\left\{d^{\rm in}_{1},d^{\rm in}_{2},\cdots,d^{\rm in}_{M}\right\}$. 其中$ l_{ii}=\sum_{j=1}^{M}a_{ij} $; 对于$ i\neq j $时, 有$ l_{ij}=-a_{ij} $. 当$d_{i}^{\rm in}= d_{i}^{\rm out}$时, 即$ \mathbf{1}_{M}^{\rm T}L=\mathbf{0}_{M}^{\rm T} $时, 有向图$ \mathcal{G} $是加权平衡图.

定义 1. $ P_{S}(\cdot) $是投影算子, $ P_{S}(u) $是$ u $在$ S $上的投影, $ P_{S}(u)={\rm arg min}_{y\in S}\|u-y\| $, 其中$ S\subset {\bf R}^{m} $是闭凸集. 由文献[24]可得当$ S $是闭凸集时, 对于$ \forall u\subset {\bf R}^{m},\; \forall y\in S $时, 有如下性质:

定义 2. $ N_{S}(x) $是$ x $在集合$ S $上的法锥^[28]

其中, 在集合$ S $上的法锥满足如下性质:

定义 3. 对于集值函数$ F:X_{0}\rightarrow {\bf R}^{m} $有微分包含式$ \dot{x}\in F(x),\; \; x(0)=x_{0} $. 则函数$ f(x) $在点$ x\in X_{0} $的李导数定义为^[28]

其中, ${\rm{d}}(f(x))$是对$ f(x) $的微分, 可以写成${\rm{d}}(f(x))= \frac{\partial f(x)}{\partial x}$.

引理 1^[28]. 在本文的假设条件下, $ x^{*} $是问题 (1) 的最优解, 当且仅当$ x^{*}\in X_{0}\subset {\bf R}^{m} $, $ \mu^{*}\in {\bf R}_{+}^{m} $满足如下条件, 其中$ i\in \mathcal{I} $.

证明. 由问题 (1) 可得出$ (L\otimes I_{m})x=0 $, $ x= {\rm col}(x_{1},x_{2},\cdots,x_{M}) $. 在本文的假设条件下, 根据文献[33]可知, 当优化问题中含有不等式约束时, 当且仅当$ \mu^{*}\in {\bf R}_{+}^{m} $满足式 (8) ~ (10) 时, $y= {\rm col}(y_{1},\cdots, y_{M})\in {\bf R}^{mM}$是问题 (1) 的最优解, $ i\in \mathcal{I} $. 将$y= {\rm col}(y_{1},\cdots,y_{M})$代入, 可得

其中, $ N_{X}(y)={\rm col}(N_{X}(y_{1}),\cdots,N_{X}(y_{M})) $. 根据式 (10) 中的等式关系可得, $ y_{i}=y_{j} $, 其中, $ i,j\in \mathcal{I} $. 因此一定存在$ y_{i}=x^{*} $, 其中$ x^{*}\in {\bf R}^{m} $, $ \forall i\in \mathcal{I} $. 则式 (8) 可以写为

等价于引理1中的式 (6).

由式 (9) 可知, $ {\mu^{*}}^{\rm T}\sum_{i=1}^{M}g_{i}(x^{*})\leq0 $, 根据法锥的定义及性质可得: $ P_{+}(\mu^{*}+\sum_{k=1}^{M}g_{k}(x^{*}))=\mu^{*} $, 进而得出$ \sum_{k=1}^{M}g_{k}(x^{*})\in N_{+}(\mu^{*}) \,.$ □

2.   分布式连续时间投影算法

2.1   算法设计

针对问题 (1), 提出如下分布式投影算法. 将非光滑目标函数$ f(x) $和$ g(x) $代入Moreau-Yosida近似函数中, 则分布式投影算法可以写为

其中, $ k,c_{1},c_{2}>0 $是增益常数, $ x_{i} $是各智能体$ i $的局部决策变量, $ \tau_{i}\in {\bf R}^{m} $, $ \mu_{i}\in {\bf R}_{+}^{m} $, $ s_{i}\in {\bf R}^{m} $是各智能体$ i $的变量.

对比文献[12]中用于离散时间系统的DIGing算法, 第2.1节中的算法不仅用到次梯度来保证算法收敛到最优解, 并且增加积分反馈项来校正由于局部梯度引起的误差, 最终满足算法在连续时间系统中的强连通加权平衡有向图的收敛.

非光滑凸函数$ f(x) $, $ g(x) $通过Moreau-Yosida近似函数转化为光滑凸函数$f_{\gamma}(x)$, $g_{\gamma}(x)$. 由于篇幅有限, 令$ x_{\gamma}=x $, $ \tau_{\gamma}=\tau $, $ \mu_{\gamma}=\mu $, $ s_{\gamma}=s $, $P^{\gamma}= P$. 定义$ x=(x_{1},\cdots,x_{M})^{\rm T} $, $ \tau=(\tau_{1},\cdots,\tau_{M})^{\rm T} $, $\mu= (\mu_{1},\cdots,\mu_{M})^{\rm T}$, $ s=(s_{1},\cdots,s_{M})^{\rm T} $, $P_{+}^{\mu}=(P_{+}^{\mu_{1}},\cdots, P_{+}^{\mu_{M}})^{\rm T}$, $ G(x)=(g_{1}(x_{1}),\cdots,g_{M}(x_{M}))^{\rm T} $. 简化后算法可以写为

其中, $P_{X}=P_{X}[x-\partial f(x)-\partial G(x)P_{+}^{\mu}-(L\otimes I_{n})\tau- (L\otimes I_{n})x]$, $P_{+}^{\mu}=P_{{\bf R}_{+}^{m}}[\mu-(L\otimes I_{m})(\mu+s)+G(x)]$.

引理 2^[28]. 当目标函数$ f $局部有界, 并且解的集合为非空凸集时, 对于任意初始点$ x_{i}(0)\in X_{i} $, 则每个智能体$ x_{i} $始终在其局部可行集$ X_{i} $内.

2.2   主要结果

假设分布式优化算法 (15) ~ (18) 一致收敛的平衡解为$ {\rm col}(x^{*},\tau^{*},\mu^{*},s^{*}) $, 在强连通加权平衡有向通信网络下, 证明其平衡解为优化问题 (1) 的最优解需满足的充要条件.

定理 1. 在假设1 ~ 3成立的条件下, 满足式(19)和式(20)时, 算法 (15) ~ (18) 的平衡解${\rm col}(x^{*},\tau^{*},\mu^{*}, s^{*})$是优化问题取得最优解的充分必要条件, 并且$ x^{*}\in {\bf R}^{m} $是问题 (1) 的最优解.

证明. 1)必要性. 在假设2中提到本文考虑的信息交互网络是强连通加权平衡有向的. 根据定义2中法锥的投影性质可知, 当且仅当$ x^{*}\in {\bf R}^{m} $满足$ -\partial f(x^{*})-\partial g(x^{*})\mu^{*}-L\tau^{*}\in N_{X}(x^{*}) $时, 有$\mathbf{0}_{mM}\in P_{X(x^{*})}\{-\partial f(x^{*})-\partial g(x^{*})\mu^{*}-L\tau^{*})\}$成立.

由引理1可知, 当且仅当$x^{*} \in {\bf R}^{m}$, $\mu^{*} \in {\bf R}^{m}_{+}$满足$\mathbf{0}_{m} \in \partial f_{i}(x^{*}) + \partial g_{i}(x^{*})\cdot\mu^{*} + N_{X_{i}}(x^{*}) ,$ $\sum_{k=1}^{M} g_{k} (x^{*})\in N_{+}(\mu{*})$时, $ x^{*}\in {\bf R}^{m} $是问题 (1) 的最优解. 因此

其中, $ \sum_{i=1}^{M}k_{i}(x^{*})=\mathbf{0}_{M} $, $k(x^{*})= [k_{1}(x^{*})^{\rm T}, k_{2}(x^{*})^{\rm T}, \cdots, k_{M}(x^{*})^{\rm T}]^{\rm T}\in {\bf R}^{mM}$. 并且可以得到: $(L\otimes I_{m})x= 0$, 即$ Lx^{*}=\mathbf{0}_{mM} $.

根据线性代数理论^[29]可知, $ {\rm ker}(L) $和$ {\rm range}(L) $是一对正交分解, 满足关系式 ${\rm ker}(L)^{\rm T}\cdots { \rm range}(L)= 0$. 本文中, 对于任意的$ x\in {\rm ker}(L) $, 有$\sum_{i=1}^{M}k_{i}^{\rm T}(x^{*})\cdots x=0$, $k\,(x^{*})\,\in {\rm range}\,(L)$. 因此存在$\tau^{*}=[\,(\tau_{1}^{*})^{\rm T}, (\tau_{2}^{*})^{\rm T},\cdots,(\tau_{M}^{*})^{\rm T}]^{\rm T}\in {\bf R}^{mM}$, $ \tau_{i}^{*}\in {\bf R}^{M} $, $ i\in \mathcal{I}_M $, 使$ k(x^{*})=-L\tau^{*} $成立. 代入式 (21) 得

2)充分性. 在有向图为强连通加权平衡图的条件下, 其拉普拉斯矩阵$ L $为对称矩阵, 并且满足等式条件$ {\bf{1}}_{M}^{\rm T}L=\mathbf{0}_{M}^{\rm T} $. 可以很容易得到: $ Ly^{*}=\mathbf{0}_{mM} $. 根据本文的假设, 问题 (1) 至少存在一个有界的解$ x^{*}\in {\bf R}^{m} $. 代入式 (19), 可得

其中, $\tau^{*}= [(\tau_{1}^{*})^{\rm T},\cdots$, $ (\tau_{M}^{*})^{\rm T}] $, $ \tau_{i}^{*}\in {\bf R}^{m} $.

加权平衡有向图的拉普拉斯矩阵$ L $是对称矩阵, 可得

因此, $k_{i}(x^{*})\in -\partial f_{i}(x^{*})\;- \partial g_{i}(x^{*})\mu^{*}- N_{X_{i}}(x^{*}).$将$ \sum_{i=1}^{M}k_{i}(x^{*})=0 $代入上式可得 $\mathbf{0}_{mM}\in -\partial f(y^{*})\;- \partial g(y^{*})\mu^{*}- N_{X}(y^{*})$. 根据引理1可知, $ x^{*} $是问题 (1) 的最优解. □

下面提出的定理2是根据文献[28]证明算法 (15) ~ (18) 的输出轨迹$ x $收敛于同一个平衡解, 并结合定理1的结论得到的. 即分布式投影算法在强连通加权平衡有向图网络下, 算法渐近收敛到优化问题 (1) 的最优解.

定理 2. 在假设1 ~ 3条件下, 对于问题 (1) 的任意初始值$(x_{i}(0),\tau_{i}(0),\mu_{i}(0),s_{i}(0))\in (X_{i}\times {\bf R}^{m}\times {\bf R}_{+}^{m}\times {\bf R}^{m})$, 各变量$ (x,\tau,\mu,s) $是有界的, 并且分布式投影算法 (15) ~ (18) 中的决策变量$ x $最终会收敛到问题 (1) 的最优解. 此时各参数$ k $, $ c_{1} $, $ c_{2} $需满足

证明. 令$ {\rm col}(x^{*},\tau^{*},\mu^{*},s^{*}) $是算法 (15) ~ (18) 的平衡点, 根据定理1可知$ x^{*} $是问题 (1) 的最优解.

为了简便, 令$ \mathfrak{L}_{m}=L\otimes I_{m} $, $ \mathfrak{L}_{n}=L\otimes I_{n} $. $X= x-\bar{x}$, $ \mathfrak{T}=\tau-\tau^{*} $, $ \mathfrak{U}=\mu-\bar{\mu} $, $ \mathfrak{S}=s-s^{*} $, $\chi= x+\tau$, $ \chi^{*}=\bar{x}+\tau^{*} $. $\mathfrak{P}_{1}=P_{X}- x$, $\mathfrak{\bar{P}}_{1}=P_{X}- \bar{x}$, $\mathfrak{P}_{2}=P_{+}^{\mu}-\mu$, $\mathfrak{\bar{P}}_{2}=P_{+}^{\mu}-\bar{\mu}$.

构造李雅普诺夫函数^[28] $ J_{1} $, $ J_{2} $, $ J_{3} $, 其中, $ J_{1} $为

已知$ f(x) $和$ g(x) $是凸函数, 根据欧几里德范数的性质可知$ \|P_{+}^{\mu}\|^{2} $是关于$ \mu $的凸函数. 显而易见, $ \chi^{\rm T}\mathfrak{L}_{n}\chi $也是关于$ x $, $ \mu $的凸函数, 易证$ J_{1} $的凸性. 根据凸函数的性质可得: $ J_{1}\geq 0 $. 因此可对$ J_{1} $求导, $ J_{1} $的李导数$\widetilde{L}_{{\rm{F}}}J_{1}$为

定义李雅普诺夫函数

将$ J_{2} $整理成矩阵形式, 可根据式 (22) 中各参数满足的不等式关系$ c_{1}\lambda_{M}(L)<2k $证明该矩阵为正定矩阵. 进而求得$ J_{2} $的李导数$ \widetilde{L}_{{\rm{F}}}J_{2} $为

对求导后的李雅普诺夫函数$\widetilde{L}_{{\rm{F}}}J_{1}$和$\widetilde{L}_{{\rm{F}}}J_{2}$相加可得

对$\widetilde{L}_{{\rm{F}}}J_{1}+\widetilde{L}_{{\rm{F}}}J_{2}$进行化简整理, 得

根据投影的性质有: $2k\{\nabla_{x}^{\rm T}[f(x)+\frac{1}{2}\|P_{+}^{\mu}\|^{2}\;+$ $\frac{1}{2}\chi^{\rm T}\mathfrak{L}_{n}\chi]\;+\;\mathfrak{P}_{1}\}^{\rm T}\mathfrak{\bar{P}}_{1}\leq 0, \;\;-2k\nabla_{x}^{\rm T}[f(\bar{x})\;+\;\frac{1}{2}\|P_{+}^{\bar{\mu}}\|^{2}\;+$ $\frac{1}{2}(\chi^{*})^{\rm T}\mathfrak{L}_{n}(\chi^{*})]\}^{\rm T}\mathfrak{\bar{P}}_{1}\leq 0 $, 则$\widetilde{L}_{{\rm{F}}}J_{1}+\widetilde{L}_{{\rm{F}}}J_{2}$可以化简为

根据凸函数的性质有: $-(\nabla f(x)-\nabla f(\bar{x}))^{\rm T}(x\;- \bar{x})\leq 0$, 通过式 (16)和式(18) 可知, $\mathfrak{L}_{n}(x-\bar{x})=\mathfrak{L}_{n}x= \dot{\tau}/c_{1}$, $ \mathfrak{L}_{n}(\mu-\bar{\mu})=\mathfrak{L}_{n}\mu=\dot{s}/c_{2} $. 则$\widetilde{L}_{{\rm{F}}}J_{1}+\widetilde{L}_{{\rm{F}}}J_{2}$可以化简为

定义李雅普诺夫函数$ J_{3} $为

将$ J_{3} $整理成矩阵形式, 可根据式 (22) 中各参数满足的不等式关系$ c_{2}\lambda_{M}(L)<2k $证明该矩阵为正定矩阵. 因此可对$ J_{3} $求导得$\widetilde{L}_{{\rm{F}}}J_{3}$, 即

对上述求导后的结果$\widetilde{L}_{{\rm{F}}}J_{1}$, $\widetilde{L}_{{\rm{F}}}J_{2}$, $\widetilde{L}_{{\rm{F}}}J_{3}$相加并化简为

根据投影性质可得, $2k\mathfrak{\bar{P}}_{2}^{\rm T}[\mathfrak{P}_{2}+\mathfrak{L}_{m}(\mu+s)\;- G(x)]\leq 0$, 代入化简为

根据定义2可知, $ 2k\mathfrak{\bar{P}}_{2}^{\rm T}(G(\bar{x})-\mathfrak{L}_{m}s^{*})\leq 0 $, 代入化简为

由凸函数的性质可得如下两个不等式关系:

那么$\widetilde{L}_{{\rm{F}}}J$可以整理为

其中, $ \dot{\mu}=k(P_{+}^{\mu}-\mu) $, $ \dot{s}=c_{2}\mathfrak{L}_{n}\mu $, 代入式(36), 可得

化简, 并将$ -\frac{1}{k}\dot{\mu}(L\otimes I_{m})\dot{\mu}\leq 0 $代入, 得

代入定理2中的设定条件可知, 上式为半正定矩阵. 因此能够得出$ J(t)\leq J(0) $, 进而证明了各参数$ x,\; \tau,\; \mu,\; s $的有界性. 结合引理2可知, 当目标函数$ f $局部有界时, 对于优化问题 (1) 的任意初始点$ x_{i}(0)\in X_{i} $, 每个智能体$ x_{i} $始终在局部可行集$ X_{i} $内.

假设存在常数$ \varepsilon>0 $, 使其满足$2kL - (c_{2} + \varepsilon)L^{2} > 2kL-(c_{1}+\varepsilon)L^{2}\geq0$. 即满足$2kL\;-\;c_{2}L^{2}\;\geq\;2kL- c_{1}L^{2}\;\geq\;\varepsilon L^{2}$. 可以看出$ \varepsilon $的范围为

根据定理2的假设条件可知, $ \frac{2k}{\lambda_{M}(L)-c_{1}}>0 $, $ \frac{2k}{\lambda_{M}(L)-c_{2}}>0 $, 则一定存在满足条件的常数$ \varepsilon $. 根据两个不等式关系, $\widetilde{L}_{{\rm{F}}}J$可以整理为

根据注${2}$中提到的Moreau-Yosida近似函数和性质可知, 对于优化问题 (1) 的任意初始解$(x(0), \tau(0),\mu(0),s(0))\in (X\times {\bf R}^{m}\times {\bf R}_{+}^{m}\times {\bf R}^{m})$ 时, 有等式关系${\rm lim}_{\gamma\rightarrow0}{\rm col}(x_{\gamma}(0),\tau_{\gamma}(0),\mu_{\gamma}(0),s_{\gamma}(0)) = {\rm col}(x(0), \tau(0),\mu(0),s(0))$. 当函数$ f $, $ g $是凸函数, 在局部可行集上是连续可微的并且有下界^[28], 那么分布式投影算法 (15) ~ (18) 的解一定存在.

当$ t\rightarrow \infty $时, 各状态为$ P_{X}=x $, $ P_{+}^{\mu}=\mu $, $x= {\boldsymbol{1}}_{M}\otimes x'$, $\mu={\boldsymbol{1}}_{M}\otimes \mu'$, 可得$\widetilde{L}_{{\rm{F}}}J\leq{{0}}$, 即优化问题的所有可行解渐近收敛到平衡解, 式 (39) 成立. 结合定理1证明的算法的平衡解为优化问题 (1) 的充分必要条件可知, 分布式投影算法 (15) ~ (18) 中的决策变量$ x $满足耦合不等式约束和局部可行集约束的条件下最终会收敛到问题 (1) 的最优解. □

3.   仿真研究

本节通过数值实验来验证强连通有向通信拓扑图下的分布式连续时间投影算法的有效性.

考虑由4个智能体组成的强连通有向通信拓扑图, 如图1所示. 局部代价函数为$ f_{i}(x)=\|x-\omega_{i}\| $, 其中, $ \omega_{i} $是各智能体对应的目标点, 即

图 1  加权平衡有向交互图

Fig. 1  Weight-balanced directed interaction graph

下载: 全尺寸图片 幻灯片

局部耦合不等式约束为$g_{i}(x)=\|x-\omega_{0}\|/4\;- i/4\leq0$, $ i\in\{1,2,3,4\} $, 其全局耦合不等式约束为$ g(x)=\|x-\omega_{0}\|-5/2\leq0 $, 其中, $ \omega_{0}={\rm col}(4,4) $是耦合不等式约束的中心点^[28]. 定义各智能体的状态初始值为$ x_{1}={\rm col}(2,6) $, $ x_{2}={\rm col}(3,3) $, $ x_{3}={\rm col}(5,2) $, $ x_{4}={\rm col}(1,2) $, 令$ k=4 $, $ c_{1}=1.3 $, $ c_{2}=1.2 $. 每个智能体的局部可行集$ X_{i} $为

由此可以看出, 针对本文所提的分布式优化问题 (1), 4个智能体在局部可行集约束和耦合不等式约束范围内共同协作找到距离4个目标点$ \omega_{i} $最近的点. 如图2所示, 其中三角形表示各智能体$ x_{i} $局部可行集的交集, 圆形表示耦合不等式约束的范围. 从仿真图中可以看出, 对于满足局部可行集约束和耦合不等式约束情况下的任意初始值, 各智能体最终收敛到分布式优化问题的最优解.

图 2  状态$ x_{i} $的轨迹图

Fig. 2  Trajectories graph of state $ x_{i} $

下载: 全尺寸图片 幻灯片

图3 ~ 5分别表示变量$ \tau $, $ \mu $, $ s $的运动轨迹, 从图中我们可知所有变量是一致收敛的, 并且$ \mu_{i} $总是非负的, 仿真算例验证了理论结果. 本文中的算法是利用各智能体在其局部可行集上进行投影, 不同于文献[24]中在切锥上的投影, 节约了智能体间的交互、计算和时间成本, 使算法更快地达到收敛. 其次, 连续时间系统更具灵活性和实时性, 可满足对实时优化精度高的实际应用.

图 3  状态$ \tau_{i} $的轨迹图

Fig. 3  Trajectories graph of state $ \tau_{i} $

下载: 全尺寸图片 幻灯片

图 4  状态$ \mu_{i} $的轨迹图

Fig. 4  Trajectories graph of state $ \mu_{i} $

下载: 全尺寸图片 幻灯片

图 5  状态$ s_{i} $的轨迹图

Fig. 5  Trajectories graph of state $ s_{i} $

下载: 全尺寸图片 幻灯片

4.   结束语

本文研究了在强连通加权平衡的有向通信拓扑网络中, 目标函数和约束为凸函数, 满足耦合不等式路径约束和局部可行集约束的情况下, 找到了证明算法的平衡解为分布式优化问题最优解的充分必要条件, 并且所提分布式连续时间投影算法渐近收敛到全局最小值点. 结合文献[28]中的分布式连续时间投影算法设计, 基于在智能体局部可行集上的投影, 通过近似函数将非光滑的目标函数和约束近似为连续可微的凸函数, 构造李雅普诺夫函数并证明算法收敛到分布式优化问题的最优解. 与加权平衡有向图相比, 分布式算法在加权不平衡有向图的设计对系统性能、资源分配等具有更普遍的意义, 其收敛性分析也具有更大的挑战. 未来的研究方向集中在将分布式投影算法拓展到加权不平衡有向图网络下, 并考虑放缩强连通的假设条件至一致联合连通时算法收敛的问题.