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
- A descent proximal level bundle method for convex nondifferentiable optimization
- A Proximal Bundle Method with Approximate Subgradient Linearizations
- A proximal cutting plane method using Chebychev center for nonsmooth convex optimization
- 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
- An Iterative Regularization Method for Total Variation-Based Image Restoration
- 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
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 3559294 (Why is no real title available?)
- 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
(9)- Solving structured nonsmooth convex optimization with complexity \(\mathcal {O}(\varepsilon ^{-1/2})\)
- Acceleration techniques for level bundle methods in weakly smooth convex constrained optimization
- A multi-step doubly stabilized bundle method for nonsmooth convex optimization
- Generalized uniformly optimal methods for nonlinear programming
- Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization
- A level-set method for convex optimization with a feasible solution path
- Accelerated bundle level methods with inexact oracle
- Universal Conditional Gradient Sliding for Convex Optimization
- Discrete level-bundle method for mean-CVaR portfolio optimization with cardinality constraint
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)
