Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-24T20:44:31.551Z Has data issue: false hasContentIssue false
  • English
  • Français

Trajectory analysis and extrapolation in barrier function methods

Published online by Cambridge University Press:  17 February 2009

Krisorn Jittorntrum  and
M. R. Osborne
Krisorn Jittorntrum
Affiliation:
Computer Centre, Australian National University, P.O. Box 4, Canberra, A.C.T. 2600
M. R. Osborne
Affiliation:
Computer Centre, Australian National University, P.O. Box 4, Canberra, A.C.T. 2600
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

It has been known for some time that if a certain non-degeneracy condition is satisfied then the successive solution estimates x(r) produced by barrier function techniques lie on a smooth trajectory. Accordingly, extrapolation methods can be used to calculate x(0). In this paper we analyse the situation further treating the special case of the log barrier function. If the non-degeneracy assumption is not satisfied then the approach to x(0) is like r½ rather than like r which would be expected in the non-degenerate case. A measure of sensitivity is introduced which becomes large when the non- degeneracy assumption is close to violation, and it is shown that this sensitivity measure is related to the growth of dix/dri with respect to i for fixed r small enough on the solution trajectory. With this information it is possible to analyse the extrapolation procedure and to predict the number of stages of extrapolation which are useful.

Type
Research Article
Information
The ANZIAM Journal , Volume 20 , Issue 3 , June 1978 , pp. 352 - 369
Copyright
Copyright © Australian Mathematical Society 1978

References

[1]Butcher, J. C., “Coefficients for the study of Runge-Kutta integration processes’, J. Aust. Math. Soc. 8 (1963), 185–201.CrossRefGoogle Scholar
[2]Fiacco, A. V. and McCormick, G. P., Nonlinear programming: sequential unconstrained minimization techniques (Wiley, New York, 1968).Google Scholar
[3]Fletcher, R., “An ideal penalty function for constrained optimization’, J. Inst. Maths. Applics. 15 (1975), 319–342.Google Scholar
[4]Fletcher, R. and McCann, A. P., “Acceleration techniques for nonlinear programming’, in Numerical methods for nonlinear optimization (ed. Lootsma, F. A.) (Academic Press, London, 1972), pp. 203–214.Google Scholar
[5]Laurent, P. J., “Convergence du procédé d'extrapolation de Richardson’, Troisième Congrès de l'Afcalti (Toulouse), pp. 81–98.Google Scholar
[6]Lootsma, F. A., “Extrapolation in logarithmic programming’, Philips Res. Repts 23 (1968), 108–116.Google Scholar
[7]Mifflin, R., “Convergence bounds for nonlinear programming algorithms’, Math. Programming 8 (1975), 251–271.CrossRefGoogle Scholar
[8]Osborne, M. R., “Topics in optimizations’, Comp. Sci. Dept, Stanford Univ. (STAN-CS-72–279, 1972).Google Scholar