×

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
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Allgower, E.; Georg, K., Simplicial and continuation methods for approximating fixed points, SIAM Rev., 22, 28-85 (1980) · Zbl 0432.65027
[2] 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] ACM Trans. Math. Software, 13, 281-310 (1987) · Zbl 0626.65049
[8] Scarf, H., The comutation of Economic Equilibria (1973), Yale Univ. Press: 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., conkub: 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, (Tech. Rept. TR-87-38 (1987), Dept. of Computer Sci., VPI&SU: Dept. of Computer Sci., VPI&SU Blacksburg, VA) · Zbl 0673.65035
[14] A.B. Poore and D. Soria, Continuation algorithms for linear programming, in preparation.; 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: 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, (Proc. IFAC Symp. on Computer Aided Design of Control Systems. Proc. IFAC Symp. on Computer Aided Design of Control Systems, Zurich, Switzerland (1979)), 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, (Tech. Rept. TR-88-50 (1988), Dept. of Computer Sci., VPI&SU: Dept. of Computer Sci., VPI&SU Blacksburg, VA)
[22] Morgan, A. P., Solving Polynomial Systems Using Continuation for Scientific and Engineering Problems (1987), Prentice-Hall: 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.