1
$\begingroup$

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

If not, what are the conditions for that?

$\endgroup$
  • 5
    $\begingroup$ If you're minimizing, then yes, since an SDP is a convex program. $\endgroup$ – Suresh Venkat Apr 23 '11 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$ – Yoshio Okamoto Apr 23 '11 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$ – Artem Kaznatcheev Apr 24 '11 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$ – András Salamon Apr 24 '11 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 '11 at 16:33
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.