1
$\begingroup$

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?

$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – littleO
    Dec 16, 2019 at 1:34
  • $\begingroup$ Ok, so you mean that if I use epigraph trick I will able to reformulate it as SDP? $\endgroup$
    – adithya
    Dec 16, 2019 at 1:38
  • 1
    $\begingroup$ That book has two authors. $\endgroup$
    – Rodrigo de Azevedo
    Dec 16, 2019 at 16:59
  • $\begingroup$ What if the quadratic objective becomes a non-convex inequality? $\endgroup$
    – Rodrigo de Azevedo
    Dec 16, 2019 at 17:00
  • $\begingroup$ 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. $\endgroup$
    – adithya
    Dec 27, 2019 at 7:41

1 Answer 1

Reset to default
0
$\begingroup$

In general, semidefinite programming uses dot product of vectors. The SDP can be written as follows:

$$ \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} $$

$\endgroup$
7
  • 1
    $\begingroup$ Thanks for the clarification $\endgroup$
    – adithya
    Dec 16, 2019 at 1:41
  • $\begingroup$ I don't see that this is equivalent to an SDP. Could you elaborate on that or provide a reference? How are semidefinite cone constraints handled in this formulation? $\endgroup$
    – littleO
    Dec 16, 2019 at 1:55
  • $\begingroup$ 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://… $\endgroup$
    – Alexandre Frias
    Dec 16, 2019 at 5:00
  • $\begingroup$ The optimization problem you've written isn't the same as the SDP which is on page 5 or the dual SDP which is on page 8 of that document. So I still don't see that what you've written is equivalent to a standard SDP. (And you seem to have no semidefinite cone constraint in your formulation.) $\endgroup$
    – littleO
    Dec 16, 2019 at 5:15
  • $\begingroup$ 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 $\endgroup$
    – Alexandre Frias
    Dec 16, 2019 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.