Alternating minimization methods for strongly convex optimization

DOI10.1515/JIIP-2020-0074MaRDI QIDQ2232092zbMATH OpenOpenAlexFDO

Authors Nazarii Tupitsa, Pavel Dvurechensky, Alexander V. Gasnikov, Sergey Guminov

Publication date 4 October 2021

Published in Journal of Inverse and Ill-posed Problems (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationnonconvex optimizationcomplexity analysisalternating minimizationblock-coordinate method

Mathematics Subject Classification ID

Convex programming (90C25)

Abstract: {We consider alternating minimization procedures for convex optimization problems with variable divided in many block, each block being amenable for minimization with respect to its variable with freezed other variables blocks. In the case of two blocks, we prove a linear convergence rate for alternating minimization procedure under Polyak-Lojasiewicz condition, which can be seen as a relaxation of the strong convexity assumption. Under strong convexity assumption in many-blocks setting we provide an accelerated alternating minimization procedure with linear rate depending on the square root of the condition number as opposed to condition number for the non-accelerated method. We also mention an approximating non-negative solution to a linear system of equations $Ax=y$ with alternating minimization of Kullback-Leibler (KL) divergence between $Ax$ and $y$.

Recommendations

• On the rate of convergence of alternating minimization for non-smooth non-strongly convex optimization in Banach spaces
• On the rate of convergence of the proximal alternating linearized minimization algorithm for convex problems
• An alternate minimization method beyond positive definite proximal regularization: convergence and complexity
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• A class of alternating linearization algorithms for nonsmooth convex optimization

Cites work

• scientific article; zbMATH DE number 4015993 (Why is no real title available?)
• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• scientific article; zbMATH DE number 3872359 (Why is no real title available?)
• scientific article; zbMATH DE number 51132 (Why is no real title available?)
• scientific article; zbMATH DE number 1099032 (Why is no real title available?)
• scientific article; zbMATH DE number 6252408 (Why is no real title available?)
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A Statistical Model for Positron Emission Tomography
• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• A literature survey of low-rank tensor approximation techniques
• A stable alternative to Sinkhorn's algorithm for regularized optimal transport
• Accelerated alternating descent methods for Dykstra-like problems
• Accelerated primal-dual gradient descent with linesearch for convex, nonconvex, and nonsmooth optimization problems
• An adaptive proximal method for variational inequalities
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
• Composite optimization for the resource allocation problem
• Computational Methods for Inverse Problems
• Convergence of an alternating maximization procedure
• Cubic regularization of Newton method and its global performance
• Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints
• Error bounds and convergence analysis of feasible descent methods: A general approach
• Fast primal-dual gradient method for strongly convex minimization problems with linear constraints
• Iteration complexity analysis of block coordinate descent methods
• Iterative Bregman projections for regularized transportation problems
• Iterative Solution of Nonlinear Equations in Several Variables
• Lectures on convex optimization
• Mirror descent and convex optimization problems with non-smooth inequality constraints
• Nonnegative tensor decomposition
• Numerical methods for the resource allocation problem in a computer network
• On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
• On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes
• Optimal combination of tensor optimization methods
• Primal-dual accelerated gradient methods with small-dimensional relaxation oracle
• Tensor Decompositions and Applications

Cited in

(13)

• Algorithms for Euclidean-regularised optimal transport
• Alternating conditional gradient method for convex feasibility problems
• Stochastic saddle-point optimization for the Wasserstein barycenter problem
• On the rate of convergence of alternating minimization for non-smooth non-strongly convex optimization in Banach spaces
• Alternating minimization algorithm for minimizing the sum of strongly convex function and weakly convex function
• Alternating minimization as sequential unconstrained minimization: a survey
• Recent theoretical advances in decentralized distributed convex optimization
• Recent Theoretical Advances in Non-Convex Optimization
• Randomized methods for computing optimal transport without regularization and their convergence analysis
• Newton-type Alternating Minimization Algorithm for Convex Optimization
• Nested alternating minimization with FISTA for non-convex and non-smooth optimization problems
• Alternating proximal gradient method for convex minimization
• Stochastic approximation versus sample average approximation for Wasserstein barycenters

This page was built for publication: Alternating minimization methods for strongly convex optimization

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