Nonsmooth Optimization

A bundle method for nonsmooth DC programming with application to chance-constrained problems

  • Welington de Oliveira
  • Sophie Demassey
  • Paul Javal
  • Hugo Morais
  • Bhargav Swaminathan
  • Wim van Ackooij
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags

    This work considers nonsmooth and nonconvex optimization problems whose objective and constraint functions are defined by difference-of-convex (DC) functions. We consider an infeasible bundle method based on the so-called improvement functions to compute critical points for problems of this class. Our algorithm neither employs penalization techniques nor solves subproblems with linearized constraints. The approach, which … Read more

    Primal Space Necessary Characterizations of Transversality Properties

  • Nguyen Duy Cuong
  • Alexander Y. Kruger
    • Categories Nonsmooth Optimization Tags , , , , ,

    This paper continues the study of general nonlinear transversality properties of collections of sets and focuses on primal space necessary (in some cases also sufficient) characterizations of the properties. We formulate geometric, metric and slope characterizations, particularly in the convex setting. The Holder case is given a special attention. Quantitative relations between the nonlinear transversality … Read more

    Proximal splitting algorithms: Relax them all!

  • Laurent Condat
  • Andres Contreras
  • Akira Hirabayashi
  • Daichi Kitahara
    • Categories Nonlinear Optimization, Nonsmooth Optimization

    Convex optimization problems, whose solutions live in very high dimensional spaces, have become ubiquitous. To solve them, proximal splitting algorithms are particularly adequate: they consist of simple operations, by handling the terms in the objective function separately. We present several existing proximal splitting algorithms and we derive new ones, within a unified framework, which consists … Read more

    A Regularized Smoothing Method for Fully Parameterized Convex Problems with Applications to Convex and Nonconvex Two-Stage Stochastic Programming

  • Pedro Borges de Melo
  • Claudia Sagastizábal
  • Mikhail V. Solodov
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    We present an approach to regularize and approximate solution mappings of parametric convex optimization problems that combines interior penalty (log-barrier) solutions with Tikhonov regularization. Because the regularized mappings are single-valued and smooth under reasonable conditions, they can be used to build a computationally practical smoothing for the associated optimal value function. The value function in … Read more

    Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach

  • Mituhiro Fukuda
  • Masaru Ito
    • Categories Convex Optimization, Nonsmooth Optimization

    In the development of first-order methods for smooth (resp., composite) convex optimization problems minimizing smooth functions, the gradient (resp., gradient mapping) norm is a fundamental optimality measure for which a regularization technique of first-order methods is known to be nearly optimal. In this paper, we report an adaptive regularization approach attaining this iteration complexity without … Read more

    The Fermat Rule for Set Optimization Problems with Lipschitzian Set-Valued Mappings

  • Gemayqzel Bouza
  • Christiane Tammer
  • Ernest Quintana
  • Vu Anh Tuan
    • Categories Multi-Criteria Optimization, Nonsmooth Optimization, Robust Optimization Tags , , , ,

    n this paper, we consider set optimization problems with respect to the set approach. Specifically, we deal with the lower less and the upper less set relations. First, we derive properties of convexity and Lipschitzianity of suitable scalarizing functionals, under the same assumption on the set-valued objective mapping. We then obtain upper estimates of the … Read more

    Active strict saddles in nonsmooth optimization

  • Damek Davis
  • Dmitriy Drusvyatskiy
    • Categories Nonsmooth Optimization Tags , , ,

    We introduce a geometrically transparent strict saddle property for nonsmooth functions. This property guarantees that simple proximal algorithms on weakly convex problems converge only to local minimizers, when randomly initialized. We argue that the strict saddle property may be a realistic assumption in applications, since it provably holds for generic semi-algebraic optimization problems. ArticleDownload View … Read more

    A subspace-accelerated split Bregman method for sparse data recovery with joint l1-type regularizers

  • Valentina De Simone
  • Daniela di Serafino
  • Marco Viola
    • Categories Convex Optimization, Finance and Economics, Nonsmooth Optimization Tags , , ,

    We propose a subspace-accelerated Bregman method for the linearly constrained minimization of functions of the form f(u)+tau_1 ||u||_1 + tau_2 ||D*u||_1, where f is a smooth convex function and D represents a linear operator, e.g. a finite difference operator, as in anisotropic Total Variation and fused-lasso regularizations. Problems of this type arise in a wide … Read more

    A Distributed Quasi-Newton Algorithm for Primal and Dual Regularized Empirical Risk Minimization

  • Stephen Wright
  • Cong Han Lim
  • Ching-pei Lee
    • Categories Nonsmooth Optimization, Parallel Algorithms Tags , , , , , , ,

    We propose a communication- and computation-efficient distributed optimization algorithm using second-order information for solving empirical risk minimization (ERM) problems with a nonsmooth regularization term. Our algorithm is applicable to both the primal and the dual ERM problem. Current second-order and quasi-Newton methods for this problem either do not work well in the distributed setting or … Read more

    A robust method based on LOVO functions for solving least squares problems

  • E. V. Castelani
  • R. Lopes
  • W. V. I. Shirabayashi
  • Francisco N. C. Sobral
    • Categories Nonlinear Systems and Least-Squares, Nonsmooth Optimization, Parallel Algorithms Tags , , ,

    The robust adjustment of nonlinear models to data is considered in this paper. When data comes from real experiments, it is possible that measurement errors cause the appearance of discrepant values, which should be ignored when adjusting models to them. This work presents a Lower Order-value Optimization (LOVO) version of the Levenberg-Marquardt algorithm, which is … Read more