An almost cyclic 2-coordinate descent method for singly linearly constrained problems

DOI10.1007/S10589-019-00082-0zbMATH Open1414.90226arXiv1806.07826OpenAlexW2809196974WikidataQ128326614 ScholiaQ128326614MaRDI QIDQ2419552FDOQ2419552

Authors: Andrea Cristofari 

Publication date: 13 June 2019

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Abstract: A block decomposition method is proposed for minimizing a (possibly non-convex) continuously differentiable function subject to one linear equality constraint and simple bounds on the variables. The proposed method iteratively selects a pair of coordinates according to an almost cyclic strategy that does not use first-order information, allowing us not to compute the whole gradient of the objective function during the algorithm. Using first-order search directions to update each pair of coordinates, global convergence to stationary points is established for different choices of the stepsize under an appropriate assumption on the level set. In particular, both inexact and exact line search strategies are analyzed. Further, linear convergence rate is proved under standard additional assumptions. Numerical results are finally provided to show the effectiveness of the proposed method.

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

Recommendations

• Cyclic coordinate descent in a class of bang-singular-bang problems
• The 2-coordinate descent method for solving double-sided simplex constrained minimization problems
• An application of the algorithm of the cyclic coordinate descent in multidimensional optimization problems with constrained speed
• On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
• scientific article; zbMATH DE number 1215271
• Cyclic coordinate descent in the Hölder smooth setting
• On faster convergence of cyclic block coordinate descent-type methods for strongly convex minimization
• On the iteration complexity of cyclic coordinate gradient descent methods
• A coordinate descent homotopy method for linearly constrained nonsmooth convex minimization
• A cyclic block coordinate descent method with generalized gradient projections

zbMATH Keywords

SVMlinear convergence rateblock coordinate descent methodsblock decomposition methods

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Nonlinear programming (90C30)

Cites Work

• Introductory lectures on convex optimization. A basic course.
• Working set selection using second order information for training support vector machines
• Optimal scaling of a gradient method for distributed resource allocation
• Efficiency of coordinate descent methods on huge-scale optimization problems
• Coordinate descent method for large-scale L2-loss linear support vector machines
• A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
• Selective bi-coordinate variations for resource allocation type problems
• The 2-coordinate descent method for solving double-sided simplex constrained minimization problems
• A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training
• Solution methodologies for the smallest enclosing circle problem
• Coordinate descent algorithms
• On the convergence of block coordinate descent type methods
• Decomposition algorithm model for singly linearly-constrained problems subject to lower and Upper bounds
• Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
• Random Coordinate Descent Algorithms for Multi-Agent Convex Optimization Over Networks
• Projected Newton Methods for Optimization Problems with Simple Constraints
• A convergent decomposition algorithm for support vector machines
• On the convergence of the coordinate descent method for convex differentiable minimization
• Random block coordinate descent methods for linearly constrained optimization over networks
• On the convergence of a modified version of SVM^lightalgorithm
• On the convergence of a Jacobi-type algorithm for singly linearly-constrained problems subject to simple bounds
• A two-stage active-set algorithm for bound-constrained optimization
• Descent methods for convex essentially smooth minimization
• Parallel decomposition methods for linearly constrained problems subject to simple bound with application to the SVMs training
• First-order Methods for the Impatient: Support Identification in Finite Time with Convergent Frank--Wolfe Variants

Cited In (10)

• Active-set identification with complexity guarantees of an almost cyclic 2-coordinate descent method with Armijo line search
• On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
• A block-coordinate descent method for linearly constrained minimization problem
• The 2-coordinate descent method for solving double-sided simplex constrained minimization problems
• A Derivative-Free Method for Structured Optimization Problems
• PolyCD: optimization via cycling through the vertices of a polytope
• On convergence of a \(q\)-random coordinate constrained algorithm for non-convex problems
• Laplacian-based semi-supervised learning in multilayer hypergraphs by coordinate descent
• A decomposition method for Lasso problems with zero-sum constraint
• A conjugate direction based simplicial decomposition framework for solving a specific class of dense convex quadratic programs

Uses Software

• LIBSVM

This page was built for publication: An almost cyclic 2-coordinate descent method for singly linearly constrained problems

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