The selection of updating formulas for the H matrix and the subproblem of one-dimensional search are considered for variable metric algorithms not using exact linear searches in the subproblem. It is argued that the convex class of updating formulas given by Fletcher is the logical choice for such algorithms. It is shown that direct linear searches are more efficient than linear searches using directional derivatives at each point, particularly for objective functions of many variables.
Features of algorithms using the convex class of formulas without exact searches are discussed. It is proven that effects on these algorithms of scaling of the variables of the objective function are identical to effects of transforming the initial H matrix. It is predicted that regions of a function where the Hessian is non-positive definite may be detrimental to convergence of these algorithms.
A function is given for which Fletcher's recent algorithm (which does not use any linear search for a minimum) fails to converge. Attempts were made to devise a test to detect non-convexity of a function so that an algorithm using no linear search for a minimum in convex regions and an alternative strategy in non-convex regions could be developed to overcome this problem.
Algorithms incorporating a test for non-convexity were coded as well as Fletcher's algorithm, an algorithm using a weak quadratic direct minimizing search, and an algorithm using the weak cubic minimizing search as used in the Fletcher Powell method. Numerical experiments were performed on functions from the literature and functions developed by the author. Fletcher's algorithm was found to be inefficient on all functions in comparison to the weak quadratic search algorithm where the initial H matrix had small eigenvalues. Where Fletcher's algorithm was relatively efficient, the former search was in all cases competitive. The value of a direct over derivative linear search is demonstrated. The algorithms using a test for convexity were not effective, since the best was not generally"effective in detecting non-convexity.
It is concluded that algorithms without a form of one-dimensional weak minimizing search are not suitable for use on general minimization problems, and that the weak quadratic direct search proposed is a more efficient and reliable alternative. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate
| Identifer | oai:union.ndltd.org:UBC/oai:circle.library.ubc.ca:2429/33336 |
| Date | January 1972 |
| Creators | Fitzpatrick, Gordon James |
| Publisher | University of British Columbia |
| Source Sets | University of British Columbia |
| Language | English |
| Detected Language | English |
| Type | Text, Thesis/Dissertation |
| Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
Page generated in 0.002 seconds