• 问题描述
• KKT条件
• 无向图的情况
• 有向图的情况

问题描述

考虑常见的带约束分布式优化问题，如下

$\begin{aligned} \min &\quad F(\boldsymbol x)=\sum_{i=1}^n f_i(x_i)\\ \operatorname{s.t.} &\quad x_1=x_2\cdots= x_n,\\ &\quad x_i\in\Omega_i, \,i\in\mathcal V, \end{aligned}$

其中$\boldsymbol x=[x_1^T,\cdots,x_n^T]^T$。每个agent的动力学建模为单积分器，即$\dot x_i=u_i$，$\forall i\in\mathcal V$。

先做两个常用假设，一是$\cap_{i=1}^n\Omega_i\neq \emptyset$，二是$f_i(x_i)$强凸。前者保证了解的存在性和Slater's condition成立，从而KKT条件是最优解的充分必要条件；后者保证了解的唯一性。

定义分布式系统的通信拓扑表示为图$\mathcal G=(\mathcal V,\mathcal E)$，其拉普拉斯矩阵满足$L\boldsymbol 1=\boldsymbol 0$。若图$\mathcal G$是weighted-balanced，那么拉普拉斯矩阵额外满足$\boldsymbol 1^TL=\boldsymbol 0^T$。

对于闭凸集$\Omega\in\mathbb R^n$，定义投影$P_\Omega(x):=\arg\min_{z\in\Omega}\|x-z\|$。投影具有如下性质：

$(x-P_\Omega(x))^T(P_\Omega(x)-z),\,\forall x\in\mathbb R^n,\,z\in\Omega，\\ \|P_\Omega(x)-P_\Omega(y)\|\leq \|x-y\|,\,\forall x,y\in\mathbb R^n。$

对于$x\in\Omega$，$\Omega$在$x$处的法锥(normal cone)定义为$N_{\Omega}(x):=\{u\in\mathbb R^n|u^T(z-x)\leq \boldsymbol 0,\,\forall z \in\Omega\}$。

法锥具有如下性质：

$x=P_{\Omega}(x-u)\Leftrightarrow - u\in N_{\Omega}(x)。$

此外，$\boldsymbol 0\in N_{\Omega}(x)$必定成立。

KKT条件

换个思路，如果考虑集中式优化问题

$\begin{aligned} \min&\quad F(x)=\sum_{i=1}^nf_i(x)\\ \operatorname{s.t.} &\quad x\in\cap_{i=1}^n\Omega_i \end{aligned}$

由KKT条件，最优解$x$满足

$\boldsymbol 0\in\sum_{i=1}^n\partial f_i(x^*)+N_{\cap_{i=1}^n\Omega_i}(x^*)。\qquad (1)$

将原优化问题写成紧凑形式

$\begin{aligned} \min&\quad F(\boldsymbol x)\\ \operatorname{s.t.}&\quad (L\otimes I_n)\boldsymbol x=\boldsymbol0，\\ &\quad \boldsymbol x\in\Omega， \end{aligned}$

其中$\boldsymbol \Omega=\Pi_{i=1}^n\Omega_i$。由KKT条件，最优解$\boldsymbol x^*$满足

$\begin{aligned} \boldsymbol 0&\in\partial \boldsymbol f(\boldsymbol x^*)+(L^T\otimes I_n)\boldsymbol y^*+N_{\boldsymbol \Omega}(\boldsymbol x^*)，\\ \boldsymbol 0&=(L\otimes I_n)\boldsymbol x^*。 \end{aligned}\qquad(2)$

最优解必定满足上述两个条件其中之一。由于这两个问题等价，所以(2)必定能推出(1)。

无向图的情况

假设图G是连通图。

给出如下算法

$\begin{aligned} \dot x_i&=P_{\Omega_i}\left(x_i-\partial f_i(x_i)-\sum_{i=1}^na_{ij}(y_i-y_j)\right)-x_i，\\ \dot y_i&=\sum_{i=1}^na_{ij}(x_i-x_j)。 \end{aligned}$

上式紧凑形式为

$\begin{aligned} \dot {\boldsymbol x}&=P_{\boldsymbol \Omega}(\boldsymbol x-\partial \boldsymbol f(\boldsymbol x)-(L\otimes I_n)\boldsymbol y)-\boldsymbol x，\\ \dot {\boldsymbol y}&= (L\otimes I_n)\boldsymbol x。 \end{aligned}$

