×

Duality theory in mathematical programming and optimal control. (English) Zbl 0589.90066

Kybernetika 20/21 (1984/85), Suppl., 119 pp. (1985).
This paper “deals with the duality theory of extremal problems. It is divided into three parts according to the nature of the original problem (convex, smooth nonconvex, nonsmooth locally Lipschitz problems). From various aspects of the duality theory preferably the possibility of replacing the original (primal) problem by another easier (dual) problem is discussed” (from the author’s abstract).
As a unifying method most dual schemes are derived by first considering a class of perturbations and then taking the dual of the corresponding extremal value function. Applications to optimal control are given. Part of this paper has a survey character without proofs. The list of references contains 117 items.
The contents is as follows: 0. Introduction, 1. Convex analysis, 2. Perturbational theory of duality, 3. Fenchel dualisation, 4. Lagrange dualisation, 5. Shifted penalties, 6. Miscellaneous items, 7. Nonconvex dualisations derived by the convex perturbational theory, 8. Nonconvex perturbational duality theory of Lindberg, 9. Shifted penalties in nonconvex problems, 10. Some other augmented Lagrangians, 11. Nonsmooth analysis, 12. A class of nonsmooth exact penalties, 13. A dual treatment of noncalm problems. Conclusion.
Reviewer: F.Colonius

MSC:

90C48 Programming in abstract spaces
90C46 Optimality conditions and duality in mathematical programming
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
49N15 Duality theory (optimization)
49-02 Research exposition (monographs, survey articles) pertaining to calculus of variations and optimal control
49M37 Numerical methods based on nonlinear programming
Full Text: EuDML

References:

