# Semi-definite Programming with Quadratic Objective

I was going through Stephen Boyd and lieven vandenberghe's Convex Optimization Book, In chapter 4 he explains Semidefinite programming (SDP) and it's the standard form.

min $$c^{T}x$$

subject to $$x_{1}F_{1} + x_{2}F_{2} +... + x_{n}F_{n} + G <= 0$$

I was wondering as SDP is the superset to Quadratic Programming having quadratic objectives should be allowed right?

• No, a quadratic term in the objective function does not fit the definition of an SDP. However, if you were to include a quadratic term in the objective function, there are tricks that would allow you to reformulate the resulting problem as an SDP. Dec 16 '19 at 1:34
• Ok, so you mean that if I use epigraph trick I will able to reformulate it as SDP? Dec 16 '19 at 1:38
• That book has two authors. Dec 16 '19 at 16:59
• What if the quadratic objective becomes a non-convex inequality? Dec 16 '19 at 17:00
• Yes, my bad, I have added the other author and as far as your second question goes I'm not sure what you mean by non-convex inequality, can you elaborate, please. Dec 27 '19 at 7:41

$$\begin{array}{rl} \min_{(x_i)_{i=1}^{n} \in \mathbb{R}^n} & \sum_{j=1}^{n}\sum_{i=1}^{n} c_{i,j} \langle x_i, x_j\rangle \\ \text{subject to} & \sum_{j=1}^{n}\sum_{i=1}^{n} a_{i,j,k} \langle x^i , x^j\rangle \leq b_k, \quad \forall k \\ \end{array}$$
• I know sdp from integer programming and maxcut. The main idea is $Y=[x_i.x_j]$. Check this report as a reference: google.com/url?sa=t&source=web&rct=j&url=https://… Dec 16 '19 at 5:00
• It is the same problem. The matrix $X=\langle x_i , x_j \rangle$ is a gram matrix. Thus $X$ is positive semidefinite. This problem is basically $\min \langle C,X\rangle$ subject to $\langle A_k,X\rangle , \quad \forall k$. Can you check this? I think that the problem written as in the answer above is more clear. en.m.wikipedia.org/wiki/Gramian_matrix Dec 16 '19 at 12:14