Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
From MaRDI portal
Publication:623454
DOI10.1007/S10107-008-0261-6zbMath1208.90113OpenAlexW2042860556MaRDI QIDQ623454
Renato D. C. Monteiro, Guanghui Lan, Zhaosong Lu
Publication date: 14 February 2011
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-008-0261-6
Numerical mathematical programming methods (65K05) Semidefinite programming (90C22) Convex programming (90C25) Numerical optimization and variational techniques (65K10) Linear programming (90C05)
Related Items (56)
An adaptive accelerated first-order method for convex optimization ⋮ Conic optimization via operator splitting and homogeneous self-dual embedding ⋮ OSGA: a fast subgradient algorithm with optimal complexity ⋮ Accelerating Block-Decomposition First-Order Methods for Solving Composite Saddle-Point and Two-Player Nash Equilibrium Problems ⋮ Accelerated gradient sliding for structured convex optimization ⋮ Exact gradient methods with memory ⋮ Proportional-integral projected gradient method for conic optimization ⋮ A Level-Set Method for Convex Optimization with a Feasible Solution Path ⋮ Polyhedral approximations inp-order cone programming ⋮ A smoothing stochastic gradient method for composite optimization ⋮ A multi-step doubly stabilized bundle method for nonsmooth convex optimization ⋮ Approximation accuracy, gradient methods, and error bound for structured convex optimization ⋮ Bregman Proximal Point Algorithm Revisited: A New Inexact Version and Its Inertial Variant ⋮ An Exact Penalty Method for Nonconvex Problems Covering, in Particular, Nonlinear Programming, Semidefinite Programming, and Second-Order Cone Programming ⋮ Algorithms for stochastic optimization with function or expectation constraints ⋮ An alternating direction method for finding Dantzig selectors ⋮ An optimal subgradient algorithm with subspace search for costly convex optimization problems ⋮ A new convergence analysis and perturbation resilience of some accelerated proximal forward–backward algorithms with errors ⋮ An extrapolated iteratively reweighted \(\ell_1\) method with complexity analysis ⋮ Iteratively reweighted \(\ell _1\) algorithms with extrapolation ⋮ Optimal subgradient algorithms for large-scale convex optimization in simple domains ⋮ Matrix-Free Convex Optimization Modeling ⋮ Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence ⋮ Iteration-Complexity of First-Order Augmented Lagrangian Methods for Convex Conic Programming ⋮ Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming ⋮ Iteration-complexity of first-order penalty methods for convex programming ⋮ Fine tuning Nesterov's steepest descent algorithm for differentiable convex programming ⋮ An extended sequential quadratically constrained quadratic programming algorithm for nonlinear, semidefinite, and second-order cone programming ⋮ A very simple SQCQP method for a class of smooth convex constrained minimization problems with nice convergence results ⋮ Implementation of an optimal first-order method for strongly convex total variation regularization ⋮ Smoothing proximal gradient method for general structured sparse regression ⋮ Accelerated first-order methods for hyperbolic programming ⋮ Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming ⋮ An Average Curvature Accelerated Composite Gradient Method for Nonconvex Smooth Composite Optimization Problems ⋮ Solving structured nonsmooth convex optimization with complexity \(\mathcal {O}(\varepsilon ^{-1/2})\) ⋮ Performance of first-order methods for smooth convex minimization: a novel approach ⋮ Templates for convex cone problems with applications to sparse signal recovery ⋮ Dynamic stochastic approximation for multi-stage stochastic optimization ⋮ An optimal randomized incremental gradient method ⋮ Random Gradient Extrapolation for Distributed and Stochastic Optimization ⋮ Super-Resolution of Positive Sources: The Discrete Setup ⋮ Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization ⋮ A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems ⋮ Fastest rates for stochastic mirror descent methods ⋮ Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity ⋮ A family of subgradient-based methods for convex optimization problems in a unifying framework ⋮ Environmental game modeling with uncertainties ⋮ An Accelerated Linearized Alternating Direction Method of Multipliers ⋮ The Supporting Halfspace--Quadratic Programming Strategy for the Dual of the Best Approximation Problem ⋮ An efficient primal dual prox method for non-smooth optimization ⋮ On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators ⋮ On inexact solution of auxiliary problems in tensor methods for convex optimization ⋮ A dual approach for optimal algorithms in distributed optimization over networks ⋮ A characterization theorem and an algorithm for a convex hull problem ⋮ Primal–dual first-order methods for a class of cone programming ⋮ Adaptive restart for accelerated gradient schemes
Uses Software
Cites Work
- Unnamed Item
- Solving semidefinite-quadratic-linear programs using SDPT3
- Smooth minimization of non-smooth functions
- Large-scale semidefinite programming via a saddle point mirror-prox algorithm
- Smoothing technique and its applications in semidefinite optimization
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- Local minima and convergence in low-rank semidefinite programming
- Smooth Optimization with Approximate Gradient
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Interior Gradient and Proximal Methods for Convex and Conic Optimization
This page was built for publication: Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
