Browse Prior Art Database

Minimization of Piecewise Linear Functions

IP.com Disclosure Number: IPCOM000088762D
Original Publication Date: 1977-Jul-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 3 page(s) / 17K

Publishing Venue

IBM

Related People

Crowder, HP: AUTHOR [+3]

Abstract

Minimization of a function of a single variable is a fundamental subroutine in most procedures for the minimization of functions of many variables. The literature [1,2] describes certain important classes of large-scale linear programming problems, having astronomically many variables, which can be recast as problems of minimizing convex, nonlinear, but piecewise linear, functions of reasonable numbers of variables. Procedures for such problems require as a subroutine (as do most procedures for nonlinear minimization) an efficient method for finding the minimum of the given function on an arbitrary line ray in the space of problem variables. In other words, a procedure is required which will efficiently find the minimum, if such exists, of any convex, piecewise linear function f of a single variable.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 41% of the total text.

Page 1 of 3

Minimization of Piecewise Linear Functions

Minimization of a function of a single variable is a fundamental subroutine in most procedures for the minimization of functions of many variables. The literature [1,2] describes certain important classes of large-scale linear programming problems, having astronomically many variables, which can be recast as problems of minimizing convex, nonlinear, but piecewise linear, functions of reasonable numbers of variables. Procedures for such problems require as a subroutine (as do most procedures for nonlinear minimization) an efficient method for finding the minimum of the given function on an arbitrary line ray in the space of problem variables. In other words, a procedure is required which will efficiently find the minimum, if such exists, of any convex, piecewise linear function f of a single variable. Further, in the given context of large-scale linear programming, the function f cannot be explicitly described; rather, given any value x of its argument, one can readily calculate f(x) and one support of the graph of f -- that is, a "slope", denoted here by f'(x), such that f(y) >/- f(x) f'(x) (y - x) for all y. -- but no more. The kind of function handled here is unusual in one respect: f'(x) is not continuous. Consequently, a method [e.g., 3,4] designed for the more usual problem, in which f'(x) is continuous, does not work well in this case, as the example shown later illustrates.

The algorithm below is an efficient means of accomplishing the required task. As far as is known, the problem is addressed here for the first time.

STATEMENT OF THE PROBLEM:

The piecewise linear (more properly, piecewise affine) function f is defined for all x>/-0 by (1) f(x) = Max ( a(i) x+ b(i) : i = 1,..,I ), where, for each i, a(i) and b(i) are real numbers. The quantities a (i)and b (i) are not explicitly given; rather it is supposed that this is a procedure which, for any x>/-0, determines the value f(x) and some a(i) b(i) for which f(x) = a(i) x+ b(i). We denote that a(i) by f'(x).

To simplify notation below, it is assumed that f(0) = 0 and, also, that f'(0) < 0 (since, otherwise, x=0 is trivially the minimizer). It is noted that f is a convex function and f'(x) a "subgradient" of f at x, and that f' is monotone nondecreasing.

Some applications may require the exact minimum of f, while often in nonlinear optimization the exact solution of the univariate minimization problem is not needed for success of the overall procedure of which it is a subroutine, and much computational labor can be saved by requiring only that the two following conditions be satisfied by the approximate minimizer x: (a) f(x) </- 0,

(b) |f'(x) | </- m|f'(0) |, where the constant m need only satisfy the relations 0</-m<1. The present goal is thus to find x>/-0, f(x), and f'(x) satisfying (a) and (b).

ALGORITHM.

1

Page 2 of 3

When f and f' are evaluated for some value of x, the data are recorded in the form of the triple (x, f(x), f'(x...