Optimization in Data Science

Retrospective Approximation Sequential Quadratic Programming for Stochastic Optimization with General Deterministic Nonlinear Constraints

  • Shagun Gupta
  • Raghu Bollapragada
  • Albert S. Berahas
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization in Data Science Tags , , , ,

    In this paper, we propose a framework based on the Retrospective Approximation (RA) paradigm to solve optimization problems with a stochastic objective function and general nonlinear deterministic constraints. This framework sequentially constructs increasingly accurate approximations of the true problems which are solved to a specified accuracy via a deterministic solver, thereby decoupling the uncertainty from … Read more

    Responsible Machine Learning via Mixed-Integer Optimization

  • Nathan Justin
  • Qingshi Sun
  • Andrés Gómez
  • Phebe Vayanos
    • Categories Applications - OR and Management Sciences, Integer Programming, Optimization in Data Science Tags , , , , , ,

    In the last few decades, Machine Learning (ML) has achieved significant success across domains ranging from healthcare, sustainability, and the social sciences, to criminal justice and finance. But its deployment in increasingly sophisticated, critical, and sensitive areas affecting individuals, the groups they belong to, and society as a whole raises critical concerns around fairness, transparency … Read more

    Fast Stochastic Second-Order Adagrad for Nonconvex Bound-Constrained Optimization

  • Stefania Bellavia
  • Serge Gratton
  • Benedetta Morini
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Data Science Algorithms, Nonlinear Optimization Tags , , , , , ,

    ADAGB2, a generalization of the Adagrad algorithm for stochastic optimization is introduced, which is also applicable to bound-constrained problems and capable of using second-order information when available. It is shown that, given  delta in (0,1) and epsilon in (0,1], the ADAGB2 algorithm needs at most O(epsilon^{-2}) iterations to ensure an epsilon-approximate first-order critical point of … Read more

    Deterministic global optimization with trained neural networks: Is the envelope of single neurons worth it?

  • Clara Witte
  • Jannik Lüthje
  • Victor Schulte
  • Alexander Mitsos
  • Dominik Bongartz
    • Categories Global Optimization, Global Optimization Applications, Optimization in Data Science Tags , , ,

    Optimization problems containing trained neural networks remain challenging due to their nonconvexity. Deterministic global optimization relies on relaxations which should be tight, quickly convergent, and cheap to evaluate. While envelopes of common activation functions have been established for several years, the envelope of an entire neuron had not. Recently, Carrasco and Mu\~{n}oz (arXiv.2410.23362, 2024) proposed … Read more

    Rank-one convexification for convex quadratic optimization with step function penalties

  • Andrés Gómez
  • Shaoning Han
    • Categories (Mixed) Integer Nonlinear Programming, Data Science Applications, Semi-definite Programming Tags ,

    We investigate convexification in convex quadratic optimization with step function penalties. Such problems can be cast as mixed-integer quadratic optimization problems, where binary variables are used to encode the non-convex step function. First, we derive the convex hull for the epigraph of a quadratic function defined by a rank-one matrix. Using this rank-one convexification, we … Read more

    A Foundational Perspective for Partitional Clustering on Networks

  • Derya Ipek Eroglu
  • Cem Iyigun
    • Categories Data Science Theory, Data-Mining, Optimization in Data Science Tags , , ,

    This study presents a theoretical analysis of partitional clustering on networks. Different versions of the problem are studied considering different assignment schemes (hard and soft) and different objective functions. Cluster centers are not restricted to only the set of nodes, it is assumed that centers can also be at the edges of the network. Four … Read more

    Mathematical programs with complementarity constraints and application to hyperparameter tuning for nonlinear support vector machines

  • Samuel Ward
  • Alain Zemkoho
  • Selin Damla Ahipasaoglu
    • Categories Bilevel Optimization, Complementarity and Variational Inequalities, Optimization in Data Science Tags , , , , ,

    We consider the Mathematical Program with Complementarity Constraints (MPCC). One of the main challenges in solving this problem is the systematic failure of standard Constraint Qualifications (CQs). Carefully accounting for the combinatorial nature of the complementarity constraints, tractable versions of the Mangasarian Fromovitz Constraint Qualification (MFCQ) have been designed and widely studied in the literature. … Read more

    Tight Semidefinite Relaxations for Verifying Robustness of Neural Networks

  • Godai Azuma
  • Sunyoung Kim
  • Makoto Yamashita
    • Categories Optimization in Data Science, Quadratic Programming, Semi-definite Programming Tags , , , ,

    For verifying the safety of neural networks (NNs), Fazlyab et al. (2019) introduced a semidefinite programming (SDP) approach called DeepSDP. This formulation can be viewed as the dual of the SDP relaxation for a problem formulated as a quadratically constrained quadratic program (QCQP). While SDP relaxations of QCQPs generally provide approximate solutions with some gaps, … Read more

    An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function

  • Nicolas Gillis
  • Margherita Porcelli
  • Giovanni Seraghiti
    • Categories Data Science Algorithms, Optimization in Data Science, Other Topics Tags , ,

    Nonlinear matrix decomposition (NMD) with the ReLU function, denoted ReLU-NMD, is the following problem: given a sparse, nonnegative matrix \(X\) and a factorization rank \(r\), identify a rank-\(r\) matrix \(\Theta\) such that \(X\approx \max(0,\Theta)\). This decomposition finds application in data compression, matrix completion with entries missing not at random, and manifold learning. The standard ReLU-NMD … Read more

    A Rank-One-Update Method for the Training of Support Vector Machines

  • Florian Jarre
    • Categories Bound-constrained Optimization, Convex Optimization, Data Science Algorithms Tags , ,

    This paper considers convex quadratic programs associated with the training of support vector machines (SVM). Exploiting the special structure of the SVM problem a new type of active set method with long cycles and stable rank-one-updates is proposed and tested (CMU: cycling method with updates). The structure of the problem allows for a repeated simple … Read more