Browse Prior Art Database

Modified Rank One No Derivative Unconstrained Optimization Method (MRIND)

IP.com Disclosure Number: IPCOM000076955D
Original Publication Date: 1972-May-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 3 page(s) / 35K

Publishing Venue

IBM

Related People

Cullum, J: AUTHOR

Abstract

The MRIND algorithm obtains a local minimum value and a local minimal point of a differentiable function f of n variables, whose derivatives are not explicitly available for use in the minimization scheme.

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

Modified Rank One No Derivative Unconstrained Optimization Method (MRIND)

The MRIND algorithm obtains a local minimum value and a local minimal point of a differentiable function f of n variables, whose derivatives are not explicitly available for use in the minimization scheme.

At step i, the jth component of the current approximation to the gradient of f, g/a/(i), is given by (g/a/(i))/j/ = ((f(x(i)+h/j/(i)e(j)) - f(x(i)))/h/j/(i)) - h/j/(i)a/jj/(i)/2 where x(i) denotes the current iterate, h/j/(i) denotes the change in x obtained either from Stewsrt's formula (J. Assoc. Comp. Mach. 14 (1967), pp. 72-83) or fixed apriori, e(j) denotes the jth coordinate line, and a(i)jj is the jth diagonal element of the current approximation to the Hessian of f, G(i). Observe that if f is quadratic f = < Qx, x >/2 + <d x> + e and G(i) = Q for some i, then g/a/(i) = g(i), the gradient of f for any value of h(i). If h/j/(i) is fixed apriori over i, then finite termination of the algorithm when f is a quadratic is possible. In general, the terminal convergence of the algorithm is second order.

Searches are made along the lines x = x(i) + aH(i)g/a/(i) and if for some i there is no point on this line such that f(x) < f(x(i)), then successive searches are made along the coordinate lines through x(i), until either a line of descent is obtained or all such lines have been used without obtaining a line of descent. In the latter case, the algorithm has converged. (The coordinate directions treated cyclically and H(i) = G/-1/(i)).

The initial step along any line of search x = x(i) + ad(i) is given by min {2, <g/a/(i), d(i)>/<G(i)d(i), d(i)>}. Thus, no a priori lower bound on f is required. This step normally transfers x(i) to the stationary point of the current approximating quadratic q(x) = <G(i)x, x>/2 + <g/a/(i) - G(i)x(i), x>.

The algorithm i...