Nonsmooth Optimization

Holder Metric Subregularity with Applications to Proximal Point Method

  • Guoyin Li
  • Boris S. Mordukhovich
    • Categories Nonsmooth Optimization Tags , , , ,

    This paper is mainly devoted to the study and applications of H\”older metric subregularity (or metric $q$-subregularity of order $q\in(0,1]$) for general set-valued mappings between infinite-dimensional spaces. Employing advanced techniques of variational analysis and generalized differentiation, we derive neighborhood and pointbased sufficient conditions as well as necessary conditions for $q$-metric subregularity with evaluating the exact … Read more

    Bundle method for non-convex minimization with inexact subgradients and function values

  • Dominikus Noll
    • Categories Control Applications, Convex and Nonsmooth Optimization, Nonsmooth Optimization Tags , ,

    We discuss a bundle method to minimize non-smooth and non-convex locally Lipschitz functions. We analyze situations where only inexact subgradients or function values are available. For suitable classes of non-smooth functions we prove convergence of our algorithm to approximate critical points. CitationTo appear in: Computational and Analytical Mathematics. Springer Proceedings in MathematicsArticleDownload View PDF

    Subgradient methods for huge-scale optimization problems

  • Yurii Nesterov
    • Categories Nonsmooth Optimization Tags , , , ,

    We consider a new class of huge-scale problems, the problems with {\em sparse subgradients}. The most important functions of this type are piece-wise linear. For optimization problems with uniform sparsity of corresponding linear operators, we suggest a very efficient implementation of subgradient iterations, which total cost depends {\em logarithmically} in the dimension. This technique is … Read more

    Smoothing and Worst Case Complexity for Direct-Search Methods in Non-Smooth Optimization

  • R. Garmanjani
  • Luis Nunes Vicente
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , , ,

    For smooth objective functions it has been shown that the worst case cost of direct-search methods is of the same order as the one of steepest descent, when measured in number of iterations to achieve a certain threshold of stationarity. Motivated by the lack of such a result in the non-smooth case, we propose, analyze, … Read more

    Slopes of multifunctions and extensions of metric regularity

  • Van Ngai Huynh
  • Alexander Y. Kruger
  • Michel Thera
    • Categories Nonsmooth Optimization Tags , , , ,

    This article aims to demonstrate how the definitions of slopes can be extended to multi-valued mappings between metric spaces and applied for characterizing metric regularity. Several kinds of local and nonlocal slopes are defined and several metric regularity properties for set-valued mappings between metric spaces are investigated. CitationPublished in Vietnam Journal of Mathematics 40:2&3(2012) 355-369. … Read more

    Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm

  • Ming-Jun Lai
  • Wotao Yin
    • Categories Nonsmooth Optimization Tags , , , ,

    This paper studies the long-existing idea of adding a nice smooth function to “smooth” a non-differentiable objective function in the context of sparse optimization, in particular, the minimization of $||x||_1+1/(2\alpha)||x||_2^2$, where $x$ is a vector, as well as those of the minimization of $||X||_*+1/(2\alpha)||X||_F^2$, where $X$ is a matrix and $||X||_*$ and $||X||_F$ are the … Read more

    Necessary optimality conditions in pessimistic bilevel programming

  • Stephan Dempe
  • Boris S. Mordukhovich
  • Alain Zemkoho
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization

    This paper is devoted to the so-called pessimistic version of bilevel programming programs. Minimization problems of this type are challenging to handle partly because the corresponding value functions are often merely upper (while not lower) semicontinuous. Employing advanced tools of variational analysis and generalized differentiation, we provide rather general frameworks ensuring the Lipschitz continuity of … Read more

    About error bounds in metric spaces

  • Marian J. Fabian
  • RenĂ© Henrion
  • Alexander Y. Kruger
  • Jiri V. Outrata
    • Categories Nonsmooth Optimization

    The paper presents a general primal space classification scheme of necessary and sufficient criteria for the error bound property incorporating the existing conditions. Several primal space derivative-like objects – slopes – are used to characterize the error bound property of extended-real-valued functions on metric sapces. CitationPublished in D. Klatte et al. (eds.), Operations Research Proceedings … Read more

    Some remarks on stability of generalized equations

  • RenĂ© Henrion
  • Alexander Y. Kruger
  • Jiri V. Outrata
    • Categories Nonsmooth Optimization Tags , , ,

    The paper concerns the computation of the graphical derivative and the regular (Frechet) coderivative of the solution map to a class of generalized equations, where the multi-valued term amounts to the regular normal cone to a (possibly nonconvex) set given by C2 inequalities. Instead of the Linear Independence qualification condition, standardly used in this context, … Read more

    Error bounds for vector-valued functions on metric spaces

  • Ewa M. Bednarczuk
  • Alexander Y. Kruger
    • Categories Multi-Criteria Optimization, Nonsmooth Optimization Tags , , ,

    In this paper, we attempt to extend the definition and existing local error bound criteria to vector-valued functions, or more generally, to functions taking values in a normed linear space. Some new primal space derivative-like objects — slopes — are introduced and a classification scheme of error bound criteria is presented. CitationPublished in Vietnam Journal … Read more