Nonsmooth Optimization

Generalized Conjugate Gradient Methods for $\ell_1$ Regularized Convex Quadratic Programming with Finite Convergence

  • Xiaojun Chen
  • Zhaosong Lu
    • Categories Convex Optimization, Nonsmooth Optimization, Quadratic Programming Tags , , , ,

    The conjugate gradient (CG) method is an efficient iterative method for solving large-scale strongly convex quadratic programming (QP). In this paper we propose some generalized CG (GCG) methods for solving the $\ell_1$-regularized (possibly not strongly) convex QP that terminate at an optimal solution in a finite number of iterations. At each iteration, our methods first … Read more

    Sparse Recovery via Partial Regularization: Models, Theory and Algorithms

  • Xiaorui Li
  • Zhaosong Lu
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Statistics Tags , , , , , , ,

    In the context of sparse recovery, it is known that most of existing regularizers such as $\ell_1$ suffer from some bias incurred by some leading entries (in magnitude) of the associated vector. To neutralize this bias, we propose a class of models with partial regularizers for recovering a sparse solution of a linear system. We … Read more

    First and second order optimality conditions for piecewise smooth objective functions

  • Andreas Griewank
  • Andrea Walther
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , , , , ,

    Any piecewise smooth function that is specified by an evaluation procedures involving smooth elemental functions and piecewise linear functions like min and max can be represented in the so-called abs-normal form. By an extension of algorithmic, or automatic differentiation, one can then compute certain first and second order derivative vectors and matrices that represent a … Read more

    Manifold Sampling for L1 Nonconvex Optimization

  • Jeffrey Larson
  • Matt Menickelly
  • Stefan M. Wild
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , ,

    We present a new algorithm, called manifold sampling, for the unconstrained minimization of a nonsmooth composite function $h\circ F$ when $h$ has known structure. In particular, by classifying points in the domain of the nonsmooth function $h$ into manifolds, we adapt search directions within a trust-region framework based on knowledge of manifolds intersecting the current … Read more

    On Cournot-Nash-Walras equilibria and their computation

  • Michal Cervinka
  • Michael C. Ferris
  • Jiri V. Outrata
    • Categories Nonsmooth Optimization Tags , , , , ,

    This paper considers a model of Cournot-Nash-Walras (CNW) equilibrium where the Cournot-Nash concept is used to capture equilibrium of an oligopolistic market with non-cooperative players/ rms who share a certain amount of a so-called rare resource needed for their production, and the Walras equilibrium determines the price of that rare resource. We prove the existence of … Read more

    Quantitative recovery conditions for tree-based compressed sensing

  • Coralia Cartis
  • Andrew Thompson
    • Categories Applications - Science and Engineering, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    As shown in [9, 1], signals whose wavelet coefficients exhibit a rooted tree structure can be recovered — using specially-adapted compressed sensing algorithms — from just $n=\mathcal{O}(k)$ measurements, where $k$ is the sparsity of the signal. Motivated by these results, we introduce a simplified proportional-dimensional asymptotic framework which enables the quantitative evaluation of recovery guarantees … Read more

    New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure

  • Robert M. Freund
  • Haihao Lu
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    Motivated by recent work of Renegar, we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem f^* = \min_{x \in Q} f(x), where we presume knowledge of a strict lower bound f_slb < f^*. [Indeed, f_slb is naturally ... Read more

    Variational Analysis and Applications to Group Dynamics

  • Antoine Soubeyran
  • Bao Q. Truong
    • Categories Applications - OR and Management Sciences, Multi-Criteria Optimization, Nonsmooth Optimization Tags , , , , ,

    In this paper, we establish a new version of Ekeland’s variational principle in a new setting of cone pseudo-quasimetric spaces. In constrast to metric spaces, we do not require that each forward Cauchy sequence is forward convergent and that each forward convergent sequence has the unique forward limit. The motivation of this paper comes from … Read more

    Local monotonicity and full stability for parametric variational systems

  • Boris S. Mordukhovich
  • Tran Nghia
    • Categories Nonsmooth Optimization Tags , ,

    The paper introduces and characterizes new notions of Lipschitzian and H\”olderian full stability of solutions to general parametric variational systems described via partial subdifferential of prox-regular functions acting in finite-dimensional and Hilbert spaces. These notions, postulated certain quantitative properties of single-valued localizations of solution maps, are closely related to local strong maximal monotonicity of associated … Read more

    On the Convergence of Multi-Block Alternating Direction Method of Multipliers and Block Coordinate Descent Method

  • Caihua Chen
  • Xin Liu
  • Yinyu Ye
  • Min Li
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , , , ,

    The paper answers several open questions of the alternating direction method of multipliers (ADMM) and the block coordinate descent (BCD) method that are now wildly used to solve large scale convex optimization problems in many fields. For ADMM, it is still lack of theoretical understanding of the algorithm when the objective function is not separable … Read more