# 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 '11 at 11:55

## 2 Answers

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 '11 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. –  F_G Jun 11 '11 at 8:36
Thank you very much –  vger Jun 14 '11 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.

-