Cetraro, July 1-7, 2007 Non-smooth optimization Prof. Vladimir Demianov, St. Petersbourg State Univ. Russia Abstract In the course, some tools and methods of nonsmooth analysis are presented which can be used for constructive solving problems of nondifferentiable optimization. 1. Smooth functions. Nonsmoothness. Optimality conditions (of the first and k-th order) of an arbitrary function on a metric space. 2. Some classes of Nonsmooth functions: convex and max-type functions. Properties. Subdifferentials of convex and max-type functions. Numerical methods for convex and max-type functions. 3. Quasidifferentiable functions. Calculus of quasidifferentials. Optimality conditions. Steepest descent and ascent directions. Numerical methods. 4. Codifferentiable functions. k-th order codifferentials and k-th order codifferentiable functions. Numerical aspects. 5. Constrained optimization problems. Exact penalties. 6. Directionally differentiable functions. Dini and Hadamard directional derivatives. Generalised directional derivatives. Clarke’s directional derivative. 7. Upper convex and lower concave approximations. Exhaustive families of approximations. Notions of upper and lower exhausters. Optimality conditions in terms of proper and adjoint exhausters. Descent and ascent directions. 8. Generalized Subdifferentials: Clarke’s subdifferential, Michel-Penot’s subdifferential, Frechet’s and Gateaux’ subdifferentials. Optimality conditions in terms of generalized derivatives and subdifferentials. Calculus of generalized subdifferentials via exhausters. References [1] Clarke, F.H., 1983, Optimization and Nonsmooth Analysis (New York: Wiley Interscience). [2] Demyanov V.F., 2000, Exhausters and Convexificators – New Tools in Nonsmooth Analysis. In: V. Demyanov and A. Rubinov (Eds.) Quasidifferentiability and related topics. (Dordrecht: Kluwer Academic Publishers), 85–137. [3] Demyanov, V.F. and Malozemov, V.N., 1972, Introduction to Minimax. – Moscow: Nauka, 1972. – 368 p. (English translation by J. Wiley, 1974, 2nd edition, 1990). [4] Demyanov V.F. and Rubinov A.M., 1995, Constructive Nonsmooth Analysis (Frankfurt a/M.: Verlag Peter Lang). [5] Demyanov V.F. and Rubinov A.M., 1986, Quasidifferential Calculus (New York: Optimization Software). [6] Di Pillo G., Grippo L. (1988), On the Exactness of a class of Nondifferentiable Penalty functions. J. Optim. Theory Appl., Vol. 57, pp. 397–408. [7] Di Pillo G., Facchinei F. (1989), Exact penalty functions for nondifferentiable programming problems. In Nonsmooth Optimization and Related Topics. Eds. F.H. Clarke, V.F. Demyanov and F. Giannessi, pp. 89-107. New York, Plenum. [8] I.I.Eremin (1967). A method of ”penalties” in Convex Programming. Soviet Mathematics Doklady 143(4), 748–751. [9] Fletcher R. (1983), Penalty functions. In Mathematical programming: the state of the art. (Eds. A. Bachen, M. Gr¨otschel, B. Korte), Springer–Verlag, Berlin, pp. 87–114. [10] Han S., Mangasarian O. (1979), Exact penalty functions in nonlinear programming. Mathematical Programming, Vol.17, pp. 251–269. [11] Ioffe, A.D., 1993, A Lagrange multiplier rule with small convex-valued subdifferentials for nonsmooth problems of mathematical programming involving equality and nonfunctional constraints. Mathematical Programming, 58, 137-145. [12] Kruger, A. Ya., 2003, On Fréchet subdifferentials. Optimization and related topics, 3. J. Math. Sci. (N. Y.) 116, No. 3, 3325–3358. [13] Michel, P. and Penot, J.-P., 1984, Calcus sous-differential pour les fonctions lipschitzienness et non-lipschitziennes, C.R. Acad. Sc. Paris, ser. I , 298, 269–272. [14] Mordukhovich B.S., 2006, Variational analysis and generalized differentiation I. Basic theory. Grundlehren der Mathematischen Wissenschaften, 330. Springer-Verlag, Berlin. [15] Pallaschke D. and Urbanski R., 2002, Pairs of compact convex sets (Dordrecht: Kluwer Academic Publishers). [16] Pschenichnyi B.N., 1980, Convex analysis and Extremal Problems (In Russian) (Moscow: Nauka Publishers). [17] Rockafellar R.T., 1970, Convex Analysis (Princeton, N.J.: Princeton University Press). [18] Uderzo A., 2000, Convex approximators, convexificators and exhausters: applications to constrained extremum problems. In: V. Demyanov and A. Rubinov (Eds.) Quasidifferentiability and related topics (Dordrecht: Kluwer Academic Publishers), 297–327. [19] Ward D.E. (1988), Exact penalties and sufficient conditions for optimality in nonsmooth optimization J. of Optimiz. Theory and Appl., Vol. 57, pp. 485–499. [20] Zangwill W.L. (1967), Nonlinear programming via penalty functions. Management Science, Vol. 13, pp. 344–358. |