Privacy-Preserving Decentralized Optimization and Event Localization

This dissertation considers decentralized optimization and its applications. On the one hand, we address privacy preservation for decentralized optimization, where N agents cooperatively minimize the sum of N convex functions private to these individual agents. In most existing decentralized optimization approaches, participating agents exchange and disclose states explicitly, which may not be desirable when the states contain sensitive information of individual agents. The problem is more acute when adversaries exist which try to steal information from other participating agents. To address this issue, we first propose two privacy-preserving decentralized optimization approaches based on ADMM (alternating direction method of multipliers) and subgradient method, respectively, by leveraging partially homomorphic cryptography. To our knowledge, this is the first time that cryptographic techniques are incorporated in a fully decentralized setting to enable privacy preservation in decentralized optimization in the absence of any third party or aggregator. To facilitate the incorporation of encryption in a fully decentralized manner, we also introduce a new ADMM which allows time-varying penalty matrices and rigorously prove that it has a convergence rate of O(1/t). However, given that encryption-based algorithms unavoidably bring about extra computational and communication overhead in real-time optimization [61], we then propose another novel privacy solution for decentralized optimization based on function decomposition and ADMM which enables privacy without incurring large communication/computational overhead. On the other hand, we address the application of decentralized optimization to the event localization problem, which plays a fundamental role in many wireless sensor network applications such as environmental monitoring, homeland security, medical treatment, and health care. The event localization problem is essentially a non-convex and non-smooth problem. We address such a problem in two ways. First, a completely decentralized solution based on augmented Lagrangian methods and ADMM is proposed to solve the non-smooth and non-convex problem directly, rather than using conventional convex relaxation techniques. However, this algorithm requires the target event to be within the convex hull of the deployed sensors. To address this issue, we propose another two scalable distributed algorithms based on ADMM and convex relaxation, which do not require the target event to be within the convex hull of the deployed sensors. Simulation results confirm effectiveness of the proposed algorithms