iteration complexity

Iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian method based on the classical Lagrangian function and a full Lagrange multiplier update

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

    This paper establishes the iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian (IAPIAL) method for solving linearly constrained smooth nonconvex composite optimization problems which is based on the classical Lagrangian function and, most importantly, performs a full Lagrangian multiplier update, i.e., no shrinking factor is incorporated on it. More specifically, each IAPIAL iteration consists … Read more

    On Inexact Accelerated Proximal Gradient Methods with Relative Error Rules

  • Yunier Bello-Cruz
  • Max L. N. Gonçalves
  • Nathan Krislock
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , ,

    One of the most popular and important first-order iterations that provides optimal complexity of the classical proximal gradient method (PGM) is the “Fast Iterative Shrinkage/Thresholding Algorithm” (FISTA). In this paper, two inexact versions of FISTA for minimizing the sum of two convex functions are studied. The proposed schemes inexactly solve their subproblems by using relative … Read more

    Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems

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

    This paper proposes and establishes the iteration-complexity of an inexact proximal accelerated augmented Lagrangian (IPAAL) method for solving linearly constrained smooth nonconvex composite optimization problems. Each IPAAL iteration consists of inexactly solving a proximal augmented Lagrangian subproblem by an accelerated composite gradient (ACG) method followed by a suitable Lagrange multiplier update. It is shown that … Read more

    A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes

  • Jiaming Liang
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , ,

    This paper presents a proximal bundle variant, namely, the relaxed proximal bundle (RPB) method, for solving convex nonsmooth composite optimization problems. Like other proximal bundle variants, RPB solves a sequence of prox bundle subproblems whose objective functions are regularized composite cutting-plane models. Moreover, RPB uses a novel condition to decide whether to perform a serious … Read more

    An accelerated inexact proximal point method for solving nonconvex-concave min-max problems

  • Renato D.C. Monteiro
  • Weiwei Kong
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    Abstract This paper presents a quadratic-penalty type method for solving linearly-constrained composite nonconvex-concave min-max problems. The method consists of solving a sequence of penalty subproblems which, due to the min-max structure of the problem, are potentially nonsmooth but can be approximated by smooth composite nonconvex minimization problems. Each of these penalty subproblems is then solved … Read more

    A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems

  • Jiaming Liang
  • Renato D.C. Monteiro
  • Chee-Khian Sim
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , ,

    In this paper, we describe and establish iteration-complexity of two accelerated composite gradient (ACG) variants to solve a smooth nonconvex composite optimization problem whose objective function is the sum of a nonconvex differentiable function f with a Lipschitz continuous gradient and a simple nonsmooth closed convex function h. When f is convex, the first ACG … Read more

    An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems

  • Jefferson Gonçalves Melo
  • Renato D.C. Monteiro
  • Weiwei Kong
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    This paper proposes an efficient adaptive variant of a quadratic penalty accelerated inexact proximal point (QP-AIPP) method proposed earlier by the authors. Both the QP-AIPP method and its variant solve linearly constrained nonconvex composite optimization problems using a quadratic penalty approach where the generated penalized subproblems are solved by a variant of the underlying AIPP … Read more

    On inexact relative-error hybrid proximal extragradient, forward-backward and Tseng’s modified forward-backward methods with inertial effects

  • M. Marques Alves
  • Raul T. Marcavillaca
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , ,

    In this paper, we propose and study the asymptotic convergence and nonasymptotic global convergence rates (iteration-complexity) of an inertial under-relaxed version of the relative-error hybrid proximal extragradient (HPE) method for solving monotone inclusion problems. We analyze the proposed method under more flexible assumptions than existing ones on the extrapolation and relative-error parameters. As applications, we … Read more

    A Doubly Accelerated Inexact Proximal Point Method for Nonconvex Composite Optimization Problems

  • Jiaming Liang
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , ,

    This paper describes and establishes the iteration-complexity of a doubly accelerated inexact proximal point (D-AIPP) method for solving the nonconvex composite minimization problem whose objective function is of the form f+h where f is a (possibly nonconvex) differentiable function whose gradient is Lipschitz continuous and h is a closed convex function with bounded domain. D-AIPP … Read more

    Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variants

  • Necdet Serhat Aybat
  • Shiqian Ma
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , , ,

    Robust PCA has drawn significant attention in the last decade due to its success in numerous application domains, ranging from bio-informatics, statistics, and machine learning to image and video processing in computer vision. Robust PCA and its variants such as sparse PCA and stable PCA can be formulated as optimization problems with exploitable special structures. … Read more