• 写在前面
• 问题描述
• 分布式算法
• 结论与证明

写在前面

原论文：Distributed Time-Varying Quadratic Optimization for Multiple Agents under Undirected Graphs^[1].

由于个人喜好问题，本文只做原论文中的Problem 2，Section 3-C，Section 3-D相关笔记。

问题描述

优化问题

$\begin{aligned} \min&\quad f(x,t)=\sum_{i=1}^n f_i(x_i,t)\\ \text{s.t.}&\quad Lx=0,\quad x\in\Omega \end{aligned} \qquad (1)$

其中$x=[x_1^T,\cdots,x_n^T]^T$，$\Omega=\Omega_1\times\cdots\times \Omega_n$。

分布式算法

改成罚函数形式

$\min F(x,t)=\sum_{i=1}^n f_i(x_i,t)+\frac{1}{2}\beta x^TLx,\quad x\in\Omega\qquad (2)$

罚函数投影算法

$\dot x_i=kP_{\Omega_i}\left(x_i-\alpha \frac{\partial f_i(x_i,t)}{\partial x_i}-\alpha\beta\sum_{j=1}^n a_{ij}(x_i-x_j) \right)-kx_i\qquad (3)$

其中$\alpha$、$k$是待定参数。

结论与证明

Lemma 3^[2]: For all $x,y\in\mathbb R^n$ and a nonempy compact set $K\subset \mathbb R^n$, $\|P_K(x)-P_K(y)\|\leq \|x-y\|$.

Lemma 6: $x^*(t)$ is an optimal solution of (2) if and only if for some fixed $\alpha>0$, $P_\Omega(-\alpha\frac{\partial F(x^*(t),t)}{\partial x}+x^*(t))=x^*(t)$, $\forall x\in\Omega$, $t>t_0$.

注意到Lemma 6成立，是因为$0\in\partial F(x^*)+N_\Omega(x^*)$（Lemma 2.1^[3]）。

最优条件得到了，下一步就是收敛性。

Theorem 5: The updating law in (3) guarantees $\|x(t)-x^*(t)\|$ uniformly ultimately bounded as $t\to \infty$ with ultimate bound $\|x(t)-x^*(t)\|\leq \sqrt{\frac{1}{2k(1-\varepsilon_L)-1}}\bar \omega_L$, where $0<\varepsilon_L<1$ is a positive constant, $\bar \omega_L$ is the upper bound of $\|\dot x^*(t)\|$, provided that there exist positive constants $q_1$ and $q_2\geq q_1$ such that $q_1 I\leq R(t)\leq q_2I$, $\dot x^*(t)$ exists, the elements in $R(t)$ and $x^*(t)$, $\dot x^*(t)$ are bounded and the control parameters $\varepsilon_L, \alpha,\beta$ and $k$ are chosen such that

$\begin{aligned} \frac{q_2+\beta \lambda_\text{max} (L)-q_1}{q_2+\beta\lambda_\text{max}(L)+q_1}&<\varepsilon_L<1,\quad k>\frac{1}{2(1-\varepsilon_L)},\\ \frac{1-\varepsilon_L}{q_1}&<\alpha<\frac{1+\varepsilon_L}{q_2+\beta\lambda_\text{max}(L)}. \end{aligned}$

证明：注意到原论文考虑二次代价函数，即

$F(x,t) = \frac{1}{2}x^T(R(t)+\beta L)x+s^T(t)x+h(t)$

则有

$\frac{\partial F(x,t)}{\partial x} = R(t)x+\beta Lx+s(t)$

式(3)重写为

$\dot x=kP_\Omega(x-\alpha R(t)x-\beta Lx-\alpha s(t))-x$

定义李雅普诺夫函数$V=\frac{1}{2}e^Te$，其中$e=x-x^*(t)$，$x^*(t)$满足$P_\Omega(x^*(t)-\alpha R(t)x^*(t)-\alpha\beta L x^*(t)-\alpha s(t))=x^*(t)$。

那么，可以得到

$\begin{aligned} P_\Omega&(x-\alpha R(t)x-\alpha s(t))-x\\ &=P_\Omega(e+x^*(t)-\alpha R(t)e-\alpha R(t)x^*(t)-\alpha\beta Le -\alpha\beta L x^*(t) -\alpha s(t))\\ &\quad -P_\Omega(x^*(t)-\alpha R(t)x^*(t)-\alpha \beta L x^*(t) -\alpha s(t))-e \end{aligned}$

李雅普诺夫函数对时间导数为

$\begin{aligned} \dot V&=e^T(kP_\Omega(x-\alpha R(t)x-\alpha \beta L x-\alpha s(t))-kx-\dot x^*(t))\\ &\leq -ke^Te+k\|e\|\|\zeta\|+\|e\|\|\dot x^*(t)\| \end{aligned}$

其中

$\begin{aligned} \zeta &= P_\Omega(e+x^*(t)-\alpha R(t)e-\alpha R(t)x^*(t)-\alpha \beta L e-\alpha \beta L x^*(t)-\alpha s(t))\\ &\quad -P_\Omega(x^*(t)-\alpha R(t)x^*(t)-\alpha \beta L x^*(t)-\alpha s(t)) \end{aligned}$

利用Lemma 3，可得$\|\zeta\|\leq \|e-\alpha R(t)e-\alpha \beta L e\|$，故

$\begin{aligned} \dot V&\leq -ke^Te+k\|e\|\|e-\alpha R(t)e-\alpha \beta L e\|+\|e\|\|\dot x^*(t)\|\\ &\leq -k\left(1-\frac{1}{2k}-\|I-\alpha R(t)-\alpha\beta L\|\right)\|e\|^2+\frac{1}{2}\|x^*(t)\|^2 \end{aligned}$

由于$\frac{1-\varepsilon_L}{q_1}<\alpha<\frac{1+\varepsilon_L}{q_2+\beta\lambda_\text{max}(L)}$(注意$\lambda_\text{min}(L)=0$)，可得$\|I-\alpha R(t)-\alpha \beta L\|\leq \varepsilon_L$，即

$\dot V\leq -k(1-\frac{1}{2k}-\varepsilon_L)\|e\|^2+\frac{1}{2}\bar \omega_L^2$

因此$\dot V<0$，$\forall \|e\|^2>\frac{1}{2k(1-\varepsilon_L)-1}\bar \omega_L^2$。即误差一致最终有界，最终界为$\|e\|\leq \sqrt{\frac{1}{2k(1-\varepsilon_L)-1}}\bar \omega_L$。