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

arXiv: https://arxiv.org/abs/1506.05320 · HTML: https://mlsanity.com/paper/1506.05320/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2015.

## Built on by (most cited first, 7 of 7)

- [A Dual Approach to Constrained Markov Decision Processes with Entropy Regularization](https://mlsanity.com/paper/2110.08923/) (2021)
- [First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/2204.03132/) (2022)
- [Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient](https://mlsanity.com/paper/2206.01209/) (2022)
- [Federated Learning with Convex Global and Local Constraints](https://mlsanity.com/paper/2310.10117/) (2023)
- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)
- [A proximal augmented Lagrangian method for nonconvex optimization with equality and inequality constraints](https://mlsanity.com/paper/2509.02894/) (2025)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)

## Abstract (arXiv)

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 a total computational complexity of Oleft(frac1ε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 Oleft(frac1ε3/2right) projections onto the same set. Then, we assume that optimal Lagrange multipliers for the cone constrained convex problem might not exist, and analyze the fast gradient method for solving penalty reformulations of the problem. For the fast gradient method combined with penalty framework we also derive a total computational complexity of Oleft(frac1ε3/2right) projections onto a simple primal set to attain an ε-optimal solution for the original problem.