Existence of Optimal Solution

Question

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:

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

What does $\operatorname{int}(\operatorname{dom}(f))$ denote (I'm guessing dom is domain, not sure about int)? — Nikos Kazazakis, Mar 13 '20 at 00:24

Robert Bassett · Accepted Answer · 2020-03-14T05:18:20.083

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

Nikos Kazazakis · Answer 2 · 2020-03-13T14:38:44.013

-4

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.

edited Mar 13 '20 at 14:38

answered Mar 13 '20 at 00:03

Nikos Kazazakis

12,121
17
59

Thanks for your answer. Could you please have a look at my edit? – independentvariable Mar 13 '20 at 00:07
Regarding KKT, how are you able to conclude the requisite continuous differentiability (or any differentiability) applies to anything? – Mark L. Stone Mar 13 '20 at 01:01
What is the derivative of max(x,0) at x = 0? – Mark L. Stone Mar 13 '20 at 01:04
Ah you are right I missed the smoothness. It's pretty late here so I'll get back to you tomorrow :) – Nikos Kazazakis Mar 13 '20 at 01:09
Let us continue this discussion in chat. – Nikos Kazazakis Mar 13 '20 at 14:42
@NikosKazazakis I think you are wrong. I think (D) is being implied by others. A proper closed convex function is lower semi-continuous, so extreme value theorem should imply that this function attains its minimum value over a closed convex set, so why shall we need (D) as an extra assumption? – independentvariable Mar 13 '20 at 18:17
2

@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. – Nikos Kazazakis Mar 13 '20 at 19:44
I second that this answer should be deleted – Robert Bassett Mar 14 '20 at 20:44
The answer is correct, so can you elaborate why? @TomHallward – Nikos Kazazakis Mar 14 '20 at 22:48

Existence of Optimal Solution

2 Answers2