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

Modern Homotopy Methods in Optimization

IP.com Disclosure Number: IPCOM000128720D
Original Publication Date: 1988-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 18 page(s) / 48K

Publishing Venue

Software Patent Institute

Related People

L.T. Watson: AUTHOR [+4]

Abstract

Probability-one homotopy methods are a class of algorithms for solving nonlinear sys-tems of equations that are accurate, robust, and converge from an arbitrary starting point almost surely. These new techniques have been successfully applied to solve Brouwer fixed point prob-lems, polynomial systems of equations, and discretizations of nonlinear two-point boundary value problems based on shooting, finite differences, collocation, and finite elements. This paper sum-marizes the theory of globally convergent homotopy algorithms for unconstrained and constrained optimization, and gives some examples of actual application of homotopy techniques to engineering optimization problems.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 18

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Modern Homotopy Methods in Optimization

L.T. Watson and R.T. Haftka TR 88 November 14, 1988 MODERN HOMOTOPY METHODS IN OPTIMIZATION

Layne. T. Watson Department of Computer Science

Raphael T. Haftka Department of Aerospace and Ocean Engineering

Virginia Polytechnic Institute & State University Blacksburg, VA

Abstract.

Probability-one homotopy methods are a class of algorithms for solving nonlinear sys-tems of equations that are accurate, robust, and converge from an arbitrary starting point almost surely. These new techniques have been successfully applied to solve Brouwer fixed point prob-lems, polynomial systems of equations, and discretizations of nonlinear two-point boundary value problems based on shooting, finite differences, collocation, and finite elements. This paper sum- marizes the theory of globally convergent homotopy algorithms for unconstrained and constrained optimization, and gives some examples of actual application of homotopy techniques to engineering optimization problems.

1. Introduction.

Continuation in various forms has been used for a long time in mathematics and engineering, with such names as parameter continuation, incremental loading, displacement incrementation, imbedding, invariant imbedding, continuous Newton, and homotopy. The state-of-the-art of continuation methods was thoroughly surveyed in (1), and more recently in (17J. Recent mathematical developments have led to a whole new class of continuation methods known as probability-one homolopy algorithms, which have been successfully applied to solve Brouwer fixed point problems, polynomial systems of equations, and discretizations of nonlinear two- point boundary value problems based on shooting, finite differences, collocation, and finite elements. These new techniques have recently begun to be applied to optimization, and have found significant application in solving some engineering optimization problems. Homotopy methods are very powerful, robust, accurate, numerically stable, and almost univer-sally applicable, but also often prohibitively expensive. They are particularly suitable for highly nonlinear problems for which initial solution estimates are difficult to obtain. Properly imple- mented they are indeed globally convergent, i.e., converge to a solution from an arbitrary starting point. This (costly) global convergence feature is their forte, but also makes them inappropriate for mildly nonlinear problems or problems for which a good initial estimate of the solution is easily obtained. The objectives of this paper are to summarize the basic theory of globally convergent homo-topy methods relevant to optimization, to show how homotopy algorithms may be applied to solve optimization problems, and to give some actual engineering applications. Section 2 gives an intu-itive explanation of what is different about the new globally convergent homotopy algorithms, and Section 3 brief...