Convex and Nonsmooth Optimization

Global convergence of a coderivative-based regularized Newton method with damping for nonsmooth optimization

  • Wei Ouyang
    • Categories Nonsmooth Optimization

    In this paper, we propose and analyze a globally convergent regularized Newton method with positive definite regularization for solving nonsmooth optimization problems. Our approach leverages the coderivative-generated second-order subdifferential (generalized Hessian) and replaces the identity matrix in traditional algorithms with a general positive-definite symmetric matrix to regularize the generalized Hessian. By appropriately selecting the regularization … Read more

    De-risking solutions to optimization problems

  • Daniel Bienstock
  • Blake Sisson
    • Categories Bilevel Optimization, Convex and Nonsmooth Optimization, Robust Optimization Tags

    We develop a cutting-plane methodology that adjusts solutions to optimization problems so as to reduce features that bring about exposure to risk, such as concentration of assets or resources. The methodology is agnostic to the representation of risk but has provably good attributes. Our procedure aims to reduce the appropriate risk metric without accruing a … Read more

    Neural Assortment Optimization

  • Zhen Yang
    • Categories Combinatorial Optimization, Nonsmooth Optimization, Yield Management

    Assortment optimization selects a subset of items to maximize expected revenue under a discrete choice model and is widely used in revenue management and online platforms. Its combinatorial nature creates a practical tension among generality, scalability, and provable guarantees: model-specific algorithms can be strong when their structural assumptions hold, but are hard to adapt across … Read more

    Automorphisms of hyperbolic polynomials

  • Michael Orlitzky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    The pair \( (p,e) \) is hyperbolic if \( p : \mathbb{R}^{n} \to \mathbb{R} \) is a homogeneous polynomial, if \( e \in \mathbb{R}^{n} \), if \( p(e) > 0 \), and if the roots of \( t \mapsto p(te – x) \) are real for all \( x \in \mathbb{R}^{n} \). In that case, … Read more

    Inexactly Smooth Performance Estimation and New Optimized Gradient Methods

  • Aaron Zoll
  • Benjamin Grimmer
    • Categories Convex Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

      We consider a general class of “inexactly smooth” convex functions, providing a universal model capturing as special cases $L$-smooth, $M$-Lipschitz, and H\”older smooth functions, and any combination thereof. Such functions possess a calculus closely following that of smooth functions. Our main results provide inexactly smooth functions with interpolation theorems that are necessary and sufficient … Read more

    Covering for Set-Valued Mappings in the Absence of Metric Regularity

  • Mario Jelitte
  • Alexey F. Izmailov
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    Covering properties build the foundation of stability and sensitivity analysis of solutions to a generalized equation and more specific optimization-related stationarity and equilibrium problems. It has been well-understood that metric regularity of the mapping defining the generalized equation is a key to furnish Lipschitzian stability of the solution of interest. With this work, we want … Read more

    Extrapolation-based Direct Search for Nonsmooth Stochastic Zeroth-Order Optimization

  • Anthony Palmieri
  • Francesco Rinaldi
  • Sara Shashaani
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , ,

    We propose and analyze a stochastic direct-search method for unconstrained zeroth-order minimization of locally Lipschitz, possibly nonsmooth, objectives. The method combines random polling directions with a stochastic extrapolating line search based on a sufficient-decrease test of order \(p\). Under conditional accuracy assumptions on the stochastic estimates, which can be verified for mean-zero finite-higher-moment oracle noise … Read more

    A Parameter-Free Restart Scheme with Only a Parallelizable $\log\log(1/\epsilon)$ Overhead

  • Yue Wu
  • Benjamin Grimmer
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    It is well-known that first-order methods can offer accelerated convergence rates in the presence of growth structures. Restarting schemes provide a general tool for such speed-ups. These schemes typically either require unrealistic problem knowledge, incur logarithmic overhead factors in oracle complexity, and/or have a nontrivial initial burn-in phase. We present a parameter-free approach for restarting … Read more

    Disjunctive Sum of Squares

  • Amir Ali Ahmadi
  • Sanjeeb Dash
  • Yixuan Hua
  • Bartolomeo Stellato
    • Categories Cone Programming, Convex Optimization, Semi-definite Programming Tags , , , , , , ,

    We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity with multiple algebraic identities which can be found in parallel. Our main result is a disjunctive Positivstellensatz … Read more