Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming
- 5 October 2017
- journal article
- research article
- Published by Taylor & Francis in Optimization Methods and Software
- Vol. 34 (2) , 305-335
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 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 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 projections onto a simple primal set to attain an ε-optimal solution for the original problem.Keywords
Funding Information
- Unitatea Executiva pentru Finantarea Invatamantului Superior, a Cercetarii, Dezvoltarii si Inovarii (MoCOBiDS no. 176/01.10.2015)
This publication has 22 references indexed in Scilit:
- Iteration-complexity of first-order augmented Lagrangian methods for convex programmingMathematical Programming, 2015
- A variable smoothing algorithm for solving convex optimization problemsTOP, 2014
- First-order methods of smooth convex optimization with inexact oracleMathematical Programming, 2013
- On the acceleration of the double smoothing technique for unconstrained convex optimization problemsOptimization, 2012
- Iteration-complexity of first-order penalty methods for convex programmingMathematical Programming, 2012
- Double Smoothing Technique for Large-Scale Linearly Constrained Convex OptimizationSIAM Journal on Optimization, 2012
- Smoothing and First Order Methods: A Unified FrameworkSIAM Journal on Optimization, 2012
- On the Complexity of the Hybrid Proximal Extragradient Method for the Iterates and the Ergodic MeanSIAM Journal on Optimization, 2010
- Primal-dual first-order methods with ${\mathcal {O}(1/\epsilon)}$ iteration-complexity for cone programmingMathematical Programming, 2009
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse ProblemsSIAM Journal on Imaging Sciences, 2009