On Simplicial Methods For Minimizing Piecewise Linear Functions

Mathematics Research Report MRR95-076

On Simplicial Methods For Minimizing Piecewise Linear Functions

Michael R. Osborne

Abstract: The problem of minimizing separable, convex, piecewise linear, functions is considered. There is a sense in which this problem represents an intermediate level of complexity between general polyhedral convex functions and linear programs. Two classes of problem are considered. In the first the number of component functions in the composite objective can be large, but the structure (number of linear pieces) is small, while in the second the number of component functions is modest, but the piecewise linear structure of each can be very complex. A compact reduced gradient algorithm is developed and has the same generic form for both classes of problem. Particular attention is given to the form of the line search which must take rather different forms for the different classes. However, an idea which provides an effective approach for both problem classes is the use of a secant algorithm applied to the directional derivative which is piecewise constant and increasing in the direction of descent. Resolution of degeneracy is considered. It is shown that for a problem of complex structure it is necessary to consider only a problem of simple structure. Results of numerical experiments are presented.

This service is maintained by the Mathematical Sciences Institute (MSI)
Comments to webmaster@maths.anu.edu.au URL: http://wwwmaths.anu.edu.au/