Nonsmooth Optimization

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

    Continuous selections of solutions for locally Lipschitzian equations

  • A.V. Arutyunov
  • Alexey F. Izmailov
  • S.E. Zhukovskiy
    • Categories Complementarity and Variational Inequalities, Nonlinear Systems and Least-Squares, Nonsmooth Optimization

    This paper answers in affirmative the long-standing question of nonlinear analysis, concerning the existence of a continuous single-valued local selection of the right inverse to a locally Lipschitzian mapping. Moreover, we develop a much more general result, providing conditions for the existence of a continuous single-valued selection not only locally, but rather on any given … Read more