A comparative analysis of the Fast-Lipschitz convergence speed

Fast-Lipschitz optimization is a recently proposed framework useful for an important class of centralized and distributed optimization problems over peer-to-peer networks. The properties of Fast-Lipschitz problems allow to compute the solution without having to introduce Lagrange multipliers, as in most other methods. This is highly beneficial, since multipliers need to be communicated across the network and thus increase the communication complexity of solution algorithms. Although the convergence speed of Fast-Lipschitz optimization methods often outperforms Lagrangian methods in practice, there is not yet a theoretical analysis. This paper provides a fundamental step towards such an analysis. Sufficient conditions for superior convergence of the Fast-Lipschitz method are established. The results are illustrated by simple examples. It is concluded that optimization problems with quadratic cost functions and linear constraints are always better solved by Fast-Lipschitz optimization methods, provided that certain conditions hold on the eigenvalues of the Hessian of the cost function and constraints.