Browse Prior Art Database

A Homotopy~Approach for Solving Constrained Optimization Problems

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

Publishing Venue

Software Patent Institute

Related People

G. Vasudevan: AUTHOR [+5]

Abstract

A homotopy approach for solving constrained parameter optimization problems is examined. The first order necessar3~ conditions, with tire complementarily conditions represented using a technique due to ll-Tangasarian, are solved. The equations are augmented to avoid singularities which occur when the active constraint changes. The Chow- Yorke algorithm is used to track the homotopy path leading to the solution to the desired problem at the terminal point. A simple example which illustrates the technique, and an application to a fuel optimal orbital transfer problem are presented.

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

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

. A Homotopy~Approach for Solving Constrained Optimization Problems

G. Vasudevan, L.T. Watson and F. H. Lutze

TR 88 Homotopy Approach for Solving Constrained Optimization Problems

G. Vasudevan ', L.T. Watson'? and F.H. Lutze =

Abstract

A homotopy approach for solving constrained parameter optimization problems is examined. The first order necessar3~ conditions, with tire complementarily conditions represented using a technique due to ll-Tangasarian, are solved. The equations are augmented to avoid singularities which occur when the active constraint changes. The Chow- Yorke algorithm is used to track the homotopy path leading to the solution to the desired problem at the terminal point. A simple example which illustrates the technique, and an application to a fuel optimal orbital transfer problem are presented.

Introduction

R In solving constrained parameter optimization problems, a known solution to some problem is often used as an initial estimate for solving a similar problem with different constants. The reasoning behind this being that if there are small variations in the problem constants, the problem characteristics are essentially unchanged, and the solution to the new problem should be in the neighborhood of the initial guess. Unfortunately, as many would attest, this procedure often fails to provide a solution. In spite of these failures, this method of obtaining solutions by systematically varying the problem constants is very appealing. The procedure of varying the system constants either in a discrete manner or in a continuous manner has been successfully applied to a number of problems. Gfrerer, Guddat and blacker' proposed an algorithm based on a this continuation idea coupled with an active constraint set strategy to solve constrained optimization problems. The algorithm starts with the solution to some known problem, with an index set keeping track of the active constraints. An estimate of the solution at the next parameter point is obtained based on the Jacobian matrix at the current point. This estimate is then used in a corrector iteration. The inequality constraints and their associated Lagrange multipliers are monitored. If at any step the status of an ' Graduate Student, Dept of Aerospace Engineering. t Professor. Dept. of Computer Science. t Professor, Dept. of Aerospace Engineering., . V'uginia Polytechnic Institute & State University. nequality constraint changes, the precise point at which it changes is found. The index set is then updated and the method proceeds as before until the desired final values of the parameters are attained.

This method, however, fails when the Jacobian matrix becomes singular, which can occur if the parameters are not monotonic with respect to the continuation parameter or if they are multivalued. Under these conditions, this method stops. This situation, however, can be tackled using Kelley's algorithm' for hand...