What algorithm does CVX implement when solving the “feasibility problem” for SDPs? That is, I have the feasible set for an SDP, and CVX produces a feasible solution. Is there a good reference??
On a deeper level; my (preliminary) understanding is that, unlike for LPs and the simplex, the “presolving step” of finding a feasible solution for an SDP is not an SDP. This is all the more confusing to me because all the hype about semi-algebraic optimization arises from the observation that nonnegativity certificates can be phrased as SDP feasibility problems, for which we have “fast” algorithms…yet most algorithms for SDP problems start by assuming a feasible solution (at least a feasible psd matrix as part of the initial solution…). Then one wonders: what are the good references detailing algorithms for finding a feasible point (psd matrix) given PSD program constraints?
That’s my point: submitting the problem with a 0 objective is just telling the program: once you found an initial solution (i.e., once you’ve solved the “feasibility problem”), stop, and report that solution.
Now, EITHER there is a way to phrase the feasibility problem as an SDP with an obvious starting value (which I don’t think is the case). In which case the question would be: what is the formulation of the SDP?
OR, the algorithm for finding the initial solution (i.e., for solving the “feasibility problem”) is different from the one you use to solve the SDP once you have an initial solution. In that case, the question (the right one, I think) is: what is the algorithm used to find a feasible solution?
Is that algorithm different if you just want a feasible solution, not necessarily a “good” starting value for the optimization problem??
Well, at this point, you’re asking questions that are beyond the scope of this forum. CVX doesn’t solve feasibility problems any differently than optimization problems. It just sets the objective to zero, and passes the resulting model down to the solvers in an otherwise identical fashion, and those solvers don’t do anything differently either. Whether or not that is a good idea in theory is beyond the scope of this forum.