Example: For positive integer n and the set of real number R , show that,
on any finite intersection of closed half spaces C in R^n, any linear
function that is bounded above on C achieves its least upper bound on C.
If C is empty (i.e. the closed half spaces do not overlap), the claim is
false, since every real number is an upper bound of every function on C,
therefore the least upper bound does not exist.
However, for non-empty C and a linear function f bounded above on C,
any x in C induces a lower bound l for the upper bounds, which guarantees
the existence of a least upper bound u.
The point where u is achieved can be determined by an iterative procedure
involving a set of half-spaces H (initially H_0 is empty), a point x in C
(initially x_0 is chosen arbitrarily) and a search direction d (initially
d_0 is the gradient of f).
The following invariant is maintained: for any boundary of a half-space in H
holds that x is on the boundary and d is parallel to it,
and for any x' in C, f(x') > f(x) implies that the dot product d (x' - x) is positive.
This holds for the inital conditions, since H_0 is empty and d_0 is the gradient
of f, which means that d_0 x' = f(x') > f(x) = d_0 x is equivalent to d_0 (x' - x) > 0.
If d ever becomes zero, the invariant implies that there are no points x' in C with
f(x') > f(x), which means that f(x) = u.
Otherwise, the value of x_{n+1} is chosen from the linear subspace x_n + t d_n, where t in [0, infinity).
As this is a closed, convex set, its intersection with C (which is an intersection of
closed, convex sets) is itself closed and convex. Since f keeps increasing linearly with
t, the upper bound u on f immediately induces an upper bound on t. Summarily, this constrains
t to an interval [0, s]. Then x_{n+1} = x_n + s d_n.
This step maintains the invariants, since x moves parallel to all boundaries of
sub-spaces in H_n and x_n was contained therein, thus x_{n+1} is also contained in
all these boundaries. Because the search direction doesn't change, its invariant is maintained as well.
At this point, there must be a half-space h that "cut off" the line at x_{n+1}, which
means that x was not moving in parallel to it. Setting adding h to H_n keeps x_{n+1}
contained within all the boundaries, but makes d_n no longer parallel to them. By also
setting d_{n+1} to the component of d_n that is parallel to the boundary of h, this
can be reinstated.
However, now it must be shown that f(x') > f(x) implies d_{n+1} (x' - x) > 0. From the
previous step, it holds that f(x') > f(x) implies 0 The above algorithm must terminate in a finite number of steps, since there is only
a finite number of half-spaces that can be added to H. Because the algorithm can
only terminate by finding an x in C where f(x) = u, this proves that the least upper
bound is achieved.