# Optimal value of a semidefinite program

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

If not, what are the conditions for that?

• If you're minimizing, then yes, since an SDP is a convex program. Apr 23, 2011 at 5:59
• (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.) Apr 23, 2011 at 13:41
• 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. Apr 24, 2011 at 15:20
• @N27: perhaps you could provide a little more motivation in your question, for instance what kinds of conditions you are interested in? Apr 24, 2011 at 20:09

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.