Abstract

This survey article reflects the topological and inverse behaviour of generalized semi-infinite optimization problems P(f,h,g,u,v)\mathcal{P}(f,h,g,u,v) and presents the analytical methods. These differentiable problems admit an infinite set Y(x) of inequality constraints y which depends on the state x. We extend our previous investigations ["Generalized Semi-Infinite Optimization and Related Topics", Research and Expositions in Mathematics 29, Heldermann Verlag (2003)] based on research of Guddat, Jongen, Rueckmann, Twilt and others. Under suitable assumptions on boundedness and qualifying conditions on lower y-stage and upper x-stage, we present manifold, continuity and global stability properties of the feasible set M[h, g, u, v], and corresponding structural stability properties of P(f,h,g,u,v)\mathcal{P}(f,h,g,u,v) referring to slight data perturbations. Hereby, the character of our investigation is essentially specialized by the linear independence constraint qualification locally imposed on Y(x). The achieved results are important for algorithm design and convergence. Two extensions refer to unboundedness and nondifferentiable max-min-type objective functions. In the course of explanation, the perturbational approach gives rise to study inverse problems of reconstruction. We trace them into optimal control of ordinary differential equations, and indicate related investigations in heating processes, continuum mechanics and discrete tomography. Throughout the article, we realize discrete-combinatorial aspects and methods.

Author information

Contact details are reproduced from the original publication and may be historical.

Gerhard-Wilhelm Weber

Fakultät für Mathematik, Technische Universität, Reichenhainer Straße, 09126 Chemnitz, Germany

Keywords

  • Generalized semi-infinite optimization
  • constraint qualification
  • structural stability
  • inverse problem
  • reconstruction
  • nondifferentiability
  • optimal control
  • directed graph
  • discrete tomography

Mathematics Subject Classification

05C20 49J15 90C34

