Convex and Nonsmooth Optimization

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

    A generalization of linearized alternating direction method of multipliers for solving two-block separable convex programming

  • Song Dunjiang
  • Zhao Pengjun
  • Chang Xiaokai
  • Liu Sanyang
    • Categories Convex and Nonsmooth Optimization

    The linearized alternating direction method of multipliers (ADMM), with indefinite proximal regularization, has been proved to be efficient for solving separable convex optimization subject to linear constraints. In this paper, we present a generalization of linearized ADMM (G-LADMM) to solve two-block separable convex minimization model, which linearizes all the subproblems by choosing a proper positive-definite … Read more

    Deep Unfolding of a Proximal Interior Point Method for Image Restoration

  • Carla Bertocchi
  • Émilie Chouzenoux
  • Marie-Caroline Corbineau
  • Jean-Christophe Pesquet
  • Marco Prato
    • Categories Convex and Nonsmooth Optimization, Network Optimization, Robust Optimization Tags , , , , ,

    Variational methods are widely applied to ill-posed inverse problems for they have the ability to embed prior knowledge about the solution. However, the level of performance of these methods significantly depends on a set of parameters, which can be estimated through computationally expensive and time-consuming methods. In contrast, deep learning offers very generic and efficient … 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

    The Sard theorem for essentially smooth locally Lipschitz maps and applications in optimization

  • Xuan Duc Ha Truong
    • Categories Convex and Nonsmooth Optimization, Multi-Criteria Optimization Tags , , , ,

    The classical Sard theorem states that the set of critical values of a $C^{k}$-map from an open set of $\R^n$ to $\R^p$ ($n\geq p$) has Lebesgue measure zero provided $k\geq n-p+1$. In the recent paper by Barbet, Dambrine, Daniilidis and Rifford, the so called “preparatory Sard theorem” for a compact countable set $I$ of $C^k$ … Read more

    A dual spectral projected gradient method for log-determinant semidefinite problems

  • Mituhiro Fukuda
  • Sunyoung Kim
  • Takashi Nakagaki
  • Makoto Yamashita
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    We extend the result on the spectral projected gradient method by Birgin et al in 2000 to a log-determinant semidefinite problem (SDP) with linear constraints and propose a spectral projected gradient method for the dual problem. Our method is based on alternate projections on the intersection of two convex sets, which first projects onto the … Read more

    Basis Pursuit Denoise with Nonsmooth Constraints

  • Aleksandr Y. Aravkin
  • Robert Baraldi
  • Rajiv Kumar
    • Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    Level-set optimization formulations with data-driven constraints minimize a regularization functional subject to matching observations to a given error level. These formulations are widely used, particularly for matrix completion and sparsity promotion in data interpolation and denoising. The misfit level is typically measured in the l2 norm, or other smooth metrics. In this paper, we present … Read more

    Parallelizing Subgradient Methods for the Lagrangian Dual in Stochastic Mixed-Integer Programming

  • Cong Han Lim
  • Jeff Linderoth
  • James R. Luedtke
  • Stephen Wright
    • Categories Nonsmooth Optimization, Stochastic Programming Tags , ,

    The dual decomposition of stochastic mixed-integer programs can be solved by the projected subgradient algorithm. We show how to make this algorithm more amenable to parallelization in a master-worker model by describing two approaches, which can be combined in a natural way. The first approach partitions the scenarios into batches, and makes separate use of … 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

    Acceleration of Primal-Dual Methods by Preconditioning and Simple Subproblem Procedures

  • Yanli Liu
  • Yunbei Xu
  • Wotao Yin
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , ,

    Primal-Dual Hybrid Gradient (PDHG) and Alternating Direction Method of Multipliers (ADMM) are two widely-used first-order optimization methods. They reduce a difficult problem to simple subproblems, so they are easy to implement and have many applications. As first-order methods, however, they are sensitive to problem conditions and can struggle to reach the desired accuracy. To improve … Read more