## When can the optimal value of a SDP be achieved?

Looking at semidefinite programs, are there any sufficient conditions for the solvability (i.e. the optimal value can be achieved, that is infimum=minimum)?

Obviously if the problem is unbounded, the optimal value cannot be attained. Also, if my objective function is continous and the domain is compact, everything is fine, right?

Any help or hint to literature would be appreciated.

-
I think this question would be more appropriate for math.stackexchange.com, but if you ask there I would be happy to answer it. – Noah Stein Jun 8 2011 at 11:55

If the primal problem is feasible and its dual problem possesses a strictly feasible point, i.e. a point belonging to the (relative) interior of the feasible region, then the primal problem

• is bounded
• attains its optimal value at some point
• has no duality gap with its dual

(note however that under these hypotheses the dual itself is not guaranteed to attain its optimal value).

-
 Thank you for your answer. Can you give me a reference where i can look this up? – vger Jun 9 2011 at 4:14 You can check section 5.2.3 (Strong duality and Slater’s constraint qualiﬁcation) in Boyd and Vandenberghe's Convex Optimization textbook,available online. – FG Jun 11 2011 at 8:36 Thank you very much – vger Jun 14 2011 at 6:47

A classical fact that is often used is that a continuous function on a compact set attains its minimum AND maximum

More flexible is, however, the following Theorem (see e.g., Thm 1.9 in Rockafellar & Wets's Variational Analysis)

Defn (level bounded) A function $f : R^n \to [-\infty,+\infty]$ is level-bounded if for every $\alpha \in R$, the set $\{x \in R^n | f(x) \le \alpha\}$ is bounded.

Theorem Let $f: R^n \to [-\infty,+\infty]$ be a lower semi-continuous, level-bounded and proper function. Then the value of $\inf f$ is finite and the set $\text{argmin} f$ is nonempty and compact.

-