Continuous exact relaxation and alternating proximal gradient algorithm for partial sparse and partial group sparse optimization problems

  • Peng Dingtao
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags

    In this paper, we consider a partial sparse and partial group sparse optimization problem, where the loss function is a continuously differentiable function (possibly nonconvex), and the penalty term consists of two parts associated with sparsity and group sparsity. The first part is the $\ell_0$ norm of ${\bf x}$, the second part is the $\ell_{2,0}$ … Read more

    Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms

  • Jiaxiang Li
  • Krishnakumar Balasubramanian
  • Shiqian Ma
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Stochastic Programming

    We present Zeroth-order Riemannian Averaging Stochastic Approximation (\texttt{Zo-RASA}) algorithms for stochastic optimization on Riemannian manifolds. We show that \texttt{Zo-RASA} achieves optimal sample complexities for generating $\epsilon$-approximation first-order stationary solutions using only one-sample or constant-order batches in each iteration. Our approach employs Riemannian moving-average stochastic gradient estimators, and a novel Riemannian-Lyapunov analysis technique for convergence analysis. … Read more

    On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity Constraints

  • Immanuel M. Bomze
  • Bo Peng
  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Semi-definite Programming Tags , , , ,

    Standard quadratic optimization problems (StQPs) provide a versatile modelling tool in various applications. In this paper, we consider StQPs with a hard sparsity constraint, referred to as sparse StQPs. We focus on various tractable convex relaxations of sparse StQPs arising from a mixed-binary quadratic formulation, namely, the linear optimization relaxation given by the reformulation-linearization technique, … Read more

    Neur2RO: Neural Two-Stage Robust Optimization

  • Justin Dumouchelle
  • Esther Julien
  • Jannis Kurtz
  • Elias B. Khalil
    • Categories Robust Optimization Tags , ,

    Robust optimization provides a mathematical framework for modeling and solving decision-making problems under worst-case uncertainty. This work addresses two-stage robust optimization (2RO) problems (also called adjustable robust optimization), wherein first-stage and second-stage decisions are made before and after uncertainty is realized, respectively. This results in a nested min-max-min optimization problem which is extremely challenging computationally, … Read more

    Strengthened MIP Formulations for the Liver Region Redesign Models of Akshat et al.

  • Aysenur Karagoz
  • Ruofeng Liu
  • Hamidreza Validi
  • Andrew J. Schaefer
    • Categories Integer Programming

    Liver transplantation has been a critical issue in the U.S. healthcare system for decades, and the region redesign aims to ameliorate this issue. This paper revisits two mixed integer programming (MIP) formulations of the liver region redesign problem proposed by Akshat et al. We study their first formulation considering two different modeling approaches: one compact … Read more

    Goldstein Stationarity in Lipschitz Constrained Optimization

  • Benjamin Grimmer
  • Zhichao Jia
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

    We prove the first convergence guarantees for a subgradient method minimizing a generic Lipschitz function over generic Lipschitz inequality constraints. No smoothness or convexity (or weak convexity) assumptions are made. Instead, we utilize a sequence of recent advances in Lipschitz unconstrained minimization, which showed convergence rates of $O(1/\delta\epsilon^3)$ towards reaching a “Goldstein” stationary point, that … Read more

    Efficient Approximation Quality Computation for Sandwiching Algorithms for Convex Multicriteria Optimization

  • Ina Lammel
  • Karl-Heinz Küfer
  • Philipp Süss
    • Categories Convex Optimization, Multi-Criteria Optimization Tags , , ,

    Computing the approximation quality is a crucial step in every iteration of Sandwiching algorithms (also called Benson-type algorithms) used for the approximation of convex Pareto fronts, sets or functions. Two quality indicators often used in these algorithms are polyhedral gauge and epsilon indicator. In this article, we develop an algorithm to compute the polyhedral gauge … Read more

    Analysis of a Class of Minimization Problems Lacking Lower Semicontinuity

  • Shaoning Han
  • Ying Cui
  • Jong-Shi Pang
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Optimization in Data Science Tags , , ,

    The minimization of non-lower semicontinuous functions is a difficult topic that has been minimally studied. Among such functions is a Heaviside composite function that is the composition of a Heaviside function with a possibly nonsmooth multivariate function. Unifying a statistical estimation problem with hierarchical selection of variables and a sample average approximation of composite chance … Read more

    On achieving strong necessary second-order properties in nonlinear programming

  • Gabriel Haeser
  • Andreas Fischer
  • Thiago P. Silveira
    • Categories Nonlinear Optimization

    Second-order necessary or sufficient optimality conditions for nonlinear programming are usually defined by means of the positive (semi-)definiteness of a quadratic form, or a maximum of quadratic forms, over the critical cone. However, algorithms for finding such second-order stationary points are currently unknown. Typically, an algorithm with a second-order property approximates a primal-dual point such … Read more

    Full-low evaluation methods for bound and linearly constrained derivative-free optimization

  • Clément W. Royer
  • Oumaima Sohab
  • Luis Nunes Vicente
    • Categories Bound-constrained Optimization, Nonlinear Optimization Tags , , ,

    Derivative-free optimization (DFO) consists in finding the best value of an objective function without relying on derivatives. To tackle such problems, one may build approximate derivatives, using for instance finite-difference estimates. One may also design algorithmic strategies that perform space exploration and seek improvement over the current point. The first type of strategy often provides … Read more