Is a local optimum value of a SDP always the global one?
If not, what are the conditions for that?
$\begingroup$
$\endgroup$
9
-
5$\begingroup$ If you're minimizing, then yes, since an SDP is a convex program. $\endgroup$– Suresh VenkatCommented 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$– Yoshio OkamotoCommented 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$– Artem Kaznatcheev ♦Commented 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$– András SalamonCommented 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$– DominiqueCommented Oct 14, 2011 at 16:33
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
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.