显然平衡点满足式(2)。

令$\boldsymbol u\in N_{\boldsymbol \Omega}(\boldsymbol x^*)$，则对任意$\boldsymbol u$，都有$\boldsymbol u^T(\boldsymbol z-\boldsymbol x^*)\leq 0$，$\forall \boldsymbol z\in\boldsymbol \Omega$。

令$\bar {\boldsymbol \Omega}=\cap_{i=1}^n\Omega_i\times\cdots\times\cap_{i=1}^n\Omega_i\in\boldsymbol\Omega$。则对于$\forall \bar {\boldsymbol z}\in\bar {\boldsymbol \Omega}\subset\boldsymbol\Omega$，上式也成立。

因此，$\boldsymbol u^T (\boldsymbol 1\otimes I_n) (\bar z-x^*)= \boldsymbol u^T (\bar {\boldsymbol z}-\boldsymbol x^*)\leq 0$，即，

$\begin{aligned} 0&\in(\boldsymbol 1^T\otimes I_n)(\partial \boldsymbol f(\boldsymbol x)+(L\otimes I_n)\boldsymbol y))+N_{\cap_{i=1}^n\Omega_i}(x)\\ &=\sum_{i=1}^n\partial f_i(x^*)+N_{\cap_{i=1}^n\Omega_i}(x^*) \end{aligned}，$

故平衡点同样满足式(1)，即(2)能推出(1)。

有向图的情况

假设图$G$是weight-balanced且强连通。

给出如下算法

$\begin{aligned} \dot x_i&=P_{\Omega_i}\left(x_i-\partial f_i(x_i)-\sum_{i=1}^na_{ij}(x_i-x_j)-y_i\right)-x_i，\\ \dot y_i&=\sum_{i=1}^na_{ij}(x_i-x_j)， \end{aligned}$

其中初始条件$\sum_{i=1}^n y_i(0)=0$。

上式紧凑形式为

$\begin{aligned} \dot {\boldsymbol x}&=P_{\boldsymbol \Omega}(\boldsymbol x-\partial \boldsymbol f(\boldsymbol x)-(L\otimes I_n)\boldsymbol x-\boldsymbol y)-\boldsymbol x，\\ \dot {\boldsymbol y}&= (L\otimes I_n)\boldsymbol x。 \end{aligned}$

由于$\sum_{i=1}^n\dot y_i=0$，所以$\sum_{i=1}^ny_i=\sum_{i=1}^ny_i(0)=0$。

令上式左侧为0，可知平衡点满足$\boldsymbol 0=(L\otimes I_n)\boldsymbol x^*$，即consensus条件成立；同时

$\boldsymbol 0\in \partial \boldsymbol f(\boldsymbol x^*) +\beta(L\otimes I_n)\boldsymbol x^*+\boldsymbol y^*+ N_{\boldsymbol \Omega}(\boldsymbol x^*)$

对于任意$\boldsymbol u\in N_\Omega(\boldsymbol x^*)$，都有$\boldsymbol u^T(\boldsymbol z-\boldsymbol x^*)\leq 0$，$\forall \boldsymbol z\in\boldsymbol \Omega$。

令$\bar {\boldsymbol \Omega}=\cap_{i=1}^n\Omega_i\times\cdots\times\cap_{i=1}^n\Omega_i\in\boldsymbol\Omega$，$\boldsymbol x^*=[x^{*T},\cdots,x^{*T}]^T$。则对于$\bar {\boldsymbol z}\in\bar {\boldsymbol \Omega}$，上式也成立。

因此，$\boldsymbol u^T (\boldsymbol 1\otimes I_n) (\bar z-x^*)= \boldsymbol u^T (\bar {\boldsymbol z}-\boldsymbol x^*)\leq \boldsymbol 0$，即

$\begin{aligned} 0&\in(\boldsymbol 1^T\otimes I_n)(\partial \boldsymbol f(\boldsymbol x)+\beta(L\otimes I_n)\boldsymbol x^*+\boldsymbol y^*)+N_{\cap_{i=1}^n\Omega_i}(x)\\ &=\sum_{i=1}^n\partial f_i(x^*)+N_{\cap_{i=1}^n\Omega_i}(x^*) \end{aligned}。$

可以看出，关键在于满足投影算子内部的补偿项求和为0，剩下的事情就是证明平衡点的稳定性。