10 June 2005

What is Dynamic Programming? (2)

Part 1

Often when you're designing something you need to find the maximum value, given some constraints. For example, suppose you are trying to decide the optimal lot size of inventory. You have an inventory of (say) quart containers of SAE-400 motor oil, which at any particular time is I(t). The annual sales amount of this item is A, and you order it n times a year:
A = nx
Well, holding inventory is not cheap. You have a holding cost and an ordering cost. The average stock of inventory is x/2, and the cost of holding one unit of inventory is Ch, while the cost of placing an order is C0. The method of solving this sort of problem is a lagrangian, and it can be applied to selecting the number of, say, extra special-purpose keys that you want on a small electronic device (like, for example, a customized keypad). Adding more keys will not be cheap; on the other hand, it can definitely make the device easier to use. Also, you can add variables to make the problem capture as many variables as you need to analyse.

That's "classical programming." In the case of "nonlinear programming," you're working with an inequality constraint. That means, your ideal solution does not have to be a point on the constraint function; it can be less than (greater than) the constraint.
One of the greatest challenges in NLP is that some problems exhibit "local optima"; that is, spurious solutions that merely satisfy the requirements on the derivatives of the functions. Think of a near-sighted mountain climber in a terrain with multiple peaks, and you'll see the difficulty posed for an algorithm that tries to move from point to point only by climbing uphill. Algorithms that propose to overcome this difficulty are termed "Global Optimization".

The word "Programming" is used here in the sense of "planning"; the necessary relationship to computer programming was incidental to the choice of name.

My textbook (a very old one) includes the problem, "a group of N persons own a square lot and plan to build their homes on it... They would like to ensure that the minimum distance between the centers of any two houses is as large as possible." (p.67, Intriligator). Again, nonlinear programming can be used to enhance designs and confirm that they are optimal, given the restrictions known to exist.



Post a Comment

<< Home