×

zbMATH — the first resource for mathematics

Characterizing optimality in mathematical programming models. (English) Zbl 0653.90073
Summary: This paper is a survey of basic results that characterize optimality in single- and multi-objective mathematical programming models. Many people believe, or want to believe, that the underlying behavioural structure of management, economic, and many other systems, generates basically ‘continuous’ processes. This belief motivates our definition and study of optimality, termed ‘structural’ optimality. Roughly speaking, we say that a feasible point of a mathematical programming model is structurally optimal if every improvement of the optimal value function, with respect to parameters, results in discontinuity of the corresponding feasible set of decision variables. This definition appears to be more suitable for many applications and it is also more general than the usual one: every optimum is a structural optimum but not necessarily vice versa. By characterizing structural optima, we obtain some new, and recover the familiar, optimality conditions in nonlinear programming.
The paper is self-contained. Our approach is geometric and inductive: we develop intuition by studying finite-dimensional models before moving on to abstract situations.

MSC:
90C31 Sensitivity, stability, parametric optimization
49K27 Optimality conditions for problems in abstract spaces
90C30 Nonlinear programming
90C48 Programming in abstract spaces
49K40 Sensitivity, stability, well-posedness
54C10 Special maps on topological spaces (open, closed, perfect, etc.)
54C60 Set-valued maps in general topology
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abrams, R. A. and Kerzner, L.: A simplified test for optimality, J. Optim. Theory Applic. 25 (1978), 161-170. · Zbl 0352.90047
[2] Avriel, M.: Nonlinear Programming: Analysis and Methods, Prentice-Hall, Englewood Cliffs, New Jersey, 1976. · Zbl 0361.90035
[3] Bank, B., Guddat, J., Klatte, D., Kummer, B., and Tammer, K.: Nonlinear Parametric Optimization, Akademie-Verlag, Berlin, 1982.
[4] Barbu, V. and Precupanu, Th.: Convexity and Optimization in Banach Spaces, Sijthoff and Noordhoff, Alphen aan de Rijn, The Netherlands, 1978.
[5] Ben-Israel, A. and Mond, B.: First order optimality conditions for generalized convex functions: A feasible directions approach, Utilitas Math. 25 (1984), 249-262. · Zbl 0523.90072
[6] Ben-Israel, A., Ben-Tal, A., and Zlobec, S.. Optimality in Nonlinear Programming: A Feasible Directions Approach, Wiley-Interscience, New York, 1981. · Zbl 0454.90043
[7] Ben-Tal, A.: Second-order and related extremality conditions in nonlinear programming, J. Optim. Theory Applic. 31 (1980). · Zbl 0416.90062
[8] Ben-Tal, A. and Zowe, J.: Necessary and sufficient optimality conditions for a class of nonsmooth minimization problems, Math. Program. 24 (1982), 70-91. · Zbl 0488.90059
[9] Berge, C.: Topological Spaces, Oliver and Boyd, London, 1963. · Zbl 0114.38602
[10] Borwein, J. M. and Wolkowicz, H.: Characterization of optimality without constraint qualification for the abstract convex program, Math. Progr. Study 19 (1982), 77-100. · Zbl 0495.90085
[11] Carpentier, J., Girard, R., and Scano, E.: Voltage collapse proximity indicators computed from an optimal power flow in Proceedings of the 8th PSCC Conference, Helsinki (1984) pp. 671-688.
[12] Charnes, A. and Cooper, W. W.: Management Models and Industrial Applications to Linear Programming, Wiley, New York, 1961. · Zbl 0107.37004
[13] Charnes, A. and Cooper, W. W.: Constrained extremization models and their use in developing system measures, in M. D.Mesarovi?, (ed.) Views on General Systems Theory, Wiley, New York, 1964, pp. 61-88. · Zbl 0199.22606
[14] Charnes, A. and Zlobec, S.: Stability of efficiency evaluations in data envelopment analysis, Zeit. Operations Research, Series A: Theorie (forthcoming). · Zbl 0671.90080
[15] Clarke, F. H.. Generalized gradients and applications. Trans. AMS 205 (1975) 247-262. · Zbl 0307.26012
[16] Clarke, F. H.: Optimization and Nonsmooth Analysis, Wiley, New York, 1983. · Zbl 0582.49001
[17] Cojocaru, I.: Regions de stabilité dans la programmation linéaire, An. Univ. Bucuresti Mat. 34 (1985), 12-21. · Zbl 0584.90054
[18] Craven, B. D.: On quasidifferentiable optimization, J. Austral. Math. Soc. (Series A) 41 (1980), 64-78. · Zbl 0633.90064
[19] Craven, B. D.: Invex functions and constrained local minima, Bull. Austral. Math. Soc. 24 (1981) 357-366. · Zbl 0452.90066
[20] Craven, B. D., Glover, B. M., and Zlobec, S.: On minimization subject to cone constraints, Numer. Funct. Anal. Optim. 6 (1983), 363-378. · Zbl 0543.49008
[21] Demyanov, V. F. and Vasiliev, L. V.: Nondifferentiable Optimization, Nauka, Moscow, 1981 (in Russian).
[22] Deutsch, F., Pollus, W., and Singer, I.: On set-valued metric projections, Duke Math. J. 40 (1988), 213-221.
[23] El-Hodiri, M. A.: The Karush characterization of constrained extrema of functions of a finite number of variables, UAR Ministry of Treasury Research Memorandum, Series A, No. 3 (1967).
[24] Fiacco, A. V.: Introduction to Sensitivity and Stability Analysis in Nonlinear Programming, Academic Press, New York, 1983. · Zbl 0543.90075
[25] Fiacco, A. V. and Kyparisis, J.: Computable bounds on parametric solutions of convex problems, Math. Progr. 40 (1988), 213-221. · Zbl 0649.90081
[26] Gal, T., Linear parametric programming: A brief survey, Math. Progr. Study 21 (1984), 43-68. · Zbl 0541.90088
[27] Gauvin, J., Directional derivative for the value function in mathematical programming, Proc. Summer School: Nonsmooth Optimization and Related Topics, Erice, Sicily, 1988 (To appear). · Zbl 0665.90086
[28] Gauvin, J. and Janin, R.: Directional behaviour of optimal solutions in nonlinear mathematical programming, Math. Op. Res. (1988) (Fortheoming). · Zbl 0665.90086
[29] Geoflrion, A. M.: Proper efficiency and the theory of vector maximization, J. Math. Anal. Appli. 22 (1968), 618-630. · Zbl 0181.22806
[30] Giannessi, F.: Theorems of the alternative and optimality conditions, J. Optim. Theory Applic. 42 (1984), 331-365. · Zbl 0504.49012
[31] Girsanov, N. V.: Lectures on Mathematical Theory of Extrema Problems, Moscow University Press, 1970 (in Russian). English translation: Lecture notes in Economics and Mathematical Systems 67, Springer-Verlag, New York, 1972.
[32] Guddat, J., Jongen, H. Th., and Rueckmann, J.: On stability and stationary points in nonlinear optimization, J. Austral. Math. Soc., Series B 28 (1986), 36-56. · Zbl 0621.49016
[33] Hanson, M. A., On sufficiency of the Kuhn-Tucker conditions, J. Math. Anal. Applic. 80 (1981), 545-550. · Zbl 0463.90080
[34] Hanson, M. A. and Mond, B.: Further generalizations of convexity in mathematical programming, J. Informat. Optim. Sci. 3 (1982), 25-32. · Zbl 0475.90069
[35] Hestenes, M. R.: Optimization Theory: The Finite Dimensional Case, Wiley, New York, 1975. · Zbl 0327.90015
[36] Hettich, R. and Jongen, H. Th.: On first and second order conditions for local optima for optimization problems in finite dimensions, Meth. Op. Res. 23 (1977), 82-97. · Zbl 0393.90078
[37] Hiriart-Urruty, J. B.: The approximate first order and second order directional derivative for a convex function, in J. P.Cecconi and J. P.Zolezzi, (eds.), Mathematical Theories of Optimization, Lecture Notes in Mathematics, Vol. 979, Springer-Verlag, New York, 1983. · Zbl 0514.90069
[38] Hogan, W. W.: Point-to-set maps in mathematical programming, SIAM Rev. 15 (1973), 591-603. · Zbl 0256.90042
[39] Homenyuk, V. V.: Elements of the Theory of Multi-Objective Optimization, Nauka, Moscow, 1983 (in Russian).
[40] Huang, S.: Regions of stability in mathematical programming models, M.Sc. Thesis, Concordia University, Montreal, September 1988.
[41] Huang, S. and Zlobec, S.: New regions of stability in input optimization, Aplikace Matematiky (1988) (forthcoming). · Zbl 0664.90085
[42] Ioffe, A. D.: Necessary and sufficient conditions for a local minimum. I: A reduction theorem and first order conditions, SIAM J. Control Optim. 17 (1979) 245-250. · Zbl 0417.49027
[43] Ivanovi?, V.: Rules for calculating the required number of transport vehicles, Vojno-Ekonomski Glasnik 2 (No. 1-3) (1940), 1-10 (in Serbo-Croatian).
[44] John, F.: Extremum problems with inequalities as subsidiary conditions, in K. O.Friedricks, O. E.Neugebauer and J. J.Stoker (eds.), Courant Anniversary Volume, Wiley Interscience, New York, 1948. · Zbl 0034.10503
[45] Jongen, H. Th., Jonker, P., and Twilt, F.: On one-parameter families of sets defined by (in)equality constraints, Nieuw Arch. Wiskunde xxx (1982), 307-322. · Zbl 0518.58032
[46] Klatte, D.: On the lower semicontinuity of optimal sets in convex parametric optimization, Math. Program. Studies 10 (1979), 104-109. · Zbl 0404.90087
[47] Krasnov, M. I., Makarenko, G. I., and Kiselev, A. I.: Problems and Exercises in the Calculus of Variations, Mir Publishers, Moscow, 1984. · Zbl 0612.49001
[48] Kuhn, H. W.: Nonlinear programming: A historical view, in R. W. Cottle and C. E. Lemke (eds.) Nonlinear Programming, SIAM-AMS Proceedings, Vol. IX, Providence, Rhode Island, 1976. · Zbl 0344.90029
[49] Kuhn, H. W. and Tucker, A. W.: Nonlinear programming, in J. Neymann (ed.) Proc. Second Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, 1951, pp. 481-492. · Zbl 0044.05903
[50] Kyparisis, J.: Optimal value function characterizations in nonlinear programming, Technical Report, Department of Decision Sciences and Information Systems, Florida International University, Miami, 1987. · Zbl 0643.90071
[51] Lemaréchal, C.: Constructing bundle methods for convex optimization, in J. B. Hiriart-Urruty (ed.) Fermat Days 85: Mathematics for Optimization, Elsevier (1986) pp. 201-240. · Zbl 0613.49017
[52] Lemaréchal, C.: An introduction to the theory of nonsmooth optimization, Optimization 17 (1986), 827-858. · Zbl 0613.49017
[53] Lewis, A. and Borwein, J.: Partially finite convex programming, Internal Report, Dalhousle University, 1988. · Zbl 0778.90050
[54] Lusternik, L. A. and V. I.Sobolev: Elements of Functional Analysis, Nauka, Moscow, 1965 (in Russian).
[55] Mangasarian, O.: Nonlinear Programming, McGraw-Hill, New York, 1969. · Zbl 0194.20201
[56] Marti?, Lj.: Characterization of complete efficiency in a special problem of multi-criterion hyperbolic programming, Economic Analysis and Workers’ Management 2(18) (1984), 171-174.
[57] Martin, D. H.: On the continuity of the maximum in parametric linear programming, J. Optim. Theory Applic. 17 (1975), 205-210. · Zbl 0298.90041
[58] Martin, D. H.: The essence of invexity, J. Optim. Theory and Applic. 47 (1985), 65-76. · Zbl 0552.90077
[59] Martos, B.: Nonlinear Programming: Theory and Methods, American Elsevier, New York, 1975. · Zbl 0357.90027
[60] Massam, H. and Zlobec, S.: Various definitions of the derivative in mathematical programming, Math. Program. 7 (1974), 144-161. Addendum, Ibid. 14 (1978), 108-111. · Zbl 0296.90042
[61] Nahum, C.: Second order sensitivity analysis, PhD. Thesis, Department of Mathematics and Statistics McGill University, 1988.
[62] Osyczka, A.: Multicriteria Optimization in Engineering with Fortran Programs, Ellis Horwood, Chichester, England, 1984.
[63] Pareto, V. V.: Cours d’Economic Politique, Rouge, Lausanne, Switzerland, 1896.
[64] Penot, J. P.: Calcul sous differential et optimisation, J. Funct. Anal. 27 (1978), 248-276. · Zbl 0404.90078
[65] Petrié, J. and Zlobec, S.: Nonlinear Programming. Nau?na, Knjiga, Belgrade, 1983 (in Serbo-Croatian).
[66] Podinovski, V. V.: Applieation of the maximization procedure of the basic local criterion to solving the problems of vector optimization, Control Systems, 6, Novosibirsk (in Russian).
[67] Pshenichnyi, B. N. and Hachatryan, R. A.: Constraints of equality type in nonsmooth optimization problems, Sov. Math. Dokl. 26 (1982), 659-662.
[68] Robinson, S.: Stability theory for systems of inequalities. Part I: Linear systems SIAM J. Numer. Anal. 12 (1975), 754-769. · Zbl 0317.90035
[69] Rockafellar, R. T.: Generalized derivatives and subgradients of nonconvex functions, Canad. J. Math. 32 (1980), 257-280. · Zbl 0447.49009
[70] Saks, S.: Theory of the Integral, Hafner, New York, 1973.
[71] Salukvadze, M. E.: Vector-Valued Optimization Problems in Control Theory, Academic Press, New York, 1979. · Zbl 0471.49001
[72] Schaible, S. and Ziemba, W. T. (eds.): Generalized Concavity in Optimization and Economics, Academic Press, New York, 1981. · Zbl 0534.00022
[73] Semple, J. and Zlobec, S.: On a necessary condition for stability in perturbed linear and convex programming, Zeit, Operations Research, Series A: Theorie, 31 (1987) 161-172. · Zbl 0643.90068
[74] Smith, D. R.: Variational Methods in Optimization, Prentice-Hall, Englewood Cliffs New Jesery, 1974. · Zbl 0344.49001
[75] Van Rooyen, M. and Zlobec, S.: A complete characterization of optimal economic systems with respect to stable perturbations, TWISK 550 (August 1987), to be published. · Zbl 0726.90079
[76] Van Rooyen, M., Sears, M., and Zlobec, S.: Constraint qualifications in input optimization, J. Austral. Math. Soc., Series B (1988, forthcoming). · Zbl 0676.90067
[77] Vukadinovi?, S.: Two rules of colonel Vlastimir Ivanovi? for calculating the required number of transport vehicles, in Proc. Yugoslav Symposium on Operations Research, Herceg Novi, 1984, pp. 23-25 (in Serbo-Croatian).
[78] Ward, D. E. and Browein, J. M.: Nonsmooth calculus in finite dimensions, SIAM J. Control 25 (1987), 1312-1340. · Zbl 0633.46043
[79] Wei, Q.-L.: Stability in mathematical programming in the sense of lower semi-continuity and continuity, J. Qufu Teachers College 1 (1981) (in Chinese).
[80] Weir, T. and Mond, B.: Duality for generalized convex programming without a constraint qualification, Utilitas Math. 31 (1985), 232-242. · Zbl 0583.90084
[81] Wolkowicz, H.: Method of reduction in convex programming, J. Optim. Theory Applic. 40 (1983), 349-378. · Zbl 0513.90068
[82] Zidaroiu, C.: Regions of stability for random decision systems with complete connections, An. Univ. Bucuresti Mat. 34 (1985), 87-97. · Zbl 0573.93077
[83] Zlobec, S.: Regions of stability for ill-posed convex programs, Aplikace Matematiky 27 (1982), 176-191. · Zbl 0482.90073
[84] Zlobec, S.: Two characterizations of Pareto minima in convex multicriteria optimization, Aplikace Matermatiky 29 (1984), 342-349. · Zbl 0549.90085
[85] Zlobec, S.: Input optimization: I. Optimal realizations of mathematical models, Math. Program. 31 (1985), 245-268. · Zbl 0589.90068
[86] Zlobec, S.: Characterizing an optimal input in perturbed convex programming, Math. Program. 25 (1983), 109-121; Corrigendum, Ibid. 35 (1986), 368-371. · Zbl 0505.90077
[87] Zlobec, S.: Input optimization: III. Optimal realizations of multi-objective models, Optimization 17 (1986), 429-445. · Zbl 0622.90078
[88] Zlobec, S.: Topics in input optimization, TWISK 543 (July 1987). Invited paper presented at the International Symposium on the Occasion of Professor A. Charnes’ 70th Birthday, University of Texas at Austin, October 14-16, 1987.
[89] Zlobec, S.: Survey of input optimization, Optimization 18 (1987), 309-348. · Zbl 0633.90077
[90] Zlobec, S. and Craven, B.: Stabilization and calculation of the minimal index set of binding constraints in convex programming, Math. Op. Stat., Series: Optim. 12 (1981), 203-220. · Zbl 0516.90066
[91] Zlobec, S. and Jacobson, D. H.: Minimizing an arbitrary function subject to convex constraints, Utilitas Math. 17 (1980), 239-257. · Zbl 0442.90079
[92] Zlobec, S., Gardner, R., and Ben-Israel, A.: Regions of stability for arbitrarily perturbed convex programs, in A. V.Fiacco (ed.) Mathematical Programming with Data Perturbations, Dekker, New York, 1981, pp. 69-89. · Zbl 0494.49027
[93] Zlobec, S.: Structural optima in nonlinear programming, in J.Guddat et al. (eds.), Advances in Mathematical Optimization, Series: Mathematical Research 45, Akademie-Verlag, Berlin, 1988, pp. 218-226. · Zbl 0654.90077
[94] Zoutendijk, G.: Mathematical Programming Methods, North-Holland, Amsterdam, 1976. · Zbl 0337.90036
[95] Zowe, J.: Nondifferentiable Optimization?A Motivation and a Short Introduction into the Subgradient-and the Bundle-Concept, in K.Schittkowski (ed.), Computational Mathematical Programming, Springer-Verlag, Berlin, Heidelberg, 1985.
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.