CONVERGENCE RATE ANALYSIS OF NONQUADRATIC PROXIMAL METHODS FOR CONVEXAND LINEAR-PROGRAMMING

The phi-divergence proximal method is an extension of the proximal min imization algorithm, where the usual quadratic proximal term is substi tuted by a class of convex statistical distances, called phi-divergenc es. In this paper, we study the convergence rate of this nonquadratic proximal method for convex and particularly linear programming. We ide ntify a class of phi-divergences for which superlinear convergence is attained both for optimization problems with strongly convex objective s at the optimum and linear programming problems, when the regularizat ion parameters tend to zero. We prove also that, with regularization p arameters bounded away from zero, convergence is at least linear for a wider class of phi-divergences, when the method is applied to the sam e kinds of problems. We further analyze the associated class of augmen ted Lagrangian methods for convex programming with nonquadratic penalt y terms, and prove convergence of the dual generated by these methods for linear programming problems under a weak nondegeneracy assumption.