iteration complexity

Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs

  • Jefferson Gonçalves Melo
  • Renato D.C. Monteiro
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    This paper establishes the iteration-complexity of a Jacobi-type non-Euclidean proximal alternating direction method of multipliers (ADMM) for solving multi-block linearly constrained nonconvex programs. The subproblems of this ADMM variant can be solved in parallel and hence the method has great potential to solve large scale multi-block linearly constrained nonconvex programs. Moreover, our analysis allows the … Read more

    Symmetric ADMM with Positive-Indefinite Proximal Regularization for Linearly Constrained Convex Optimization

  • Bin Gao
  • Feng Ma
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Parallel Algorithms Tags , , ,

    The proximal ADMM which adds proximal regularizations to ADMM’s subproblems is a popular and useful method for linearly constrained separable convex problems, especially its linearized case. A well-known requirement on guaranteeing the convergence of the method in the literature is that the proximal regularization must be positive semidefinite. Recently it was shown by He et … Read more

    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