290
A Dutta
developments that are of u n d o u b t e d interest fbr the reader.
References Bonnans J.F. and Shapiro A. (2000). Perturbation Analysis of Optimization Problems. Springer Verlag. Borwein J.M. and Zhu Q.J. (2005). Techniques of Variational Analysis. Springer Verlag. Clarke F.H. (1975). Generalized Gradients and Applications. Transactions of the American Mathematical Society 205~ 247 262. Clarke F.H. (1983). Optimization and Nonsmooth Analysis. Wiley. Dernyanov V.F. and Rubinov A.M. (1980). On quasidifferentiable functions. Soviet Mathematics Doklady 21~ 14 17. Dernyanov V.F. and Rubinov A.M. (1995). Peter Lang Verlag.
Constructive Nonsmooth Analysis.
Iofl~ A.D. (2000). Metric Regularity and Subdifl~rential Calculus. Russian Mathematical S'ar~eys 55, 501 558. Mordukhovich B.S. (1976). Maximum Principle in the Problem of Time Optimal Response with Nonsmooth Constraints. You~nal of Applied Mathefnatics and Mechanics 40, 960 969. Mordukhovieh B.S. (1993). Complete Characterization of Openness~ Metric Regularity~ and Lipschitzian Properties of Multifunctions. Transactions of the American Mathematical Society 340~ 1 35. Mordukhovich B.S. (2005a). Variational Analysis and Generalized D~Erentiation, I: Basic Theory. Springer Verlag. Mordukhovich B.S. (2005b). Variational Analysis and Generalized D~Erentiation, II: Applications. Springer Verlag. Rockafellar R.T. and Wets R.J.-B. (1998). Variational Analysis. Springer Verlag.
Jean-Paul Penot Universit~ de P a u et des Pays de l'Adour, France Writing a survey paper a b o u t the present state of nonsmooth analysis is a great challenge. The topic is still rather fresh (about three or four
Generalized Derivatives and Nonsmooth Optimization
291
decades if one leaves apart the early contributions of Bouligand, Severi, Dubovitskii-Miljutin and others who only dealt with geometrical concepts without making links with analytical aspects) and its conclusions are not necessarily clear to a wide audience or widely accepted. Nonetheless, the literature on the subject is so abundant that it is impossible not to leave in the shade some valuable contributions. Thus, the merit of the author is great. He has succeeded in giving an account which reflects the opinion of the majority of researchers in the field and at the same time he has shed light on some approaches which are more or less off the beaten tracks. Among them are the study of quasidifferentiability (I would prefer the terms bi-diffbrentiability or disubdifferentiability) in the sense of Demyanov and Rubinov (Demyanov and Rubinov (1980), Demyanov and Rubinov (1995), and Demyanov and Vasilev (1985)) and Jeyakumar (Jeyakumar and Luc (2002) and Jeyakumar and Yen (2004)). As mentioned above, some other approaches of interest are neglected; among them let us mention quasidifferentiability in the sense of Pshenichnyi (Pshenichnyi (1971)), the first appearance of true nonsmooth analysis, the derivative containers of Warga (Warga (1976)) and their variants by Ermoliev-Norkin-Wets (Ermoliev et al. (1995)), semismoothness and its applications to algorithms. The mutual relationships of the different notions are also important missing elements. More importantly, one may wonder whether the main f~atures of nonsmooth analysis are sufficiently delineated in such a survey and whether the implicit philosophy it carries is universally accepted. For what concerns the first point, it seems to me that it would be necessary to stress some key facts concerning nonsmooth analysis which explain its importance. For the first time in the history of mathematics, nonsmooth analysis brings tools which allow a joint study of functions, sets and correspondences. Such a revolution may have the magnitude of the discovery of analysis. It is not just a sort of supplement or extension of differential calculus. The passages from functions to sets (epigraphs, graphs and sublevel sets) and vice versa (distance functions, indicator functions, support functions) are simple and fruitful. They make nonsmooth analysis a powerful and versatile tool. The importance of such passages calls for unified notations and terminologies. By this I mean that the notation for normal cones of some sort should fit the notation of the related subdifferential (and the notation fbr
292
A D,ttta
the related tangent cone and directional derivative when available). Alas, such a natural requirement is not always observed in practice. Moreover, a kind of behaviorist philosophy (not to speak of self flattering) often prevails. By this I mean that concepts are not described or ordered according to their nature or essence, but in terms of convenience for such or such purposes; basic objects are denoted with an involved notation, while more sophisticated constructions receive a simple notation, while the proofs impose to return every now and then to the basic objects. The main motivation usually presented is the presence of calculus rules. I do not want to deny the interest of such rules: for many questions they are crucial. However, while sum rules and composition rules are of utmost importance, some other rules, such as preservation of order are often neglected (see Penot (2000b) fbr some surrogate preservation properties). As a result, a loss of precision or realism sometimes deprives the results of most of their interests. In this sense, the present state of common thinking about nonsmooth analysis has some similarities with the views of Ancient Greeks for whom fbur elements (air, earth, fire, water) were the constituents of the universe. Modern physics distinguished more subtle fundamental elements. While the explanations of Antiquity were sufficient tbr the existing technology (but not fbr a real understanding of all natural phenomena such as comets, earthquakes...) a lot of other properties of m a t t e r have been mastered by a less superficial representation of its structure in terms of molecules and atoms. The preceding analogy with physics suggests another view about calculus rules. In m a n y cases, a given problem leads to a natural choice of space (sometimes several choices are possible); in turn, a natural choice of subdifferential appears, because not all subdifferentials have interesting properties in any space, in particular in terms of precision and calculus rules. A modern point of view about calculus rules consists in accepting some fuzziness (see Borwein and Zhu (2005) and Ioffe (1998)). Rejecting fuzziness appears to me as a blindness similar to the views of physicists rejecting the Heisenberg's principle. I admit that such an acceptance is not easy; but I see it as a necessity. Finally, a broader view of applications would increase the interest of the survey under review. Such an aim would require another study, as applications of nonsmooth analysis are numerous and varied. T h e y go much beyond mathematical programming as treated in the survey under review and the interpretation of multipliers (Penot (1997), Penot (2005b)). As a sample of such applications, let us briefly mention the following fields
Generalized Derivatives and Nonsrnooth Optimization
293
(again, we do not aim at exhaustiveness and we essentially omit references quoted in the survey). Nonlinear analysis is so much connected to the subject that it immediately received contributions (Aubin and Ekeland (1984), Aubin and Frankowska (1990), Ioffe and Schwartzman (1997)); moreover, these contributions reach partial differential equations and boundary value problems (Motreanu and Panagiotopoulos (1998), Naniewicz and Panagiotopoulos (1994), Panagiotopoulos (1993)), so that several monographs have been devoted to nonsmooth approaches to mechanics (Demyanov and Rubinov (2000), Motreanu and Panagiotopoulos (1998), Motreanu and Radulescu (2003)). Spectral analysis (Borwein and Lewis (2000), Lewis (1998), Martinez-Legaz (1995), Qi and Yang (2003)) is a topic in which striking results have appeared during the last few years. Algorithms have been influenced by nonsmooth analysis methods, in particular fbr Newton methods and semismooth mappings (Chaney (1988), Chen et al. (2000), Gowda (2004), Qi (1990), Qi et al. (2003), Qi and Yang (2003)). Far reaching links between Euler-Lagrange equations, Hamilton equations in the calculus of variations and the theory of characteristics have given a new life, to a classical subject (Ioffe (1997), Ioffe and Rockafe,llar (1996), Rockafe,1lar and Wolenski (2000a), Rockafellar and Wolenski(2000b),...). A large part of optimal control theory receives an illuminating interpretation in terms of generalized derivatives: in particular, the most fundamental parts of optimal control theory such as the maximum principle and the so-called dynamic programming can be given a new light by using tools fl'om nonsmooth analysis (Bardi and Capuzzo-Dolcetta (1997), Clarke et al. (1998), Mirica (2004), Vinter (2000), . . . ) . Hamilton-Jacobi equations cannot be treated in a modern way without some views on interpretations of viscosity solutions in terms of subdifferentials. The connections with sensitivity analysis are still partly unrevealed. The blending of nonsmooth analysis with variational convergences has given rise to what has been called variational analysis (Aubin and Frankowska (1990), and Rockafe,llar and Wets (1998)), a rich field in which convergences are viewed in a one-sided way, as are optimality conditions and generalized derivatives. Such a "unilateral" view is characteristic of the new constructions and approaches (Goeleven et al. (2003), Goeleven and Motreanu (2003), and Penot (2005b)). It also influences duality theories (Pallaschke and Rolewicz (1997), Penot (2005b), and Rubinov (2000)) and their applications to mathematical economics (Crouzeix (2003), Martfnez-Legaz (2002), and Penot (2005a)). The study of generalized convexity (Crouzeix et al. (1998), Hadjisavvas et al. (2005),
294
A Dutta
Ioffe (2001), Pallaschke and Rolewicz (1997), and Penot (2000a)) has much beneficed from the advances in nonsmooth analysis; thus, modelizations in economics, game theory, variational inequalities and equilibrium analysis (Facchinei and Pang (2003), Ferris et al. (2004), and Pang and Qi (1993)) can be given more realistic assumptions. There is no doubts that the range of applications will still increase in the future. For this reason (and others) a clear view of nonsmooth analysis will be useful. Thus, the contribution of J. D u t t a is welcome.
References Aubin J.-P. and Ekeland I. (1984). Applied Nonlinear Analysis. Wiley. Aubin J.-P. and Frankowska H. (1990). Set-Val'aed Analysis. Birkh~user. Bardi M. and Capuzzo-Dolcetta I. (1997). Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bdlman Equations. Birkh/iuser. Borwein J.M. and Lewis A.S. (2000) Convex Analysis and Nonlinear Optimization. Theo
Constructive Nonsmooth Analysis.
Demyanov V.F. and Rubinov A.M. (2000). Quasidi~Erentiability and Related Top-
Generalized Derivatives and Nonsmooth Optimization
295
ies. Kluwer Academic Publishers. Demyanov V.F. and Vasilev L.V. (1985). Nond~4fferentiable Optimization. Optimization Software. Ermoliev Y.M., Norkin V.I. and Wets R.J.-B. (1995). The Minimization of Semicontinuous Functions: Mollifier Subgradients. SIAM Journal on Control Optimization 33, 149-167. Facchinei F. and Pang J.-S. (2003). Finite-Dimensional Variational Inequalities and Complementarity Problems (volume I and II). Springer Verlag. Ferris M.C., Pang J.-S., Ralph D. and Scholtes S. (2004). Complementarity Problems: 40 Years On. Mathematical Programming 101, 1-295. Goeleven D., Motreanu D., Dumont Y. and Rochdi M. (2003). Variational and Hemivariational Inequalities. Theory, Methods and Applications. Volume I: Unilateral Analysis and Unilateral Mechanics. Kluwer Academic Publishers. Goeleven D. and Motreanu D. (2003). Variational and Hemivariational Inequalities. Theory, Methods and Applications. Volume II: Unilaterzzl Problems. Kluwer Academic Publishers. Gowda M.S. (2004). Inverse and Implicit Function Theorems for H-Differentiable and Semismooth Functions. Optimization Methods and Software 19, 443-461. Hadjisavvas N., KomlSsi S. and Schaible S. (2005). Handbook of Generalized Convexity and Generalized Monotonicity. Springer Verlag. Iofle A.D. (1997). Euler-Lagrange and Harniltonian Formalisms in Dynamic Optimization. Transactions of the American Mathematical Society 349, 2871-2900. Iofle A.D. (1998). Fuzzy Principles and Characterization of Trustworthiness. SetValued Analysis 6, 265-276. Iofle A.D. (2001). Abstract Convexity and Non-Smooth Analysis. In: Kusuoka S. and Yamazaki A. (ed.), Advances in Mathematical Economics. Springer Verlag. Iofle A.D. and Rockafellar R.T. (1996). The Euler and Weierstrass Conditions for Nonsmooth Variational Problems. Calculus of Variations and Partial D{fferential Equations 4, 59-87. Iofle A. and Schwartzman E. (1997). Metric Critical Point Theory. II. Deformation Techniques. In: Glazman I.M., Gohberg I. and Liubich I. (eds.), New Results in Operator Theory and its Applications: The Israel M. Glazman Memorial I/olume. Birkhguser, 132-144. Jeyakumar V. and Luc D.T. (2002). An Open Mapping Theorem Using Unbounded Generalized Jacobians. Nonlinear Analysis. Theow~ Methods and Applications 50, 647-663.
296
A Dutta
Jeyakumar V. and Yen N.D. (2004). Solution Stability of Nonsmooth Continuous Systems with Applications to Cone-Constrained Optimization. S I A M Journal on Optimization 14, 1106-1127. Lewis A.S. (1998). Nonsmooth Analysis of Eigenvalues: A Summary. Rendiconti del Seminavio Materagtico c Fisico di Milano 66, 33-41. Martinez-Legaz J.-E. (1995). On convex and quasiconvex spectral functions. Proceedings of the 2nd Catalan days on applied mathematics. Font-Romeu, Odeillo, France, 1995. Martfnez-Legaz J.-E. (2002). Generalized Convex Duality and its Economic Applications. Monograffas del Instituto de Matem&tica y Ciencias Afines 27. Instituto de Matem&tica y Ciencias Afines, IMCA, Pontificia Universidad Catdlica del Peril, Lima. Mirica S. (2004). Constructive Dynamic Programming irk Optimal Control. Editura Academiei Rom&ne. Motreanu D. and Panagiotopoulos P.D. (1998). Nonsmooth Variational Methods and Applications to Discontinuous Boundary Value Problems. In: Bainov D. (ed.), Proceedings of the 9th International Colloquium on Difterential Equations, 18-23. Motreanu D. and Radulescu V. (2003). Variational and Non-Variational Methods irk Nonlinear Analysis and Boundary Value Problems. Kluwer Academic Publishers. Naniewicz Z. and Panagiotopoulos P.D. (1994). Mathematical Theory of Hemivariational Inequalities and Applications. Marcel Dekker. Panagiotopoulos P.D. (1993). Hemivariational Inequalities. Applications irk Mechanics and Engineering. Springer Verlag. Pallaschke D. and Rolewicz S. (1997). Foundations of Mathematical Optimization: Convez Analysis Without Linearity. Kluwer Academic Publishers. Pang J.Q. and Qi L. (1993). Nonsrnooth Equations: Motivation and Algorithms. S I A M Journal on Optimization 3, 443-465. Penot J.-P. (1997). Central and Peripheral Results in the Study of Marginal and Performance Functions. In: Fiacco A.V. (ed.), Mathematical Programming with Data Perturbations. Marcel Dekker, 305-337. Penot J.-P. (2000a). What is Quasiconvex Analysis? Optimization 47, 35-110. Penot J.-P. (2000b). The Compatibility with Order of Some Subdift)rentials. Positivity 6, 413-432. Penot J.-P. (2005a). The Bearing of Duality on Microeconomics. Advances in Mathematical Economics 7, 113-139.
Generalized Derivatives and Nonsmooth Optimization
297
Penot J.-P. (2005b). Unilateral Analysis and Duality. In: Audet C., Hansen P. and Savard G. (eds.), Essays and Surveys in Global Optimization. Springer Verlag, 1-37. Pshenichnyi B.N. (1971). Necessary Conditions for ark Eztremum. Marcel Dekker. Qi L. (1990). Semismoothness and Decomposition of Maximal Normal Operators. Journal of Mathematical Analysis and Applications 146, 271-279. Qi L., Wu S.-Y and Zhou G. (2003). Semismooth Newton Methods for Solving Semi-Infinite Programming Problems. Journal of Global Optimization 27, 215232. Qi H. and Ya.ng X. (2004). Semismoothness of Spectral Functions. SIAM Journal on Matriz Analysis and Applications 25, 766-783. Rockafellar R.T. and Wets R.J.-B. (1998). l/ar~ational Analysis. Springer Verlag. Rockafellar R.T. and Wolenski P.R. (2000a). Convexity in Hamilton Jacobi Theory. I: Dynamics and Duality. SIAM Journal on Control Optimization 39, 1323-1350. Rockafellar R.T. and Wolenski P. R.(2000b). Convexity in Hamilton Jacobi Theory. II: Envelope Representations. SIAM Journal Control Optimization 39, 1351-1372. Rubinov A.M. (2000). Abstract Convexity and Global Optimization. Kluwer Academic Publishers. Vinter R. (2000). Optimal control, Systems and Control: Foundations and Applications. Birkhguser. Warga J. (1976). Derivate Containers, Inverse Functions, and Controllability. Proceedings of the Symposium of the Mathematics Research Center (Madison 1975), 13-46.
Alexander Rubinov University of Ballarat, Australia The paper under discussion is an interesting contribution. The author gives a good survey of different approaches to non-smooth analysis and non-smooth optimization. There are some parts of the paper (including examples) that can be presented simpler and it will be good to give more links between different constructions. However, this criticism does not destroy the good impression that I got reading the paper