Convex and Nonsmooth Optimization

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

    Proximal Alternating Penalty Algorithms for Nonsmooth Constrained Convex Optimization

  • Quoc Tran-Dinh
    • Categories Convex and Nonsmooth Optimization, Convex Optimization

    We develop two new proximal alternating penalty algorithms to solve a wide range class of constrained convex optimization problems. Our approach mainly relies on a novel combination of the classical quadratic penalty, alternating, Nesterov’s acceleration, and homotopy techniques. The first algorithm is designed to solve generic and possibly nonsmooth constrained convex problems without requiring any … Read more

    Douglas-Rachford Splitting for Pathological Convex Optimization

  • Yanli Liu
  • Ernest K. Ryu
  • Wotao Yin
    • Categories Convex Optimization Tags , , , , , , ,

    Despite the vast literature on DRS, there has been very little work analyzing their behavior under pathologies. Most analyses assume a primal solution exists, a dual solution exists, and strong duality holds. When these assumptions are not met, i.e., under pathologies, the theory often breaks down and the empirical performance may degrade significantly. In this … Read more

    Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive stepsizes and convergence

  • Dirk A. Lorenz
  • Quoc Tran-Dinh
    • Categories Convex Optimization Tags , , , ,

    We revisit the classical Douglas-Rachford (DR) method for finding a zero of the sum of two maximal monotone operators. Since the practical performance of the DR method crucially depends on the stepsizes, we aim at developing an adaptive stepsize rule. To that end, we take a closer look at a linear case of the problem … Read more

    Simplified Versions of the Conditional Gradient Method

  • Igor V. Konnov
    • Categories Constrained Nonlinear Optimization, Convex Optimization

    We suggest simple modifications of the conditional gradient method for smooth optimization problems, which maintain the basic convergence properties, but reduce the implementation cost of each iteration essentially. Namely, we propose the step-size procedure without any line-search, and inexact solution of the direction finding subproblem. Preliminary results of computational tests confirm efficiency of the proposed … Read more

    A forward-backward penalty scheme with inertial effects for montone inclusions. Applications to convex bilevel programming

  • Radu Ioan Bot
  • Dang-Khoa Nguyen
    • Categories Convex Optimization Tags , , ,

    We investigate forward-backward splitting algorithm of penalty type with inertial effects for finding the zeros of the sum of a maximally monotone operator and a cocoercive one and the convex normal cone to the set of zeroes of an another cocoercive operator. Weak ergodic convergence is obtained for the iterates, provided that a condition express … Read more

    Convergence rates of proximal gradient methods via the convex conjugate

  • David H. Gutman
  • Javier F. Peña
    • Categories Convex Optimization Tags , ,

    We give a novel proof of the $O(1/k)$ and $O(1/k^2)$ convergence rates of the proximal gradient and accelerated proximal gradient methods for composite convex minimization. The crux of the new proof is an upper bound constructed via the convex conjugate of the objective function. Citation Technical Report, Carnegie Mellon University, January 2018. Article Download View … Read more

    The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates

  • Radu Ioan Bot
  • Dang-Khoa Nguyen
    • Categories Nonsmooth Optimization Tags , , , , , , ,

    We propose two numerical algorithms for minimizing the sum of a smooth function and the composition of a nonsmooth function with a linear operator in the fully nonconvex setting. The iterative schemes are formulated in the spirit of the proximal and, respectively, proximal linearized alternating direction method of multipliers. The proximal terms are introduced through … Read more

    Convergence rates of Forward-Douglas-Rachford splitting method

  • Jalal Fadili
  • Jingwei Liang
  • Cesare Molinari
    • Categories Convex and Nonsmooth Optimization

    Over the past years, operator splitting methods have become ubiquitous for non-smooth optimization owing to their simplicity and efficiency. In this paper, we consider the Forward–Douglas–Rachford splitting method (FDR) [10, 40], and study both global and local convergence rates of this method. For the global rate, we establish an o(1/k) convergence rate in terms of … Read more

    GEP-MSCRA for computing the group zero-norm regularized least squares estimator

  • Shaohua Pan
  • Shujun Shujun
    • Categories Nonsmooth Optimization, Statistics

    This paper concerns with the group zero-norm regularized least squares estimator which, in terms of the variational characterization of the zero-norm, can be obtained from a mathematical program with equilibrium constraints (MPEC). By developing the global exact penalty for the MPEC, this estimator is shown to arise from an exact penalization problem that not only … Read more