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$
2
  • $\begingroup$ What does $\operatorname{int}(\operatorname{dom}(f))$ denote (I'm guessing dom is domain, not sure about int)? $\endgroup$ Mar 13, 2020 at 0:24
  • $\begingroup$ @NikosKazazakis interior! $\endgroup$ Mar 13, 2020 at 0:29

2 Answers 2

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$
9
  • $\begingroup$ Thanks for your answer. Could you please have a look at my edit? $\endgroup$ Mar 13, 2020 at 0:07
  • $\begingroup$ Regarding KKT, how are you able to conclude the requisite continuous differentiability (or any differentiability) applies to anything? $\endgroup$ Mar 13, 2020 at 1:01
  • $\begingroup$ What is the derivative of max(x,0) at x = 0? $\endgroup$ Mar 13, 2020 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$ Mar 13, 2020 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$ Mar 13, 2020 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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