Santanu S. Dey

Cutting Plane Generation Through Sparse Principal Component Analysis

  • Santanu S. Dey
  • Aleksandr M. Kazachkov
  • Andrea Lodi
  • Gonzalo Muñoz
    • Categories Cutting Plane Approaches, Quadratic Programming Tags , , ,

    Quadratically-constrained quadratic programs (QCQPs) are optimization models whose remarkable expressiveness has made them a cornerstone of methodological research for nonconvex optimization problems. However, modern methods to solve a general QCQP fail to scale, encountering computational challenges even with just a few hundred variables. Specifically, a semidefinite programming (SDP) relaxation is typically employed, which provides strong … Read more

    Branch-and-Bound Solves Random Binary IPs in Polytime

  • Santanu S. Dey
  • Yatharth Dubey
  • Marco Molinaro
    • Categories 0-1 Programming, Branch and Cut Algorithms, Global Optimization Theory Tags ,

    Branch-and-bound is the workhorse of all state-of-the-art mixed integer linear programming (MILP) solvers. These implementations of branch-and-bound typically use variable branching, that is, the child nodes are obtained by fixing some variable to an integer value v in one node and to v + 1 in the other node. Even though modern MILP solvers are … Read more

    A K-Nearest Neighbor Heuristic for Real-Time DC Optimal Transmission Switching

  • Shabbir Ahmed
  • Santanu S. Dey
  • Jean-Paul Watson
  • Emma S. Johnson
    • Categories Applications - OR and Management Sciences Tags , , ,

    While transmission switching is known to reduce power generation costs, the difficulty of solving even DC optimal transmission switching (DCOTS) has prevented optimal transmission switching from becoming commonplace in real-time power systems operation. In this paper, we present a k-nearest neighbors (KNN) heuristic for DCOTS which relies on the insight that, for routine operations on … Read more

    Sparse PSD approximation of the PSD cone

  • Santanu S. Dey
  • Blekherman Grigoriy
  • Marco Molinaro
  • Shengding Sun
    • Categories Global Optimization Theory, Semi-definite Programming Tags ,

    While semidefinite programming (SDP) problems are polynomially solvable in theory, it is often difficult to solve large SDP instances in practice. One technique to address this issue is to relax the global positive-semidefiniteness (PSD) constraint and only enforce PSD-ness on smaller k times k principal submatrices — we call this the sparse SDP relaxation. Surprisingly, … Read more

    A study of rank-one sets with linear side constraints and application to the pooling problem

  • Santanu S. Dey
  • Burak Kocuk
  • Asteroide Santana
    • Categories Applications - Science and Engineering, Global Optimization

    We study sets defined as the intersection of a rank-1 constraint with different choices of linear side constraints. We identify different conditions on the linear side constraints, under which the convex hull of the rank-1 set is polyhedral or second-order cone representable. In all these cases, we also show that a linear objective can be … Read more

    The convex hull of a quadratic constraint over a polytope

  • Santanu S. Dey
  • Asteroide Santana
    • Categories Global Optimization Theory, Quadratic Programming, Second-Order Cone Programming

    A quadratically constrained quadratic program (QCQP) is an optimization problem in which the objective function is a quadratic function and the feasible region is defined by quadratic constraints. Solving non-convex QCQP to global optimality is a well-known NP-hard problem and a traditional approach is to use convex relaxations and branch-and-bound algorithms. This paper makes a … Read more

    A convex integer programming approach for optimal sparse PCA

  • Santanu S. Dey
  • Rahul Mazumder
  • Guanyi Wang
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming

    Principal component analysis (PCA) is one of the most widely used dimensionality reduction tools in scientific data analysis. The PCA direction, given by the leading eigenvector of a covariance matrix, is a linear combination of all features with nonzero loadings—this impedes interpretability. Sparse principal component analysis (SPCA) is a framework that enhances interpretability by incorporating … Read more

    Subset selection in sparse matrices

  • Alberto Del Pia
  • Santanu S. Dey
  • Robert Weismantel
    • Categories Global Optimization Theory, Nonlinear Systems and Least-Squares Tags , , ,

    In subset selection we search for the best linear predictor that involves a small subset of variables. From a computational complexity viewpoint, subset selection is NP-hard and few classes are known to be solvable in polynomial time. Using mainly tools from discrete geometry, we show that some sparsity conditions on the original data matrix allow … Read more

    New SOCP relaxation and branching rule for bipartite bilinear programs

  • Santanu S. Dey
  • Asteroide Santana
  • Yang Wang
    • Categories Global Optimization Applications, Global Optimization Theory

    A bipartite bilinear program (BBP) is a quadratically constrained quadratic optimization problem where the variables can be partitioned into two sets such that fixing the variables in any one of the sets results in a linear program. We propose a new second order cone representable (SOCP) relaxation for BBP, which we show is stronger than … Read more

    Sparse principal component analysis and its l1-relaxation

  • Santanu S. Dey
  • Rahul Mazumder
  • Marco Molinaro
  • Guanyi Wang
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining

    Principal component analysis (PCA) is one of the most widely used dimensionality reduction methods in scientific data analysis. In many applications, for additional interpretability, it is desirable for the factor loadings to be sparse, that is, we solve PCA with an additional cardinality (l0) constraint. The resulting optimization problem is called the sparse principal component … Read more