# 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. – Suresh Venkat Apr 23 '11 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.) – Yoshio Okamoto Apr 23 '11 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. – Artem Kaznatcheev Apr 24 '11 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? – András Salamon Apr 24 '11 at 20:09
$$\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.