Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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 2

up vote 0 down vote accepted

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).

share|improve this answer
    
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 qualification) 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.