6 citations · 9 across the 8 of their papers we have counts for
8 papers
Exact algorithms for quadratic optimization over roots of unity
Ahmad Al-Sulami, Hamza Fawzi, Shengding Sun
We consider the problem of optimizing a multivariate quadratic function where each decision variable is constrained to be a complex 'th root of unity. Such problems have applica…
Matrix Fejér-Riesz type theorem for a union of an interval and a point
Shengding Sun, Aljaž Zalar
The matrix Fejér-Riesz theorem characterizes positive semidefinite matrix polynomials on the real line. In the previous work of the second-named author this was extended to the cha…
On the strength of Burer's lifted convex relaxation to quadratic programming with ball constraints
Fatma Kılınç-Karzan, Shengding Sun
We study quadratic programs with ball constraints, and the strength of a lifted convex relaxation for it recently proposed by Burer (2024). Burer shows this relaxation is exact…
Aggregations of quadratic inequalities and hidden hyperplane convexity
Grigoriy Blekherman, Santanu S. Dey, Shengding Sun
We study properties of the convex hull of a set described by quadratic inequalities. A simple way of generating inequalities valid on is to take a nonnegative linear combin…
Linear Principal Minor Polynomials: Hyperbolic Determinantal Inequalities and Spectral Containment
Grigoriy Blekherman, Mario Kummer, Raman Sanyal +2
A linear principal minor polynomial or lpm polynomial is a linear combination of principal minors of a symmetric matrix. By restricting to the diagonal, lpm polynomials are in bije…
Hardness and Approximation of Submodular Minimum Linear Ordering Problems
Majid Farhadi, Swati Gupta, Shengding Sun +2
The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to mi…
Hyperbolic Relaxation of -Locally Positive Semidefinite Matrices
Grigoriy Blekherman, Santanu S. Dey, Kevin Shu +1
A successful computational approach for solving large-scale positive semidefinite (PSD) programs is to enforce PSD-ness on only a collection of submatrices. For our study, we let $…
Sparse PSD approximation of the PSD cone
Grigoriy Blekherman, Santanu S. Dey, Marco Molinaro +1
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 iss…