BTW, you can make the Step 2 objective convex by adding a large quadratic term to each dimension. I think this makes it a Quadratically Constrained Quadratic Program.
There are some specialized solvers for QCQP, it would be neat if they were easily accessible from Mathematica.
It seems arbitrary polynomial minimization problem can be reformulated as sparse QCQP -- [Rank-2 Matrix Solution for Semidefinite Relaxations of Arbitrary
Polynomial Optimization Problems](https://lavaei.ieor.berkeley.edu/CDC_Polynomial_2014.pdf)
