Sign projected gradient flow: A continuous-time approach to convex optimization with linear equality constraints

摘要

In this paper, we exploit the possibility of combining nonsmooth control jointly with projected gradient approaches to solve convex optimization problems with linear equality constraints. Our development gives rise to a sign projected gradient method employing only "coarse" information, which has finite-time convergence capability and preserves the simplicity and elegance of gradient descent. Our primary objective is to understand the design principle of the projection matrix in the nonsmooth setting and to investigate some key features of the method, such as convergence time. Specifically, we offer a set of convergence results via nonsmooth analysis, revealing that the algorithm guarantees finite-time convergence for a wide range of cost functions, including strongly convex, strictly convex, and convex functions, provided that the proposed design criteria and conditions are satisfied. The results suggest that the choice of the projection matrix might not be unique, which motivates the optimal design issue of the projection matrix to minimize convergence time. We show that the problem can be formulated as a convex optimization problem, which can be solved readily by existing optimization tools. We discuss the possibility of employing the proposed method to solve unconstrained optimization problems, which in turn gives an initial feasible solution to the sign projected gradient flow. We apply the algorithm to solve a formation control problem, and the numerical results show the effectiveness of the algorithm. (C) 2020 Elsevier Ltd. All rights reserved.