6
$\begingroup$

Assume we are solving $\min\{f(x) \ | \ x \in S \}$.

If $f: \mathbb{R}^n \mapsto \mathbb{R}$ is a proper closed convex function, and $S$ is a non-empty closed convex set, does this imply that the above minimization problem has a non-empty solution set? Does an optimal solution always exist in such a setting?

What I know is that (by Wikipedia) a proper convex function is closed if and only if it is lower semi-continuous. Moreover, if I know $f$ is proper closed convex, then this implies the function is lower semi-continuous. By the extension of extreme value theorem to semi-continuous functions, we know that the above minimization has a non-empty solution set since $f$ is lower semi-continuous. So maybe this is it...

Edit: Based on the answer to this question below, I see that such an optimal value always exists. However, in Amir Beck's first-order methods book, there is the following set of assumptions:

enter image description here Then don't (A,B,C) imply (D) anyways? Why are we also assuming (D) at all?

$\endgroup$
  • $\begingroup$ What does $\operatorname{int}(\operatorname{dom}(f))$ denote (I'm guessing dom is domain, not sure about int)? $\endgroup$ – Nikos Kazazakis Mar 13 '20 at 0:24
  • $\begingroup$ @NikosKazazakis interior! $\endgroup$ – independentvariable Mar 13 '20 at 0:29
5
$\begingroup$

No, an optimal solution need not exist. Take $f: \mathbb{R} \to \mathbb{R}$ with $f(x) = e^{x}$.

However if you restrict $S$ to be compact instead of just closed, then you are guaranteed a solution. In fact, convexity is not required. For a simple proof, let $f(x_n) \to \inf_{x \in S} f(x)$. $x_n \in S$ has a convergent subsequence by compactness, and let $x \in S$ be its limit point. By lower semicontinuity $x$ minimizes $f$ on $S$. Lastly, note that the infimum above must be finite because $f$ is proper, hence $f(x) \neq \pm \infty$.

$\endgroup$
-4
$\begingroup$

An optimal solution exists iff the KKT are satisfied.

As Mark Stone pointed out in the comments, the brief does not give us any guarantees on continuous differentiability, which is necessary for KKT. Without (D), there might or might not be KKT points, we can't tell. (D) imposes that we have at least one KKT point.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Could you please have a look at my edit? $\endgroup$ – independentvariable Mar 13 '20 at 0:07
  • $\begingroup$ Regarding KKT, how are you able to conclude the requisite continuous differentiability (or any differentiability) applies to anything? $\endgroup$ – Mark L. Stone Mar 13 '20 at 1:01
  • $\begingroup$ What is the derivative of max(x,0) at x = 0? $\endgroup$ – Mark L. Stone Mar 13 '20 at 1:04
  • $\begingroup$ Ah you are right I missed the smoothness. It's pretty late here so I'll get back to you tomorrow :) $\endgroup$ – Nikos Kazazakis Mar 13 '20 at 1:09
  • 2
    $\begingroup$ @independentvariable That is the mistake I made originally, because there is no guarantee that those points will be KKT points. There will be a minimal value, but there is no guarantee that it will be optimal. $\endgroup$ – Nikos Kazazakis Mar 13 '20 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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