Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data. (English) Zbl 0542.49011

Hiriart-Urruty, Jean-Baptiste; Strodiot, Jean-Jacques; Nguyen, V. Hien

Appl. Math. Optimization 11, 43-56 (1984).

This paper has two objectives: 1. Use Clarke’s generalized derivative concept to generalize the ”Hessian” concept to C(1,1) functions; that is, to functions with locally Lipschitz gradients. For example, if f is \(C^ 2\), then \(\{\max(f,0)\}^ 2\) is C(1,1). 2. Use the properties of generalized Hessian including Taylor expansion, to derive second order optimality conditions for mathematical programming problems with nonlinear constraints and C(1,1) data.
The following two theorems are of interest: 1. Let \({\mathcal O}\) be a nonempty open subset of \(R^ n\). Let \(f\in C(1,1)({\mathcal O})\) and [a,b]\(\subset {\mathcal O}\). Then, there is \(c\in(a,b)\) and \(M_ c\in \partial^ 2f(c)\) such that \(f(b)=f(a)+<\nabla f(a),b-a>+{1\over2}<M_ c(b-a),b-a>.\) Here, \(\partial^ 2f(c)\) denotes the convex hull of the set of all limits of the form lim \(\nabla^ 2f(x_ i)\), for all possible sequences \(\{x_ i\}\) converging to c and for which f is twice differentiable and \(\nabla^ 2f(x_ i)\) is meaningful.
2. Let \(x_ 0\) be a local minimum of the constrained problem (c): Minimize f(x) subject to \(g_ i(x)\leq 0\), \(i=1,...,m\) and \(h_ j(x)=0\), \(j=1,...,n\); where f, \(g_ i\), and \(h_ j\) are all C(1,1). Let \(G(\lambda)=\{x| g_ i(x)=0\) if \(\lambda_ i>0\), \(g_ i(x)\leq 0\) if \(\lambda_ i=0\) and \(h_ j=0\) for all \(j\}\) and let \(T_{\lambda}\) be the tangent cone to \(G(\lambda)\) at \(x_ 0\). Let L denote the Lagrangian \(L(x,\lambda,u)=f(x)+\sum \lambda_ ig_ i(x)+\sum \mu_ jh_ j(x)\) and let \(\partial^ 2_{xx}L(x_ 0,\lambda,\mu)\) denote the generalized Hessian of L at \(x_ 0\). Then, for each Kuhn-Tucker multiplier (\(\lambda\),\(\mu)\) and for each \(d\in T_{\lambda}\), there is a matrix \(A\in \partial^ 2_{xx}L(x_ 0,\lambda,\mu)\) such that \(<Ad,d>\geq 0\).

Reviewer: M.Sury

MSC:

49K10	Optimality conditions for free problems in two or more independent variables
58C20	Differentiation theory (Gateaux, Fréchet, etc.) on manifolds
90C30	Nonlinear programming
49M37	Numerical methods based on nonlinear programming
26B05	Continuity and differentiation questions

Keywords:

Clarke’s generalized derivative; functions with locally Lipschitz gradients; generalized Hessian; second order optimality conditions; nonlinear constraints

References:

[1]	Araya Schulz R, Gormaz Arancibia R (1979) Problemas localmente Lipschitzianos en optimizacion. (Master’s thesis) University of Chile at Santiago
[2]	Auslender A (1979) Penalty methods for computing points that satisfy second order necessary conditions. Math Programming 17:229-238 · Zbl 0497.90061
[3]	Auslender A (1981) Stability in mathematical programming with nondifferentiable data; second order directional derivative for lower-C 2 functions.
[4]	Ben-Tal A, Zowe J (1982) Necessary and sufficient optimality conditions for a class of nonsmooth minimization problems. Math Programming 24:70-91 · Zbl 0488.90059
[5]	Brezis H (1973) Op?rateurs maximaux monotones. North-Holland, Amsterdam
[6]	Bernstein B, Toupin R (1962) Some properties of the Hessian matrix of a strictly convex function. Journal f?r die Reine und Angewandte Mathematik 210:65-72 · Zbl 0107.27701
[7]	Clarke FH (1975) Generalized gradients and applications. Trans Amer Math Soc 205:247-262 · Zbl 0307.26012
[8]	Clarke FH (1976) On the inverse function theorem. Pacif J Math 64:97-102 · Zbl 0331.26013
[9]	Fitzpatrick S, Phelps R (to appear) Differentiability of the metric projection in Hilbert spaces.
[10]	Hestenes M (1975) Optimization theory: The finite dimensional case. Wiley, New York · Zbl 0327.90015
[11]	Hiriart-Urruty J-B (1977) Contributions ? la programmation math?matique: Cas d?terministe et stochastique. (Doctoral thesis) Sciences Math?matiques, Universit? de Clermont-Ferrand II
[12]	Hiriart-Urruty J-B (1979) Refinements of necessary optimality conditions in nondifferentiable programming I. Appl Math Optim 5:63-82 · Zbl 0395.90075
[13]	Hiriart-Urruty J-B (1982a) Refinements of necessary optimality conditions in nondifferentiable programming II. Math Programming Study 19:120-139 · Zbl 0507.90082
[14]	Hiriart-Urruty J-B (1982b) Characterizations of the plenary hull of the generalized Jacobian matrix. Math Programming Study 17:1-12 · Zbl 0532.26007
[15]	Holmes R (1973) Smoothness of certain metric projections on Hilbert spaces. Trans Amer Math Soc 184:87-100 · Zbl 0268.46043
[16]	Ioffe A (1981) Second order conditions in nonlinear nonsmooth problems of semi-infinite programming.
[17]	Kinderlehrer D, Stampacchia G (1980) An introduction to variational inequalities and their applications. Academic Press, New York · Zbl 0457.35001
[18]	Moreau J-J (1965) Proximit? et dualit? dans un espace hilbertien. Bulletin de la Soci?t? Math?matique de France 93:273-299 · Zbl 0136.12101
[19]	Ortega JM, Rheinboldt WC (1970) Iterative solution of nonlinear equations in several variables. Academic Press, New York
[20]	Rockafellar RT (1976) Solving a nonlinear programming problem by way of a dual problem. Symposia Mathematica 19:135-160
[21]	Stoer J, Witzgall C (1970) Convexity and optimization in finite dimensions I. Springer-Verlag, Berlin · Zbl 0203.52203