Generalized Derivatives and Nonsmooth Optimization, a Finite Dimensional Tour.

• Autores: Joydeep Dutta
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 13, Nº. 2, 2005, págs. 185-314
• Idioma: inglés
• DOI: 10.1007/bf02579049
• Texto completo no disponible (Saber más ...)
• Resumen

  • During the early 1960's there was a growing realization that a large number of optimization problems which appeared in applications involved minimization of non-di_erentiable functions. One of the important areas where such problems ap- peared was optimal control. The subject of nonsmooth analysis arose out of the need to develop a theory to deal with the minimization of nonsmooth functions. The first impetus in this direction came with the publication of Rockafellar's sem- inal work titled Convex Analysis which was published by the Princeton University Press in 1970. It would be impossible to overstate the impact of this book on the development of the theory and methods of optimization. It is also important to note that a large part of convex analysis was already developed by Werner Fenchel nearly twenty years earlier and was circulated through his mimeographed lecture notes titled Convex Cones, Sets and Functions, Princeton University, 1951. In this article we trace the dramatic development of nonsmooth analysis and its appli- cations to optimization in finite dimensions. Beginning with the fundamentals of convex optimization we quickly move over to the path breaking work of Clarke which extends the domain of nonsmooth analysis from convex to locally Lipschitz functions. Clarke was the second doctoral student of R.T. Rockafellar. We discuss the notions of Clarke directional derivative and the Clarke generalized gradient and also the relevant calculus rules and applications to optimization. While discussing locally Lipschitz optimization we also try to blend in the computational aspects of the theory wherever possible. This is followed by a discussion of the geometry of sets with nonsmooth boundaries. The approach to develop the notion of the normal cone to an arbitrary set is sequential in nature. This approach does not rely on the standard techniques of convex analysis. The move away from convexity was pioneered by Mordukhovich and later culminated in the monograph Variational Analysis by Rockafellar and Wets. The approach of Mordukhovich relied on a non- convex separation principle called the extremal principle while that of Rockafellar and Wets relied on various convergence notions developed to suit the needs of opti- mization. We then move on to a parallel development in nonsmooth optimization due to Demyanov and Rubinov called Quasidi_erentiable optimization. They study the class of directionally di_erentiable functions whose directional derivatives can be represented as a di_erence of two sublinear functions. On other hand the di- rectional derivative of a convex function and also the Clarke directional derivatives are sublinear functions of the directions. Thus it was thought that the most useful generalizations of directional derivatives must be a sublinear function of the directions. Thus Demyanov and Rubinov made a major conceptual change in nonsmooth optimization. In this section we define the notion of a quasidi_erential which is a pair of convex compact sets. We study some calculus rules and their applications to optimality conditions. We also study the interesting notion of Demyanov di_erence between two sets and their applications to optimization. In the last section of this paper we study some second-order tools used in nonsmooth analysis and try to see their relevance in optimization. In fact it is important to note that unlike the classical case, the second-order theory of nonsmoothness is quite complicated in the sense that there are many approaches to it. However we have chosen to describe those approaches which can be developed from the first order nonsmooth tools discussed here. We shall present three di_er- ent approaches, highlight the second order calculus rules and their applications to optimization.