Projection-free numerical algorithms for large-scale constrained optimization in networked engineering applications

Abstract

In the paper, a prospect of large-scale optimization problems faced during the operation of networking engineering systems such as smart grids, multi-agent systems based on sensor arrays, or systems for distribution of resources are discussed since it deals with high-dimensional coupled constraints making metric projections difficult. The use of conventional numerical projection-based methods in practice involves the repeated solution of quadratic problems in each iteration, leading to costs increasing super-linearly with the increase in network size, thus limiting applicability in real-time engineering practice. In this paper, projection-free numerical methods based on linear minimization oracles are proposed; in particular, the responses of conditional gradient methods (Frank-Wolfe algorithm) are applied to decentralized networks. The study presents an optimization problem defined over a communication graph, as well as present assumption considering smoothness, convexity, and boundedness in respect to both feasible set and the function goal of optimization. The study proves sublinear convergence of the primal and its dual formulations in general convex case; in addition, for strong convex/Polyak-Łojasiewicz case, it is proved that linear convergence is possible. The communication complexity bounds that evaluate the amount of data exchange between nodes to achieve epsilon-optimality is offered along with the results concerning convergence proofs. The conducted numerical simulation in respect to a distributed resource allocation case study 
illustrates the established rates of the algorithm efficiency, demonstrates the advantages of the proposed method 
over projection-based problems, and discusses the scalability of the proposed methods as concerning 
implementation of up to five hundred nodes in a network.