iteration complexity

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

    A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem

  • Jean-Pierre Dussault
  • Mathieu Frappier
  • Jean Charles Gilbert
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization Tags , , , , , , , , ,

    The plain Newton-min algorithm for solving the linear complementarity problem (LCP) 0 ≤ x ⊥ (Mx+q) ≥ 0 can be viewed as an instance of the plain semismooth Newton method on the equational version min(x,Mx+q) = 0 of the problem. This algorithm converges for any q when M is an M-matrix, but not when it … Read more

    An ADMM-Based Interior-Point Method for Large-Scale Linear Programming

  • Tianyi Lin
  • Shiqian Ma
  • Yinyu Ye
  • Shuzhong Zhang
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper, we propose a new framework to implement interior point method (IPM) in order to solve some very large scale linear programs (LP). Traditional IPMs typically use Newton’s method to approximately solve a subproblem that aims to minimize a log-barrier penalty function at each iteration. Due its connection to Newton’s method, IPM is … Read more

    Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs

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

    This paper analyzes the iteration-complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs. More specifically, the objective function is of the form f + h where f is a differentiable function whose gradient is Lipschitz continuous and h is a closed convex function with a bounded domain. … Read more