A distributed algorithm based on KKT conditions for convex intersection computation
Xin Yu, Bing‐Chang Wang, Hailing Dong · 2017
Intersection computation of convex sets is a typical problem in distributed optimization. In this paper, a multi-agent network is considered for continuous-time dynamics with the fixed topology, in which each agent is associated with a convex set. The objective is for all the agents to achieve an agreement within the intersection of the associated convex sets. A distributed “projected consensus algorithm” is introduced, and the computation of the projection term is converted to a constrained optimization problem. The solution of the optimization problem is determined by Karush-Kuhn-Tucker (KKT) conditions. Particularly, when the associated set of each agent is a polyhedral set, the projection computation is converted to solving a quadratic programming problem, in which an extension algorithm of the simplex method can be used. A numerical example is given to illustrate the effectiveness of the algorithms.