Optimization algorithms based on conic approximations and collinear scalings.

摘要

In this dissertation we study optimization algorithms based on conic approximations and collinear scalings. We begin with a chapter on many interesting fundamental properties of conic functions and collinear scalings which are useful in the study of optimization algorithms based on these approximations and scalings.; In 1990 Ariyawansa presented a class of collinear scaling algorithms. In 1987 Byrd, Nocedal and Yuan showed that all members except the DFP method of the Broyden convex family of quasi-Newton methods with Armijo and Goldstein line search termination criteria are globally and q-superlinearly convergent on convex functions. Extension of this result to the above class of collinear scaling algorithms of Ariyawansa has been impossible because line search termination criteria for collinear scaling algorithms were not known until recently. In 1994 Ariyawansa proposed such line search termination criteria where the function being minimized belongs to a certain class of convex functions. In Chapter 3 we provide global convergence results analogues to that of Byrd, Nocedal and Yuan (1987) for the class of collinear scaling algorithms of Ariyawansa (1990) with line search termination criteria of Ariyawansa (1994).; In Chapters 4, 5 and 6 we numerically investigate whether optimization algorithms using conic approximations and collinear scalings have improved performance relative to existing algorithms, especially in the context of barrier functions.; In 1994 More and Thuente developed a line search algorithm which uses cubic interpolations and satisfies (modified) Armijo and Goldstein line search termination criteria. In Chapter 4 we develop a safeguarded line search algorithm based on conic interpolations to compute step lengths satisfying (modified) Armijo and Goldstein line search termination criteria. Our numerical experiments indicate that in general problems our algorithm is comparable to that of More and Thuente, while in line search problems arising in barrier optimization problems the performance of our algorithm is better.; In Chapter 5 we develop a univariate minimization algorithm which uses conic interpolations. Our numerical experiments indicate that our algorithm performs better than a similar algorithm with cubic interpolations on univariate problems arising from multivariate barrier functions.; The work in Chapter 6 is concerned with preliminary numerical evaluation of collinear scaling algorithms in minimizing barrier functions. Our numerical testing indicates that the performance of our collinear scaling algorithms is promising relative to existing algorithms.