<p>Here are a few more details for Suresh and Yoshio's answer. Following e.g. <a href="https://en.wikipedia.org/wiki/Semidefinite_programming" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Semidefinite_programming</a>, an SDP is of the form</p>

<p>$$\begin{array}{rl}
{\displaystyle\min_{X \in \mathbb{S}^n}} 
&amp; \langle C, X \rangle_{\mathbb{S}^n} \quad\text{subject to}\\
&amp; \langle A^{(k)}, X \rangle_{\mathbb{S}^n} \leq b_k, \quad (\forall k \in \{1,\ldots,m\}) \\
&amp; 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. <a href="https://en.wikipedia.org/wiki/Positive-definite_matrix#Positive_semidefinite" rel="nofollow noreferrer">here</a>.)
Hence, the SDP is equivalent to
$$\begin{array}{rr@{}ll}
{\displaystyle\min_{X \in \mathbb{R}^{n\times n}}} 
&amp; \sum_{ij} C_{ij} X_{ij}  &amp;\text{subject to}\\
&amp; \sum_{ij} A^{(k)}_{ij} X_{ij} &amp;\leq b_k,
&amp; (\forall k \in \{1,\ldots,m\}) \\
&amp; \sum_{ij} y_i y_j X_{ij} &amp;\ge 0 
&amp; (\forall y\in \mathbb{R}^n)\\
&amp; X_{ij} &amp;= X_{ji} &amp; (\forall i,j\in\{1,\ldots,n\}).
\end{array}$$</p>

<p>So, we can think of the SDP as minimizing (or maximizing) a linear function of the <em>vector</em> $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.</p>

CC BY-SA 4.0
2018-08-18T12:01:28.400Z
2018-08-18T12:01:28.400Z
Neal Young
<p>Is a local optimum value of a SDP always the global one? </p>

<p>If not, what are the conditions for that?</p>

CC BY-SA 3.0
2011-04-23T05:59:08.323Z
If you're minimizing, then yes, since an SDP is a convex program.
Suresh Venkat
CC BY-SA 3.0
2011-04-23T08:21:46.380Z
I know that it is a convex program, but I also know that sdp has some 'pathological cases' that cause problems to its efficiency in computing the global optima. For example in http://www.aimath.org/WWN/convexalggeom/AIM.pdf (p.27) it says that this is not always the case.
N27
CC BY-SA 3.0
2011-04-23T08:48:17.107Z
also you don't have to minimize necessarily, it can be a maximizing program too, as the SDP of Goemans-Williamson for Max-Cut
N27
CC BY-SA 3.0
2011-04-23T13:41:21.697Z
(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
CC BY-SA 3.0
2011-04-24T15:20:45.493Z
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
CC BY-SA 3.0
2011-04-24T20:09:00.540Z
@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
CC BY-SA 3.0
2011-04-25T03:31:32.387Z
I am studying applications of SDP in general (max cut, sparsest cut etc) and there are certain issues I have questions with. Another one is obtaining the dual (this is kind of complicated in many cases-since I cannot understand how they obtain it in certain occasions), but I may open a new thread for that in the future.
N27
CC BY-SA 3.0
2011-10-14T16:33:13.583Z
@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.
Dominique
CC BY-SA 3.0
2011-10-17T12:32:00.247Z
@Dominique: Thank you for the suggestion, but I don't think my comment can be turned into an answer, even if it's combined with Artem's comment.  I would be able to answer the question, but then I'd need to look up the literature.
Yoshio Okamoto
<ds.algorithms><optimization><convex-optimization><semidefinite-programming>
Optimal value of a semidefinite program
N27
# Optimal value of a semidefinite program

(Asked by: username_0 on 2011-04-23)

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

If not, what are the conditions for that?

**Tags:** ds.algorithms, optimization, convex-optimization, semidefinite-programming
> **Comments:**
> **username_1**: If you're minimizing, then yes, since an SDP is a convex program.  
> **username_0**: I know that it is a convex program, but I also know that sdp has some 'pathological cases' that cause problems to its efficiency in computing the global optima. For example in http://www.aimath.org/WWN/convexalggeom/AIM.pdf (p.27) it says that this is not always the case.  
> **username_0**: also you don't have to minimize necessarily, it can be a maximizing program too, as the SDP of Goemans-Williamson for Max-Cut  
> **username_2**: (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.)  
> **username_3**: 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.  
> **username_4**: @N27: perhaps you could provide a little more motivation in your question, for instance what kinds of conditions you are interested in?  
> **username_0**: I am studying applications of SDP in general (max cut, sparsest cut etc) and there are certain issues I have questions with. Another one is obtaining the dual (this is kind of complicated in many cases-since I cannot understand how they obtain it in certain occasions), but I may open a new thread for that in the future.  
> **username_5**: @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.  
> **username_2**: @Dominique: Thank you for the suggestion, but I don't think my comment can be turned into an answer, even if it's combined with Artem's comment.  I would be able to answer the question, but then I'd need to look up the literature.  

---

## 1 answers

### Answer by username_6 on 2018-08-18. Score: 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](https://en.wikipedia.org/wiki/Positive-definite_matrix#Positive_semidefinite).)
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.


---

