有向图上去中心式一致优化快速算法研究

发布时间：2020-07-02 03:44

【摘要】：随着信息技术的迅猛发展,在通讯、控制、互联网与物联网等领域中的需求呈现出实时、高并发、大数据分布式存储等特点。在这样的时代背景下,去中心式一致优化算法研究引起了广泛的关注。去中心式优化的基本思想是不借助网络中心节点,而通过网络节点的自主优化和网络节点间的相互通信来实现整网的最优性和一致性。它通常具有更好的网络鲁棒性和可扩展性、通信及计算负载均衡、无多跳通信及隐私保护等优点。基于此,去中心式一致优化在区块链、车联网和无人机协调控制、智能电网的资源调度,以及机器学习等领域中具有广泛应用。目前,大多数去中心式一致优化方面的研究都是针对无向图,即双向通信网络的。然而,在实际应用(比如社交网络)中,通常存在安全等级分级,或者信任机制等问题,导致实际网络通常是有向图。因此,研究有向图上的去中心式一致优化算法不仅具有重要的科学价值,而且对于当前大数据背景下的网络应用具有重要的实际意义。本文聚焦于有向图上的去中心一致优化快速算法研究,主要工作归纳如下:1.针对有向图上的去中心式光滑优化模型,即目标函数连续可微,我们通过巧妙结合两个已有的算法,即EXTRA和Subgradient-push算法,提出一个快速、有效的算法,称为ExtraPush。从数值上,我们发现新算法能够很好地保持EXTRA算法的线性收敛性,从而远快于已有的Subgradient-push算法,其中Subgradient-push被证明仅具有亚线性收敛速率。理论上,我们在序列有界假设下给出了ExtraPush的收敛性。2.本文进一步考虑有向图上的去中心式复合优化模型,即目标函数具有“光滑+非光滑”结构。通过引入邻近算子,本文把ExtraPush算法推广到复合优化模型求解,并提出了PG-ExtraPush算法。在强凸情形下,本文建立了PG-ExtraPush算法的线性收敛性。一系列的数值实验验证了算法的有效性。令人惊奇的是,在某些非凸的实验例子中,我们同样观察到PG-ExtraPush算法具有线性收敛速度。针对这一点,我们将在未来工作中进一步研究。注意到本文所提的算法都要求同步,从而极大地造成了计算资源的浪费。因此,研究算法的异步版本将是我们未来研究的重要方向。
【学位授予单位】：江西师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5;TP301.6
【图文】：

有向图,混合矩阵,有向网络,性质

图 2-1.一个有向图 (左) 以接下来，针对所研究的有向网络，我们需假设 1：图是强连通的。在假设 1 下，我们罗列一些与有向网络混1(1)和(4)可参见文献[8]推论 2，性质 1(2)和性质 1：在假设 1 成立时，以下结论成立（1）令t=tA A A A 其中t Ν，则随着tA 以指数的速度收敛其中 0i 为某个固定的分布向量，并且 ni i {1, , n}，( )tijA 和i ，有|( ) | , t tij iA C （2） ( ) ( )Tn n nnull Ι 1 null Ι A。（3） A= 。

运行结果,损失最小化,最小二乘问题,损失函数

图 3-1：实验 3.3.1 的运行结果。记录*2t‖ x x‖ 变化情况，*x 为极值点3.3.2 去中心式 Huber 回归与最小二乘问题不同的是，本实验是要使得 Huber 损失最小化。问题如下：*1argmin ( ) ( ),pnixix f x f x R(3-7)其中( ) ( )1( ) ( )imi i j i jjf x H B x b ，( i )jB 为矩阵( )im piB R的第j行，( i )jb 为向量( )imib R的第j项， i 1, ,n。Huber 损失函数定义如下：2 2211, for| | ( zone),2( )1(| | ), otherwise ( zone).a aH aa (3-8)

【相似文献】