Convex and Nonsmooth Optimization

Solving large scale polynomial convex problems on \ell_1/nuclear norm balls by randomized first-order algorithms

  • Aharon Ben-Tal
  • Arkadi Nemirovski
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformulation of the problem of interest and solving the resulting problem by a fast First Order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when … 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

    A Globally Convergent Primal-Dual Active-Set Framework for Large-Scale Convex Quadratic Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Zheng Han
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , ,

    We present a primal-dual active-set framework for solving large-scale convex quadratic optimization problems (QPs). In contrast to classical active-set methods, our framework allows for multiple simultaneous changes in the active- set estimate, which often leads to rapid identification of the optimal active-set regardless of the initial estimate. The iterates of our framework are the active-set … Read more

    Metric regularity of composition set-valued mappings: metric setting and coderivative conditions

  • Marius Durea
  • Van Ngai Huynh
  • Huu Tron Nguyen
  • Radu Strugariu
    • Categories Convex and Nonsmooth Optimization

    The paper concerns a new method to obtain a direct proof of the openness at linear rate/metric regularity of composite set-valued maps on metric spaces by the unification and refinement of several methods developed somehow separately in several works of the authors. In fact, this work is a synthesis and a precise specialization to a … 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

    The Spectral Bundle Method with Second-Order Information

  • Christoph Helmberg
  • Michael L. Overton
  • Franz Rendl
    • Categories Convex Optimization, Semi-definite Programming Tags ,

    The spectral bundle method was introduced by Helmberg and Rendl to solve a class of eigenvalue optimization problems that is equivalent to the class of semidefinite programs with the constant trace property. We investigate the feasibility and effectiveness of including full or partial second-order information in the spectral bundle method, building on work of Overton … Read more

    Rate analysis of inexact dual first order methods: Application to distributed MPC for network systems

  • Ion Necoara
  • Valentin Nedelcu
    • Categories Convex Optimization, Distributed Control, Parallel Algorithms Tags , , , , ,

    In this paper we propose two dual decomposition methods based on inexact dual gradient information for solving large-scale smooth convex optimization problems. The complicating constraints are moved into the cost using the Lagrange multipliers. The dual problem is solved by inexact first order methods based on approximate gradients and we prove sublinear rate of convergence … 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