References

  1. A. Alpers, P. Gritzmann, L. Thorens: Stability and instability in discrete tomography, Munich University of Technology, Germany, preprint (2001).https://doi.org/10.1007/3-540-45576-0_11Google Scholar
  2. H. Amann: Gewöhnliche Differentialgleichungen, Walter de Gruyter, Berlin, New York (1983).Google Scholar
  3. F.-J. Barthold: Zur Kontinuumsmechanik inverser Geometrieprobleme, Habilitation Thesis, Braunschweig University of Technology, Germany (2000).Google Scholar
  4. C. Berge: Espaces Topologique, Fonctions Multivoque, Dunod, Paris (1966).Google Scholar
  5. A. Bertram, T. Böhlke, N. Gaffke, B. Heiligers, R. Offinger: On the generation of discrete isotropic orientation distribution for linear elastic crystals, University of Magdeburg, Germany, Faculty of Engineering, Faculty of Mathematics, preprint (2000).Google Scholar
  6. M. Breuss, B. Fischer, A. Meister: The unsteady thermoregulation of premature infants – a model and its application, in: Discrete Modelling and Discrete Algorithms in Continuum Mechanics, Th. Sonar, I. Thomas (eds.), Logos Verlag, Berlin (2001) 47–56.Google Scholar
  7. Y. Censor: Binary steering in discrete tomography reconstruction with sequential and simultaneous iterative algorithms, University of Haifa, Israel, preprint (2001).https://doi.org/10.1016/S0024-3795(01)00470-0Google Scholar
  8. L.-Y. Chen, N. Goldenfeld, Y. Oono, C. Paquette: Selection, stability and renormalization, Physica A 204 (1994) 111–133.https://doi.org/10.1016/0378-4371(94)90421-9Google Scholar
  9. R. Diestel: Graphentheorie, Springer (1996).https://doi.org/10.1007/978-3-662-07551-7Google Scholar
  10. A.-L. Dontchev, W.-W. Hager, A.-B. Poore, B. Yang: Optimality, stability, and convergence in nonlinear control, Appl. Math. Optim. 31 (1995) 297–326.https://doi.org/10.1007/BF01215994Google Scholar
  11. V. Fragnelli, F. Patrone, E. Sideri, S. Tijs: Balanced games arising from infinite linear models, University of Tilburg, Netherland, preprint (1999).https://doi.org/10.1007/s001860050077Google Scholar
  12. N. Gaffke, B. Heiligers: Algorithms for optimal design with applications to multiple polynomial regression, Metrika 42 (1995) 173–190.https://doi.org/10.1007/BF01894298Google Scholar
  13. A. Geletu, A. Hoffmann: Solving generalized semi-infinite programming problems via global optimization, Ilmenau University of Technology, submitted for publication in the proceedings of Workshop: Smooth and Nonsmooth Optimization – Theory and Applications, Rotterdam, preprint (2001).Google Scholar
  14. N. Gaffke, B. Heiligers: Approximative designs for polynomial regression: invariance, admissibility, and optimality, in: Handbook of Statistics 13, S. Ghosh, C. R. Rao (eds.), Elsevier Science (1996) 1149–1199.https://doi.org/10.1016/S0169-7161(96)13032-7Google Scholar
  15. R. J. Gardner, P. Gritzmann: Uniqueness and complexity in discrete tomography, in: Discrete Tomography – Foundations, Algorithms and Applications, G. T. Herman, A. Kuba (eds.), Birkhäuser Verlag, Boston, Basel, Berlin (1999) 85–113.https://doi.org/10.1007/978-1-4612-1568-4_4Google Scholar
  16. M. A. Goberna, M. A. López: Linear Semi-Infinite Optimization, John Wiley, New York (1998).Google Scholar
  17. J. Guddat, H. Th. Jongen: Structural stability and nonlinear optimization, Optimization 18 (1987) 617–631.https://doi.org/10.1080/02331938708843275Google Scholar
  18. J. Guddat, H. Th. Jongen, J.-J. Rückmann: On stability and stationary points in nonlinear optimization, J. Austral. Math. Soc., Ser. B 28 (1986) 36–56.https://doi.org/10.1017/S033427000000518XGoogle Scholar
  19. A. Gupta: Embedding tree metrics into low-dimensional Euclidean spaces, Discrete and Computational Geometry 24 (2000) 105–116.https://doi.org/10.1007/s004540010020Google Scholar
  20. M. Haase: An exploration of self-similar structures with wavelets, in: Similarity Methods, B. Kröplin, St. Rudolph, St. Brückner (eds.), Institut für Statik und Dynamik der Luft- und Raumfahrtkonstruktionen, University of Stuttgart (2000) 183–192.Google Scholar
  21. M. R. Hestenes: Calculus of Variations and Optimal Control Theory, John Wiley, New York (1966).Google Scholar
  22. R. Hettich, H. Th. Jongen: Semi-infinite programming: conditions of optimality and applications, in: Optimization Techniques 2, J. Stoer (ed.), Lecture Notes in Control and Information Sci., Springer (1978) 1–11.https://doi.org/10.1007/BFb0006502Google Scholar
  23. R. Hettich, R. Zencke: Numerische Methoden der Approximation und semi-infiniten Optimierung, Teubner, Stuttgart (1982).https://doi.org/10.1007/978-3-322-93108-5Google Scholar
  24. J. E. Higgins, E. Polak: Minimizing pseudoconvex functions on convex compact sets, Journal of Optimization Theory and Applications 65 (1990) 1–27.https://doi.org/10.1007/BF00941156Google Scholar
  25. M. W: Hirsch: Differential Topology, Springer (1976).https://doi.org/10.1007/978-1-4684-9449-5Google Scholar
  26. Th. Ihringer: Diskrete Mathematik, Heldermann (2002).Google Scholar
  27. H. Th. Jongen: personal communication, Alicante, 1999.Google Scholar
  28. H. Th. Jongen, P. Jonker, F. Twilt: Nonlinear Optimization in IRn, I: Morse Theory, Chebychev Approximation, Peter Lang Publ. House, Frankfurt a. M., Bern, New York (1983).Google Scholar
  29. H. Th. Jongen, P. Jonker, F. Twilt: Nonlinear Optimization in IRn, II: Transversality, Flows and Parametric Aspects, Peter Lang Publ. House, Frankfurt a. M., Bern, New York (1986).Google Scholar
  30. H. Th. Jongen, P. Jonker, F. Twilt: Critical sets in parametric optimization, Mathematical Programmming 34 (1986) 333–353.https://doi.org/10.1007/BF01582234Google Scholar
  31. H. Th. Jongen, D. Pallaschke: On linearization and continuous selections of functions, Optimization 19 (1988) 343–353.https://doi.org/10.1080/02331938808843350Google Scholar
  32. H. Th. Jongen, J.-J. Rückmann: On stability and deformation in semi-infinite optimization, in: Semi-Infinite Programming, R. Reemtsen, J.-J. Rückmann (eds.), Kluwer Academic Publishers, Boston, Dortrecht, London (1998) 29–67.https://doi.org/10.1007/978-1-4757-2868-2_2Google Scholar
  33. H. Th. Jongen, J.-J. Rückmann, O. Stein: Generalized semi-infinite optimization: a first order optimality condition and examples, Mathematical Programming 83 (1998) 145–158.https://doi.org/10.1007/BF02680555Google Scholar
  34. H. Th. Jongen, E. Triesch: Optimization Theory, Kluwer Academic Publishers, Boston, Dortrecht, London (2001).Google Scholar
  35. H. Th. Jongen, F. Twilt, G.-W. Weber: Semi-infinite optimization: structure and stability of the feasible set, J. Optim. Theory Appl. 72 (1992) 529–552.https://doi.org/10.1007/BF00939841Google Scholar
  36. H. Th. Jongen, G.-W. Weber: Nonlinear optimization: characterization of structural stability, J. Global Optimization 1 (1991) 47–64.https://doi.org/10.1007/BF00120665Google Scholar
  37. H. Th. Jongen, G.-W. Weber: Nonconvex optimization and its structural frontiers, in: Modern Methods in Optimization, W. Krabs, J. Zowe (eds.), Lecture Notes in Econom. and Math. Systems 378 (1992) 151–203.https://doi.org/10.1007/978-3-662-02851-3_6Google Scholar
  38. C. Kaiser, W. Krabs: Ein Problem der semi-infiniten Optimierung im Maschinenbau und seine Verallgemeinerung, working paper, Darmstadt University of Technology, Department of Mathematics (1986).Google Scholar
  39. A. Kaplan, R. Tichatschke: On the numerical treatment of a class of semi-infinite terminal problems, Optimization 41 (1997) 1–36.https://doi.org/10.1080/02331939708844323Google Scholar
  40. M. Kojima: Stable stationary solutions in nonlinear programs, in: Analysis and Computation of Fixed Points, S. M. Robinson (ed.), Academic Press, New York (1980) 93–138.https://doi.org/10.1016/B978-0-12-590240-3.50009-4Google Scholar
  41. M. Kojima, R. Hirabayashi: Continuous deformations of nonlinear programs, Math. Programming Study 21 (1984) 150–198.https://doi.org/10.1007/BFb0121217Google Scholar
  42. W. Krabs: Optimization and Approximation, John Wiley, New York (1979).Google Scholar
  43. W. Krabs: On time-minimal heating or cooling of a ball, International Series of Numerical Mathematics 81, Birkhäuser, Basel (1987) 121–131.https://doi.org/10.1007/978-3-0348-6656-9_11Google Scholar
  44. E. Kropat, St. Pickl, A. Rößler, G.-W. Weber: A new algorithm from semi-infinite optimization for a problem from time-minimal optimal control, J. Computational Technologies 5(4) (2000) 67–81.Google Scholar
  45. E. B. Lee, L. Markus: Foundations of Optimal Control Theory, John Wiley, New York (1969).Google Scholar
  46. E. Levitin, R. Tichatschke: A branch and bound approach for solving a class of generalized semi-infinite programming problems, University of Trier, submitted for publication, preprint (1996).Google Scholar
  47. L. A. Ljusternik, W. I. Sobolew: Elemente der Funktionalanalysis, Akademie Publ. House, Berlin (1960).https://doi.org/10.1515/9783112719930Google Scholar
  48. K. Malanowski, H. Maurer: Sensitivity analysis for parametric control problems with control-state constraints, Comp. Optim. Appl. 5 (1996) 253–283.https://doi.org/10.1007/BF00248267Google Scholar
  49. O. L. Mangasarian, S. Fromovitz: The Fritz John necessary optimality conditions in the presence of equality and inequality constraints, J. Math. Anal. Appl. 17 (1967) 37–47.https://doi.org/10.1016/0022-247X(67)90163-1Google Scholar
  50. H. Maurer, S. Pickenhain: Second-order sufficient conditions for control problems with control-state constraints, J. Optim. Theory Appl. 86 (1995) 649–667.https://doi.org/10.1007/BF02192163Google Scholar
  51. St. Pickl, G.-W. Weber: An algorithmic approach by linear programming problems in generalized semi-infinite optimization, J. Computational Technologies 5(3) (2000) 62–82.Google Scholar
  52. St. Pickl, G.-W. Weber: Optimal control of heating processes – with special emphasis on earth warming, in: Operations Research Proceedings 2001, P. Chamoni, R. Leisten, A. Martin, J. Minnemann, H. Stadler (eds.) (2002) 247–254.https://doi.org/10.1007/978-3-642-50282-8_31Google Scholar
  53. L. S. Pontryagin, V. G. Boltryanski, R. V. Gamkrelidze, E. F. Mishchenko: The Mathematical Theory of Optimal Processes, Interscience Publishers, John Wiley, New York (1962).Google Scholar
  54. R. Reemtsen, J.-J. Rückmann: Semi-Infinite Programming, Kluwer Academic Publishers, Boston, Dordrecht, London (1998).https://doi.org/10.1007/978-1-4757-2868-2Google Scholar
  55. R. T. Rockafellar: Convex Analysis, Princeton University Press (1970).https://doi.org/10.1515/9781400873173Google Scholar
  56. J.-J. Rückmann: Stability of noncompact feasible sets in nonlinear optimization, in: Parametric Optimization and Related Topics III, J. Guddat, H. Th. Jongen, B. Kummer, F. Nožička (eds.), Peter Lang Publ. House, Frankfurt a. M., Bern, New York (1993) 163–214.Google Scholar
  57. J.-J. Rückmann: On the existence and uniqueness of stationary points in semi-infinite optimization, Mathematical Programming, Ser. A 86 (1999) 387–415.https://doi.org/10.1007/s101070050095Google Scholar
  58. J.-J. Rückmann, G.-W. Weber: Semi-infinite optimization: excisional stability of noncompact feasible sets, Sibirskij Mathematicheskij Zhurnal 39 (1998) 129–145 (in Russian). An English version of this article appeared in Siberian Mathematical Journal 39 (1998) 113–125.https://doi.org/10.1007/BF02732366Google Scholar
  59. T. Schwartz, M. Sharir: On the piano movers problem I. The case of two-dimensional rigid polygonal body moving amidst polygonal barriers, Comm. Pure Appl. Math. 36 (1983) 345–398.https://doi.org/10.1002/cpa.3160360305Google Scholar
  60. T. Schwartz, M. Sharir: On the piano movers problem II. General techniques for computing topological properties of real algebraic manifolds, Advances in Applied Mathematics 4 (1983) 298–351.https://doi.org/10.1016/0196-8858(83)90014-3Google Scholar
  61. M. Shub: Global Stability of Dynamical Systems, Springer, Berlin, Heidelberg, New York (1987).https://doi.org/10.1007/978-1-4757-1947-5Google Scholar
  62. Th. Sonar, I. Thomas (eds.): Discrete Modelling and Discrete Algorithms in Continuum Mechanics, proceedings of GAMM workshop (Braunschweig, 2000), Logos Verlag, Berlin (2001).Google Scholar
  63. E. H. Spanier: Algebraic Topology, McGraw-Hill, New York (1966).https://doi.org/10.1007/978-1-4684-9322-1_5Google Scholar
  64. O. Stein: On level sets of marginal functions, Optimization 48 (2000) 43–67.https://doi.org/10.1080/02331930008844493Google Scholar
  65. O. Stein, G. Still: On optimality conditions for generalized semi-infinite programming problems, Journal of Optimization Theory and Applications 104 (2000) 443–458.https://doi.org/10.1023/A:1004622015901Google Scholar
  66. O. Stein, G. Still: On generalized semi-infinite optimization and bilevel optimization, to appear in European J. Operational Research.Google Scholar
  67. O. Stein, G. Still: Solving semi-infinite optimization problems with interior point techniques, Aachen University of Technology, Chair C, submitted for publication, preprint (2001).Google Scholar
  68. G. Still: Generalized semi-infinite programming: Theory, methods, European J. Operational Research 119 (1999) 301–313.https://doi.org/10.1016/S0377-2217(99)00132-0Google Scholar
  69. G. Still: Generalized semi-infinite programming: Numerical aspects, Optimization 49(3) (2001) 223–242.https://doi.org/10.1080/02331930108844531Google Scholar
  70. G. Still: Discretization in semi-infinite programming: Rate of convergence, to appear in Math. Programming (2002).https://doi.org/10.1007/s101070100239Google Scholar
  71. G.-W. Weber: Charakterisierung struktureller Stabilität in der nichtlinearen Optimierung, Doctoral Thesis, Aachen University of Technology, Department of Mathematics, Aachener Beiträge zur Mathematik 5, H. H. Bock, H. Th. Jongen, W. Plesken (eds.), Augustinus Publ. House, Aachen (1992).Google Scholar
  72. G.-W. Weber: Minimization of a max-type function: characterization of structural stability, in: Parametric Optimization and Related Topics III, J. Guddat, H. Th. Jongen, B. Kummer, F. Nožička (eds.), Peter Lang Publ. House, Frankfurt a. M., Bern, New York (1993) 519–538.Google Scholar
  73. G.-W. Weber: On the topology of parametric optimal control, J. Austral. Math. Soc., Ser. B 39 (1998) 463–497.https://doi.org/10.1017/S033427000000775XGoogle Scholar
  74. G.-W. Weber: Optimal control theory: on the global structure and connections with optimization. Part 1, J. Computational Technologies 4(2) (1999) 3–25.Google Scholar
  75. G.-W. Weber: Generalized semi-infinite optimization: on some foundations, J. Computational Technologies 4(3) (1999) 41–61.Google Scholar
  76. G.-W. Weber: Generalized semi-infinite optimization: on iteration procedures and topological aspects, in: Similarity Methods, B. Kröplin, St. Rudolph, St. Brückner (eds.), Institute of Statics and Dynamics of Aviation and Space-Travel Constructions (1998) 281–309.Google Scholar
  77. G.-W. Weber: Generalized Semi-Infinite Optimization and Related Topics, Habilitation Thesis, Darmstadt University of Technology, Department of Mathematics (1999/2000).Google Scholar
  78. G.-W. Weber: Approaches to mechanics from discrete and nonlinear optimization and control, lecture held at Workshop: Discrete Modelling and Discrete Algorithms in Continuum Mechanics, Th. Sonar, I. Thomas (org.), Braunschweig (November 2000).Google Scholar
  79. G.-W. Weber: Impulses from results of inverse problems to discrete tomography, lecture held at Workshop: The Mathematics of Discrete Tomography, R. J. Gardner, P. Gritzmann (org.), Oberwolfach (December 2000).https://doi.org/10.1016/S1571-0653(05)80097-6Google Scholar
  80. G.-W. Weber: Generalized semi-infinite optimization: theory and applications in optimal control and discrete optimization, to appear in: Optimality Conditions, Generalized Convexity and Duality in Vector Optimization, J. Statistics and Management Systems 5, A. Cambini, L. Martein (eds.) (2002).https://doi.org/10.1080/09720510.2002.10701064Google Scholar
  81. G.-W. Weber: Generalized semi-infinite minimization of max-min type functions: characterization of structural stability, preprint, University of Cologne, Center of Applied Computer Science, in preparation.Google Scholar
  82. W. W. E. Wetterling: Definitheitsbedingungen für relative Extrema bei Optimierungs- und Approximationsaufgaben, Numer. Math. 15 (1970) 122–136.https://doi.org/10.1007/BF02165377Google Scholar

Suggested citation

G.-W. Weber. “On the Topology of Generalized Semi-Infinite Optimization.” Journal of Convex Analysis 9 (2002), No. 2, 665–691. https://doi.org/10.68381/jca09039

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2002. Rights now held by Banach Press.