iteration complexity

An Inexact Spingarn’s Partial Inverse Method with Applications to Operator Splitting and Composite Optimization

  • M. Marques Alves
  • Samara Costa Lima
    • Categories Convex and Nonsmooth Optimization Tags , , , , , ,

    We propose and study the iteration-complexity of an inexact version of the Spingarn’s partial inverse method. Its complexity analysis is performed by viewing it in the framework of the hybrid proximal extragradient (HPE) method, for which pointwise and ergodic iteration-complexity has been established recently by Monteiro and Svaiter. As applications, we propose and analyze the … Read more

    Randomized Primal-Dual Proximal Block Coordinate Updates

  • Xiang Gao
  • Yangyang Xu
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    In this paper we propose a randomized primal-dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its $O(1/t)$ convergence rate in terms of the objective value and feasibility measure. The framework includes several existing algorithms as special cases such … Read more

    Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis

  • Bo Jiang
  • Tianyi Lin
  • Shiqian Ma
  • Shuzhong Zhang
    • Categories Nonlinear Optimization Tags , , , , ,

    Nonconvex optimization problems are frequently encountered in much of statistics, business, science and engineering, but they are not yet widely recognized as a technology. A reason for this relatively low degree of popularity is the lack of a well developed system of theory and algorithms to support the applications, as is the case for its … Read more

    Conditional gradient type methods for composite nonlinear and stochastic optimization

  • Saeed Ghadimi
    • Categories Nonlinear Optimization Tags , , , , ,

    In this paper, we present a conditional gradient type (CGT) method for solving a class of composite optimization problems where the objective function consists of a (weakly) smooth term and a (strongly) convex regularization term. While including a strongly convex term in the subproblems of the classical conditional gradient (CG) method improves its rate of … Read more

    First-Order Algorithms for Convex Optimization with Nonseparate Objective and Coupled Constraints

  • Xiang Gao
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    In this paper we consider a block-structured convex optimization model, where in the objective the block-variables are nonseparable and they are further linearly coupled in the constraint. For the 2-block case, we propose a number of first-order algorithms to solve this model. First, the alternating direction method of multipliers (ADMM) is extended, assuming that it … Read more

    The Cyclic Block Conditional Gradient Method for Convex Optimization Problems

  • Amir Beck
  • Shoham Sabach
  • Edouard Pauwels
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization Tags , , , , ,

    In this paper we study the convex problem of optimizing the sum of a smooth function and a compactly supported non-smooth term with a specific separable form. We analyze the block version of the generalized conditional gradient method when the blocks are chosen in a cyclic order. A global sublinear rate of convergence is established … Read more

    On the Iteration Complexity of Some Projection Methods for Monotone Linear Variational Inequalities

  • Caihua Chen
  • Xiaoling Fu
  • Bingsheng He
  • Xiao-Ming Yuan
    • Categories Complementarity and Variational Inequalities Tags , , ,

    Projection type methods are among the most important methods for solving monotone linear variational inequalities. In this note, we analyze the iteration complexity for two projection methods and accordingly establish their worst-case O(1/t) convergence rates measured by the iteration complexity in both the ergodic and nonergodic senses, where t is the iteration counter. Our analysis … Read more

    On the Information-Adaptive Variants of the ADMM: an Iteration Complexity Perspective

  • Xiang Gao
  • Bo Jiang
  • Shuzhong Zhang
    • Categories Convex Optimization Tags , , , ,

    Designing algorithms for an optimization model often amounts to maintaining a balance between the degree of information to request from the model on the one hand, and the computational speed to expect on the other hand. Naturally, the more information is available, the faster one can expect the algorithm to converge. The popular algorithm of … Read more

    Iteration Bounds for Finding the $\epsilonhBcStationary Points for Structured Nonconvex Optimization

  • Bo Jiang
  • Shuzhong Zhang
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    In this paper we study proximal conditional-gradient (CG) and proximal gradient-projection type algorithms for a block-structured constrained nonconvex optimization model, which arises naturally from tensor data analysis. First, we introduce a new notion of $\epsilon$-stationarity, which is suitable for the structured problem under consideration. %, compared with other similar solution concepts. We then propose two … Read more

    Block-wise Alternating Direction Method of Multipliers for Multiple-block Convex Programming and Beyond

  • Bingsheng He
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , , , , ,

    The alternating direction method of multipliers (ADMM) is a benchmark for solving a linearly constrained convex minimization model with a two-block separable objective function; and it has been shown that its direct extension to a multiple-block case where the objective function is the sum of more than two functions is not necessarily convergent. For the … Read more