Title: Echelon Forms and Reformulations of Pathological Semidefinite Programs

Abstract: This thesis seeks to better understand when and why various well-known pathologies arise in semidefinite programs (SDP). The first part of this thesis is concerned with the pathology of weak infeasibility. Unlike in linear programs, Farka’s lemma may fail to identify infeasible SDPs. This pathology occurs precisely when an SDP has no feasible solution, but it has nearly feasible solutions that approximate the constraint set to arbitrary precision. These SDPs are ill-posed and numerically often unsolvable. They are also closely related to “bad” linear projections that map the cone of positive semidefinite matrices to a nonclosed set. We describe a simple echelon form of weakly infeasible SDPs with the following properties: it is obtained by elementary row operations and congruence transformations; it makes weak infeasibility evident; and using it we can construct any weakly infeasible SDP or bad linear projection by an elementary combinatorial algorithm. We also prove that some SDPs in the literature are in our echelon form, for example, the SDP from the sum-of-squares relaxation of minimizing the famous Motzkin polynomial. The second part of this thesis deals with the pathology of exponentially sized solutions in SDPs. As a classic example of Khachiyan shows, some SDPs have solutions whose size – the number of bits necessary to describe it – is exponential in the size of the input. Although the common consent seems that large solutions in SDPs are rare, we prove that they are actually quite common: a linear change of variables transforms every strictly feasible SDP into a Khachiyan type SDP, in which the leading variables are large. As to how large, that depends on the singularity degree of a dual problem. We further show some SDPs in which large solutions appear naturally, without any change of variables. Along the way, we draw connections to continued fractions, Fourier-Motzkin elimination, and give positive progress to answering the long-standing open question: can we decide feasiblility of SDPs in polynomial time?

Share this Event