Convex and Nonsmooth Optimization

A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints

  • Ion Necoara
  • Andrei Patrascu
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Network Optimization Tags , , , ,

    In this paper we present a variant of random coordinate descent method for solving linearly constrained convex optimization problems with composite objective function. If the smooth part has Lipschitz continuous gradient, then the method terminates with an ϵ-optimal solution in O(N2/ϵ) iterations, where N is the number of blocks. For the class of problems with … Read more

    Hardness and Approximation Results for hBcBall Constrained Homogeneous Polynomial Optimization Problems

  • Ke Hou
  • Anthony Man-Cho So
    • Categories Constrained Nonlinear Optimization, Convex Optimization

    In this paper, we establish hardness and approximation results for various $L_p$-ball constrained homogeneous polynomial optimization problems, where $p \in [2,\infty]$. Specifically, we prove that for any given $d \ge 3$ and $p \in [2,\infty]$, both the problem of optimizing a degree-$d$ homogeneous polynomial over the $L_p$-ball and the problem of optimizing a degree-$d$ multilinear … 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

    Minimal Representation of Insurance Prices

  • Alois Pichler
  • Alexander Shapiro
    • Categories Convex Optimization, Finance and Economics, Statistics Tags , , ,

    This paper addresses law invariant coherent risk measures and their Kusuoka representations. By elaborating the existence of a minimal representation we show that every Kusuoka representation can be reduced to its minimal representation. Uniqueness — in a sense specified in the paper — of the risk measure’s Kusuoka representation is derived from this initial result. … Read more

    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