Optimization Online


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

Andrea Cristofari (andrea.cristofari***at***unipd.it)

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.

Keywords: Block coordinate descent methods. Block decomposition methods. Linear convergence rate. SVM.

Category 1: Nonlinear Optimization

Citation: Computational Optimization and Applications

Download: [PDF]

Entry Submitted: 11/30/2018
Entry Accepted: 11/30/2018
Entry Last Modified: 03/05/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society