# Benefits of SDP over other methods

I have general question regarding the benefits of semi-definite programming.

Assuming I have a non-convex program which can by relaxed to an SDP. Why should I use the SDP formulation (and the corresponding SDP solvers) over a standard convex programming formulation (and its corresponding solvers) when I adopt the same relaxation?

To the best of my knowledge, many SDP solvers and many standard solvers for convex programs use interior point methods. Where are the advantages of the one over the other?

Edit (sorry for being so imprecise):

What I meant is the (corner ?) case in which I can relax a non-convex problem to an SDP (e.g. having actually a non-affine equality constraint and using Schur's complement to make it a SDP-conform inequality constraint) and then using an SDP solver like Sedumi. Compared to the case when applying the same/equivalent relaxation to the non-convex problem but then using standard interior points methods directly (e.g. using MATLABs fmincon).

Meaning in the example above, I assume that the objective is convex but there is non-convex constraint.

Edit 2

Assuming e.g. that I have a convex objective and and some convex constraint, and also one non-convex constraint of the form $\delta = d^2$ where $\delta$ is some slack variable. Then I can obtain a SDP-conform relaxation using Schur complement via

$$S = \begin{bmatrix} 1 & d \\ d & \delta \end{bmatrix} \succeq 0$$

Consequently, I am forcing all eigenvalues of $S$ to be non-negative. If I now obtain the corresponding constrains on $\delta$ and $d$ such that $S$ is PSD and use them e.g. in fmincon: What are the benefits of using an SDP solver in the example above, compared to the case where I incorporate the non-negative eigenvalue constraints in to e.g. into fmincon?

• By "standard convex programming formulation" are you referring to a convex optimization problem with arbitrary (perhaps smooth) convex functions in the objectives and constraints? Or something else? Dec 11, 2017 at 14:56
• Similar question to Brian here. Do you have a specific example in mind of a non-convex problem with two different nonlinear convex relaxations---one SDP and one otherwise? Dec 11, 2017 at 16:19
• Or, are you referring to situations where the convex relaxation can be formulated as an LP, CQP, or SOCP (all of which can be solved as SDP's)? Dec 11, 2017 at 16:28
• @BrianBorchers I made an edit that hopefully clarifies the questions. Dec 11, 2017 at 18:26
• @MichaelGrant I made an edit that hopefully clarifies the questions. Dec 11, 2017 at 18:26