×

zbMATH — the first resource for mathematics

Modern homotopy methods in optimization. (English) Zbl 0693.65046
Authors’ summary: Probability-one homotopy methods are a class of algorithms for solving nonlinear systems 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 problems, polynomial systems of equations, and discretizations of nonlinear two-point boundary value problems based on shooting, finite differences, collocation and finite elements. This paper summarizes 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.
Reviewer: E.Allgower

MSC:
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
65H10 Numerical computation of solutions to systems of equations
Software:
PITCON
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allgower, E.; Georg, K., Simplicial and continuation methods for approximating fixed points, SIAM rev., 22, 28-85, (1980) · Zbl 0432.65027
[2] Watson, L.T., Numerical linear algebra aspects of globally convergent homotopy methods, (), SIAM rev., 28, 529-545, (1986) · Zbl 0608.65028
[3] Chow, S.N.; Mallet-Paret, J.; Yorke, J.A., Finding zeros of maps: homotopy methods that are constructive with probability one, Math. comp., 32, 887-899, (1978) · Zbl 0398.65029
[4] Watson, L.T.; Wang, C.Y., A homotopy method applied to elastica problems, Internat. J. solids and structures, 17, 29-37, (1981) · Zbl 0452.73071
[5] Watson, L.T.; Yang, W.H., Optimal design by a homotopy method, Applicable anal., 10, 275-284, (1980) · Zbl 0448.73083
[6] Watson, L.T., A globally convergent algorithm for computing fixed points of C^{2} maps, Appl. math. comput., 5, 297-311, (1979) · Zbl 0445.65032
[7] Watson, L.T.; Billups, S.C.; Morgan, A.P., {\schompack}: A suite of codes for globally convergent homotopy algorithms, (), ACM trans. math. software, 13, 281-310, (1987) · Zbl 0626.65049
[8] Scarf, H., The comutation of economic equilibria, (1973), Yale Univ. Press New Haven, CT
[9] Rheinboldt, W.C.; Burkardt, J.V., Algorithm 596: A program for a locally parameterized continuation process, ACM trans. math. software, 9, 236-241, (1983)
[10] Mejia, R., {\scconkub}: A conversational path-follower for systems of nonlinear equations, J. comput. phys., 63, 67-84, (1986) · Zbl 0588.65037
[11] Watson, L.T., Computational experience with the Chow-Yorke algorithm, Math. programming, 19, 92-101, (1980) · Zbl 0436.90096
[12] Watson, L.T., Solving the nonlinear complementarity problem by a homotopy method, SIAM J. control optim., 17, 1, 36-46, (1979) · Zbl 0407.90083
[13] Watson, L.T.; Bixler, J.P.; Poore, A.B., Continuous homotopies for the linear complementarity problem, () · Zbl 0673.65035
[14] A.B. Poore and D. Soria, Continuation algorithms for linear programming, in preparation.
[15] Poore, A.B.; Al-Hassan, Q., The expanded Lagrangian system for constrained optimization problems, SIAM J. control optim., 26, 417-427, (1988) · Zbl 0643.90081
[16] Bertaekas, D.P., Constrained optimization and Lagrange multiplier methods, (1982), Academic Press New York
[17] Shin, Y.S.; Haftka, R.T.; Watson, L.T.; Plaut, R.H., Tracing structural optima as a function of available resources by a homotopy method, Comput. methods appl. mech. engrg., 70, 151-164, (1988) · Zbl 0636.49014
[18] Kreisselmeier, G.; Steinhauser, R., Systematic control design by optimizing a vector performance index, (), 113-117 · Zbl 0443.49028
[19] Barthelemy, J.-F.M.; Riley, M.F., Improved multi-level optimization approach for the design of complex engineering systems, Aiaa j., 26, 353-360, (1988)
[20] Managasarian, O.L., Equivalence of the complementarity problem to a system of nonlinear equations, SIAM J. appl. math., 31, 89-92, (1976) · Zbl 0339.90051
[21] Vasudevan, G.; Watson, L.T.; Lutze, F.H., A homotopy approach for solving constrained optimization problems, ()
[22] Morgan, A.P., Solving polynomial systems using continuation for scientific and engineering problems, (1987), Prentice-Hall Englewood Cliffs, NJ · Zbl 0733.65031
[23] Watson, L.T.; Fenner, D., Chow-Yorke algorithm for fixed points or zeros of C^{2} maps, ACM trans. math. software, 6, 252-260, (1980) · Zbl 0445.65033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.