Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Sum of Eigenvalues Minimization Algorithm

IP.com Disclosure Number: IPCOM000082724D
Original Publication Date: 1975-Jan-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 3 page(s) / 19K

Publishing Venue

IBM

Related People

Cullum, JK: AUTHOR [+2]

Abstract

Sum of eigenvalues (SEV) is an algorithm for finding a minimizing point of any member of a particular class F of convex but not everywhere differentiable functions. Each function in F is defined in terms of the sum of the q largest eigenvalues of a symmetric matrix A+D algebraically, where D is a diagonal matrix and the entries of D are allowed to vary.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Sum of Eigenvalues Minimization Algorithm

Sum of eigenvalues (SEV) is an algorithm for finding a minimizing point of any member of a particular class F of convex but not everywhere differentiable functions. Each function in F is defined in terms of the sum of the q largest eigenvalues of a symmetric matrix A+D algebraically, where D is a diagonal matrix and the entries of D are allowed to vary.

For a more detailed description of the SEV algorithm see the IBM Research Center Report RC 4611, pgs. 27-29, November 6, 1973. Its computer implementation is discussed in Section 6, pp. 45-60 of this report.

Existing minimization algorithms for convex, but not everywhere differentiable functions, require either, (1) the use of sets whose characterization does not seem possible for functions in F, or (2) the choice of a nonapparent step-size strategy for the minimization path. (See RC 4611 pp. 23-26 for details). The SEV algorithm is similar to algorithms requiring (1). However, the sets it uses can be completely characterized in terms of computable quantities. (See pp. 15- 19 of RC 4611). The key points in the algorithm are the following:

(1) A parameter epsilon, similar to that used in feasible direction algorithms for minimizing continuously differentiable functions subject to constraints, is used in SEV to allow the algorithm to identify iterates that are too close to a point at which f is not differentiable, so that appropriate action can be taken whenever this situation arises. (In practical applications of RC 4611, the minimizing point of f is very often a point at which f is not differentiable).

Epsilon may vary from iteration to iteration so it should be called epsilon Its initial value is determined heuristically from knowledge of the spread of the eigenvalues in the matrix A. Its size at iteration i, is determined by the magnitude of the decrease in f obtained on the previous iteration. epsilon(i) is used as follows. At iteration i, if

(Image Omitted)

for -r</-j</-s, then in the compu...