Polynomial-in-SOSPolynomialSet to VectorAffineFunction-in-PSD bridge

[Zinoex]

Right now, the translation process is as follows: given a polynomial p(x), the constraint p(x)-in-SOS is translated to a constraint p(x) - q(x) = 0 where q(x) = M(x)^T Q M(x), M(x) are Gram basis vectors and Q is a PSD matrix, and p(x) - q(x) = 0 is then further reduced to each coefficient to equated to zero (where all the linear constraints come from).

A better approach that avoids constructing variables for monomials that are not present in p(x) is to directly perform a translation of p(x)-in-SOS to (Az + b)-in-PSD where z is the decision variable. It will require that the monomials corresponding to A and b are stored, but it will also avoid constructing Q, thus being sparse.

[Zinoex]

I thought that adding the affine conic constraint of VectorAffineFunction-in-PSD would be more efficient due to sparsity of the Gram matrix. And it is correct that sparsity can be pushed directly down into Mosek. However, Mosek will internally construct an PSD variable, scalarize it, and equate the entries of the VectorAffineFunction with the scalarize variables. The only potential is if Mosek only constructs the PSD variable in a sparse format.

[Zinoex]

I am closing this for good. You cannot rewrite Polynomial-in-SOS as VectorAffineFunction-in-PSD because multiple basis pairs in the Gram basis may generate the same polynomial (thus requiring an equality constraint rather than VectorAffineFunction-in-PSD). Pablo Parrilo notes the same on page 22 of this Sum of Squares Optimization in the Analysis and Synthesis of Control Systems slides.