[1] E. Asplund, R. T. Rockafellar: Gradients of convex functions. Trans. Amer. Math. Society 189 (1969), 443-467. · Zbl 0181.41901
[2] A. Auslender: Optimization, Methodes Numeriques. Masson, Paris 1976.
[3] V. I. Blagodatskich: On the convexity of reachable sets. (in Russian). Differenciaľnye Uravnenija VIII (1972), 2149-2155.
[4] F. L. Chernousko, N. V. Banichuk: Variational Problems of Mechanics and Control. (in Russian). Nauka, Moskva 1973.
[5] A. Charnes, W. W. Cooper: Programming with linear fractional functional. Naval Res. Logist. Quart. 9 (1962), 181-196. · Zbl 0127.36901
[6] R. J. Duffin E. L. Peterson, C. Zener: Geometric Programming - Theory and Application. J. Wiley and Sons, New York 1967. · Zbl 0171.17601
[7] R. E. Edwards: Functional Analysis - Theory and Applications. Holt, Rinehart ard Winston, New York 1965. · Zbl 0182.16101
[8] I. Ekeland, R. Temam: Analyse Convexe et Problèmes Variationnels. Dunod, Paris 1974. · Zbl 0281.49001
[9] E. G. Golshtein: Gradient methods for determination of saddle points and modified Lagrangians. Proc. of the Workshop ”Matem. Optimierung - Theorie und Anwendungen”, Wartburg/Eisenach 1983.
[10] M. R. Hestenes: Multiplier and gradient methods. J. Optimiz. Theory Appl. 4 (1969), 303-320. · Zbl 0208.18402
[11] O. A. Ladyzhenskaya: Boundary Value Problems of Mathematical Physics. (in Russian). Nauka, Moskva 1973. · Zbl 0164.12501
[12] C. Lemaréchal: Nondifferentiable optimization, subgradient and \(\epsilon\)-subgradient methods. Numerical Methods in Optimization and Operations Research (Proc. of a Conference held at Oberwolfach, 1975), Springer Verlag, Berlin 1976.
[13] C. Lemaréchal: A view of line-searches. Optimization and Optimal Control (Proc. of a Conference held at Oberwolfach, 1980, A. Auslender, W. Oettli, J. Stoer, Springer Verlag, Berlin 1981.
[14] P. O. Lindberg: A generalization of Fenchel conjugation giving generalized Lagrangians and symmetric nonconvex duality. Survey of Mathematical Programming (Proc. of the 9th Internat. Mathematical Programming Symp., A Prekopa, Budapest 1976. · Zbl 0447.90073
[15] P. O. Lindberg: Report TRITA-MAT-1976-12. Dept. of Math., Royal Inst, of Technology, Stockholm.
[16] D. E. Luenberger: Optimization by Vector Space Methods. J. Wiley and Sons, New York 1968.
[17] G. P. McCormick: Nonlinear Programming. J. Wiley and Sons, New York 1983. · Zbl 0563.90068
[18] G. D. Maistrovskii: Gradient methods for finding saddle points. (in Russian). Ekonom. i Mat. Metody 12 (1976), 917-929.
[19] J. J. Moreau: Proximité et dualité dans un espace Hilbertian. Bull. Soc. Math. France 93 (1965),273-299. · Zbl 0136.12101
[20] J. V. Outrata: Duality theory for a class of discrete optimal control problems. Proc. 1978 IFAC Congress, 2, 1085-1092, Pergamon Press, London 1978.
[21] J. V. Outrata, Z. Schindler: Augmented Lagrangians for a class of convex continuous optimal control problems. Problems Control Inform. Theory 10 (1981), 67-81. · Zbl 0475.49032
[22] J. V. Outrata, J. Jarušek: On Fenchel dual schemes in convex optimal control problems. Kybernetika 18 (1982), 1-21. · Zbl 0487.49023
[23] B. T. Polyak: A general method for solution of extremal problems. Doklady AN SSSR 174 (1967), 33-36. In Russian.
[24] B. T. Polyak: Minimization of nonsmooth functionals. Zh. vych. mat. i mat. fiz. 9 (1969) 504-521. In Russian.
[25] J. Ch. Pomerol, P. Levine: Sufficient conditions for Kuhn-Tucker vectors in convex programming. SIAM J. Control Optimiz. 17 (1976), 689-699. · Zbl 0432.90084
[26] M. J. D. Powell: A method for nonlinear constraints in minimization problems. Optimization (R. Fletcher, Academic Press, New York 1969, 283 - 298. · Zbl 0194.47701
[27] R. T. Rockafellar: Extension of Fenchel’s duality theorem for convex functions. Duke Math. J. ii(1966), 81-89. · Zbl 0138.09301
[28] R. T. Rockafellar: Integrals which are convex functionals. Pacific J. Math. 24 (1968), 525-539. · Zbl 0159.43804
[29] R. T. Rockafellar: Some convex programs whose duals are linearly constrained. Non-linear Programming (J. B. Rosen, O. L. Mangasarian, K. Ritter, Academic Press, New York 1970, 293-322. · Zbl 0252.90046
[30] R. T. Rockafellar: A dual approach to solving nonlinear programming problems by unconstrained optimization. Math. Programming 5 (1973), 354-373. · Zbl 0279.90035
[31] R. T. Rockafellar: The multiplier method of Hestenes and Powell applied to convex programming. J. Optimiz. Theory Appl. 12 (1973), 555 - 562. · Zbl 0254.90045
[32] R. T. Rockafellar: Conjugate Duality and Optimization. SIAM/CBMS monograph series No. 16, SIAM Publications, 1974. · Zbl 0296.90036
[33] S. Schaible: Parameter-free convex equivalent and dual programs of fractional programming problems. Z. Oper. Res. 18 (1974), 187-196. · Zbl 0291.90067
[34] S. Schaible: Duality in fractional programming: A unified approach. Oper. Res. 24 (1976), 452-461. · Zbl 0348.90120
[35] S. Schaible: Fractional programming. I. Duality. Management Sci. 22 (1976), 858-867. · Zbl 0338.90050
[36] J. F. Toland: Duality in nonconvex optimization. J. Math. Anal. Appl. 66 (1978), 399-415. · Zbl 0403.90066
[37] J. F. Toland: A duality principle for non-convex optimisation and the calculus of variations. Arch. Rat. Mech. Anal. 71 (1979), 41-61. · Zbl 0411.49012
[38] A. P. Wierzbicki, S. Kurcyusz: Projection on a cone, penalty functionals and duality theory for problems with inequality constraints in Hilbert space. SIAM J. Control Optimiz. 75 (1977), 25-56. · Zbl 0355.90045
[39] J. Nedoma: Contribution to the Arrow-Hurwicz concave programming method. Ekonomicko-matematický obzor 2 (1966), 247-260.
[40] K. J. Arrow, L. Hurwicz: Reduction of constrained maxima to saddlepoint problems. Proc. of 3-rd Berkeley Symposium on Mathematical Statistical and Probability. Univ. of California Press, Berkeley 1956. · Zbl 0070.05804
[41] K. J. Arrow F. J. Gould, S. M. Howe: A generalized saddle-point result for constrained optimization. Math. Programming 5 (1973), 225-234. · Zbl 0276.90055
[42] M. Atteia, A. El Quortobi: Quasi-convex duality. Optimization and Optimal Control (Proc. of a Conf. Held at Oberwolfach March 1980; A. Auslender, W. Oettli, J. Stoer. L. N. in Control Inform. Sci., Vol. 30, Springer-Verlag, Berlin 1981.
[43] E. J. Balder: An extension of duality-stability relations to nonconvex optimization problems. SIAM J. Control Optim. 75 (1977), 329-343. · Zbl 0366.90103
[44] A. Ben-Tal, A. Ben-Israel: F-convex functions: properties and applications. Generalized Concavity in Optimization and Economics. Academic Press, New York 1981. · Zbl 0535.90074
[45] D. P. Bertsekas: Combined primal-dual and penalty methods for constrained minimization. SIAM J. Control 13 (1975), 521-544. · Zbl 0269.90044
[46] D. P. Bertsekas: Constrained-Optimization and Lagrange Multiplier Methods. Academic Press, New York 1982. · Zbl 0572.90067
[47] J. D. Buys: Dual Algorithms for Constrained Optimization. Thesis, Leiden 1972.
[48] B. D. Craven: Invex functions and constrained local minima. Bull. Austral. Math. Soc. 24 (1981), 357-366. · Zbl 0452.90066
[49] J. P. Crouzeix: Conjugacy in quasiconvex analysis. Convex Analysis and Its Applications. (Proc. of a Conference Held at Murat-le-Quaire, March 1976, A. Auslender. L. N. in Econom. and Math. Systems, Vol. 144. Springer-Verlag, Berlin 1977. · Zbl 0362.90096
[50] J. P. Crouzeix: Conditions for convexity of quasiconvex functions. Math. Oper. Res. 5 (1980), 120-125. · Zbl 0428.26007
[51] J. P. Crouzeix, J. A. Ferland: Criteria for quasiconvexity and pseudoconvexity and their relationships. Generalized Concavity in Optimization and Economics. Academic Press, New York 1981. · Zbl 0538.90079
[52] V. F. Demyanov, V. N. Malozemov: An Introduction to Minimax. (in Russian). Nauka, Moscow 1972.
[53] R. Deumlich, K.-H. Elster: \(\phi\)-conjugation and nonconvex optimization. Math. Operationsforsch. Statist. Ser. Optim. 14 (1983), 125-149. · Zbl 0524.90081
[54] S. Dolecki, S. Kurcyusz: On \(\phi\)-convexity in extremal problems. SIAM J. Control Optim. 16 (1978), 277-300. · Zbl 0397.46013
[55] S. Dolecki: Semicontinuity in constrained optimization. Part II. Control. Cybernet. 7 (1978), 51-68. · Zbl 0422.90086
[56] M. Dragomirescu: H-duality. Proc. of the 6th Conference on Probability Theory, Brasov, Sept. 1979, (B. Bereanu, Ş. Grigorescu, M. Iosifescu, T. Postelnicu. Acad. Rep. Soc. Rom., Bucureşti 1981. · Zbl 0484.90079
[57] I. Ekeland: Legendre duality in nonconvex optimization and calculus of variations. SIAM J. Control. Optim. 15 (1977), 905-934. · Zbl 0377.90089
[58] I. Ekeland: Problèmes variationnels non convexes en dualité. C. R. Acad. Sci. Paris, t. 291, Série A-493 (1980). · Zbl 0448.90063
[59] F. J. Gould: Extensions of Lagrange multiplier functions and duality in nonconvex programming. SIAM J. Appl. Math. 17 (1969), 1280-1297. · Zbl 0191.49001
[60] H. J. Greensberg, W. P. Pierskalla: Quasiconjugate functions and surrogate duality. Cahiers Centre Études Rech. Oper. 15 (1973), 437-448.
[61] R. Kaltcheva J. V. Outrata Z. Schindler, M. Straškraba: An optimization model for the economic control of reservoir eutrophication. Ecological Modelling 77 (1982), 121-128.
[62] P. Kanniappan: Fenchel-Rockafellar type duality for a non-convex non-differentia! optimization problem. J. Math. Anal. Appl. 97 (1983), 266-276. · Zbl 0543.90087
[63] F. Lempio, H. Maurer: Differential stability in infinite-dimensional nonlinear programming. Appl. Math. Optim. 6 (1980), 139-152. · Zbl 0426.90072
[64] H. Maurer, J. Zowe: First and second-order necessary and sufficient optimality conditions for infinite-dimensional programming problems. Math. Programming 16 (1979), 98-110. · Zbl 0398.90109
[65] O. L. Mangasarian: Unconstrained Lagrangians in nonlinear programming. SIAM J. Control 13 (1975), 772-791. · Zbl 0269.90045
[66] H. Nakayama H. Sagama, Y. Sawaragi: A generalized Lagrangian dnd multiplier method. J. Optim. Theory Appl. 17 (1975), 211-227. · Zbl 0298.49016
[67] R. Nehse: Some general separation theorems. Math. Nachr. 84 (1978), 319-327. · Zbl 0323.46004
[68] R. Nehse: A new concept of separation. Comment. Math. Univ. Carolin. 22 (1981), 169-179. · Zbl 0518.46005
[69] E. A. Nurminskii: Numerical Methods for the Solution of Deterministic and Stochastic Minimax Problems. (in Russian). Naukova dumka, Kiev 1979.
[70] E. Polak: Computational Methods in Optimization. Academic Press, New York 1971. · Zbl 0257.90055
[71] D. A. Pierre, M. J. Lowe: Mathematical Programming Via Augmented Lagrangians. Addison-Wesley Publ. Comp., Reading 1975. · Zbl 0347.90048
[72] R. T Rockafellar: Augmented Lagrange multiplier functions and duality in nonconvex programming. SIAM J. Control 12 (1974), 268-285. · Zbl 0257.90046
[73] R. T. Rockafellar: Solving a nonlinear programming problem by way of a dual problem. Symposia Mathematica 19 (1976), 135-160. · Zbl 0394.90078
[74] S. Rolewicz: On conditions warantying \(\phi\)-subdifferentiability. Math. Programming Study 14, (1981), 215-224. · Zbl 0444.90106
[75] Z. Schindler: Multiplier Methods in Discrete-Time Optimal Control. (in Czech). Ph.D. Thesis, Prague 1980.
[76] I. Singer: A Fenchel-Rockafellar type duality theorem for maximization. Bull. Austral. Math. Soc. 20 (1979), 193-198. · Zbl 0404.90101
[77] I. Singer: Some new applications of the Fenchel-Rockafellar duality theorem: Lagrange multipliers theorems and hyperplane theorems for convex optimization and best approximation. Nonlinear Analysis 3 (1979) 2, 239-248. · Zbl 0444.41015
[78] R. Temam: Nouvelles applications de la dualité en calcul des variations. Analyse Convexe et Ses Applications, Comptes Rendus, Janvier 1974. Springer-Verlag, Berlin 1974. · Zbl 0305.49039
[79] A. P. Wierzbicki, A. Hatko: Computational methods in Hilbert space for optimal control problems with delays. Proc. of 5th IFIP Conf. on Optimization Techniques, Rome (R. Conti, A. Ruberti. L. N. in Comp. Sci., Vol. 3, Springer-Verlag, Berlin 1973. · Zbl 0289.49030
[80] E. H. Zarantonello: Projections on convex sets in Hilbert space and spectral theory. Contributions to Nonlinear Functional Analysis (E. H. Zarantonello. Academic Press, New York 1971. · Zbl 0281.47043
[81] J. L. Lions, E. Magenes: Problèmes aux limites non-homogénes et applications. Dunod, Paris 1968. · Zbl 0165.10801
[82] A.D. Ioffeand V. M. Tichomirov: Extensions of variational problems. Trans. Moscow Math. Soc. 18 (1968), 207-273.
[83] J. P. Aubin: Gradients généralisés de Clarke. Ann. Sci. Math. Québec II (1978), 2, 197-252. · Zbl 0411.49001
[84] A. Auslender: Differentiable stability in non-convex and non-differentiable programming. Math. Programming Study 10 (1979), 29-41. · Zbl 0403.90068
[85] J. M. Borwein: Semi-infinite programming duality: how special is it?. Semi-infinite Programming and Applications. (Proc. of a conference, A. V. Fiacco, K. O. Kortanek. L. N. in Econom. and Math. Systems, Vol. 215, Springer-Verlag, Berlin 1983. · Zbl 0514.49019
[86] F. H. Clarke: Generalized gradients and applications. Trans. Amer. Math. Soc. 205 (1975), 247-262. · Zbl 0307.26012
[87] F. H. Clarke: Generalized Gradients of Lipschitz Functionals. MRC Technical Summary Report # 1687, University of Wisconsin-Madison 1976. · Zbl 0463.49017
[88] F. H. Clarke: A new approach to Lagrange multipliers. Math. Oper. Res. 1 (1976), 165-174. · Zbl 0404.90100
[89] F. H. Clarke: Optimization and Nonsmooth Analysis. J. Wiley and Sons, New York 1983. · Zbl 0582.49001
[90] V. F. Demyanov: Nondifferentiable Optimization. (in Russian). Nauka, Moscow 1981.
[91] J. Gauvin: The generalized gradient of a marginal function in mathematical programming. Math. Oper. Res. 4 (1979), 458-463. · Zbl 0433.90075
[92] J.-B. Hiriart Urruty: New concepts in nondifferentiable programming. Bull. Soc. Math. France, Mem. 60 (1979), 57-85. · Zbl 0469.90071
[93] A. D. Ioffe V. M. Tichomirov: Theory of Extremal Problems. (in Russian). Nauka, Moscow 1974.
[94] A. D. Ioffe: Necessary and sufficient conditions for a local minimum. (3 parts). SIAM J. Control. Optimiz. 17 (1979), 245-265. · Zbl 0417.49029
[95] O. A. Ladyzhenskaya V. A. Solonnikov, N. N. Uralceva: Linear and Quasilinear Equations of the Parabolic Type. (in Russian). Nauka, Moscow 1967.
[96] CI. Lemaréchal J. J. Strodiot, A. Bihain: On a Bundle Algorithm for Nonsmooth Optimization. NPS 4, Madison 1980. · Zbl 0533.49023
[97] O. L. Mangasarian, S. Fromowitz: The Fritz John necessary optimality conditions in the presence of equality and inequality constraints. J. Math. Anal. Appl. 17(1967), 37-47. · Zbl 0149.16701
[98] R. Mifflin: Semismooth and semiconvex functions in optimization. SIAM J. Control Optimiz. 15 (1977), 959-972. · Zbl 0376.90081
[99] J. Nečas: Introduction to the Theory of Nonlinear Elliptic Equations. Teubner Texte zur Math., Band 52, Teubner Verlag, Leipzig 1983. · Zbl 0526.35003
[100] J. Nečas, I. Hlaváček: Mathematical Theory of Elastic and Elasto-Plastic Bodies. An Introduction. Elsevier, Amsterdam -Oxford-New York 1981.
[101] J. V. Outrata: On a class of nonsmooth optimal control problems. Appl. Math. Optim. 10 (1983), 287-306. · Zbl 0524.49021
[102] J. V. Outrata, Z. Schindler: On some nondifferentiable problems in optimal control. Prep. of the IIASA Workshop ”Nondifferentiable optimization: Motivations and Applications” held at Sopron, September 1984. · Zbl 0584.49019
[103] J. V. Outrata, J. Jarušek: Exact penalties with Sobolev norms in optimal control. Proc. of the Workshop ”Mathematical Programming - Theory and Applications” held at Wartburg, November 1984.
[104] T. Pietrzykowski: The potential method for conditional maxima in the locally compact metric spaces. Numer. Math. 14 (1970), 4, 325-329. · Zbl 0195.46304
[105] J. C. Pomerol: The Lagrange multiplier set and the generalized gradient set of the marginal function of a differentiable program in a Banach space. J. Optim. Theory Appl. 38 (1982), 307-317. · Zbl 0472.90077
[106] R. T. Rockafellar: The Theory of Subgradients and Its Applications to Problems of Optimization: Convex and Nonconvex Functions. Helderman Verlag, Berlin 1981. · Zbl 0462.90052
[107] T. I. Sivelina: The minimization of one kind of quasidifferentiable functions. (in Russian). Vestnik LGU (1983), 7, 103-105. · Zbl 0536.90077
[108] Z. Schindler: Optimal control of the eutrophisation in water reservoirs. (in Czech). Vodohosp. Časopis 30 (1982), 5, 536-548.
[109] R. H. Smith: Multiplier Functionals for Programming in Normed Spaces. Ph.D. Thesis, Johns Hopkins Univ., Baltimore 1971.
[110] R. H. Smith, V. D. VandeLinde: A saddle-point optimality criterion for nonconvex programming in normed spaces. SIAM J. Appl. Math. 23 (1972), 2, 203-213. · Zbl 0226.90043
[111] L. Thibault: Sur les fonctions compactement lipschitziennes et leurs applications: programmation mathématique, controle optimal, espérance conditionnele. Thèses, Montpellier 1980.
[112] J.-B. Hiriart Urruty: Gradients généralisés de fonctions marginales. SIAM J. Control Optimiz. 16 (1978), 301-316. · Zbl 0385.90099
[113] S. Agmon A. Douglis, L Nirenberg: Estimates near boundary for solutions of elliptic partial differential equations satisfying general boundary conditions. Part II. Comm. Pure Appl. Math. 17 (1964), 35-92. · Zbl 0123.28706
[114] J. A. Nelder, R. Mead: A simplex method for function minimization. Computer J. 7 (1965), 4, 308-313. · Zbl 0229.65053
[115] V. F. Demyanov S. Gamidov, T. I. Sivelina: An algorithm for minimizing a certain class of quasidifferentiable functions. NASA Working Paper WP-83-122. · Zbl 0602.90123
[116] R. E. Burkard: Methoden der ganzzähligen Optimierung. Springer-Verlag, Berlin-Heidelberg-New York 1972.
[117] W. I. Zangwill: Non-linear programming via penalty functions. Management Sci. 13 (1967), 344-358. · Zbl 0171.18202
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.