A semidefinite feasibility problem is a convex optimization problem, over a subset of the positive semidefinite cone, having no objective function.  Constraining rank of a feasible solution can be thought of as introducing a linear objective function whose normal opposes the direction of search.  If one knows the proper search direction, then a solution of desired rank can be found.

"In any SDP feasibility problem, an SDP feasible solution with the lowest rank must be an extreme point of the feasible set.  Thus, there must exist a linear objective function such that this lowest-rank feasible solution uniquely optimizes it."

In Chapter 4.4, we show how to determine what linear objective function will replace a rank constraint in a semidefinite program.  Finding the normal representing that linear function turns out to be a convex optimization problem over a Fantope.  Fantopes are introduced in Chapter 2.  Some semidefinite problems having a rank constraint can thereby be formulated as convex optimization problems.

Read more...