Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming

Abstract

In this paper we present a complete iteration complexity analysis of inexact first-order Lagrangian and penalty methods for solving cone-constrained convex problems that have or may not have optimal Lagrange multipliers that close the duality gap. We first assume the existence of optimal Lagrange multipliers and study primal–dual first-order methods based on inexact information and augmented Lagrangian smoothing or Nesterov-type smoothing. For inexact (fast) gradient augmented Lagrangian methods, we derive an overall computational complexity of $\mathcal{O}\left(1/ϵ\right)$ projections onto a simple primal set in order to attain an ε-optimal solution of the conic convex problem. For the inexact fast gradient method combined with Nesterov-type smoothing, we derive computational complexity $\mathcal{O}\left(1/{ϵ}^{3/2}\right)$ projections onto the same set. Then, we assume that optimal Lagrange multipliers might not exist for the cone-constrained convex problem, and analyse the fast gradient method for solving penalty reformulations of the problem. For the fast gradient method combined with penalty framework, we also derive an overall computational complexity of $\mathcal{O}\left(1/{ϵ}^{3/2}\right)$ projections onto a simple primal set to attain an ε-optimal solution for the original problem.

Keywords:

• conic convex problems
• smooth (augmented) dual functions
• penalty functions
• (augmented) dual first-order methods
• penalty fast gradient methods
• approximate primal solution
• overall computational complexity

AMS Subject Classification:

• 90C25
• 90C46
• 68Q25
• 65K05

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The research leading to these results has received funding from Unitatea Executiva pentru Finantarea Invatamantului Superior, a Cercetarii, Dezvoltarii si Inovarii (UEFISCDI), Romania, PNII-RU-TE-2014, project MoCOBiDS no. 176/01.10.2015. It also presents research results of the Belgian Network DYSCO funded by the Interuniversity Attraction Poles Programme initiated by the Belgian State, and of the Concerted Research Action programme supported by the Federation Wallonia-Brussels, no. ARC 14/19-060. Support from two WBI-Romanian Academy grants is also acknowledged. The authors thank Prof. Yu. Nesterov for inspiring discussions.