Nonsmooth Optimization

Partial Second-Order Subdifferentials in Variational Analysis and Optimization

  • Boris S. Mordukhovich
  • Nguyen Mau Nam
  • Nguyen Thi Yen Nhi
    • Categories Nonsmooth Optimization Tags , , , , , ,

    This paper presents a systematic study of partial second-order subdifferentials for extended-real-valued functions, which have already been applied to important issues of variational analysis and constrained optimization in finite-dimensional spaces. The main results concern developing extended calculus rules for these second-order constructions in both finite-dimensional and infinite-dimensional frameworks. We also provide new applications of partial … Read more

    Clarke subgradients for directionally Lipschitzian stratifiable functions

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
  • Alexander D. Ioffe
    • Categories Nonsmooth Optimization

    Using a geometric argument, we show that under a reasonable continuity condition, the Clarke subdifferential of a semi-algebraic (or more generally stratifiable) directionally Lipschitzian function admits a simple form: the normal cone to the domain and limits of gradients generate the entire Clarke subdifferential. The characterization formula we obtain unifies various apparently disparate results that … Read more

    Iterative Hard Thresholding Methods for $ Regularized Convex Cone Programming

  • Zhaosong Lu
    • Categories Combinatorial Optimization, Nonsmooth Optimization Tags , , , ,

    In this paper we consider $l_0$ regularized convex cone programming problems. In particular, we first propose an iterative hard thresholding (IHT) method and its variant for solving $l_0$ regularized box constrained convex programming. We show that the sequence generated by these methods converges to a local minimizer. Also, we establish the iteration complexity of the … Read more

    Variational Analysis of the Spectral Abscissa at a Matrix with a Nongeneric Multiple Eigenvalue

  • Sara Grundel
  • Michael L. Overton
    • Categories Nonsmooth Optimization

    The spectral abscissa is a fundamental map from the set of complex matrices to the real numbers. Denoted $\alpha$ and defined as the maximum of the real parts of the eigenvalues of a matrix $X$, it has many applications in stability analysis of dynamical systems. The function $\alpha$ is nonconvex and is non-Lipschitz near matrices … Read more

    Reducing the Number of Function Evaluations in Mesh Adaptive Direct Search Algorithms

  • Charles Audet
  • Sébastien Le Digabel
  • Christophe Tribes
  • Andrea Ianni
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    The mesh adaptive direct search (MADS) class of algorithms is designed for nonsmooth optimization, where the objective function and constraints are typically computed by launching a time-consuming computer simulation. Each iteration of a MADS algorithm attempts to improve the current best-known solution by launching the simulation at a finite number of trial points. Common implementations … Read more

    On parallelizing dual decomposition in stochastic integer programming

  • Miles Lubin
  • Kipp Martin
  • Burhaneddin Sandikçi
  • Cosmin G. Petra
    • Categories Nonsmooth Optimization, Parallel Algorithms, Stochastic Programming Tags , , , , ,

    For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Car\o{}e and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parallel execution by identifying a formulation that permits the parallel solution of the \textit{master} program by using structure-exploiting interior-point solvers. Our results demonstrate the potential … Read more

    Iterative Reweighted Minimization Methods for $ Regularized Unconstrained Nonlinear Programming

  • Zhaosong Lu
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags ,

    In this paper we study general $l_p$ regularized unconstrained minimization problems. In particular, we derive lower bounds for nonzero entries of first- and second-order stationary points, and hence also of local minimizers of the $l_p$ minimization problems. We extend some existing iterative reweighted $l_1$ (IRL1) and $l_2$ (IRL2) minimization methods to solve these problems and … Read more

    Variable Neighborhood Search for parameter tuning in Support Vector Machines

  • Emilio Carrizosa
  • Belén Martín-Barragán
  • Dolores Romero Morales
    • Categories Data-Mining, Nonsmooth Optimization, Unconstrained Optimization Tags , , , , ,

    As in most Data Mining procedures, how to tune the parameters of a Support Vector Machine (SVM) is a critical, though not sufficiently explored, issue. The default approach is a grid search in the parameter space, which becomes prohibitively time-consuming even when just a few parameters are to be tuned. For this reason, for models … Read more

    On RIC bounds of Compressed Sensing Matrices for Approximating Sparse Solutions Using Lq Quasi Norms

  • Sheu Ruey-Lin
  • Hsia Yong
    • Categories Basic Sciences Applications, Global Optimization Theory, Nonsmooth Optimization Tags , , ,

    This paper follows the recent discussion on the sparse solution recovery with quasi-norms Lq; q\in(0,1) when the sensing matrix possesses a Restricted Isometry Constant \delta_{2k} (RIC). Our key tool is an improvement on a version of “the converse of a generalized Cauchy-Schwarz inequality” extended to the setting of quasi-norm. We show that, if \delta_{2k}\le 1/2, … Read more

    On Stable Piecewise Linearization and Generalized Algorithmic Differentiation

  • Andreas Griewank
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Optimization Software Design Principles Tags , , , , , , , , , , , , ,

    It is shown how functions that are defined by evaluation programs involving the absolute value function (besides smooth elementals), can be approximated locally by piecewise-linear models in the style of algorithmic, or automatic, differentiation (AD). The model can be generated by a minor modification of standard AD tools and it is Lipschitz continuous with respect … Read more