Optimal Resource Allocation: With Practical Statistical Applications and Theory

CHAPTER 4

Steepest Descent Method

4.1 The Main Idea of SDM

The Steepest Descent Method (SDM) is based on a very natural idea: moving from an arbitrary point in the direction of the maximal gradient of the goal function, it is possible to reach the maximum of a multi-dimensional unimodal function. The origin of the method's name lies in the fact that a water drop runs down a non-flat surface choosing the direction of instantaneous maximum descent.

The next simple example explains the algorithm more graphically. Suppose that a traveler comes to a hill that is hidden in a thick mist. His goal is to reach the hill top with no knowledge about the mountain shape except the fact that the hill is smooth enough (has no ravines or local hills). The traveler sees only a very restricted area around the starting point. The question is: What is the shortest path from the initial point to the mountain's top? Intuition hints that the traveler has to move in the direction of the maximal possible ascent at each point on his path to the mountain's top (Fig. 4.1). This direction coincides with the gradient of the function at each point.

FIGURE 4.1 A path of a traveler up to the hill top.

However, optimal redundancy problems have an integer nature: redundant units can be added to the system one by one. The previous analogy is useful in case of continuous functions of continuous arguments. But in the ...