It's common for convex optimization procedures to require a bounded region containing an optimal solution, either as input, like the initial ellipsoid of the ellipsoid method, or for run time bounds, e.g., analysis of the popular AdaGrad algorithm and its many relatives.

In the case of a linear program with feasible region $R = \{ x \mid Ax \leq b \}$, we can simply bound the extreme points of $R$ in terms of the coefficients of $A$ and $b$ (see e.g. Thm. 10.6 here). According to pg. 48 #3 of this paper, similar bounds do not exist for semidefinite programs.

I'd like to know if there is any way to find such a bound for a generic SDP that is less expensive than solving it directly. If not, are there any large classes of SDPs for which this is possible? (e.g. it's easy to find bounds for the standard MAX-CUT relaxation or, more generically, SDPs with feasible regions of the form $\{ X \mid {\rm diag}(X) = b, X \geq 0\}$, by looking at the spectrum of the coefficient matrix)



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.