论文总字数：60286字
摘 要
\renewcommand{\abstractname}{摘\ \ 要}
\begin{abstract}
随着多智能体系统理论的快速发展，分布式优化也逐渐成为了一个重要的研究方向。本文研究了几类凸优化问题，主要工作如下：第一章介绍了分布式优化的研究背景、现状和主要成果；第二章介绍了凸分析和代数图论的相关基础知识，并对所研究的问题进行了数学描述；第三章研究了一些经典的集中式优化算法，并简要分析了其在分布式系统中所面临的问题；第四章将分布式优化算法分为无约束和带约束的情况分别进行讨论，重点介绍了一种用于无约束分布式优化的量化次梯度算法和一种针对同时有全网络整体等式约束和局部可行性约束的分布式优化问题的投影梯度算法（及其微分变种），并分别进行了理论分析；第五章针对量化次梯度算法进行了仿真实验验证；第六章对全文的内容进行了总结。
\bigskip
\noindent 关键词：分布式优化，资源分配，多智能体系统，凸优化，通信网络，图论
\end{abstract}
\newpage
\vskip 0.5cm
\begin{center}
\fontsize{22}{\baselineskip}\textrm{Distributed Optimization Theory and Applications on Resource Allocation Problems}
\end{center}
\vskip 0.5cm
\addcontentsline{toc}{section}{Abstract}
\renewcommand{\abstractname}{Abstract}
\begin{abstract}
With the rapid development of multi-agent systems, distributed optimization has become an important research direction. In this paper, several types of convex optimization problems are studied. The main work is as follows: Chapter 1 introduces the research background, current situation and main results of distributed optimization theory; Chapter 2 introduces convex analysis and algebraic graph theory as preliminaries, and gives the problem studied a mathematical description; Chapter 3 studies some classical centralized optimization algorithms and briefly analyzes the problems they face in distributed systems; Chapter 4 classifies the distributed optimization algorithms into two types: unconstrained and constrained, and discusses them separately, highlighting a quantized subgradient algorithm for unconstrained distributed optimization problems and a projected gradient algorithm (and variants) for distributed optimization problems with both global constraints and local feasibility constraints; Chapter 5 conducts a simulation, which verifies the quantized subgradient algorithm; Chapter 6 gives some conclusions.
\bigskip
\noindent Key Words: Distributed optimization, Resource allocation, Multi-agent system, convex optimization, Communication network, Graph theory
\end{abstract}
\newpage
\renewcommand{\contentsname}{目\ \ \ \ 录}
\tableofcontents
\newpage
\pagenumbering{arabic}
\titleformat{\section}[block]{\bfseries\fontsize{15}{\baselineskip}\filcenter}{}{0pt}{\thesection\ }
\pagestyle{fancy}
\section{绪论} \label{sec.intro}
多智能体系统是由一群具备一定的感知、通信、计算和执行能力的智能体通过各种通信方式组成的网络系统。随着多智能体系统理论的发展，多智能体系统中的优化问题也逐渐引起了科学工作者的关注。当优化问题的规模增长时，通讯成本、通信延迟、隐私等问题更加显著。这些问题促进了分布式优化理论的发展。在分布式优化过程中，所有的智能体结合了本地计算和网络通信，协作达成优化目标\cite{init-free}。
近年来，分布式优化已经取得了一系列重要成果。分布式优化主要研究两大类问题：第一类是对性能指标函数的优化。在一些重要的现实问题如资源分配问题中，每个智能体往往有各自的目标函数，而整个网络的目标函数由各智能体的目标函数决定。此类问题的目标为通过智能体间的局部信息交流来完成全局的优化。第二类是对系统动态过程的优化。这类问题往往涉及到随机动态规划，具有较高的条件需求，难以进行深入理论分析，研究程度远不如前一类问题。本文接下来主要讨论第一类问题\cite{distributed-design}。
在优化理论的发展过程中，凸优化由于其基本性而占据着极其重要的地位\cite{convex-optimization}。许多实际的优化问题也可以转化为凸优化问题，本文主要研究在分布式凸优化领域的工作。
受到 \textit{Ho}, \textit{Servi} 和 \textit{Suri} 在分布式资源分配问题上所做的开创性工作的启发，许多资源分配优化的分布式算法被提出\cite{optimal-distributed, multistep-gradient, decentralized-resource, a-random, optimal-scaling, approximate-projected, constrained-consensus, adaptation-learning, quantized}。
\textit{Arrow}, \textit{Hurwicz} 和 \textit{Uzawa} 的早期工作引导了许多对连续时间梯度算法的研究\cite{studies-linear, control-perspectives, neurodynamical-optimization}。梯度流算法在网络控制和优化\cite{stability-primal, network-resource-ferragut, internet-congestion}、神经网络\cite{neurodynamical-optimization}、随机近似\cite{asymptotic-behavior}等方面得到了应用。连续时间梯度流算法也被用于解决无约束的分布式优化问题\cite{continuous-time, distributed-continuous, distributed-convex, a-control}。不仅如此，基于投影的梯度流动力学也被用于解决复杂的带约束优化问题，投影梯度流被应用于带约束分布式优化问题中\cite{cherukuri-2016, exponential, projected-dynamical, venets, on-the-stability, second-order, distributed-qiu, gradient}。
经济调度问题是一种特殊的分布式资源分配优化问题，其目标为寻找最优的电量分配。\textit{Zhao} \cite{zhao-2014} 提出的原始-对偶梯度流算法有效解决了分布式经济调度问题，显式考虑了物理网络互联和发电机动力学，提供了一个相当全面的的方法和启发性的观点。此外，\textit{Cherukuri} \cite{a-class} 通过结合罚函数法和分布式连续时间算法解决了分布式经济调度问题，并提出了一个满足算法初始化条件的过程。
在分布式资源分配问题中，每个智能体只能使用其本地数据，例如局部目标函数、局部可行性约束和本地资源数据等。由于网络总资源是一定的，因此各智能体必须以分布式的方式使得总目标函数（即各局部目标函数之和）在满足所有约束的情况下达到最优值。局部可行性约束对于网络的安全操作有着至关重要的意义\cite{convex-separable, efficiency-loss}，然而现有的大部分对于分布式资源分配问题的研究并未考虑这一点。目前为止，许多分布式经济调度问题的工作都只考虑了简单的局部可行性约束\cite{cherukuri-2014, cherukuri-2015, zhang-2015, zhao-2014}。
本文将在\ref{sec.problem}中介绍预备知识，并对研究的主要问题进行数学描述。\ref{sec.algo.centralized}会研究一些经典的集中式优化算法，并简要分析其在分布式系统中所面临的问题。\ref{sec.algo.distributed}将分布式优化问题划分为无约束与带约束的情况分别进行讨论，重点介绍两种具体的算法并进行理论分析。\ref{sec.emu}使用仿真实验，对无约束的量化次梯度算法进行验证。\ref{sec.conclude}对全文的内容进行总结。
\section{预备知识和问题描述} \label{sec.problem}
本章将介绍与本文相关的基本知识，包括凸分析和代数图论，同时对研究问题进行描述。
\subsection{凸分析}
函数 $ f : \mathbb{R}^m \to \mathbb{R} $ 有局部 Lipschitz 连续梯度，若给定任意紧集 $ Q $，存在常数 $ k^Q $ 使得 $ \| \nabla f(x) - \nabla f(y) \| \leq k^Q \| x - y \|,\;\forall x, y \in Q $。函数 $ f(x) $ 是 $ \mu $-强凸函数，若存在常数 $ \mu $ 使得 $ f(y) \geq f(x) \nabla^T f(x)(y - x) \frac{1}{2} \mu \| y - x \|^2 $ 或
\begin{equation*}
(x - y)^T (\nabla f(x) - \nabla f(y)) \geq \mu \| y - x \|^2,\;\forall x, y \in \mathbb{R}^m.
\end{equation*}
集合 $ \Omega $ 为凸集，若 $ (1 - t) x t y \in \Omega,\;\forall x, y \in \Omega,\;t \in [0, 1] $。定义 $ C_\Omega(x) $ 为 $ \Omega $ 在 $ x $ 处的标准锥 $ C_\Omega(x) = \{v\;|\;\leftlt; v, y - x \rightgt; \leq 0,\;\forall y \in \Omega\} $。$ \Omega $ 在 $ x $ 处的可行方向锥为 $ K_\Omega(x) = \{d\;|\;d = \beta (y - x), y \in \Omega, \beta \geq 0\} $。定义 $ \Omega $ 在 $ x $ 处的正切锥为 $ T_\Omega(x) = \{v\;|\;v = \lim_{k \to \infty} \frac{x^k - x}{\tau_k}, \tau_k \geq 0, \tau_k \to 0, x^k \in \Omega, x^k \to x\} $。
\begin{lemma}
\cite{nonlinear-optimization}
当 $ \Omega $ 为闭凸集时，$ T_\Omega(x) $ 为 $ K_\Omega(x) $ 的闭包，且为 $ C_\Omega(x) $ 的极锥，即 $ T_\Omega(x) = \{y\;|\;\leftlt; y, d \rightgt; \leq 0,\;\forall d \in C_\Omega(x)\} $。
\end{lemma}
定义 $ x $ 在凸集 $ \Omega $ 上的投影为 $ P_\Omega(x) = \mathrm{arg} \min_{y \in \Omega} \| x - y \| $。显然：
\begin{equation*}
\leftlt; x - P_\Omega(x), P_\Omega(x) - y \rightgt; \geq 0,\;\forall x \in \mathbb{R}^m,\;\forall y \in \Omega.
\end{equation*}
由上式可得投影运算的两条性质：
\begin{property}
点 $ x $ 到其在 $ \Omega $ 上的投影 $ P_\Omega(x) $ 的距离与 $ P_\Omega(x) $ 到点 $ y \in \Omega $ 的距离之和不超过 $ x $ 到 $ y $ 的距离：
\begin{equation*}
\| x - P_\Omega(x) \|_2^2 \| P_\Omega(x) - y \|_2^2 \;\leq\; \| x - y \|_2^2,\;\forall x \in \mathbb{R}^m,\;\forall y \in \Omega.
\end{equation*}
\end{property}
\begin{property}
两个点投影之间的距离不超过两点之间的距离：
\begin{equation*}
\| P_\Omega(x) - P_\Omega(y) \| \;\leq\; \| x - y \|,\;\forall x, y \in \mathbb{R}^m.
\end{equation*}
\end{property}
由上述定义，又可将标准锥 $ C_\Omega(x) $ 定义如下\cite{nonlinear-optimization}：
\begin{equation*}
C_\Omega(x) = \{v\;|\;P_\Omega(x v) = x\}.
\end{equation*}
对于闭凸集 $ \Omega $，$ x \in \Omega $ 和方向 $ v $，定义微分投影算子\cite{asymptotic-behavior, projected-dynamical}：
\begin{equation} \label{eqo.proj-op}
剩余内容已隐藏，请支付后下载全文，论文总字数：60286字
该课题毕业论文、开题报告、外文翻译、程序设计、图纸设计等资料可联系客服协助查找;
