We design and analyze a novel gradient-based algorithm for unconstrained convex optimization. When the objective function is m-strongly convex and its gradient is L-Lipschitz continuous, the iterates and function values converge linearly to the optimum at rates p and p 2 , respectively, where p = 1 - √m/L. These are the fastest known guaranteed linear convergence rates for globally convergent first-order methods, and for high desired accuracies the corresponding iteration complexity is within a factor of two of the theoretical lower bound. We use a simple graphical design procedure based on integral quadratic constraints to derive closed-form expressions for the algorithm parameters. The new algorithm, which we call the triple momentum method, can be seen as an extension of methods such as gradient descent, Nesterov's accelerated gradient descent, and the heavy-ball method.
16 April 2020 in IEEE Transactions on Control of Network Systems
This work concerns the analysis and design of distributed first-order optimization algorithms over time-varying graphs. The goal of such algorithms is to optimize a global function that is the average of local functions using only local computations and communications. Several different algorithms have been proposed that achieve linear convergence to the global optimum when the local functions are strongly convex. We provide a unified analysis that yields the worst-case linear convergence rate as a function of the condition number of the local functions, the spectral gap of the graph, and the parameters of the algorithm. The framework requires solving a small semidefinite program whose size is fixed; it does not depend on the number of local functions or the dimension of their domain. The result is a computationally efficient method for distributed algorithm analysis that enables the rapid comparison, selection, and tuning of algorithms. Finally, we propose a new algorithm, which we call SVL, that is easily implementable and achieves a faster worst-case convergence rate than all other known algorithms.
In the distributed optimization problem for a multi-agent system, each agent knows a local function and must find a minimizer of the sum of all agents’ local functions by performing a combination of local gradient evaluations and communicating information with neighboring agents. We prove that every distributed optimization algorithm can be factored into a centralized optimization method and a second-order consensus estimator, effectively separating the “optimization” and “consensus” tasks. We illustrate this fact by providing the decomposition for many recently proposed distributed optimization algorithms. Conversely, we prove that any optimization method that converges in the centralized setting can be combined with any second-order consensus estimator to form a distributed optimization algorithm that converges in the multi-agent setting. Finally, we describe how our decomposition may lead to a more systematic algorithm design methodology.
In wireless communications, traditional base stations act as the backbone for providing network connectivity to users. These base stations, however, require significant resources to construct and are therefore not suitable for remote areas and disaster scenarios. This challenge makes them unfit for deployment in remote areas or in disaster scenarios where fast network establishment is necessary. To address these challenges, cellular base stations installed on Unmanned Aerial Vehicles (UAVs) can be an alternative solution. UAVs provide quick deployment capability and can adapt to changing environmental situations, making them ideal for dynamic network scenarios. In this paper, we address the critical issue of UAV positioning to maximize the total user coverage, which can be formulated as a mixed-integer linear program. Given the complexity of larger-scale scenarios related to the number of users, we suggest a two-step method. First, we group users into clusters, and then we optimize the UAV positions with respect to these clusters. This approach introduces a trade-off between computational time efficiency and optimality, which can be tuned by adjusting the number of clusters. By varying the number of clusters, we balance computation time with the optimality of the UAV locations, allowing flexible deployment in diverse scenarios.
The block diagram for a general average consensus estimator is developed and we show how this can be used to easily identify properties of the estimator. This structure is then used to design average consensus estimators which achieve exact average consensus for constant inputs, are robust to initial conditions and switching graph topologies, and are internally stable. Additionally, the estimators have the optimal worst-case asymptotic convergence rate over the set of connected undirected graphs whose weighted Laplacian matrices have nonzero eigenvalues in a known interval [λmin, λmax]. Two designs are presented. The first is a modification of the polynomial filter estimator proposed by Kokiopoulou and Frossard [1] which is the optimal estimator having only one state variable. The proposed design is robust to initial conditions, but not robust to switching graph topologies. The second design uses root locus techniques to obtain higher-dimensional estimators in closed-form which are robust to both initial conditions and switching graph topologies. Plots of the worst-case asymptotic convergence factor of each estimator are given as a function of the ratio λmin/λmax.
In this study, we deploy drones as dynamic base stations to address the issue of optimizing user coverage in areas without fixed base station infrastructure. To optimize drone placement, we employ Deep Q-Learning, beginning with a centralized approach due to its simplicity and ease of training. In this centralized approach, all drones are trained simultaneously. We also employ a decentralized technique in which each drone acts autonomously while sharing a common neural network, allowing for individualized learning. In addition, we explore the impacts of jamming on UAVs and provide a reliable approach for mitigating this interference. To boost robustness, we employ stochastic user distributions, which train our policy to successfully respond to a wide range of user situations.