• 写在前面
• 问题描述和算法
• 收敛性证明

写在前面

原论文：Distributed Optimization with Projection-free Dynamics.

本文是Chen 2021^[1]的笔记，主要记录了一种带约束的gradient tracking算法，该算法无需投影算子即可保证约束集始终满足。

问题描述和算法

考虑分布式优化问题

$\min_{x}\, F(x) \quad \text{s.t.} \,\, x\in\Omega$

其中$F(x)=\frac{1}{n}\sum_{i=1}^nf_i(x)$。

假设1：

• 集合$\Omega$紧凸非空；
• $f_i$凸可微，$\nabla f_i$在$\Omega$上$\kappa$-Lipschitz连续。
• 有向图是强连通平衡的。

给出算法

$\begin{aligned} \dot x_i&=\sum_{j=1}^n a_{ij}(x_j-x_i)+\beta(t)(v_i-x_i)\\ \dot y_i&=\sum_{j=1}^n a_{ij}(y_j-y_i)+\dot \nabla f_i(x_i)\\ v_i&=\arg\min_{v\in\Omega}y_i^Tv \end{aligned}$

其中初始条件满足$x_i(0),v_i(0)\in\Omega$，$y_i(0)=\nabla f_i(x_i(0))$。

此外，控制参数$\beta(t)$满足$\operatorname{lim}_{t\to\infty}\beta(t)=0$且$\operatorname{lim}_{t\to\infty}\int_0^t\beta(\tau)d\tau=\infty$。

收敛性证明

写成矩阵形式

$\begin{aligned} \dot x&=-Lx+\beta(v-x)\\ \dot y&=-Ly+\dot g \end{aligned}$

其中$g_i:=\nabla f_i(x_i)$。

引理1：在假设1满足情况下，对任意$i\in\mathcal V$，如果$x_i(0)\in\Omega$，那么$x_i(t)\in\Omega$，$t>0$。

证明：首先给出法锥定义，$\mathcal N_\Omega(x)=\{v|v^T(y-x)\leq 0, y\in\Omega \}$。

由于$(x_i-P_\Omega(x_i))^T(y-x_i)\leq 0$，故$x_i-P_\Omega(x_i)\in \mathcal N_\Omega(x_i)$。

因为$v_i\in\Omega$，故$v_i-x_i\in \mathcal T_\Omega(x_i)$。而一旦$x_j\in\Omega$，则有$x_j-x_i\in \mathcal T_\Omega(x_i)$。(需要所有agent的约束集相同)

因此$\dot x_i=\sum_{j=1}^n a_{ij}(x_j-x_i)+\beta(t)(v_i-x_i)\in\mathcal T_\Omega(x_i)$。

定义能量函数

$E = \frac{1}{2}\|x_i-P_\Omega(x_i)\|^2$

对时间求导

$\dot E=(x_i-P_\Omega (x_i))^T\dot x_i$

因为切锥法锥是正交的，一旦$x_i\in\Omega$，则$\dot E=0$，故得证。

引理2：给定$\varepsilon(t)\geq 0$，$s(t)\geq 0$和$\gamma (t)\geq 0$，如果$\operatorname{lim}_{t\to\infty}\varepsilon(t)=0$且$\operatorname{lim}_{t\to\infty}\int_0^t\gamma(\tau)d\tau=\infty$，

$\dot s(t)\leq -\gamma(t)s(t)+\gamma (t)\varepsilon(t),$

那么$\lim_{t\to \infty}s (t)=0$。

证明：令$h(t)=\operatorname{exp}\int_0^t\gamma(\tau)d\tau$。则$\operatorname{lim}_{t\to\infty}h(t)=\infty$且$\dot h(t)=\gamma(t)h(t)$。

由于$s(t)\geq 0$和$\dot s(t)\leq -\gamma(t)s(t)+\gamma(t)\varepsilon(t)$，两边同乘$h(t)$得到

$\frac{d}{dt}(s(t)h(t))\leq \gamma(t)h(t)\varepsilon(t).$

由比较引理，对上式两边同时积分，得到

$s(t)\leq \frac{s(0)}{h(t)}+\frac{1}{h(t)}\int_0^t\gamma(\tau)h(\tau)\varepsilon(\tau)d\tau.$

如果$\int_0^t\gamma(\tau)h(\tau)\varepsilon(\tau)d\tau\leq \infty$，那么$\lim_{t\to \infty}s(t)=0$。

否则根据L’ Hospital rule，有

$\lim_{t\to\infty} \sup s(t)\leq \lim_{t\to\infty}\frac{\gamma(t)h(t)\varepsilon(t)}{\gamma(t)h(t)}=\lim_{t\to\infty}\varepsilon(t)=0.$

L’ Hospital rule：

定理1：在假设1和初始条件满足情况下，

• 所有$x_i$达成一致性；
• 所有$y_i$渐进收敛于$\frac{1}{n}\sum_{i=1}^n g_i$。
• 所有$x_i$收敛于最优解$x^*$。

