Chapter Three
Problem Statement and Thesis Objectives
3.1 Existing Methodologies
No methods or complete tools were found in the research for this paper to directly or optimally numerically find the objective function solution for the minisum SFLP point. Other researchers have made attempts, noted in the previous chapter, to limit the problem, or to find other alternative methods of obtaining 'good' start positions for gradient descent or other optimization techniques. The most promising result so far remains the centroid projection method of Litwhiler (25).
Drezner (13) has proven an 'always convergent algorithm' for co-hemispherical demand points. He notes that based on previous research and proofs, there is a single global minimum on the spherical surface with a radius of less than or equal to Π/4, and that although there may be local minima on the hemispherical problem there is also a global minima. The mathematical proof of his problem is difficult to apply in code, and although it shows that most of this problem is soluble, will not be further addressed. The proposals herein attempt to dissect alternative methodologies leading to the same ends.
Most researchers have noted that possibly the only way to determine the problem optimal solution is through complete enumeration of the possibilities (an infinite number of possibilities, even for an extremely small surface to analyze) through code. Most likely only a 'very good' solution can be obtained, as complete enumeration is infinitely impossible (results will in the general case only lead to more and more highly defined very small regions of optimality).
3.2 'Solutions' in the Weiszfeld's Algorithm Methodology
Wieszfeld's algorithm iteratively solves for the minisum location to the Weber problem based on it's objective function,
min f(x,y)=∑wi[(x-ai)**2+(y-bi)**2]**1/2. [7]
The theory is based on differentiating the objective function and setting those differentials equal to zero. Because the function (for L2 metrics) is convex, the differentials (when combined, for as many perpendicular dimensions as are involved) define a minimum, except at the demand points (division by zero errors). The mechanics of the problem are left to location science courses and should be apparent to students of the problem (see the codes for reference).
It is not clear whether the algorithm will hold for direct solution on the spherical surface, even for problems within the convex hull, because of the non-differentiability of the distance norm. Without attempting a proof (or dis-proof) of this idea, we will find a 'good' solution for each sample problem and then use a modification of the standard Weiszfeld algorithm, substituting great circle arc distances for L2 distances, and attempt to ascertain how the results compare. Because our data sets cover from very small area to spherical-covering problems, we may be able to draw some inferences. The proof of whether or not the different norm can be successfully used is left for future research; we will simply try it and report results.
3.3 Computational Complexity of the Problem
The 'normal' solution of the Weber problem is contingent upon many factors which make it unsuitable for determination of a standard computational complexity. Typically, computational complexity can be derived from mean execution times of a number of runs with a varying number of inputs, n. In the Weber problem (and the examined extensions), the inputs are variable: The number of demand points, n, can be set as a standard, but other factors will make the problem of classifying these methods inconsistent. Among these factors in L2 space are induced error (for computer processing to disallow division-by-zero errors), degree of optimality required (precision criteria), and initial (trial) solution location. In more advanced methods attempting to arrive more quickly at a 'global' solution, multiple runs of advanced search techniques external to the problem algorithm (for example, simulated annealing) may take more run time than the main program. In addition, when working on the surface of a sphere points and distances must be dual-analyzed for minima and maxima because of the wrapping nature of the solution space.
Another concern in calculating complexity arises from potential 'flatness' of the objective functions. Flatness can be described as a relation between the linearity of the gradient descent of the Weiszfeld algorithm step per the relative weights of demands distant from the attempted solution point. For a planar L2 3-point equal weight problem with demand points (0,1), (1,0), and (1,1) and initial point (0.5,0.5), the Weiszfeld algorithm requires 37 iterations to find a solution within .00001 (1**-6) accuracy. For a similar problem with demand point (0,1), (2,3), and (4,3) with a starting point of (1,1), it requires 41 steps to reach 1**-6 precision. For another problem with demand points (0,0), (0,1), (1,0), and (100,100) and starting point (1,1), where the first three points have weights of 1 and the last of 2.9999, it requires 118,626 steps. An additional factor in this argument could be the non-linearity of the combinatorial trigonometric objective functions incurred when dealing with a spherical surface. Flatness of the objective function has a direct link to the majority theorem's implications in the last case.
This paper shall not attempt to ascertain any relations to the computational complexity of the investigated problem. The above paragraph provides sufficient detail as to why computational complexity is not an adequate description of the problem. Should a best-for-spherical-surface search technique become available, computational complexity could be computed in two- or three-variable space. This is left for future research.
One of the major problems of prior research in this and other complex fields was the limited availability of processor time; many calculations had to be either done by hand or scheduled on a busy mainframe, and heaven forbid if there was a programming error in your punch cards. The advent of desktop computers with speeds and FLOPS exceeding those of the early mainframes has made these concerns history; it can now be considered almost efficient to search the entire near-continuous surface of a sphere (using a relatively dense network methodology) in order to find a global minimum, and the problem will still be solved in a very short amount of time (order of minutes, not hours or days). It would be desirable to find a simple algorithm not requiring this processor time, but it appears (from 20 years of research) to not be in the realm of our present methods of logic. Therefore, we attempt to decrease the amount of time spent searching for the global minima by working with 'good' starting locations and other methods (not considering other techniques such as simulated annealing or gradient acceleration search modifications to existing methods).
3.4 Problem Statement
The objective of this research is to investigate an alternative geometric method which will attempt to find a solution to the Weber problem on the sphere. This method, fully defined in section 4.2, finds the L2 three-dimensional spatial median of the demand points, and projects a ray through the spatial median from the sphere center to the surface. The resultant surface point is then examined to determine how close it is to the optimal spherical surface median. Use of the projected centroid has been made in previous research by others, but the median was not investigated heavily because of the iterative computational difficulties involved in resolving it's location.
The results of the geometric investigation may allow a loophole through the non-convexity issues noted when dealing with great circle distances and maximum spherical circle convex hulls. If the results are promising, the obvious extension is to attempt to find good solutions for demand point sets which lie outside the maximum spherical circle (hemispherical) convex hull.
Figure 4 defines the conventions for measuring latitude and longitude coordinates on the spherical surface. The measures are taken from a zero point located on the equator at the prime (zero) meridian. Longitudinal measures are taken positive to the east from the prime meridian and negative to the west, and latitudinal measures positive north from the equator and negative south. Spheres have wrapping properties, so that a longitudinal measure of 3Π/2 is equivalent to 7Π/2 (3Π/2 + 2Π); these properties are the same in latitude. This wrapping property requires some extra computational steps in determining shortest distances between points: for two points on the equator at longitudes of -.1 and .1, the shortest arc distance equation will yield an answer of >Π, or over halfway around the sphere. To check these erroneous 'shortest arcs,' steps in any program must include a check for distances >Π and reduce these distances to 2Π minus the calculated answer. To keep the programs consistent, all problems have been described with a longitude defined from -90 (inclusive) to 90 (exclusive) and a latitude from -90 (inclusive) to 90 (inclusive). This covers the entire sphere; the degree coordinates for Colorado Springs, typically listed as approximately 105W 39N become -105long 39lat.
An additional term is necessary to properly locate surface points in R3 space. When converting to or from R3 space terms (x, y, and z coordinates) to these longitude and latitude coordinates, the latitude must be converted to colatitude. Colatitude is simply the measure of the latitude taken from 0-2Π from the north pole of the sphere. The equations used for the problem computations fail when done in standard longitude/latitude measures, just as the distance metric measures fail when using longitude/colatitude measures. The formula for obtaining colatitude is simply
colatitude=(Π/2)-latitude. [8]
Figure 4. Latitude Φ, longitude Θ, and convention for A=(ΦA,ΘA)
3.5 Anticipated Results
As noted in the literature review, a similar approximate solution can be arrived at using the centroid instead of the spatial median. The solution in that case yields a point that should be 'in the neighborhood' of the optimal solution, and may offer a good starting point for other search techniques. The 3d spatial median and projection technique described may allow a direct solution to optimal; it may only yield another approximate starting point solution; or, it may fail completely as the covering spherical circle for the demand points increases in diameter.
All investigations shall be compared with alternative approximate solution methods so that conclusions may be drawn regarding the comparative 'goodness' of the achieved results.
3.6 Objectives of Research
This research will attempt to determine whether the proposed geometric method is applicable for any of the variety of spherical surface problems which could be encountered, and the relative 'goodness' of any solutions found.
This attempt is not to find or derive a specific algorithm to determine the optimal location of a spherical Weber solution, rather to pursue a previous 'recommendation for future work.' The numerical approach (this is an engineering pursuit, not a mathematical one) may (or may not) prove useful to future problem aficionados.
3.7 Majority Theorem Implications
Of important note in developing or testing solutions of this nature is the majority theorem, which, in L2 metrics says that if a demand point's weight is greater than the sum of all of the other demand points' weights is less than the first that the optimal solution is at the first ('heaviest') demand point. The emphasis of this research is the alternative geometric solution, and so this theorem was not applied in the testing. If (which was not the case in our sample problems) a point was 'heavy' enough for the theorem to apply, the projected point would have been at the same spherical coordinates as the 'heavy' point, as the L2 3-dimensional Euclidean metric was employed to generate these. No implication is made as to the follow-on testing of a direct Weiszfeld solution using great circle arc distances and the majority theorem; this is left for future research.
Next Page
Back to Index