Primal-dual block-proximal splitting for a class of non-convex problems

DOI10.1553/ETNA_VOL52S509zbMATH Open1457.90156arXiv1911.06284OpenAlexW2985873675MaRDI QIDQ2218923FDOQ2218923

Authors: Stanislav Mazurenko, Jyrki Jauhiainen, Tuomo Valkonen 

Publication date: 18 January 2021

Published in: ETNA - Electronic Transactions on Numerical Analysis (Search for Journal in Brave)

Abstract: We develop block structure adapted primal-dual algorithms for non-convex non-smooth optimisation problems whose objectives can be written as compositions $G(x)+F(K(x))$ of non-smooth block-separable convex functions $G$ and $F$ with a non-linear Lipschitz-differentiable operator $K$. Our methods are refinements of the non-linear primal-dual proximal splitting method for such problems without the block structure, which itself is based on the primal-dual proximal splitting method of Chambolle and Pock for convex problems. We propose individual step length parameters and acceleration rules for each of the primal and dual blocks of the problem. This allows them to convergence faster by adapting to the structure of the problem. For the squared distance of the iterates to a critical point, we show local $O(1/N)$, $O(1/N^2)$ and linear rates under varying conditions and choices of the step lengths parameters. Finally, we demonstrate the performance of the methods on practical inverse problems: diffusion tensor imaging and electrical impedance tomography.

Full work available at URL: https://arxiv.org/abs/1911.06284

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Primal-dual proximal splitting and generalized conjugation in non-smooth non-convex optimization
• Acceleration and global convergence of a first-order primal-dual method for nonconvex problems
• Local linear convergence analysis of primal-dual splitting methods
• The Primal-Dual Hybrid Gradient Method for Semiconvex Splittings
• Block-proximal methods with spatially adapted acceleration

zbMATH Keywords

convex optimizationstep lengthnon-smooth optimizationprimal-dual algorithms

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonlinear programming (90C30) Programming in abstract spaces (90C48)

Cites Work

• ARock: an algorithmic framework for asynchronous parallel coordinate updates
• Julia: a fresh approach to numerical computing
• Primal-dual extragradient methods for nonlinear nonsmooth PDE-constrained optimization
• Variational Analysis
• An algorithm for total variation minimization and applications
• A first-order primal-dual algorithm for convex problems with applications to imaging
• Total generalized variation in diffusion tensor imaging
• Parallel coordinate descent methods for big data optimization
• Distributed coordinate descent method for learning with big data
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Accelerated, parallel, and proximal coordinate descent
• Coordinate descent algorithms
• TGV for diffusion tensors: a comparison of fidelity functions
• A primal-dual hybrid gradient method for nonlinear operators with applications to MRI
• Stochastic primal-dual coordinate method for regularized empirical risk minimization
• Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
• A two-stage image segmentation method for blurry images with Poisson or multiplicative gamma noise
• A globally convergent algorithm for nonconvex optimization based on block coordinate update
• Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications
• Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
• A coordinate-descent primal-dual algorithm with large step size and possibly nonseparable functions
• Block-proximal methods with spatially adapted acceleration
• A stochastic semismooth Newton method for nonsmooth nonconvex optimization
• Stochastic model-based minimization of weakly convex functions
• Testing and non-linear preconditioning of the proximal point method
• Block stochastic gradient iteration for convex and nonconvex optimization
• Relaxed Gauss-Newton methods with applications to electrical impedance tomography
• Acceleration and Global Convergence of a First-Order Primal-Dual Method for Nonconvex Problems
• Primal-dual proximal splitting and generalized conjugation in non-smooth non-convex optimization

Cited In (4)

• Primal-dual proximal splitting and generalized conjugation in non-smooth non-convex optimization
• A nonsmooth primal-dual method with interwoven PDE constraint solver
• BlockPDPS.jl
• An alternative extrapolation scheme of PDHGM for saddle point problem with nonlinear function

Uses Software

• Julia
• ARock
• Teem
• nlpdegm

This page was built for publication: Primal-dual block-proximal splitting for a class of non-convex problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2218923)