Bifurcation problems in nonlinear parametric programming.(English)Zbl 0639.90084
Summary: The nonlinear parametric programming problem is reformulated as a closed system of nonlinear equations so that numerical continuation and bifurcation techniques can be used to investigate the dependence of the optimal solution on the system parameters. This system, which is motivated by the Fritz John first-order necessary conditions, contains all Fritz John and all Karush-Kuhn-Tucker points as well as local minima and maxima, saddle points, feasible and nonfeasible critical points. Necessary and sufficient conditions for a singularity to occur in this system are characterized in terms of the loss of a complementarity condition, the linear dependence of the gradients of the active constraints, and the singularity of the Hessian of the Lagrangian on a tangent space. Any singularity can be placed in one of seven distinct classes depending upon which subset of these three conditions hold true at a solution. For problems with one parameter, we analyze simple and multiple bifurcation of critical points from a singularity arising from the loss of the complementarity condition, and then develop a set of conditions which guarantees the unique persistence of a minimum through this singularity.
MSC:
| 90C30 | Nonlinear programming |
| 90C31 | Sensitivity, stability, parametric optimization |
| 49M37 | Numerical methods based on nonlinear programming |
Keywords:
nonlinear parametric programming;closed system of nonlinear equations;numerical continuation and bifurcation techniques;optimal solution;active constraints;singularity;simple and multiple bifurcation;unique persistence of a minimumCite
Full Text:DOI
References:
| [1] | E. L. Allgower and K. Georg, ”Predictor-Corrector and simplical methods for approximating fixed points and zero points of nonlienar mappings,” in: A. Bachem, M. Grötschel and B. Korte, eds.,Mathematical Programming The State of the Art (Springer-Verlag, New York, 1983) pp. 15–36. ·Zbl 0541.65032 |
| [2] | B. Bank, J. Guddat, D. Klatte, B. Kummer and K. Tammer,Nonlinear Parametric Optimization (Birkhauser-Verlag, Basel, 1983). ·Zbl 0502.49002 |
| [3] | S.-N. Chow and J.K. Hale,Methods of Bifurcation Theory (Springer-Verlag, New York, 1982). ·Zbl 0487.47039 |
| [4] | E.J. Doedel, ”AUTO: A program for the automatic bifurcation analysis of autonomous systems,” Cong. Num. 30 (1981) 265–284,Proceedings of the Tenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, Canada). |
| [5] | E.J. Doedel, A.D. Jepson and H.B. Keller, ”Numerical methods for Hopf bifurcation and continuation of periodic solution paths,” in: R. Glowinski and J.L. Lions, eds.,Computing Methods in Applied Sciences and Engineering VI (North-Holland, Amsterdam, 1984) pp 127–138. ·Zbl 0566.65041 |
| [6] | A.V. Fiacco,Introduction to Sensitivity and Stability Analysis in Nonlinear Programming (New York, Academic Press, 1983). ·Zbl 0543.90075 |
| [7] | A.V. Fiacco,Mathematical Programming Study 21: Sensitivity, Stability and Parametric Analysis (North-Holland, Amsterdam, 1984). ·Zbl 0602.00009 |
| [8] | R. Fletcher,Practical Methods of Optimization Vol. 2 (John Wiley and Sons, New York, 1981). ·Zbl 0474.65043 |
| [9] | P.E. Gill, W. Murray, M. Wright,Practical Optimization (Academic Press, London, 1981). ·Zbl 0503.90062 |
| [10] | G.H. Golub and C.F. Van Loan,Matrix Computations (The Johns Hopkins University Press, Baltimore, 1983). ·Zbl 0559.65011 |
| [11] | M. Golubitsky and D.G. Schaeffer,Singularities and Groups in Bifurcation Theory, Vol. 1 (Springer-Verlag, New York, 1985). ·Zbl 0607.35004 |
| [12] | C.D. Ha, ”Application of degree theory in stability of the complementarity problem,” to appear inMathematics of Operations Research. ·Zbl 0616.90082 |
| [13] | G. Iooss and D.D. Jospeh,Elementary Stability and Bifurcation Theory (Springer-Verlag, New York, 1980). |
| [14] | H.Th. Jongen, P. Jonker and F. Twilt, ”On one-parameter families of sets defined by (in)equality constraints,”Nieuw Archief Voor Wiskunde, 3 (1982) 307–322. ·Zbl 0518.58032 |
| [15] | H.Th. Jongen, P. Jonker and F. Twilt, ”Critical sets in parametric optimization,”Mathematical Programming 34 (1984) 333–353. ·Zbl 0599.90114 ·doi:10.1007/BF01582234 |
| [16] | H.Th. Jongen, P. Jonker and F. Twilt, ”One-parameter families of optimization problems: Equality constraints,”Journal of Optimization Theory and Applications 48 (1986) 141–161. ·Zbl 0556.90086 |
| [17] | H.Th. Jongen, P. Jonker and F. Twilt,Nonlinear Optimization in \(\mathbb{R}\) n : 1.Morse Theory, Chebyshev Approximation (Verlag Peter Lang, New York, 1983). ·Zbl 0527.90064 |
| [18] | T. Kato,Perturbation Theory for Linear Operators (Springer-Verlag, New York, 1966). ·Zbl 0148.12601 |
| [19] | H.B. Keller, ”Numerical solution of bifurcation and nonlinear eigenvalue problems,” in: P.H. Rabinowitz, ed.,Applications of Bifurcation Theory (Aacademic Press, New York, 1977) 359–384. ·Zbl 0581.65043 |
| [20] | M. Kojima, ”Strongly stable solutions in nonlinear programs,” in: S.M. Robinson, ed.,Analysis and Computation of Fixed Points (Academic Press, New York, 1980) 93–138. |
| [21] | M. Kojima and R. Hirabayashi, ”Continuous deformation of nonlinear programs,” in: A.V. Fiacco, ed.,Mathematical Programming Study 21: Sensitivity, Stability and Parametric Analysis (North-Holland, Amsterdam, 1984). ·Zbl 0569.90074 |
| [22] | T. Kupper, H.D. Mittelmann and H. Weber,Numerical Methods for Bifurcation Problems (Birkhauser-Verlag, Boston, 1984). |
| [23] | O.L. Mangasarian and S. Fromovitz, ”The Fritz John necessary optimality conditions in the presence of equality and inequality constraints,”Journal of Mathematical Analysis and Applications 17 (1967) 37–47. ·Zbl 0149.16701 ·doi:10.1016/0022-247X(67)90163-1 |
| [24] | O.L. Mangasarian,Nonlinear Programming (Robert E. Krieger Publishing Company, Huntington, New York, 1979). |
| [25] | G.P. McCormick,Nonlinear Programming: Theory, Algorithms and Applications (John Wiley & Sons, New York, 1983). ·Zbl 0563.90068 |
| [26] | J. Palis and F. Takens, ”Stability of parametrized families of gradient vector fields,”Annals of Mathematics 118 (1983) 383–421. ·Zbl 0533.58018 ·doi:10.2307/2006976 |
| [27] | W.C. Rheinboldt,Numerical Analysis of Parametrized Nonlinear Equations (John Wiley, New York, 1985). ·Zbl 0583.65038 |
| [28] | W.C. Rheinboldt, ”Solution fields of nonlinear equations and continuation methods,”SIAM Journal on Numerical Analysis 17 (1980) 221–237. ·Zbl 0431.65035 ·doi:10.1137/0717020 |
| [29] | W.C. Rheinboldt and J.V. Burkardt, ”A locally parametrized continuation process,”Association of Computing Machinery Transactions on Mathematical Software 9 (1983) 215–235. ·Zbl 0516.65029 ·doi:10.1145/357456.357460 |
| [30] | S.M. Robinson, ”Stability theory for systems of inequalities, part II,”SIAM Journal of Numerical Analysis 13 (1976) 497–513. ·Zbl 0347.90050 ·doi:10.1137/0713043 |
| [31] | S.M. Robinson, ”Strongly regular generalized equations,”Mathematics of Operations Research 5 (1980) 43–62. ·Zbl 0437.90094 ·doi:10.1287/moor.5.1.43 |
| [32] | Y. Sawaragi, H. Nakayama and T. Tanino,Theory of Multiobjective Optimization (Academic Press, New York, 1985). ·Zbl 0566.90053 |
| [33] | S. Schecter, ”Structure of the first-order solution set of a class of nonlinear programs with parameters,”Mathematical Programming 34 (1986) 84–110. ·Zbl 0582.90093 ·doi:10.1007/BF01582165 |
| [34] | D. Siersma, ”Singularties of functions on boundaries, corners, etc.,”Quarterly Journal of Mathematics Oxford, Second Series 32 (1981) 119–127. ·doi:10.1093/qmath/32.1.119 |
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.
