How does topological properties of sets (openness, closed, compactness) matter in practical algorithm design for optimization problems?

67 Views Asked by At

In optimization problems, one places great emphasizes the properties of the constraint set

$$\min_{x \in \mathcal{C}} f(x)$$

For instance, when $\mathcal{C}$ is compact, we have the existence of an optimizer by Weierstrass, whereas when $\mathcal{C}$ is open or closed, we do not. Many algorithms such as gradient descent or other methods have properties depending on whether certain properties of $f$ are satisfied. Some functions such as $e^{-x}$ are not strongly convex, but it is locally strongly convex.

But in practice, we have a limitation on the largest number that can be represented in a computer. For instance, in C++, the largest number is unsigned integer is $18446744073709551616$. Hence every minimization problem solved in C++ is a constrained minimization problem over the compact set $$[-18446744073709551616, 18446744073709551616]^n$$

Ok, of course this is not the largest number that can be represented in a computer. It is a very large number $M$. The implications include all strictly convex functions are always locally strongly convex over a compact set $[-M, M]^n$, and every optimization problem are solved on this compact set as well.

My point is that we have a non-trivial loss of generality when solving problems on paper vs in a computer due to finite representation of numbers. Does it mean that the distinction between closed/open/compact, etc. are invalidated in practical algorithm design?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, assumptions matter a lot. We need to know that any solution resulting from a floating-point algorithm must also solve the problem on the underlying space (e.g. $\mathbb{R}$). In a sense, the fact that the floating point numbers are compact may imply that some poorly-written optimization algorithms may terminate when they shouldn't. For instance, a minimization algorithm may tell you that the minimizer of $e^{-x}$ is $M$ (the number you've written above). However, the minimizer of this function does not exist! These sort of problems can arise when we do not check assumptions.

The consequences can be catastrophic when we don't check the mathematical assumptions. In this article, not checking assumptions yielded a loss of $700 million dollars and 3 years of work.