1. Art and Diseño

MOLLIFIED DERIVATIVES AND SECOND-ORDER
OPTIMALITY CONDITIONS
GIOVANNI P. CRESPI – DAVIDE LA TORRE –
MATTEO ROCCA
Working Paper n.10.2003 – giugno
Dipartimento di Economia Politica e Aziendale
Università degli Studi di Milano
via Conservatorio, 7
20122 Milano
tel. ++39/02/50321501
fax ++39/02/50321450
E Mail: [email protected]
In pubblicazione sul Journal of Nonlinear and Convex Analysis
Mollified derivatives and second-order optimality
conditions
Giovanni P. Crespi∗
Davide La Torre†
Matteo Rocca‡
Abstract
The class of strongly semicontinuous functions is considered. For these functions the notion of mollified derivatives, introduced by Ermoliev, Norkin and
Wets [8], is extended to the second order. By means of a generalized Taylor’s formula, second order necessary and sufficient conditions are proved for
both unconstrained and constrained optimization. Finally a characterization of
convex functions is given.
Keywords: Smooth approximations, Nonsmooth optimization, Strong semicontinuity .
1
Introduction
In this paper we extend to the second-order the approach introduced by Ermoliev,
Norkin and Wets [8] to define generalized derivatives even for discontinuous functions, which often arise in applications (see [8] for references). A similar technique
has been previously used by Craven in [7], but for the only class of locally Lipschitz
functions. To deal with such problems a number of approaches have been proposed
to develop a subdifferential calculus for nonsmooth and even discontinuous functions. Among the many possibilities, let us remember the notions due to Aubin [2],
∗
Universit`
a Bocconi, I.M.Q., v.le Isonzo 25, 20137 Milano, Italia. e–mail: giovanni.crespi@uni-
bocconi.it
†
Universit`
a di Milano, Dipartimento di Economia Politica e Aziendale, via Conservatorio 7,
20122 Milano, Italia. e–mail: [email protected]
‡
Universit`
a dell’Insubria, Dipartimento di Economia, via Ravasi 2, 21100 Varese, Italia. e–mail:
[email protected]
1
Clarke [5], Ioffe [14], Michel and Penot [21], Rockafellar [23], in the context of Variational Analysis. The previous approaches are based on the introduction of first-order
generalized derivatives. Extensions to higher-order derivatives have been provided
for instance by Hiriart-Hurruty, Strodiot and Hien Nguyen [13], Jeyakumar and Luc
[15], Klatte and Tammer [16], Michel and Penot [20], Yang and Jeyakumar [31] ,
Yang [32]. Most of these higher-order approaches assume that the functions involved
are of class C 1,1 , that is once differentiable with a locally Lipschitz gradient, or at
least of class C 1 . Anyway, another possibility, concerning the differentiation of nonsmooth functions dates back to the 30’s and is related to the names of Sobolev [27],
who introduced the concept of “weak derivative” and later of Schwartz [26] who generalized Sobolev’s approach with the “theory of distributions”. These tecniques are
widely used in the theory of partial differential equations, in Mathematical Physics
and in related problems, but they have not been applied to deal with optimization
problems involving nonsmooth functions, until the work of Ermoliev, Norkin and
Wets.
The tools which allow to link the “modern” and the “ancient” approaches to Nonsmooth Analysis are those of “mollifier” and of “mollified functions”. More specifically, the approach followed by Ermoliev, Norkin and Wets appeals to some of the
results of the theory of distributions. They associate with a point x ∈ Rn a family
of mollifiers (density functions) whose support tends toward x and converges to the
Dirac function. Given such a family, say {ψε , ε > 0}, one can define a family of
mollified functions associated to a function f : Rn → R as the convolution of f and
ψε (mollified functions will be denoted by fε ). Hence a mollified function can be
viewed as an averaged function. The mollified functions possess the same regularity
of the mollifiers ψε and hence, if they are at least of class C 2 , one can define first
and second-order generalized derivatives as the cluster points of all possible values
of first and second-order derivatives of fε . For more details one can see [8].
We remember also that an approach based on similar techniques has beeen used
to solve nonsmooth equations, with the introduction of smoothing functions and
smoothing Newton methods [22].
2
In this paper, section 2 recalls the notions of mollifier, epi-convergence of a
sequence of functions and some definitions introduced in [8]. Section 3 is devoted to
the introduction of second-order derivatives by means of mollified functions; sections
4 and 5 deal, respectively, with second-order necessary and sufficient optimality
conditions for unconstrained and constrained problems; finally, section 6 is devoted
to a second–order characterization of convex functions.
2
Preliminaries
To follow the approach presented in [8] we first need to introduce the notion of
mollifier (see e.g. [4]):
Definition 1 A sequence of mollifiers is any sequence of functions {ψε : Rm → R+ },
ε ↓ 0, such that:
i) supp ψε := {x ∈ Rn | ψε (x) > 0} ⊆ ρε B, ρε ↓ 0,
Z
ii)
ψε (x)dx = 1,
Rn
where B is the closed unit ball in Rm .
Although in the sequel we may consider general families of mollifiers, some examples may be useful.
Example 1 Let ε be a positive number.
i) The functions:



ψε (x) =
1
εm ,
max1,...,m |xi | ≤

 0,
ε
2
otherwise
are called Steklov mollifiers.
ii) The functions:
ψε (x) =


C
εm
exp
ε2
kxk2 −ε2
R
Rm
,
if kxk < ε
if kxk ≥ ε
 0,
with C ∈ R such that
ψε (x)dx = 1, are called standard mollifiers.
3
It is easy to check that the second family of functions is of class C ∞ .
Definition 2 ([4]) Given a locally integrable function f : Rm → R and a sequence
of bounded mollifiers, define the functions fε (x) through the convolution:
Z
f (x − z)ψε (z)dz.
fε (x) :=
Rm
The sequence fε (x) is said a sequence of mollified functions.
In the following all the functions considered will be assumed to be at least locally
integrable.
Remark 1 There is no loss of generality in considering f : Rm → R. The results
in this paper remain true also if f is defined on an open subset of Rm .
Some properties of the mollified functions can be considered classical.
Theorem 1 ([4]) Let f ∈ C (Rm ). Then fε converges continuously to f , i.e. fε (xε ) →
f (x) for all xε → x. In fact fε converges uniformly to f on every compact subset of
Rm as ε ↓ 0.
The previous convergence property can be generalized.
Definition 3 ([1], [25]) A sequence of functions {fn : Rm → R} epi–converges to
f : Rm → R at x, if:
i) lim inf n→+∞ fn (xn ) ≥ f (x) for all xn → x;
ii) limn→+∞ fn (xn ) = f (x) for some sequence xn → x.
The sequence {fn } epi–converges to f if this holds for all x ∈ Rm , in which case we
write f = e − lim fn .
Remark 2 It can be easily checked that when f is the epi–limit of some sequence
fn then f is lower semicontinuous. Moreover if fn converges continuously, then it
also epi–converges.
4
Definition 4 ([8]) A function f : Rm → R is said strongly lower semicontinuous
(s.l.s.c.) at x if it is lower semicontinuous at x and there exists a sequence xn → x
with f continuous at xn (for all n) such that f (xn ) → f (x). The function f is
strongly lower semicontinuous if this holds at all x.
The function f is said strongly upper semicontinuous (s.u.s.c.) at x if it is upper
semicontinuous at x and there exists a sequence xn → x with f continuous at xn
(for all n) such that f (xn ) → f (x). The function f is strongly lower semicontinuous
if this holds at all x.
Proposition 1 If f : Rm → R is s.l.s.c., then −f is s.u.s.c. .
Proof: It follows directly from the definitions.
2
Theorem 2 ([8]) Let εn ↓ 0 as n → +∞. For any s.l.s.c. function f : Rm → R,
and any associated sequence fn of mollified functions we have f = e − lim fn .
Remark 3 It can be seen that, according to Remark 2, Theorem 1 follows from
Theorem 2.
Proposition 2 Let εn ↓ 0 as n → +∞. For any s.u.s.c. function f : Rm → R and
any associated sequence fn of mollified functions, we have for any x ∈ Rm :
i) lim supn→+∞ fn (xn ) ≤ f (x) for any sequence xn → x;
ii) limn→+∞ fn (xn ) = f (x) for some sequence xn → x.
Proof: It is immediate from definition 4 and Proposition 1
2
The following Proposition plays a crucial role in the sequel.
Proposition 3 ([26, 27]) Whenever the mollifiers ψε are of class C k , so are the
associated mollified functions fε .
By means of mollified functions it is possible to define generalized directional
derivatives for a nonsmooth function f , which, under suitable regularity of f , coincide with Clarke’s generalized derivative. Such an approach has been deepened by
several authors (see e.g. [7, 8]) in the first–order case.
5
Definition 5 ([8]) Let f : Rm → R, n ↓ 0 as n → +∞ and consider the sequence
{fεn } of mollified functions with associated mollifiers ψεn ∈ C 1 . The upper mollified
derivative of f at x in the direction d ∈ Rm , with respect to (w.r.t.) the mollifiers
sequence ψn is defined as:
D ψ f (x; d) := sup lim sup ∇fεn (xn )> d,
xn →x n→+∞
where the supremum is taken over all possible sequences xn tending to x.
Similarly, we might introduce the following:
Definition 6 Let f : Rm → R, n ↓ 0 as n → +∞ and consider the sequence
{fεn } of mollified functions with associated mollifiers ψεn ∈ C 1 . The lower mollified
derivative of f at x in the direction d ∈ Rm , w.r.t. the mollifiers sequence ψn is
defined as:
D ψ f (x; d) := inf lim inf ∇fεn (xn )> d,
xn →x n→+∞
where the infimum is taken over all possible sequences xn tending to x.
Let us recall that, for any sequence an ∈ Rm , Limsupn→∞ an denotes the set of all
cluster points of an . Under the setting of Definition 5, in [8] it has been defined also
a generalized gradient w.r.t. the mollifiers sequence ψn , in the following way:
∂ψ f (x) := {Limsupn→∞ ∇fεn (xn ), xn → x}
i.e. the set of cluster points of all possible sequences {∇fn (xn )} such that xn → x.
Clearly (see e.g. [8]) for the above mentioned upper mollified derivative it holds:
D ψ f (x; d) ≥
sup
L> d,
L∈∂ψ f (x)
D ψ f (x; d) ≤
inf
L> d.
L∈∂ψ f (x)
This generalized gradient has been used in [8] to prove first–order necessary optimality conditions for nonsmooth optimization. The equivalence with the well–known notions of Nonsmooth Analysis is contained in the following Proposition. We recall that
fC0 (x; d) = lim supx0 →x,
t↓0
f (x0 +td)−f (x0 )
,
t
denotes Clarke’s generalized derivative of f
6
at the point x in the direction d, while ∂C f (x) = {v ∈ Rm |v > d ≤ fC0 (x; d), ∀d ∈ Rm }
denotes Clarke’s generalized gradient.
Proposition 4 ([8])
i) Let f : Rm → R be locally integrable. Then for every
choice of sequences εn ↓ 0 and ψεn ∈ C 1 , we have D ψ f (x; d) ≤ fC0 (x; d). If f
is also continuous, then D ψ f (x; d) = fC0 (x; d).
ii) If f is lower semicontinuous and locally integrable, then conv ∂ψ f (x) ⊆ ∂C f (x)
(here conv A stands for the convex hull of the set A ⊆ Rm ). If, in addition, f
is locally Lipschitz, then conv ∂ψ f (x) = ∂C f (x).
Remark 4 ¿From the previous proposition and the well–known properties of Clarke’s
generalized gradient, we deduce that, if f and ψεn ∈ C 1 , then ∂ψ f (x) = {∇f (x)} and
D ψ f (x; d) = D ψ f (x; d) = ∇f (x)> d. More generally, it is easy to see that, whenever
f (x) = g(x) + h(x), with g of class C 1 and h = 0 a.e., then ∂ψ f (x) = {∇g(x)} and
D ψ f (x; d) = D ψ f (x; d) = ∇g(x)> d.
The following example shows that the inequalities and inclusions of Proposition
4 can be strict.
Example 2 We consider the following function f : R → R:
 p


 − |x|, x = ±1/n, n = 1, 2, . . .
f (x) =



−x,
elsewhere
It can be easily verified that f is s.l.s.c.. We get fC0 (0; −1) = fC0 (0; 1) = +∞, thus
∂C f (0) = R, while D ψ f (0; d) = D ψ f (0; d) = −d and ∂ψ f (0) = −1.
Warga [28, 29, 30] defines subgradients of continuous functions using a construction similar to that of [8]. In this last paper comparison results between mollified
derivatives and Warga’s notion are given.
For the aim of our paper, we will need to point out the following proposition
(contained in [8]) of which we give an alternative proof.
7
Proposition 5 Let f : Rm → R and x ∈ Rm . Then, for every choice of sequences
εn ↓ 0 and ψεn ∈ C 1 we have:
i) D ψ f (·; d) is upper semicontinuous (u.s.c.) at x for all d ∈ Rm ;
ii) D ψ f (·; d) is lower semicontinuous (l.s.c.) at x for all d ∈ Rm .
Proof: We can prove only i), since ii) follows with the same reasoning.
Assume d ∈ Rm is fixed. First we note that the upper semicontinuity is obviuous if
D ψ f (x; d) = +∞. Otherwise, for all K > D ψ f (x; d), there exists a neighborhood
U of x and an integer n0 so that:
∇fn (x0 )> d < K,
∀n > n0 , ∀x0 ∈ U.
Therefore, for each x0 ∈ U , we have:
D ψ f (x0 ; d) = sup lim sup ∇fn (xn )> d ≤ K,
xn →x0 n→+∞
which shows that D ψ f (·; d) is u.s.c. .
2
Furthermore, we point out the following property:
Proposition 6 Whenever the choice of sequences εn ↓ 0 and ψεn ∈ C 1 , D ψ f (x; ·)
and D ψ f (x; ·) are positively homogeneous functions.
Furthermore, if D ψ f (x; ·) 6= −∞ (D ψ f (x; ·) 6= +∞ respectively), then it is subadditive (resp. superadditive) and hence convex (resp. concave) as a function of the
direction d.
Proof: The positive homogeneity is trivial. Concerning the second part of the Theorem, we have, ∀d1 , d2 ∈ Rm :
D ψ f (x; d1 + d2 ) =
≤
sup lim sup ∇f (xn )> (d1 + d2 ) ≤
xn →x n→+∞
sup lim sup ∇f (xn )> d1 + sup lim sup ∇f (xn )> d2 =
xn →x n→+∞
xn →x n→+∞
= D ψ f (x; d1 ) + D ψ f (x; d2 ),
and hence D ψ f (x; ·) is subadditive. Convexity follows considering positive homogeneity and subadditivity. The proof for D ψ f (x; ·) is analogous.
8
2
3
Second–order mollified derivatives
As suggested in [8], by requiring some more regularity of the mollifiers, it is possible
to construct also second–order generalized derivatives.
Definition 7 Let f : Rm → R, n ↓ 0 as n → +∞ and consider the sequence of
mollified functions {fεn }, obtained from a family of mollifiers ψεn ∈ C 2 . We define
the second–order upper mollified derivative of f at x in the directions d and v ∈ Rm ,
w.r.t. to the mollifiers sequence {ψn }, as:
D 2ψ f (x; d, v) := sup lim sup d> Hfεn (xn )v,
xn →x n→+∞
where Hfεn (x) is the Hessian matrix of the function fεn ∈ C 2 at the point x and the
supremum is taken over all possible sequences xn tending to x.
Definition 8 Let f : Rm → R, n ↓ 0 and consider the sequence of mollified functions {fn }, obtained from a family of mollifiers ψn ∈ C 2 . We define the second–
order lower mollified derivative of f at x in the directions d and v ∈ Rm , w.r.t. the
mollifiers sequence {ψn }, as:
D 2ψ f (x; d, v) := inf lim inf d> Hfεn (xn )v,
xn →x n→+∞
where the infimum is taken over all possible sequences xn tending to x.
The following proposition summarizes some basic properties of second–order mollified derivatives.
Proposition 7 Let f : Rm → R and x ∈ Rm .
i) If λ > 0, then:
D 2ψ λf (x; d) = λD 2ψ f (x; d);
D 2ψ λf (x; d) = λD 2ψ f (x; d).
Moreover, if λ < 0 we get:
D 2ψ λf (x; d) = λD 2ψ f (x; d).
9
ii) The maps (d, v) → D 2ψ f (x; d, v) and (d, v) → D 2ψ f (x; d, v) are symmetric (that
is D 2ψ f (x; d, v) = D 2ψ f (x; v, d) and D 2ψ f (x; d, v) = D 2ψ f (x; v, d) ∀d, v ∈ Rm ).
iii) The functions D 2ψ f (x; d, ·) and D 2ψ f (x; d, ·) are positively homogeneous, for
any fixed d ∈ Rm .
iv) Whenever d ∈ Rm , if D 2ψ f (x; d, ·) 6= −∞ (D 2ψ f (x; d, ·) 6= +∞ resp.), then it
is sublinear (superlinear).
v) D 2ψ f (x; d, −v) = −D 2ψ f (x; d, v), ∀d, v ∈ Rm .
vi) Whenever x ∈ Rm , D 2ψ f (·; d, v) is upper semicontinuous (u.s.c.) at x for every
d, v ∈ Rm .
vii) Whenever x ∈ Rm , D 2ψ f (·; d, v) is lower semicontinuous (l.s.c.) at x for every
d, v ∈ Rm .
viii) If f (x) = g(x) + h(x), with g of class C 2 and h = 0 a.e., then D 2ψ f (x; d, v) =
D 2ψ f (x; d, v) = d> Hg(x)v.
Proof: i), ii), iii) and viii) are obvious from the definitions. The proof of iv) is
similar to that of Proposition 6.
To prove v), observe that we have:
D 2ψ f (x; d, −v) =
=
sup lim sup −d> Hfn (xn )v =
xn →x n→+∞
sup − lim inf d> Hfn (xn )v =
xn →x
n→+∞
= − inf lim inf d> Hfn (xn )v =
xn →x n→+∞
= −D 2ψ f (x; d, v).
The proofs of vi) and vii) are analogous to that of Proposition 5.
In the following we will set for simplicity:
D 2ψ f (x; d) := D 2ψ f (x; d, d)
and:
D 2ψ f (x; d) := D 2ψ f (x; d, d).
10
2
Remark 5 One of the main advantages of considering mollified derivatives is that
we need not to go through a first–order approximation to get the second–order
derivative. Practically we derive both first and second–order generalized derivatives
as the limit of two indipendent well defined sequences of “numbers”.
Using these notions of derivatives, we shall introduce a Taylor’s formula for
strongly semicontinuous functions:
Theorem 3 (Mean value theorem and Taylor’s formula) Let f : Rm → R be
a s.l.s.c. (resp. s.u.s.c.) function and let n ↓ 0, t > 0, d and x ∈ Rm .
i) If ψn ∈ C 1 is a sequence of mollifiers, there exists a point ξ ∈ [x, x + td] such
that:
f (x + td) − f (x) ≤ tD ψ f (ξ; d)
(f (x + td) − f (x) ≥ tD ψ f (ξ; d))
ii) If ψn ∈ C 2 is a sequence of mollifiers, there exists ξ ∈ [x, x + td] such that:
t2
2
2 D ψ f (ξ; d),
2
+ t2 D 2ψ f (ξ; d))
f (x + td) − f (x) ≤ tD ψ f (x; d) +
(f (x + td) − f (x) ≥ tD ψ f (x; d)
assuming that the righthand sides are well defined, i.e. it does not happen the
expression +∞ − ∞.
Proof: We prove only the second part. The proof of the first part is similar.
For any xn → x, we can easily write Taylor’s formula for each mollified function:
fn (xn + td) − fn (xn ) = t∇fn (xn )> d +
t2 >
d Hfn (ξn )d
2
where ξn ∈ (xn , xn + td). Without loss of generality, we can think that ξn → ξ ∈
[x, x + td]. Now, we consider the lim sup as n → +∞ and the definition of D ψ f (x; d)
and D 2ψ f (x; d) to get:
lim sup fn (xn + td) − lim sup fn (xn ) ≤ lim sup[fn (xn + td) − fn (xn )] ≤
n→+∞
n→+∞
t2 >
>
≤ lim sup[t∇fn (xn ) d +
n→+∞
2
n→+∞
d Hfn (ξn )d] ≤ tD ψ f (x; d) +
11
t2 2
D f (ξ; d).
2 ψ
By the strong lower semicontinuity assumed on f , there exists a sequence yn → x
such that:
lim fn (yn ) = f (x).
n→+∞
Thus, recalling Theorem 2, we have, considering in particular this sequence:
lim sup fn (yn + td) − lim sup fn (yn ) = lim sup fn (yn + td) − lim fn (yn ) ≥
n→+∞
n→+∞
n→+∞
n→+∞
lim inf fn (yn + td) − lim fn (yn ) ≥ f (x + td) − f (x),
n→+∞
n→+∞
from which the thesis follows.
The other formula follows in a similar way, recalling Proposition 2 instead of Theorem 2.
2
It should be clear that, for both semicontinuity of the generalized derivatives and
Taylor’s formula, we need some conditions to avoid “triviality” of the derivatives,
such as local Lipschitziannes of f so that, as already seen, the first–order mollified
derivative is finite, since it coincides with Clarke’s derivative.
Remark 6 One has to observe that the previous second–order derivatives may be
infinity. Furthermore they are dependent on the specific family of mollifiers which
we choose and also on the sequence n . However the results presented above and
those in the sequel hold true for any mollifiers sequence (provided the mollifiers are
at least of class C 2 ) and for any choice of n .
Now we wish to prove that for a suitable class of functions, D 2ψ f (x; d, v) and
D 2ψ f (x, v, d) are finite, independent on εn and on the choice of the mollifiers sequence
ψεn ∈ C 2 and coincide with the second–order derivative in Clarke’s sense introduced
in [6] and [13].
Before proving this result we recall the definition and the theorem that follow.
Definition 9 A function f : Rm → R is said to be of class C 1,1 at x0 ∈ Rm when it
is differentiable in a neighborhood of x0 and its gradient is locally Lipschitz at x0 .
Theorem 4 ([18]) Let f : Rm → R be a bounded function. Then f is of class C 1,1
at x0 ∈ Rm if and only if there exist a neighborhood U of x0 , a right neighborhood
12
V of 0 ∈ R and a constant M ≥ 0 such that:
f (x + 2td) − 2f (x + td) + f (x) ≤ M,
t2
∀x ∈ U, t ∈ V and d ∈ S 1 (the unit sphere in Rm ).
Theorem 5
i) A continuous function f : Rm → R is of class C 1,1 at x0 ∈ Rm
if and only if there exist a neighborhood U of x0 , and a constant M ≥ 0 such
that, for every choice of sequences εn ↓ 0 and ψεn ∈ C 2 it holds:
−M ≤ D 2ψ f (x; d) ≤ D 2ψ f (x; d) ≤ M,
for every x ∈ U and d ∈ S 1 .
ii) if f : Rm → R is a function of class C 1 in a neighborhood of x0 ∈ Rm , then:
∇f (x0 + tv)> d − ∇f (x0 )> d
,
t
x0 →x,t↓0
D 2ψ f (x; d, v) = lim sup
for any choice of the sequence n ↓ 0 and of the mollifiers ψn ∈ C 2 .
Proof:
i) Necessity. Let f be a function of class C 1,1 at x0 and let ψε We prove that there
exists a constant M ≥ 0 and a positive number ε0 such that |d> Hfε (x)d| ≤ M ,
∀x ∈ Rm , ∀d ∈ S 1 and ∀ε ∈ (0, ε0 ).
It is easy to see that for every ε > 0 we have:
d> Hfε (x)d = lim
t↓0
Z
lim
t↓0
Rm
fε (x + 2td) − 2fε (x + td) + fε (x)
=
t2
f (x − z + 2td) − 2f (x − z + td) + f (x)
ψε (z)dz.
t2
Recalling theorem 4, we have that for x and z in suitable neighborhoods U of
x0 and U 0 of 0 ∈ Rm respectively, d ∈ S 1 and t > 0 ”small enough”, it holds:
f (x − z + 2td) − 2f (x − z + td) + f (x) ≤ M,
t2
for some constant M ≥ 0. Hence, remembering Definition 1, it follows the
existence of a number
Z
>
d Hfε (x)d ≤ lim
t↓0
ε0 > 0 such that:
f (x − z + 2td) − 2f (x − z + td) + f (x) ψε (z)dz ≤ M,
t2
Rm
13
for every x ∈ U , z ∈ U 0 , d ∈ S 1 and ε ∈ (0, ε0 ). Now the thesis follows recalling
the definitions of D 2ψ f (x; d) and D 2ψ f (x; d).
Sufficiency. Let U1 be a neighborhood of x0 and V a right neighborhood of
0 ∈ R such that U1 ⊂ U and x + 2td ∈ U for every x ∈ U , t ∈ V and d ∈ S 1 .
We can write, for such x, t and d and for every couple of sequences εn ↓ 0 and
ψεn ∈ C 2 :
fεn (x + 2td) = fεn (x) + 2t∇fεn (x)> d + 2t2 d> Hfεn (ξn )d,
where ξn ∈ (x, x + 2td), ∀n and:
fεn (x + td) = fεn (x) + t∇fεn (x)> d +
t2 >
d Hfεn (ξn0 )d,
2
where ξn0 ∈ (x, x + td), ∀n. Hence we have:
fεn (x + 2td) − 2fεn (x + td) + fεn (x)
= 2d> Hfεn (ξn )d − d> Hfεn (ξn0 )d.
t2
Sending n to +∞, without loss of generality we can assume that ξn → ξ ∈
[x, x+2td] and ξn0 → ξ 0 ∈ [x, x+td]and recalling Theorem 1 and the definitions
of D 2ψ f (x; d) and D 2ψ f (x; d) we have:
2D 2ψ f (ξ; d) − D 2ψ f (ξ 0 ; d) ≤ lim inf 2d> Hfεn (ξn )d − lim sup d> Hfεn (ξn0 )d ≤
n→+∞
≤
n→+∞
f (x + 2td) − 2f (x + td) + f (x)
≤ lim sup 2d> Hfεn (ξn )d−
t2
n→+∞
− lim inf d> Hfεn (ξn0 )d ≤ 2D 2ψ f (ξ; d) − D 2ψ f (ξ 0 ; d).
n→+∞
Hence, since
D 2ψ f (x; d)
and D 2ψ f (x; d) are bounded by a constant M for x ∈ U
and d ∈ S 1 , we obtain:
−3M ≤
f (x + 2td) − 2f (x + td) + f (x)
≤ 3M.
t2
Now the proof is complete recalling theorem 4.
ii) If f is of class C 1 in a neighborhood of x0 , we obtain for i = 1, · · · , m:
Z
∂fε
∂f
∂f
(x) =
(x − z)ψε (z)dz =
(x).
∂xi
∂xi ε
Rm ∂xi
The proof is complete recalling Proposition 4.10 in [8].
2
14
Remark 7 Point ii) of the previous theorem implies that when f is a function of
class C 1,1 at x0 , D 2ψ f (x0 ; d, v) coincides with the derivative introduced in [6] and [13],
that is Clarke’s generalized derivative of ∇f (·)> d at x0 in the direction v. Hence,
in this case D 2ψ f (x0 ; d, v) is finite. (This last property holds also for D 2ψ f (x0 ; d, v)
since it coincides with −D 2ψ f (x0 ; d, −v)).
4
Optimality Conditions
In this section we give second–order necessary and sufficient optimality conditions.
We begin considering the following problem:
P1 )
minx∈K f (x)
where K ⊆ Rm .
Definition 10 The radial tangent cone of the set K at x is given by:
R(K, x) := {d ∈ Rm | ∀α > 0 : ∃t ∈ (0, α) , x + td ∈ K} =
{d ∈ Rm | ∃tn ↓ 0 : x + tn d ∈ K} .
Definition 11 The set:
T (K, x0 ) := {d ∈ Rm | ∃dn → d, ∃tn ↓ 0 : x0 + tn dn ∈ K}
is called the Bouligand tangent cone of the set K at x.
Clearly we have the following inclusion:
R(K, x) ⊆ T (K, x).
Definition 12 The second–order radial tangent set of K at x in the direction d is:
t2n
2
m
R (K, x, d) = w ∈ R | ∃tn ↓ 0 : x + tn d + w ∈ K .
2
Clearly R2 (K, x, 0) = R(K, x).
15
Theorem 6 Let f : Rm → R be s.l.s.c., let εn ↓ 0 and ψεn ∈ C 2 and assume
that D ψ f (x0 ; d) is finite for every d ∈ Rm and D 2ψ f (x0 ; d, w)y is finite for every d
d, w ∈ Rm . If x0 ∈ K is a local solution of problem P1 ), then:
i) D ψ f (x0 ; d) ≥ 0, ∀d ∈ R(K, x0 ),
ii) If d ∈ Rm is such that D ψ f (x0 ; d) = 0, then D ψ f (x0 ; w) + D 2ψ f (x0 ; d) ≥ 0,
∀w ∈ R2 (K, x0 , d).
Proof: i) Let d ∈ R(K, x0 ). Then there exists a sequence tn ↓ 0 such that x0 + tn d ∈
K. Since x0 is optimal, applying the mean value theorem, we obtain:
0 ≤ f (x0 + tn d) − f (x0 ) ≤ D ψ f (ξn ; d),
where for every n, ξn ∈ [x0 , x0 + tn d]. Hence, from the upper semicontinuity of
D ψ f (x0 ; d), we have:
0 ≤ lim sup D ψ f (ξn ; d) ≤ lim sup D ψ f (x0 ; d) ≤ D ψ f (x0 ; d).
x0 →x0
n→+∞
ii) Let d ∈ Rm be such that D ψ f (x0 ; d) = 0 and let w ∈ R2 (K, x0 , d). Hence there
exists a sequence tn ↓ 0 such that x0 + tn d +
t2n
2w
∈ K and we have, for n ”large
enough”:
0 ≤ f (x0 + tn d +
t2
t2n
tn
tn
w) − f (x0 ) ≤ tn D ψ f (x0 ; d + w) + n D 2ψ f (ξn ; d + w),
2
2
2
2
where ξn ∈ [x0 , x0 + tn d +
t2n
2 w].
Recalling the sublinearity of D ψ f (x0 ; ·) and of
D 2ψ f (x0 ; d, ·), the simmetry of D 2ψ f (x0 , d, v) and that by definition D 2ψ f (x0 ; d) =
D 2ψ f (x0 ; d, d), we have:
0 ≤ f (x0 + tn d +
t2n
t2
w) − f (x0 ) ≤ tn D ψ f (x0 ; d) + n D ψ f (x0 ; w)+
2
2
t2n 2
t4
t3
D ψ f (ξn ; d) + n D 2ψ f (ξn ; w) + n D 2ψ f (ξn ; d, w) =
2
8
2
t2n
t2n 2
t4n 2
t3
D ψ f (x0 ; w) + D ψ f (ξn ; d) + D ψ f (ξn ; w) + n D 2ψ f (ξn ; d, w).
2
2
8
2
Now observe that from the finiteness assumption on the derivatives and their upper
+
semicontinuity it follows that, for every ε > 0, there exists a positive integer n0 such
that, for every n > n0 it holds:
D 2ψ f (ξn ; d) ≤ D 2ψ f (x0 ; d) + ε;
16
D 2ψ f (ξn ; w) ≤ D 2ψ f (x0 ; w) + ε;
D 2ψ f (ξn ; d, w) ≤ D 2ψ f (x0 ; d, w) + ε.
Hence for n ” large enough” it holds:
0≤
f (x0 + tn d +
≤ D ψ f (x0 ; w) + D 2ψ f (x0 ; d) + ε +
t2n
2 w)
− f (x0 )
t2n
2
≤
t2n 2
[D ψ f (x0 ; w) + ε] + tn [D 2ψ f (x0 ; d, w) + ε].
4
Sending n to +∞ we obtain, since ε is arbitrary:
D ψ f (x0 ; w) + D 2ψ f (x0 ; d) ≥ 0
and the theorem is proved.
2
Corollary 1 Under the assumptions of Theorem 6, a necessary condition for x0 to
be a local solution of Problem P1 ) is that:
i) D ψ f (x0 ; d) ≥ 0, ∀d ∈ R(K, x0 );
ii) D 2ψ f (x0 ; d) ≥ 0, ∀d ∈ R(K, x0 )
suchthat
D ψ f (x0 ; d) = 0.
Proof: It follows from the previous theorem, observing that if d ∈ R(K, x0 ), then
0 ∈ R2 (K, x0 , d).
2
Remark 8 In Example 2, the point x = 0 is not a minimizer and does not satisfy
condition i) of the previuos Theorem. On the contrary x = 0 fulfils necessary
optimality conditions expressed through Clarke generalize derivative (fC0 f (0; d) ≥
0, ∀d).
Remark 9 When K is an open subset of Rm , then from corollary 1 one obtains that
the following conditions are necessary for x0 to be an unconstrained local minimizer
of f :
i) D ψ f (x0 ; d) ≥ 0, ∀d ∈ Rm ;
17
ii) D 2ψ f (x0 ; d) ≥ 0, ∀d ∈ Rm
suchthat
D ψ f (x0 ; d) = 0.
Theorem 7 Let f : Rm → R be s.u.s.c., x0 ∈ K and assume that for some choice of
sequences εn ↓ 0 and ψεn ∈ C 2 , one of the following conditions holds ∀d ∈ T (K, x0 ) ∩
S1:
i) if D ψ f (x0 ; d) > 0, then there exist a real number α(d) > 0 and a neighborhood
of the direction d, say U (d) such that:
D ψ f (x0 + td0 ; d0 ) > 0, ∀t ∈ (0, α(d)), ∀d0 ∈ U (d) ∩ S 1 ;
ii) if D ψ f (x0 ; d) = 0, then there exist a real number α(d) > 0 and a neighborhood
of the direction d, say U (d), such that, for each t ∈ (0, α(d)) and for each
d0 ∈ U (d) ∩ S 1 we have D ψ f (x0 ; d0 ) ≥ 0 and D 2ψ f (x0 + td0 ; d0 ) > 0.
Then x0 is a local solution of problem P1 ).
Proof: Ab assurdo, let assume there exists a feasible sequence xn → x0 such that
f (xn ) < f (x0 ). It can be easily written, without loss of generality xn = x0 + tn dn ,
dn ∈ S 1 , dn → d ∈ S 1 , tn ↓ 0, and hence d ∈ T (K, x0 ).
i) If D ψ f (x0 ; d) > 0, then, as n → +∞:
0 ≥ f (x0 + tn dn ) − f (x0 ) ≥ tn D ψ f (ξn ; dn ),
with ξn ∈ [x0 , x0 + tn dn ], which is trivially a contradiction.
ii) If D ψ f (x0 ; d) = 0, then:
0 ≥ f (x0 + tn dn ) − f (x0 ) ≥ tn D ψ f (x0 ; dn ) +
t2 2
D f (ξn ; dn ),
2 ψ
with ξn ∈ [x0 , x0 + tn dn ], which is again a contradiction.
2
Remark 10 Conditions similar to those of the previous theorem have been proved
in [32] for functions of class C 1,1 .
18
Now we deal with the following constrained optimization problem:
P2 )
min f (x)
s.t.
gi (x) ≤ 0, i = 1, . . . , r
where f, gi : Rm → R. We will define the set of active constraints at a point
x0 as the index set I(x0 ) : {i = 1, . . . , r : gi (x0 ) = 0} and the feasible set as
Γ := {x ∈ Rm : gi (x) ≤ 0, i = 1, . . . , r}.
Concerning this problem, we will first investigate first–order conditions expressed
by means of mollified derivatives.
Lemma 1 (Generalized Abadie Lemma) Let f and gi be s.l.s.c. for i ∈ I(x0 ),
gi be u.s.c. for i ∈
/ I(x0 ) and assume that x0 ∈ Γ is a local solution of problem P2 ).
Then, whatever the choice of sequences εn ↓ 0 and ψεn ∈ C 2 , @d ∈ Rm such that:

 D f (x ; d) < 0
ψ
0
 D ψ gi (x0 ; d) < 0, i ∈ I(x0 )
Proof: Since x0 is a local solution of P2 ), we can easily check that, ∀d ∈ Rm ,
@α(d) > 0 such that ∀t ∈ (0, α(d)):

 D f (x + td; d) < 0
0
ψ
 D ψ gi (x0 + td; d) < 0, i ∈ I(x0 )
Indeed, if for some d such an α(d) would exist, from Theorem 3 we would get,
∀t ∈ (0, α(d)):
f (x0 + td) < f (x0 )
and
gi (x0 + td) < 0,
i ∈ I(x0 ).
Since gi , i ∈
/ I(x0 ) are u.s.c. we obtain also, for t “small enough”, gi (x0 + td) <
0, i ∈
/ I(x0 ). This fact contradicts that x0 ∈ Γ is a local solution of P2 ).
Hence, for any fixed d ∈ Rm one can find a sequence tn ↓ 0 such that for all n it
holds or D ψ f (x0 + tn d; d) ≥ 0 either D ψ gi (x0 + tn d; d) ≥ 0, for some fixed i ∈ I(x0 ).
Recalling that the first–order upper mollified derivative is u.s.c. we obtain that
either D ψ f (x0 ; d) ≥ 0 or D ψ gi (x0 ; d) ≥ 0 and hence we get the thesis.
19
2
Theorem 8 (Generalized F. John Conditions) Let f, gi , i ∈ I(x0 ) be s.l.s.c.,
gi , i ∈
/ I(x0 ) be u.s.c. and let εn ↓ 0 and ψεn ∈ C 2 . Assume that x0 ∈ Γ is a local
solution of problem P2 ) and that D ψ f (x0 ; ·) and D ψ gi (x0 ; ·), i ∈ I(x0 ) are finite.
Then there exist scalars τ ≥ 0, λi ≥ 0, i ∈ I(x0 ), not all zero, such that:
τ D ψ f (x0 ; d) +
≥ 0, ∀d ∈ Rm .
P
i∈I(x0 ) λi D ψ gi (x0 ; d)
(1)
Proof: ¿From the previous Lemma we know that the system:

 D f (x ; d) < 0
0
ψ
 D ψ gi (x0 ; d) < 0 i ∈ I(x0 )
has no solution. Since the first–order upper mollified derivatives are convex (Proposition 6), from a well known Theorem of the alternative ([3] Theorem 7.1.2), we
obtain the thesis.
2
Remark 11 Of course a relevant question is which conditions would ensure τ > 0
(or equivalently τ = 1) in formula (1). It can be easily seen that this is the case if
the following generalized Slater–type constraint qualification condition holds:
∃ d ∈ Rm
D ψ gi (x0 ; d) < 0, i ∈ I(x0 ).
such that
Now we prove necessary and sufficient second–order optimality conditions for
problem P2 ).
Theorem 9 Let f, gi , i ∈ I(x0 ) be s.l.s.c., gi , i ∈
/ I(x0 ) be u.s.c. and assume that
x0 ∈ Γ is a local solution of problem P2 ). Moreover let εn ↓ 0, ψεn ∈ C 2 and assume
that D ψ f (x0 ; ·) and D ψ gi (x0 ; ·), i ∈ I(x0 ), are finite.
Then, if τ ≥ 0, λi ≥ 0, i ∈ I(x0 ) satisfy (1), the following condition holds:
if d ∈ R(Γ(λ), x0 ) is such that τ D ψ f (x0 ; d) +
τ D 2ψ f (x0 ; d)
then
where Γ(λ) = {x ∈ Γ |
P
i∈I(x0 ) λi gi (x)
+
i∈I(x0 ) λi D ψ gi (x0 ; d)
2
i∈I(x0 ) λi D ψ gi (x0 ; d)
P
= 0}.
20
P
≥0
=0
(2)
Proof: Let d ∈ R(Γ(λ), x0 ) be such that τ D ψ f (x0 ; d) +
P
i∈I(x0 ) λi D ψ gi (x0 ; d)
=0
and observe that, since D ψ f (x0 ; ·) and D ψ gi (x0 ; ·), i ∈ I(x0 ) are finite, we can write,
for t > 0:
f (x0 + td) − f (x0 ) ≤ tD ψ f (x0 ; d) +
gi (x0 + td) − gi (x0 ) ≤ tD ψ gi (x0 ; d) +
t2
2
2 D ψ f (ξ; d)
t2
2
2 D ψ gi (ξi ; d),
i ∈ I(x0 )
where ξ, ξi ∈ [x0 , x0 + td].
Hence we have:
τ f (x0 + td) +
X
X
λi gi (x0 + td) − τ f (x0 ) −
i∈I(x0 )
λi gi (x0 ) ≤
i∈I(x0 )
≤
t2
2


τ D 2ψ f (ξ; d) +
X
λi D 2ψ gi (ξi ; d) .
i∈I(x0 )
For t “small enough”, the lefthandside is nonnegative and hence, using the upper
semicontinuity of second–order mollified derivatives:
X
0 ≤ lim sup[τ D 2ψ f (ξ; d) +
λi D 2ψ gi (ξi ; d)] ≤
t↓0
≤ τ
i∈I(x0 )
lim sup D 2ψ f (ξ; d)
t↓0
≤ τ D 2ψ f (x0 ; d) +
+
X
λi lim sup D 2ψ gi (ξi ; d) ≤
t↓0
i∈I(x0 )
λi D 2ψ gi (x0 ; d),
X
i∈I(x0 )
and so we get the thesis.
2
Theorem 10 Let f, gi , i ∈ I(x0 ) be s.u.s.c. and x0 ∈ Γ. Moreover, assume that for
some choice of sequences εn ↓ 0 and ψεn ∈ C 2 there exist scalars λi ≥ 0, i ∈ I(x0 )
such that ∀d ∈ T (Γ, x0 ) ∩ S 1 one of the following conditions holds:
i) If D ψ f (x0 ; d) +
P
i∈I(x0 ) λi D ψ gi (x0 ; d)
> 0, then there exist a real α(d) > 0
and a neighborhood of the direction d, U (d), so that:
D ψ f (x0 + td0 ; d0 ) +
ii) If D ψ f (x0 ; d) +
P
i∈I(x0 ) λi D ψ gi (x0
P
i∈I(x0 ) λi D ψ gi (x0 ; d)
+ td0 ; d0 ) > 0 ∀t ∈ (0, α(d)), ∀d0 ∈ U (d).
= 0, then there exist a real α(d) > 0
and a neighborhood of the direction d, U (d), so that:
D 2ψ f (x0 + td0 ; d0 ) +
2
i∈I(x0 ) λi D ψ gi (x0
P
21
+ td0 ; d0 ) > 0 ∀t ∈ (0, α(d)), ∀d0 ∈ U (d).
Then x0 is a (strict) local solution of P2 ).
Proof: By contradiction assume there exists a feasible sequence xn → x0 so that
f (xn ) − f (x0 ) ≤ 0. We shall write xn = x0 + tn dn for some dn → d ∈ T (Γ, x0 ) ∩ S 1 .
i) If D ψ f (x0 ; d) +
P
i∈I(x0 ) λi D ψ gi (x0 ; d)
> 0, then we would have:
f (x0 + tn dn ) − f (x0 ) ≥ tn D ψ f (ξn ; dn )
and
gi (x0 + tn dn ) − gi (x0 ) ≥ tn D ψ gi (ξni ; dn ), i ∈ I(x0 ),
where ξn , ξni ∈ [x0 , x0 + tn dn ]. Using multipliers λi , we get:
0 ≥ f (x0 + tn dn ) +
X
i∈I(x0 )
λi gi (x0 ) ≥
i∈I(x0 )
X
≥ tn D ψ f (ξn ; dn ) + tn
X
λi gi (x0 + tn dn ) − f (x0 ) −
λi D ψ gi (ξni ; dn )
i∈I(x0 )
which contradict the hypothesis, for n large enough.
ii) If D ψ f (x0 ; d) +
P
i∈I(x0 ) λi D ψ gi (x0 ; d)
= 0, then we shall write:
f (x0 + tn dn ) − f (x0 ) ≥ tn D ψ f (x0 ; dn ) +
t2n 2
D f (ξn ; dn )
2 ψ
and
gi (x0 + tn dn ) − gi (x0 ) ≥ tn D ψ gi (x0 ; dn ) +
t2n 2
D gi (ξni ; dn ), i ∈ I(x0 ),
2 ψ
where ξn , ξni ∈ [x0 , x0 + tn dn ]. Using multipliers λi and the assumption, we
get:
0 ≥ f (x0 + tn dn ) +
≥
X
i∈I(x0 )
t2n X
t2n 2
D f (ξn ; dn ) +
2
2 ψ
X
λi gi (x0 + tn dn ) − f (x0 ) −
λi gi (x0 ) ≥
i∈I(x0 )
λi D 2ψ gi (ξni ; dn )
i∈I(x0 )
which contradict again the hypothesis, for n large enough.
2
22
5
Characterization of convex functions
In this section we give a characterization of convex functions by means of second–
order mollified derivatives. The following result is classical:
Lemma 2 ([34]) Let f : Rm → R be a continuous function. Then f is convex if
and only if:
f (x + td) − 2f (x) + f (x − td)
≥ 0,
t2
∀x, d ∈ Rm , ∀t ∈ R.
Lemma 3 ([9]) Let f : Rm → R be a continuos function. Then f is convex if
and only if the mollified functions fε , obtained from a sequence of mollifiers ψε , are
convex for every ε > 0.
Theorem 11 Let f : Rm → R be a continuous function and let εn ↓ 0 and ψεn ∈ C 2 .
A necessary and sufficient condition for f to be convex is that:
D 2ψ f (x; d) ≥ 0, ∀x ∈ Rm , ∀d ∈ Rm .
Proof: Necessity. By definition:
D 2ψ f (x; d) = inf lim inf d> Hfεn (xn )d.
xn →x n→+∞
Recalling the previous lemma, from the convexity of the functions fε , we have:
d> Hfεn (x)d ≥ 0, ∀x, d ∈ Rm , ∀n
and the necessity follows.
Sufficiency. We can write for every n:
fεn (x + td) − 2fεn (x) + fεn (x − td)
=
t2
t2 >
t2 >
1
>
0
= 2 t∇fεn (x) d + d Hfεn (ξn )d − t∇fεn (x)d + d Hfεn (ξn )d =
t
2
2
=
i
1h >
d Hfεn (ξn )d + d> Hfεn (ξn0 )d ,
2
23
where ξn ∈ (x, x + td), ξn0 ∈ (x, x − td). As n → +∞ we can assume that ξn → ξ ∈
[x, x + td] and ξn0 → ξ 0 ∈ [x, x − td] and recalling Theorem 1 we obtain:
i
f (x + td) − 2f (x) + f (x − td)
1h >
>
0
=
lim
d
Hf
(ξ
)d
+
d
Hf
(ξ
)d
≥
ε
n
ε
n
n
n
n→+∞ 2
t2
lim inf d> Hfεn (ξn )d + lim inf d> Hfεn (ξn0 )d ≥
n→+∞
n→+∞
1
1
≥ D 2ψ f (ξ; d) + D 2ψ f (ξ 0 ; d) ≥ 0.
2
2
2
References
[1] Aubin J.P., Frankowska H.: Set–valued analysis. Birkhauser, Basel, 1990
[2] Aubin J.P.:Lipschitz behaviour of solutions to convex minimization problems.
Mathematics of Operations Research, 8, 1984, 87–111
[3] Bazaraa M.S., Shetty C.M.: Foundations of Optimization. Springer, Berlin,
1976
[4] Brezis H.: Analyse fonctionelle – Theorie et applications. Masson editeur,
Paris, 1963
[5] Clarke F.H.: Optimization and nonsmooth analysis. SIAM, Classics in Applied
Mathematics, Philadelphia, 1990
[6] Cominetti R., Correa R.: A generalized second–order derivative in nonsmooth
optimization. SIAM J. Control Optim., 28, 1990, 789-809.
[7] Craven B.D.: Nondifferentiable optimization by smooth approximations. Optimization, 17, 1, 1986, 3–17
[8] Ermoliev Y.M., Norkin V.I.,Wets R.J.B.: The minimization of semicontinuous
functions: mollifier subgradient. SIAM J. Control and Optimization, 33, 1,
1995, 149–167.
24
[9] Evans L.C., Gariepy R.F.: Measure theory and fine properties of functions.
CRC Press, 1992.
[10] Ginchev I., Guerraggio A.:Second order optimality conditions in nonsmooth
unconstrained optimization. Pliska Stud. Math. Bulgar., 12, 1998, 39-50.
[11] Guerraggio A., Luc. D.T.: On optimality conditions for C 1,1 vector optimization problems. Journal of Optimization Theory and Applications, 109, 3, 2001,
615–629.
[12] Hiriart-Hurruty J.B.: Contributions a la programmation mathematique: deterministe et stocastique. (Doctoral thesis), Univ. Clermont-Ferrand, 1977.
[13] Hiriart-Urruty J.B., Strodiot J.J., Hien Nguyen V.: Generalized Hessian matrix and second–order optimality conditions for problems with C 1,1 data. Appl.
Math. Optim., 11, 1984, 43-56.
[14] Ioffe A.D., Nonsmooth Analysis: differentiable calculus of nondifferentiable
mappings. Transaction of American Mathematical Society, 266, 1981, 1–56
[15] Jeyakumar V., Luc D.T.: Approximate Jacobian matrices for nonsmooth continuous maps and C 1 –optimization. SIAM J. Control and Optimization, 36, 5,
1998, 1815–1832
[16] Klatte D., Tammer K.: On second–order sufficient optimality conditions for
C 1,1 optimization problems. Optimization, 19, 1988, 169-179.
[17] La Torre D., Rocca M.: C k,1 functions and divided differences. Real Analysis
Exchange, 25, 1999-2000,743-752.
[18] La Torre D., Rocca M.: C 1,1 functions on Rn and Riemann derivatives. Journal
of Computational Analysis and Applications, to appear.
[19] Luc D.T.: Taylor’s formula for C k,1 functions. SIAM J. Optimization, 5, 1995,
659-669.
[20] Michel P., Penot J.P.: Second-order moderate derivatives. Nonlin. Anal., 22,
1994, 809–824.
25
[21] Michel P., Penot J.P.: Calcul sous-diff´erential pour des fonctions lischitziennes
an nonlipschitziennes. Comptes Rendus de l’Academie des Sciences Paris, 298,
1984, 269–272.
[22] Qi L., Sun D.: Smoothing functions and smoothing Newton methods for complementarity and variational inequalities problems. Journal of Optimization
Theory and Applications, 113, 2002, 121–147.
[23] Rockafellar R.T.: The theory of subgradients and its application to problems
of optimization: convex and nonconvex functions. Heldermann Verlag, Berlin,
1981
[24] Rockafellar R.T., Wets R. J–B.: Variational systems, an introduction, multifunctions and integrands. G. Salinetti ed., Lecture Notes in Mathematics 1091,
Springer–Verlag, Berlin, 1–54, 1984
[25] Rockafellar R.T., Wets R. J–B.: Variational Analysis. Springer–Verlag, Berlin,
1998
[26] Schwartz L.: Th´eorie des distributions. Hermann, Paris, 1966
[27] Sobolev S.L.: Some applications of functional analysis in mathematical phisics.
3rd ed., Nauka, Moscow, 1988 (In Russian)
[28] Warga J.: Necessary conditions without differentiability assumptions in optimal control. J. Differential Equations, 15, 1975, 41-61.
[29] Warga J.: Derivative Containers, inverse functions and controllability. Calculus of Variations and Control Theory, D. Russell ed., Academic Press, New
York, 1976, 13-46.
[30] Warga J.: Fat homeomorphisms and unbounded derivate containers. J. Math.
Anal. Appl., 81, 1981, 545-560.
[31] Yang X.Q., Jeyakumar V.: Generalized second–order directional derivatives
and optimization with C 1,1 functions. Optimization, 26, 1992, 165-185.
26
[32] Yang X.Q.: Second–order conditions in C 1,1 optimization with applications.
Numer. Funct. Anal. and Optimiz., 14, 1993, 621-632.
[33] Yang X.Q.: On second–order directional derivatives. Nonlinear Anal.-TMA,
26, 1, 1996, 55-66.
[34] Zygmund A.: Trigonometric series. Cambridge, 1959.
27
La serie dei Working Papers del Dipartimento di Economia Politica e Aziendale può essere richiesta
al seguente indirizzo: Sezione Working Papers - Dipartimento di Economia Politica e Aziendale Università degli Studi di Milano, Via Conservatorio 7 - 20122 Milano - Italy - fax 39-02-50321450
- Email: [email protected]. A partire dal numero 98.01, i working papers sono scaricabili dal sito
Internet del dipartimento, all’indirizzo:
http://www.economia.unimi.it
The Working Paper Series of the Dipartimento di Economia Politica e Aziendale can be requested
at the following address: Sezione Working Papers - Dipartimento di Economia Politica e Aziendale
- Università degli Studi di Milano, Via Conservatorio 7 - 20122 Milano - Italy - fax 39-0250321450 - Email: [email protected]. From number 98.01, working papers are downloadable from
the Internet website of the Department at the following location:
http://www.economia.unimi.it
Papers già pubblicati/Papers already published
94.01 – D. CHECCHI, La moderazione salariale negli anni 80 in Italia. Alcune ipotesi interpretative basate sul
comportamento dei sindacati
94.02 – G. BARBA NAVARETTI, What Determines Intra-Industry Gaps in Technology? A Simple Theoretical
Framework for the Analysis of Technological Capabilities in Developing Countries
94.03 – G. MARZI, Production, Prices and Wage-Profit Curves:An Evaluation of the Empirical Results
94.04 – D. CHECCHI, Capital Controls and Conflict of Interests
94.05 – I. VALSECCHI, Job Modelling and Incentive Design: a Preliminary Study
94.06 – M. FLORIO, Cost Benefit Analysis: a Research Agenda
94.07 – A. D’ISANTO, La scissione di società e le altre operazioni straordinarie: natura, presupposti economici e
problematiche realizzative
94.08 – G. PIZZUTTO, Esistenza dell’ equilibrio economico generale: approcci alternativi
94.09 – M. FLORIO, Cost Benefit Analysis of Infrastructures in the Context of the EU Regional Policy
94.10 – D. CHECCHI - A. ICHINO - A. RUSTICHINI, Social Mobility and Efficiency - A Re-examination of the
Problem of Intergenerational Mobility in Italy
94.11 – D. CHECCHI - G. RAMPA - .L. RAMPA, Fluttuazioni cicliche di medio termine nell’economia italiana del
dopoguerra
95.01 – G. BARBA NAVARETTI, Promoting the Strong or Supporting the Weak? Technological Gaps and
Segmented Labour Markets in Sub-Saharan African Industry
95.02 – D. CHECCHI, I sistemi di assicurazione contro la disoccupazione: un'analisi comparata
95.03 – I. VALSECCHI, Job Design and Maximum Joint Surplus
95.04 – M. FLORIO, Large Firms, Entrepreneurship and Regional Policy: "Growth Poles" in the Mezzogiorno over
Forty Years
95.05 – V. CERASI - S. DALTUNG, The Optimal Size of a Bank: Costs and Benefits of Diversification
95.06 – M. BERTOLDI, Il miracolo economico dei quattro dragoni: mito o realtà?
95.07 – P. CEOLIN, Innovazione tecnologica ed alta velocità ferroviaria: un'analisi
95.08 – G. BOGNETTI, La teoria della finanza a Milano nella seconda metà del Settecento: il pensiero di Pietro
Verri
95.09 – M. FLORIO, Tax Neutrality in the King-Fullerton Framework, Investment Externalities, and Growth
95.10 – D. CHECCHI, La mobilità sociale: alcuni problemi interpretativi e alcune misure sul caso italiano
95.11 – G. BRUNELLO - D. CHECCHI , Does Imitation help? Forty Years of Wage Determination in the Italian
Private Sector
95.12 – G. PIZZUTTO, La domanda di lavoro in condizioni di incertezza
95.13 – G. BARBA NAVARETTI - A. BIGANO, R&D Inter-firm Agreements in Developing Countries. Where?
Why? How?
95.14 – G. BOGNETTI - R. FAZIOLI, Lo sviluppo di una regolazione europea nei grandi servizi pubblici a rete
96.01 – A. SPRANZI, Il ratto dal serraglio di W. A. Mozart. Una lettura non autorizzata
96.02 – G. BARBA NAVARETTI - I. SOLOAGA - W. TAKACS, Bargains Rejected? Developing Country Trade
Policy on Used Equipment
96.03 – D. CHECCHI - G. CORNEO, Social Custom and Strategic Effects in Trade Union Membership:
Italy 1951-1993
96.04 – V. CERASI, An Empirical Analysis of Banking Concentration
96.05 – M. FLORIO, Il disegno dei servizi pubblici locali dal socialismo municipale alla teoria degli incentivi
96.06 – G. PIZZUTTO, Piecewise Deterministic Markov Processes and Investment Theory under Uncertainty:
Preliminary Notes
96.07 – I. VALSECCHI, Job Assignment and Promotion
96.08 – D. CHECCHI, L'efficacia del sistema scolastico in prospettiva storica
97.01 – I. VALSECCHI, Promotion and Hierarchy: A Review
97.02 – D. CHECCHI, Disuguaglianza e crescita. Materiali didattici
97.03 – M. SALVATI, Una rivoluzione copernicana: l'ingresso nell'Unione Economica e Monetaria
97.04 – V. CERASI - B. CHIZZOLINI - M. IVALDI, The Impact of Deregulation on Branching and Entry Costs in
the Banking Industry
97.05 – P.L. PORTA, Turning to Adam Smith
97.06 – M. FLORIO, On Cross-Country Comparability of Government Statistics:OECD National Accounts 1960-94
97.07 – F. DONZELLI, Pareto's Mechanical Dream
98.01 – V. CERASI - S. DALTUNG, Close-Relationships between Banks and Firms: Is it Good or Bad?
98.02 – M. FLORIO - R. LUCCHETTI - F. QUAGLIA, Grandi e piccole imprese nel Centro-Nord e nel Mezzogiorno:
un modello empirico dell'impatto occupazionale nel lungo periodo
98.03 – V. CERASI – B. CHIZZOLINI – M. IVALDI, Branching and Competitiveness across Regions in the Italian
Banking Industry
98.04 – M. FLORIO – A. GIUNTA, Planning Contracts in Southern Italy, 1986-1997: a Prelimary Evaluation
98.05 – M. FLORIO – I. VALSECCHI, Planning Agreements in the Mezzogiorno: a Principle Agent Analysis
98.06 – S. COLAUTTI, Indicatori di dotazione infrastrutturale: un confronto tra Milano e alcune città europee
98.07 – G. PIZZUTTO, La teoria fiscale dei prezzi in un’economia aperta
98.08 – M. FLORIO, Economic Theory, Russia and the fading “Washington Consensus”
99.01 – A. VERNIZZI – A. SABA, Alcuni effetti della riforma della legislazione fiscale italiana nei confronti delle
famiglie con reddito da lavoro dipendente
99.02 – C. MICHELINI, Equivalence Scales and Consumption Inequality: A Study of Household Consumption Patterns
in Italy
99.03 – S.M. IACUS, Efficient Estimation of Dynamical Systems
99.04 – G. BOGNETTI, Nuove forme di gestione dei servizi pubblici
99.05 – G.M. BERNAREGGI, Milano e la finanza pubblica negli anni 90: attualità e prospettive
99.06 – M. FLORIO, An International Comparison of the Financial and Economic Rate of Return of Development
99.07 – M. FLORIO, La valutazione delle politiche di sviluppo locale
99.08 – I. VALSECCHI, Organisational Design: Decision Rules, Operating Costs and Delay
99.09 – G. PIZZUTTO, Arbitraggio e mercati finanziari nel breve periodo. Un’introduzione
00.01 – D. LA TORRE – M. ROCCA, A.e. Convex Functions on Rn
00.02 – S. M. IACUS – YU A. KUTOYANTS, Semiparametric Hypotheses Testing for Dynamical Systems with Small
Noise
00.03 – S. FEDELI – M. SANTONI, Endogenous Institutions in Bureaucratic Compliance Games
00.04 – D. LA TORRE – M. ROCCA, Integral Representation of Functions: New Proofs of Classical Results
00.05 – D. LA TORRE – M. ROCCA, An Optimization Problem in IFS Theory with Distribution Functions
00.06 – M. SANTONI, Specific excise taxation in a unionised differentiated duopoly
00.07 – H. GRAVELLE – G. MASIERO, Quality incentives under a capitation regime: the role of patient expectations
00.08 – E. MARELLI – G. PORRO, Flexibility and innovation in regional labour markets: the case of Lombardy
00.09 – A. MAURI, La finanza informale nelle economie in via di sviluppo
00.10 – D. CHECCHI, Time series evidence on union densities in European countries
00.11 – D. CHECCHI, Does educational achievement help to explain income inequality?
00.12 – G. BOESSO – A. VERNIZZI, Carichi di famiglia nell’Imposta sui Redditi delle Persone Fisiche in Italia e in
Europa: alcune proposte per l’Italia
01.01 G. NICOLINI, A method to define strata boundaries
01.02 – S. M. IACUS, Statistical analysis of the inhomogeneous telegrapher’s process
01.03 – M. SANTONIi, Discriminatory procurement policy with cash limits can lower imports: an example
01.04 – D. LA TORRE, L’uso dell’ottimizzazione non lineare nella procedura di compressione di immagini con IFS
01.05 – G. MASIERO, Patient movements and practice attractiveness
01.06 – S. M. IACUS, Statistic analysis of stochastic resonance with ergodic diffusion noise
01.07 – B. ANTONIOLI – G. BOGNETTI, Modelli di offerta dei servizi pubblici locali in Europa
01.08 – M. FLORIO, The welfare impact of a privatisation: the British Telecom case-history
01.09 – G. P. CRESPI, The effect of economic policy in oligopoly. A variational inequality approach.
01.10 – G. BONO – D. CHECCHI, La disuguaglianza a Milano negli anni ’90
01.11 – D. LA TORRE, On the notion of entropy and optimization problems
01.12 – M. FLORIO – A. GIUNTA, L’esperienza dei contratti di programma: una valutazione a metà percorso
01.13 – M. FLORIO – S. COLAUTTI, A logistic growth law for government expenditures: an explanatory analysis
01.14 – L. ZANDERIGHI, Town Center Management: uno strumento innovativo per la valorizzazione del centro
storico e del commercio urbano
01.15 – A. MAFFIOLETTI – M. SANTONI, Do trade union leaders violate subjective expected utility?
Some insights from experimental data
01.16 – D. LA TORRE, An inverse problem for stochastic growth models with iterated function systems
01.17 – D. LA TORRE – M. ROCCA, Some remarks on second-order generalized derivatives for C1,1 functions
01.18 – A. BUCCI, Human capital and technology in growth
01.19 – R. BRAU – M. FLORIO, Privatisation as price reforms: an analysis of consumers’ welfare change in the UK
01.20 – A. SPRANZI, Impresa e consumerismo: la comunicazione consumeristica
01.21 – G. BERTOLA – D. CHECCHI, Sorting and private education in Italy
01.22 – G. BOESSO, Analisi della performance ed external reporting: bilanci e dati aziendali on-line in Italia
01.23 – G. BOGNETTI, Il processo di privatizzazione nell’attuale contesto internazionale
02.01 – D. CHECCHI – J. VISSER, Pattern persistence in european trade union density
02.02 – G. P. CRESPI – D. LA TORRE – M. ROCCA, Second order optimality conditions for
differentiable functions
02.03 – S. M. IACUS – D. LA TORRE, Approximating distribution functions by iterated function systems
02.04 – A. BUCCI – D. CHECCHI, Crescita e disuguaglianza nei redditi a livello mondiale
02.05 – A. BUCCI, Potere di mercato ed innovazione tecnologica nei recenti modelli di crescita endogena con
concorrenza imperfetta
02.06 – A. BUCCI, When Romer meets Lucas: on human capital, imperfect competition and growth
02.07 – S. M. IACUS – D. LA TORRE, On fractal distribution function estimation and applications
02.08 – P. GIRARDELLO – O. NICOLIS – G. TONDINI, Comparing conditional variance models: theory and
empirical evidence
02.09 – L. CAMPIGLIO, Issues in the measurement of price indices: a new measure of inflation
02.10 – D. LA TORRE – M. ROCCA, A characterization of Ck,1 functions
02.11 – D. LA TORRE – M. ROCCA, Approximating continuous functions by iterated function systems and
optimization problems
02.12 – D. LA TORRE – M. ROCCA, A survey on C1,1 functions: theory, numerical methods and applications
02.13 – D. LA TORRE – M. ROCCA, C1,1 functions and optimality conditions
02.14 – D. CHECCHI, Formazione e percorsi lavorativi dei laureati dell’Università degli Studi di Milano
02.15 – D. CHECCHI – V. DARDANONI, Mobility comparisons: Does using different measures matter?
02.16 – D. CHECCHI – C. LUCIFORA, Unions and Labour Market Institutions in Europe
02.17 – G. BOESSO, Forms of voluntary disclosure: reccomendations and business practices in Europe and U.S.
02.18 – A. MAURI – C.G. BAICU, Storia della banca in Romania – Parte Prima 02.19 – D. LA TORRE – C. VERCELLIS, C1,1approximations of generalized support vector machines
02.20 – D. LA TORRE, On generalized derivatives for C1,1 vector functions and optimality conditions
02.21 – D. LA TORRE, Necessary optimality conditions for nonsmooth optimization problems
02.22 – D. LA TORRE, Solving cardinality constrained portfolio optimization problems by C 1,1 approximations
02.23 – M. FLORIO – K. MANZONI, The abnormal returns of UK privatisations: from underpricing to outperformance
02.24 – M. FLORIO, A state without ownership: the welfare impact of British privatisations 1979-1997
02.25 – S.M.IACUS – D. LA TORRE, Nonparametric estimation of distribution and density functions in presence of
missing data: an IFS approach
02.26 – S.M. IACUS – G. PORRO, Il lavoro interinale in Italia: uno sguardo all’offerta
02.27 –G.P.CRESPI – D. LA TORRE, M. ROCCA, Second-order optimality conditions for nonsmooth multiobjective
02.28– D. CHECCHI –T. JAPPELLI, School Choice and Quality
03.01– D. CHECCHI, The Italian educational system family background and social stratification
03.02 – G. NICOLINI, – D. MARASIN, I Campionamento per popolazioni rare ed elusive: la matrice dei profili
03.03 – S. COMI, Intergenerational mobility in Europe: evidence from ECHP
03.04 – A. MAURI, Origins and early development of banking in Ethiopia
03.05 – A. ALBERICI, Strategie bancarie e tecnologia
03.06 – D. LA TORRE – M. ROCCA, On C^(1,1) constrained optimization problems
03.07 – M. BRATTI – A. BUCCI, Effetti di complementarietà, accumulazione di capitale umano e crescita economica:
teoria e risultati empirici
03.08 – R. MacCULLOCH – S. PEZZINI, The role of freedom, growth and religion in the taste for revolution
03.09 – L. PILOTTI –N. RIGHETTO, Web strategy and intelligent software agents in decision process for networks
knowledge based
03.10 – G. P. CRESPI –D. LA TORRE – M. ROCCA, Mollified derivatives and second-order optimality conditions