证明：1）由引理1，$x_i\in\Omega$。又$v_i\in\Omega$，故$v_i-x_i$有界。因此$\beta(v_i-x_i)\to 0$当$t\to 0$。由Shi 2013^[2]可知，$x_i-x_j\to 0$。

2）定义$W=y-\frac{1}{n}1_n1_n^Tg$。考虑$y=y_0+y_\bot$，使得$y_0\in\ker(L)$且$y_\bot\in \ker(L)_\bot$。

由于$1_n^T y=1_n^Tg$，且$y_0\in\ker(L)$，故$y_0-\frac{1}{n}1_n1_n^Tg=0$。即$W=y_\bot\in \ker(L)_\bot$。

（实际上$1_n^T y_0=1_n^Tg$且$1_n^Ty_\bot=0$）

定义能量函数$J=\frac{1}{2}\|W\|^2$。由于图是平衡图，$L^T1_n=0$。对时间求导，

$\begin{aligned} \dot J&=-(y-\frac{1}{n}1_n1_n^Tg)^TLy+(y-\frac{1}{n}1_n1_n^Tg)^T\Pi\dot g\\ &\leq -W^TL_sW+\|W\|\|\Pi\|\|\dot g\|\\ &\leq -\lambda_2\|W\|^2+\|W\|\|\Pi\|\|\dot g\|\\ \end{aligned}$

又

$\frac{d}{dt}\|W\|=\frac{d}{dt}\sqrt{2J}=\frac{\dot J}{\|W\|}\leq-\lambda_2\|W\|^2+\|W\|\|\Pi\|\|\dot g\|$

由于$g$是$\kappa$-Lipschitz的，$\|\dot g\|\leq \kappa\|\dot x\|=\kappa\|-Lx+\beta(v-x)\|$。由1）的分析，$\|\dot g\|\to 0$。

再由引理2，$\|W\|\to 0$。

3）令$\bar x=\frac{1}{n}\sum_{i=1}^nx_i$。考虑函数

$V=F(\bar x)-F(x^*)\geq 0$

定义$\bar g_i = \nabla f_i(\bar x)$。对时间求导，

$\begin{aligned} \dot V&=\frac{1}{n}(1_n^T\bar g)^T\dot {\bar x}\\ &=\frac{1}{n^2}(1_n^T\bar g)^T1_n^T\dot x\\ &=\frac{1}{n^2}\bar g^T1_n1_n^T(-Lx+\beta(v-x))\\ &=\frac{\beta}{n^2}\bar g^T1_n1_n^T(v-x)\\ &=\frac{\beta}{n^2}(\bar g^T1_n1_n^T-ny^T)(v-x)+\frac{\beta}{n}y^T(v-x) \end{aligned}$

由于$y^Tv\leq y^T(1_n\otimes x^*)$恒成立，得到

$\begin{aligned} \dot V&\leq \frac{\beta}{n^2}(\bar g^T1_n1_n^T-ny^T)(v-x)+\frac{\beta}{n}y^T(1_n\otimes x^*-x)\\ &=\frac{\beta}{n^2}(\bar g^T1_n1_n^T-ny^T)(v-1_n\otimes x^*+1_n\otimes x^*-x)+\frac{\beta}{n}y^T(1_n\otimes x^*-x)\\ &=\frac{\beta}{n^2}(\bar g^T1_n1_n^T-ny^T)(v-1_n\otimes x^*)+\frac{\beta}{n^2}\bar g^T1_n1_n^T(1_n\otimes x^*-x)\\ \end{aligned}$

由凸函数性质

$\begin{aligned} \frac{\beta}{n^2}g^T1_n1_n^T(1_n\otimes x^*-x)&=\beta(\frac{1}{n}1_n^T\bar g)^T(x^*-\bar x)\\ &\leq \beta(F(x^*)-F(\bar x))=-\beta V \end{aligned}$

$\begin{aligned} \frac{\beta}{n^2}(\bar g^T1_n1_n^T-ny^T)(v-1_n\otimes x^*)&=\frac{\beta}{n^2}( g^T1_n1_n^T-ny^T)(v-1_n\otimes x^*)\\ &\quad +\frac{\beta}{n^2}(\bar g^T1_n1_n^T- g^T1_n1_n^T)(v-1_n\otimes x^*)\\ &\leq \frac{\beta}{n}(\|W\|+\kappa n\|1_n\otimes \bar x-x\|)\|v-1_n\otimes x^*\| \end{aligned}$

因为$v_i,x^*\in\Omega$，故$\|v-1_n\otimes x^*\|\leq c$有界。则

$\dot V\leq -\beta V+\frac{c\beta}{n}(\|W\|+\kappa n\|1_n\otimes \bar x-x\|)$

再次利用引理2，得到$V\to 0$。

由于$F(x)$不是强凸，需要加证明$x\to x^*$，见原论文。

---

1. G. Chen, P. Yi, and Y. Hong, “Distributed Optimization with Projection-free Dynamics,” May 2021. ↩︎

2. G. Shi and K. H. Johansson, “Robust consensus for continuous-time multiagent dynamics,” SIAM Journal on Control and Optimization, vol. 51, no. 5, pp. 3673–3691, 2013. ↩︎