Gradient methods for minimizing composite functions
From MaRDI portal
Let \(E\) be a finite-dimensional linear space with dual \(E^*\). The author provides new extended gradient methods for solving optimization problems of the form \[ \phi(x)= f(x)+ \psi(x)\to\min,\quad\text{s.t. } x\in Q, \] i.e. optimization problems where the objective function \(\phi: E\to\mathbb{R}\) is the sum of a smooth (not necessary convex) function \(f\) and a convex (not necessary smooth) function \(\psi\). The set \(Q\subset E\) is assumed to be a convex set. First it is pointed out that for general nonsmooth, nonconvex functions even resolving the question of whether a descent direction from a point exists is NP-hard. However, for the above-mentioned special form of the objective function, this problem is better solvable using the so-called composite gradient mapping \(g_L: E\to E^*\) introduced by \[ \begin{gathered} T_L(y):= \text{argmin}\Biggl\{f(y)+ \langle\nabla f(y),x-y\rangle+{L\over 2}\| x-y\|^2+ \psi(x)\mid x\in Q\Biggr\},\\ g_L(y):= L\cdot B(y- T_L(y)),\end{gathered} \] where \(B: E\to E^*\) is a fixed positive definite self-adjoint operator which defines the norm \(\| h\|=\langle Bh,h\rangle^{1/2}\) and \(L\) is a positive constant. That means that the objective of the composite gradient mapping is the sum of the objective of the known gradient mapping for smooth problems and the nonsmooth convex term. After the discussion of this mapping, some generalized gradient methods for the optimization problem are presented. It is shown that in convex and nonconvex cases there are exactly the same complexity results as in the usual smooth situation \((\psi=0)\). At the end of the paper, the author gives some examples of applications and some computational results of the proposed methods.
Recommendations
Cites work
- A generalized proximal point algorithm for certain non-convex minimization problems
- Accelerating the cubic regularization of Newton's method on convex problems
- Atomic Decomposition by Basis Pursuit
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1906319 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 3381785 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Just relax: convex programming methods for identifying sparse signals in noise
- Linear Inversion of Band-Limited Reflection Seismograms
- Rounding of convex sets and efficient gradient methods for linear programming problems
- Smooth minimization of non-smooth functions
Cited in
(only showing first 100 items - show all)- Primal-dual subgradient methods for convex problems
- Nonnegative data interpolation by spherical splines
- Accelerating ^1-^2 deblurring using wavelet expansions of operators
- Convergence analysis of primal-dual based methods for total variation minimization with finite element approximation
- On group-wise \(\ell_p\) regularization: theory and efficient algorithms
- Adaptive restart of the optimized gradient method for convex optimization
- Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
- A unified approach to error bounds for structured convex optimization problems
- Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints
- Optimal subgradient algorithms for large-scale convex optimization in simple domains
- Inexact proximal stochastic gradient method for convex composite optimization
- Hierarchical sparse modeling: a choice of two group Lasso formulations
- A modified strictly contractive peaceman-Rachford splitting method for multi-block separable convex programming
- Accelerated first-order methods for hyperbolic programming
- Conditional gradient type methods for composite nonlinear and stochastic optimization
- Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
- On variance reduction for stochastic smooth convex optimization with multiplicative noise
- A proximal difference-of-convex algorithm with extrapolation
- Proximal quasi-Newton methods for regularized convex optimization with linear and accelerated sublinear convergence rates
- Universal method for stochastic composite optimization problems
- Pathwise coordinate optimization for sparse learning: algorithm and theory
- Accelerating the DC algorithm for smooth functions
- DC formulations and algorithms for sparse optimization problems
- Nesterov's smoothing technique and minimizing differences of convex functions for hierarchical clustering
- I-LAMM for sparse learning: simultaneous control of algorithmic complexity and statistical error
- Solving structured nonsmooth convex optimization with complexity \(\mathcal {O}(\varepsilon ^{-1/2})\)
- Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization
- An optimal randomized incremental gradient method
- Complexity bounds for primal-dual methods minimizing the model of objective function
- Reconstruction of 3D X-ray CT images from reduced sampling by a scaled gradient projection algorithm
- An alternating direction method of multipliers with the BFGS update for structured convex quadratic optimization
- On the quality of first-order approximation of functions with Hölder continuous gradient
- The landscape of empirical risk for nonconvex losses
- Inexact proximal \(\epsilon\)-subgradient methods for composite convex optimization problems
- Second-order orthant-based methods with enriched Hessian information for sparse \(\ell _1\)-optimization
- Local and global convergence of a general inertial proximal splitting scheme for minimizing composite functions
- Point process estimation with Mirror Prox algorithms
- Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems
- Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems
- Globalized inexact proximal Newton-type methods for nonconvex composite functions
- Nearly optimal first-order methods for convex optimization under gradient norm measure: an adaptive regularization approach
- The condition number of a function relative to a set
- Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems
- Self adaptive inertial extragradient algorithms for solving bilevel pseudomonotone variational inequality problems
- Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences
- Accelerated Bregman proximal gradient methods for relatively smooth convex optimization
- A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems
- Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
- Stochastic proximal splitting algorithm for composite minimization
- Iteration complexity of generalized complementarity problems
- Solving convex min-min problems with smoothness and strong convexity in one group of variables and low dimension in the other
- A piecewise conservative method for unconstrained convex optimization
- Mining events with declassified diplomatic documents
- High-dimensional robust approximated M-estimators for mean regression with asymmetric data
- Generalized Nesterov's accelerated proximal gradient algorithms with convergence rate of order o(1/k^2)
- Some modified fast iterative shrinkage thresholding algorithms with a new adaptive non-monotone stepsize strategy for nonsmooth and convex minimization problems
- Inertial proximal incremental aggregated gradient method with linear convergence guarantees
- Linesearch Newton-CG methods for convex optimization with noise
- Limited-memory common-directions method for large-scale optimization: convergence, parallelization, and distributed optimization
- From differential equation solvers to accelerated first-order methods for convex optimization
- A control-theoretic perspective on optimal high-order optimization
- Nonregular and minimax estimation of individualized thresholds in high dimension with binary responses
- A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem
- Sparse regression at scale: branch-and-bound rooted in first-order optimization
- On stochastic accelerated gradient with convergence rate
- Accelerated proximal envelopes: application to componentwise methods
- Additive Schwarz methods for convex optimization with backtracking
- Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization
- A unified convergence rate analysis of the accelerated smoothed gap reduction algorithm
- Accelerated methods with fastly vanishing subgradients for structured non-smooth minimization
- A high-dimensional M-estimator framework for bi-level variable selection
- GSDAR: a fast Newton algorithm for \(\ell_0\) regularized generalized linear models with statistical guarantee
- An accelerated coordinate gradient descent algorithm for non-separable composite optimization
- Oracle complexity separation in convex optimization
- Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics
- Accelerated gradient sliding for structured convex optimization
- Proximal methods avoid active strict saddles of weakly convex functions
- A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization
- Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration
- Accelerated inexact composite gradient methods for nonconvex spectral optimization problems
- Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems
- Proximal gradient algorithms under local Lipschitz gradient continuity. A convergence and robustness analysis of PANOC
- Fast inertial dynamic algorithm with smoothing method for nonsmooth convex optimization
- Proximal algorithm for minimization problems in \(l_0\)-regularization for nonlinear inverse problems
- A note on approximate accelerated forward-backward methods with absolute and relative errors, and possibly strongly convex objectives
- Convergence analysis of positive-indefinite proximal ADMM with a Glowinski's relaxation factor
- Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem
- Subsampled nonmonotone spectral gradient methods
- Gradient methods for problems with inexact model of the objective
- An inexact interior-point Lagrangian decomposition algorithm with inexact oracles
- Efficient first-order methods for convex minimization: a constructive approach
- Accelerated and unaccelerated stochastic gradient descent in model generality
- Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
- Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
- Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
- Implementable tensor methods in unconstrained convex optimization
- Decomposition in derivative-free optimization
- Improved convergence rates and trajectory convergence for primal-dual dynamical systems with vanishing damping
- Accelerated proximal point method for maximally monotone operators
- On the linear convergence rates of exchange and continuous methods for total variation minimization
This page was built for publication: Gradient methods for minimizing composite functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q359630)
