We study polynomials upto degree six arising in nonconvex projection problems. When finding nearest points onto certain sets of bilinear constraints, we discover these problems have hidden convexity. We establish this fact using SDP duality and exploit it further to develop convex relaxations to solve certain bilinear combinatorial optimization problems.

The singularity degree plays a crucial role in understanding linear and semidefinite programming, providing a theoretical framework for analyzing these problems. It is defined as the minimum number of facial reduction (FR) steps needed to reach strict feasibility for a convex set. On the other hand, the maximum singularity degree (MSD) is the maximum number of steps required. Recent progress in the applications of MSD has motivated us to explore its fundamental properties.

For semidefinite programming, we establish a necessary condition for an FR sequence to be the longest. Additionally, we propose an upper bound for MSD, which can be computed more easily. By leveraging these findings, we prove that computing MSD is NP-hard. This complexity result complements the existing algorithms for computing the singularity degree found in the literature. For linear programming, we provide a characterization for the longest FR sequences, which also serves as a polynomial-time algorithm for constructing such a sequence. In addition, we introduce two operations that ensure the longest FR sequences remain the longest. Lastly, we prove that MSD is equivalent to a novel parameter called the implicit problem singularity.

Ramana’s dual is a fundamental result in semidefinite programming. In contrast to the usual SDP dual, 1) it requires no Slater like constraint qualification, 2) it always attains its optimal value, and 3) has no duality gap with the primal. It is mainly of interest due to its complexity implications, which -- 25 years after its publication – are still the best known results on the complexity of SDP.

The correctness proofs of Ramana’s dual tend to be somewhat technical. A dual with similar properties, but based on arguments from algebraic geometry has also been proposed. Here we give a nontechnical and very short proof, that is based almost purely on elementary linear algebra. In addition we prove a result that appears to be new: we completely characterize the set of feasible solutions of Ramana’s dual -- a result that may be useful for computational purposes.

This paper considers the NP-hard protein side-chain positioning problem, SCP,
an important final task of protein structure prediction as a
integer quadratic program, IQP. We derive its doubly nonnegative, DNN,
(convex) relaxation. Strict feasibility fails for this relaxation and
we apply facial reduction, FR as a natural splitting of variables.
This allows for a variation of the
application of Peaceman-Rachford splitting method, PRSM.
The resulting relaxation and rounding procedures provide strong approximate
solutions. Empirical evidence shows that almost all our instances of this
NP-hard SCP problem, taken from the Protein Data Bank, are solved to provable
optimality. We provide further applications to the Wasserstein
Barycenter problem.