Fast bundle-level methods for unconstrained and ball-constrained convex optimization
From MaRDI portal
Abstract: It has been shown in cite{Lan13-1} that the accelerated prox-level (APL) method and its variant, the uniform smoothing level (USL) method, have optimal iteration complexity for solving black-box and structured convex programming problems without requiring the input of any smoothness information. However, these algorithms require the assumption on the boundedness of the feasible set and their efficiency relies on the solutions of two involved subproblems. These hindered the applicability of these algorithms in solving large-scale and unconstrained optimization problems. In this paper, we first present a generic algorithmic framework to extend these uniformly optimal level methods for solving unconstrained problems. Moreover, we introduce two new variants of level methods, i.e., the fast APL (FAPL) method and the fast USL (FUSL) method, for solving large scale black-box and structured convex programming problems respectively. Both FAPL and FUSL enjoy the same optimal iteration complexity as APL and USL, while the number of subproblems in each iteration is reduced from two to one. Moreover, we present an exact method to solve the only subproblem for these algorithms. As a result, the proposed FAPL and FUSL methods have improved the performance of the APL and USL in practice significantly in terms of both computational time and solution quality. Our numerical results on solving some large-scale least square problems and total variation based image reconstruction have shown great advantages of these new bundle-level type methods over APL, USL, and some other state-of-the-art first-order methods.
Recommendations
Cites work
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 3559294 (Why is no real title available?)
- A Proximal Bundle Method with Approximate Subgradient Linearizations
- A descent proximal level bundle method for convex nondifferentiable optimization
- A proximal cutting plane method using Chebychev center for nonsmooth convex optimization
- An Iterative Regularization Method for Total Variation-Based Image Restoration
- An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems
- An accelerated linearized alternating direction method of multipliers
- An aggregate subgradient method for nonsmooth convex minimization
- An inexact bundle variant suited to column generation
- Approximate level method for nonsmooth convex minimization
- Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization
- Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems
- Convex proximal bundle methods in depth: a unified analysis for inexact oracles
- Fast algorithms for image reconstruction with application to partially parallel MR imaging
- Fast alternating direction optimization methods
- Fast alternating linearization methods for minimizing the sum of two convex functions
- Inexact bundle methods for two-stage stochastic programming
- Introductory lectures on convex optimization. A basic course.
- Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers
- Level bundle methods for oracles with on-demand accuracy
- NESTA: A fast and accurate first-order method for sparse recovery
- New variants of bundle methods
- Non-Euclidean restricted memory level method for large-scale convex optimization
- Nonlinear total variation based noise removal algorithms
- On the global and linear convergence of the generalized alternating direction method of multipliers
- Optimal primal-dual methods for a class of saddle point problems
- Piecewise-quadratic approximations in convex numerical optimization
- Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities
- Proximity control in bundle methods for convex nondifferentiable minimization
- Smooth minimization of non-smooth functions
- The Cutting-Plane Method for Solving Convex Programs
Cited in
(8)- Accelerated bundle level methods with inexact oracle
- A level-set method for convex optimization with a feasible solution path
- Acceleration techniques for level bundle methods in weakly smooth convex constrained optimization
- Universal Conditional Gradient Sliding for Convex Optimization
- Solving structured nonsmooth convex optimization with complexity \(\mathcal {O}(\varepsilon ^{-1/2})\)
- Generalized uniformly optimal methods for nonlinear programming
- A multi-step doubly stabilized bundle method for nonsmooth convex optimization
- Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization
This page was built for publication: Fast bundle-level methods for unconstrained and ball-constrained convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2419544)
