Is a local optimum value of a SDP always the global one?

If not, what are the conditions for that?

  • 5
    $\begingroup$ If you're minimizing, then yes, since an SDP is a convex program. $\endgroup$ Apr 23, 2011 at 5:59
  • 10
    $\begingroup$ (1) In SDP, the objective function is linear. So it doesn't matter if you maximize or minimize. (2) SDP has some computationally pathological cases, but the question is not about computation. (Actually there are some mathematically pathological cases as well, but this is not a point of the question.) $\endgroup$ Apr 23, 2011 at 13:41
  • 2
    $\begingroup$ Also, be careful that you are not confusing strong duality with the local optimum, global optimum issue. There are cases when strong duality does not hold for SDP... although there are also many cases when it does. $\endgroup$ Apr 24, 2011 at 15:20
  • 2
    $\begingroup$ @N27: perhaps you could provide a little more motivation in your question, for instance what kinds of conditions you are interested in? $\endgroup$ Apr 24, 2011 at 20:09
  • 3
    $\begingroup$ @YoshioOkamoto, would you please combine your comments with Artem's comments into a proper answer so this question doesn't show up as unanswered any more? I believe your two comments answer the question. $\endgroup$
    – Dominique
    Oct 14, 2011 at 16:33

1 Answer 1


Here are a few more details for Suresh and Yoshio's answer. Following e.g. https://en.wikipedia.org/wiki/Semidefinite_programming, an SDP is of the form

$$\begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} \quad\text{subject to}\\ & \langle A^{(k)}, X \rangle_{\mathbb{S}^n} \leq b_k, \quad (\forall k \in \{1,\ldots,m\}) \\ & X \succeq 0 \end{array}$$ where $\mathbb{S}^n$ is the space of all $n\times n$ real symmetric matrices, $\langle C, X \rangle_{\mathbb{S}^n} = \sum_{ij} C_{ij} X_{ij}$, and $X \succeq 0$ constrains $X$ to be positive semi-definite. The latter constraint is equivalent to (sometimes by definition) $$y^T X y \ge 0~~~(\forall y\in \mathbb{R}^n).$$ (See e.g. here.) Hence, the SDP is equivalent to $$\begin{array}{rr@{}ll} {\displaystyle\min_{X \in \mathbb{R}^{n\times n}}} & \sum_{ij} C_{ij} X_{ij} &\text{subject to}\\ & \sum_{ij} A^{(k)}_{ij} X_{ij} &\leq b_k, & (\forall k \in \{1,\ldots,m\}) \\ & \sum_{ij} y_i y_j X_{ij} &\ge 0 & (\forall y\in \mathbb{R}^n)\\ & X_{ij} &= X_{ji} & (\forall i,j\in\{1,\ldots,n\}). \end{array}$$

So, we can think of the SDP as minimizing (or maximizing) a linear function of the vector $X$ subject to (infinitely many) linear constraints on $X$. Hence, it is an optimization problem with a convex feasible region and a linear objective. So any local optimum is a global optimum.


Your Answer

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

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