Weakly Infeasible Semidefinite Program Algorithm

An algorithm for generating any weakly infeasible semidefinite program and bad projection of the semidefinite cone based on the paper.

Background

A semidefinite program (SDP) is a class of optimization problem of the form

for which is the standard Euclidean inner product between real symmetric matrices, says that is positive semidefinite and

We will refer to the SDP of the above form as the primal problem . If is a solution to the above linear system, then we note that the feasible set of this problem may be expressed as the intersection of an affine space

with the semidefinite cone . Thus, we say the problem is infeasible if

It is strongly infeasible if the distance between these sets is positive, that is...

Otherwise, if the problem is infeasible but not strongly infeasible we say that the problem is weakly infeasible.

A related notion is the idea of a bad projection of the semidefinite cone. We say that is a bad projection of the semidefinite cone if it maps the semidefinite cone to a non-closed set. It is easy to check that

Understanding when a linear operator is a bad projection is important in the theory and solution methods for conic linear systems. In particular, it is well known that the closure of a cone under a linear operator is a sufficient condition to guarantee the application of Farka's Lemma, but one may ask, "how does weak infeasibility appear in theory and application of SDPs?"

Classically, weakly infeasible SDPs were simply viewed as instances in which was an asymptote of the semidefinite cone; however, in modern optimization, these instances appear...

• as hard SDPs, identified as feasible even by state-of-the-art solvers such as Mosek or SDPA-GMP. (Liu, Pataki 2017)
• as infeasible and ill-posed SDPs with no convergence guarantees on classifying feasibility with IPMs based around standard condition metrics. (Pena, Renegar 2000)
• as bad projections of the semidefinite cone with algebraic characterizations of related bad subspaces. (Jiang, Sturmfels 2020)
• as instances in the Lasserre hierarchy of polynomial optimization for certain classes of polynomial optimization problems. (Henrion, Lasserre 2005)
• as SDPs in which facial reduction certificates are necessary to certify infeasibility. (Lourenco, Muramatsu, Tsuchiya 2015)
• as difficult to generate test cases for SDP solvers. (Waki 2011)

The code base presented here gives us an algorithm for solving the problem presented in the last of these bullets in its entirety by producing suitable matrices and right hand side vector .

Usage and Examples

We will use the vocabulary of the paper above when discussing the code. The first step is to define the structure of the regularized facial reduction sequence for certifying the problem's infeasibility. We do this by defining the block sizes of our partition.

P = CreateConsecPartition([2,1,3,2,1,3])

Similarly, we define the structure of the facial reduction sequence used to certify our problem's not-strong infeasibility by specifying the number of partitions.

Q = CreateCertificateStructure(5, P)

Execute the main algorithm to generate a weakly infeasible SDP with certificate structures given above.

[A, b, X] = CreateWeakSysCertSDE(P, Q, [-2,2], [1,1])

Append optional additional constraints to the problem.

[A, b] = ExtendWeakSDE(A, b, X, 2)

Optionally, we can also apply congruence transforms and rotations of our problem to make a messy instance.

# Rotate elements of A and X arbitrarily
[T,Ti] = RotateBases(A, X, 100)

# Rotate the entire sequence A using row operations
[A, b, F] = RotateSequence(A, b)

Prior to rotation, the steps above produce the instance defined by the two sequences.