Nonsmooth Optimization

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

    Deriving Solution Value Bounds from the ADMM

  • Jonathan Eckstein
    • Categories Convex Optimization, Nonsmooth Optimization Tags ,

    This short paper describes a simple subgradient-based techniques for deriving bounds on the optimal solution value when using the ADMM to solve convex optimization problems. The technique requires a bound on the magnitude of some optimal solution vector, but is otherwise completely general. Some computational examples using LASSO problems demonstrate that the technique can produce … Read more

    An inexact augmented Lagrangian method for nonsmooth optimization on Riemannian manifold

  • Deng Kangkang
  • Peng Zheng
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization

    We consider a nonsmooth optimization problem on Riemannian manifold, whose objective function is the sum of a differentiable component and a nonsmooth convex function. We propose a manifold inexact augmented Lagrangian method (MIALM) for the considered problem. The problem is reformulated to a separable form. By utilizing the Moreau envelope, we get a smoothing subproblem … Read more

    An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities

  • Robert M. Freund
  • Michael J. Todd
  • Jourdain Lamperski
    • Categories Convex Optimization, Linear Programming, Nonsmooth Optimization Tags , , , ,

    The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P) when its set of solutions has positive volume. However, when (P) is infeasible, the ellipsoid algorithm has no mechanism for proving that (P) is infeasible. This is in contrast to the other two … Read more