The PERT method
---------------
In 1958, at the height of the Cold War, the US Navy sought to develop the Polaris nuclear missile submarine system as quickly as possible. The project involved 250 suppliers, not counting subcontractors. To coordinate the entire undertaking, the Navy devised a method based on graph theory: PERT (Program Evaluation and Review Technique). It breaks the project down into a number of tasks, each of which may or may not depend on another and has a specified duration. This yields a graph with nodes (the beginning and end of each task) and edges (representing tasks and their durations). PERT identifies the longest path from the start node (A in the figure) to the end node (F in the figure), shown in red.
This path gives the minimum time needed to complete the project and highlights the most critical tasks. Using this method, the Polaris project was completed in 1960, five years ahead of the original schedule!
Similarly, thanks to the PERT method, only eight years elapsed between John Kennedy's speech announcing the American project to send a man to the Moon (25 May 1961) and Apollo 11's landing on our satellite (20 July 1969)!
-
Minimizing sums of absolute values
----------------------------------------
The absolute-value function f (defined by f (x) = | x |) is not differentiable at its minimum (f (0) = 0). Its derivative is constant on either side, jumping from –1 to +1 at x = 0. Similarly, the function g that maps x to | x – a | attains its minimum (g (a) = 0) at x = a, where it is not differentiable. How can sums of absolute differences be minimized? Consider the function h (x) = (| x – a | + | x – b |),
where a < b. This continuous function is piecewise affine: it consists of a ray of slope –2 for all x less than a, a horizontal line segment (with y-coordinate b – a) between a and b, and a ray of slope 2 for x > b. The minimum is attained at every point in the interval [a, b] (in the graph, a = 2 and b = 4).
The same reasoning applies to a sum of several absolute values. Simply arrange the parameters (here, a, b and c) in increasing order (a < b < c) and consider the function j (x) = (| x – a | + | x – c |) + | x – b |. The expression in parentheses attains its minimum (namely c – a) for every value in [a, c]. The second term (which is always non-negative) attains its minimum value of 0 at x = b, which is therefore the function's unique global minimizer.
-
The metric that justifies the median
-----------------------------------
Given a dataset x1, x2… *xn, how can we summarize its n numerical values with a constant? Replacing a sequence of varying numbers by a single number a yields a new dataset of the residuals (or errors) ei = xi – a. A well-chosen central value a* has some errors that are positive and others that are negative. The appropriate choice of a must minimize the total error. We therefore take the absolute value of every error and add them together. One simple approach is to take the total error ET to be the sum of the absolute values of the errors. Arrange the observations in ascending order. Pair the observations by forming nested intervals: pair the first with the last, the second with the penultimate, and so on. With an odd number of observations, there is a single middle observation, which gives the minimum. With an even number of observations, there are two "central" observations. The minimum is then attained at every value between those two observations. This is precisely the median! Thus, the absolute-value metric need not yield a unique location parameter.
