Convex Optimization via Finite-Time Projected Gradient Flows

摘要

In this paper, we exploit the possibility of combining nonsmooth control jointly with projected gradient approaches to solve convex optimization problems. Our development gives rise to a nonsmooth projected gradient method which has the finite-time convergence capability, thus overcoming the shortcoming of slow convergence speed of conventional projected gradient approaches, as well as preserves the simplicity. 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 finite-time convergence and sensitivity to initialization errors. Specifically, we offer a set of criteria for the design of the projection matrix. The convergence results, derived via nonsmooth analysis, reveal that the algorithm has a finite-time convergence property, provided that it meets the proposed design criteria. When there exists an initialization error, the optimization error is doomed inevitably. Nevertheless, we show that the optimization error incurred by the initialization error is upper bounded, and we can prescribe the upper bound by the maximal Lipschitz constant of the optimal value function over some compact set.