On the behavior of first-order penalty methods for conic constrained convex programming when Lagrange multipliers do not exist

In this paper we analyze the numerical behavior of first-order quadratic penalty methods for solving large-scale conic constrained convex problems with composite objective function. Contrary to the most of the results on penalty methods, in this work we do not assume the existence of a finite optimal Lagrange multiplier. We derive the iteration complexity of the classical quadratic penalty method, where the corresponding penalty regularized formulation of the original problem is solved using Nesterov´s fast gradient algorithm. We provide rate of convergence results in terms of feasibility violation and suboptimality for adaptive and non-adaptive variants of the penalty scheme, under various assumptions on the composite objective function. Finally, we show on a simple example that our complexity estimates are tight.