Complexity certifications of first order inexact Lagrangian and penalty methods for conic convex programming
Ion Necoara, Andrei Pătraşcu, François Glineur · arXiv (Cornell University) · 2015
In this paper we analyze first order Lagrangian and penalty methods for general cone constrained convex programming with bounded or unbounded optimal Lagrange multipliers. In the first part of our paper we assume bounded optimal Lagrange multipliers and we study primal-dual first order methods based on inexact information and smoothing techniques (augmented Lagrangian smoothing and Nesterov type smoothing). For inexact (fast) gradient augmented Lagrangian methods we derive overall computational complexity $\mathcal{O}\left( \frac{1}{\epsilon}\right)$ projections onto a simple primal set in order to attain an $\epsilon-$optimal solution of the conic convex problem. On the other hand, the inexact fast gradient method combined with Nesterov type smoothing technique requires $\mathcal{O}\left( \frac{1}{\epsilon^{3/2}}\right)$ projections onto the same set to attain an $\epsilon-$optimal solution of the original problem. In the second part of the paper, we assume possibly unbounded optimal Lagrange multipliers, and combine the fast gradient method with penalty strategies for solving the conic constrained optimization problem. We prove that, in this scenario, the penalty methods also require $\mathcal{O}\left( \frac{1}{\epsilon^{3/2}}\right)$ projections onto a simple primal set to attain an $\epsilon-$optimal solution for the original problem.