IVANOV, IVAN GINCHEV

Доклади на Българската академия на науките Comptes rendus de l’Acad´ emie bulgare des Sciences

Tome 62, No 7, 2009

MATHEMATIQUES Th´ eorie de l’optimisation

SUBDIFFERENTIABILITY WITH RESPECT TO min-TYPE FUNCTIONS

Ivan Ginchev

(Submitted by Academician P. Kenderov on April 7, 2009)

Abstract

A characterization of the L

-subdifferentiable functions (k positive inte- ger) is obtained. Recall that a function f : R

→ R ∪ {+∞} is called L

- subdifferentiable (Rubinov [

]) if it admits a L

-subgradient at any point x

∈ dom f , that is a functional ℓ : R

→ R, ℓ(x) = min

hl

, xi, such that f (x) ≥ ℓ(x) − ℓ(x

) + f (x

), ∀x ∈ R

. We call f L

-subdifferentiable if f admits at any x

∈ dom f an L

-subgradient of special form (as explained in the paper).

Key words: abstract convexity, abstract subdifferentiability, min-type functions

2000 Mathematics Subject Classification: 49J52, 49N15

1. Introduction. The abstract convex analysis, grown after the monographs

of Pallaschke, Rolewicz [

], Singer [

] and Rubinov [

] to a mathematical

discipline with its own problems, aims to generalize the results of convex analysis

to abstract convex functions on the base of global aspects of the subdifferential

(generalizations on the base of local aspects lead to nonsmooth analysis). Its im-

portance is due mainly to applications to global optimization. One of the problems

of abstract convex analysis is to characterize the class of abstract subdifferentiable

functions. In this paper we characterize the class of L

-subdifferentiable functions,

k positive integer. The L

-subdifferentiability is defined in the next section. The

paper continues the research from [

] where this problem is solved for positively

homogeneous (PH) functions in the special case k = n, and from [

] where the

case k ≥ n + 1 is studied.

2. Preliminaries. Denote by R

:= R ∪ {+∞}. Let X be a given set and L be a set of functions ℓ : X → R. The functions from L are called abstract linear functions. For a function f : X → R

the function ℓ ∈ L, such that f(x) ≥ ℓ(x) − ℓ(x

) + f (x

), ∀x ∈ X, is called an L-subgradient of f at x

. The set ∂

f (x

) of all subgradients of f at x

is called the L-subdifferential of f at x

. If ∂

f (x

) 6= ∅, then f is called L-subdifferentiable at x

. The function f is called L-subdifferentiable, if it is L-subdifferentiable at any point x

∈ dom f :=

{x ∈ X | f (x) 6= +∞}.

The set H = H

= {h : X → R | h(x) = ℓ(x) − c, ℓ ∈ L, c ∈ R} forms the set of abstract affine functions. A function f : X → R

is said H-convex at x

, if f (x

) = sup{h(x

) | h ∈ H, h ≤ f }, and H-convex if it is H-convex at any x

∈ X. Here h ≤ f means h(x) ≤ f (x) for all x ∈ X.

In the sequel we consider the case X = R

. Then hx, yi = P

j=1

x

y

denotes the scalar product of the vectors x = (x

, . . . , x

) ∈ R

and y = (y

, . . . , y

) ∈ R

, and kxk = hx, xi

stands for the Euclidean norm of x.

In this paper we are interested in abstract subdifferentiability with respect to min-type functions. For a positive integer k we define the class of abstract linear functions L

(min-type functions) as the set of the functionals ℓ : R

→ R such that ℓ(x) = min

hl

, xi for some l

, . . . , l

∈ R

. Abstract convexity, and in particular abstract subdifferentiability, with respect to min-type functions is studied in [

] and [

]. The original aim of the present paper was to characterize the class of L

-subdifferentiable functions. This aim underwent some change as it is explained below. When k ≥ n + 1 the problem finds a satisfactory solution (compare with Rubinov [

], Theorem 5.19). So, the interesting case is k ≤ n.

Confining to PH functions in [

], we consider the case k = n as a crucial one.

Observe also that L

is the class of the linear functions, so the case k = 1 leads to the usual convexity and subdifferentiability.

For a given function f : R

→ R

and x

∈ dom f the problem to find a generic L

-subgradient ℓ meets with constructive difficulties. So, we will confine to look for L

-subgradiends ℓ(x) = min

hl

, xi from ∂

f (x

) having the property

(1) hl

, x

i = hl

, x

i = · · · = hl

, x

i (= ℓ(x

)) .

The set of all these subgradients is denoted by L

(x

). By definition L

(x

) ⊂ L

. We say that f is L

-subdifferentiable at x

if it is L

(x

)-subdifferentiable at x

, and we use to write often ∂

k

f (x

) for this subdifferential instead of ∂

k(x⁰)

f (x

).

In the sequel we use the notion of calmness originating from [

]. The function f : R

→ R

is called (globally) calm at the point x

∈ dom f if

Calm f (x

) := inf  f (x) − f (x

)

kx − x

k | x ∈ R

, x 6= x



> −∞ .

The value Calm f (x

) is called the (global) calmness of f at x

.

Proposition 1. If f is L

-subdifferentiable at x

∈ dom f , then Calm f (x

)

> −∞.

Proof. If ℓ ∈ ∂

k

f (x

) and ℓ(x) = min

hl

, xi, then for x 6= x

holds f (x) − f (x

)

kx − x

k ≥ ℓ(x) − ℓ(x

)

kx − x

k = min

hl

, x − x

i

kx − x

k ≥ − max

1≤i≤k

kl

k , whence Calm f (x

) ≥ − max

kl

k > −∞.

3. L

-subdifferentiability. Given a function f : R

→ R

, a point x

∈ R

, an m-dimensional subspace L ⊂ R

, and a vector ζ ∈ R

, we introduce the function

f ˜

(x) =

 f (x

) + hζ, zi , x = x

+ z, z ∈ L , f (x) , otherwise .

With the function f we relate the following condition:

C (f, x

, L, ζ) : inf

z∈L

Calm ˜ f

(x

+ z) > −∞ .

Given a function g : R

→ R

and a subspace L, we denote by g|

the restriction of g on L. The dual space of L is denoted by L

(that is L

stands for the set of the linear functionals on L). The notation ∂g|

(x

) denotes the subdifferential of g|

at x

∈ L, that is

∂g|

(x

) = {ℓ

∈ L

| g|

(x) ≥ ℓ

(x) − ℓ

(x

) + g|

(x

) for all x ∈ L} . The elements ℓ

∈ ∂g|

(x

) are called subgradients of g|

at x

. From the repre- sentation ℓ

(x) = hζ, xi with appropriate ζ ∈ R

, we can identify the functional ℓ

with the vectors ζ, considering equivalent any two vectors ζ

, ζ

, which difference ζ

− ζ

is orthogonal to L. On the basis of this identification the subdifferential

∂g|

(x

) is considered as a set of vectors ζ ∈ R

. In this sense in the sequel we use to write ζ ∈ ∂g|

(x

).

Theorem 1. Let f : R

→ R

and x

∈ dom f . Let k be integer with 1 ≤ k ≤ n. Then f is L

-subdifferentiable at x

if and only if there exists an (n + 1 − k)-dimensional subspace L ⊂ R

with x

∈ L, and there exists ζ ∈ ∂f |

, such that condition C(f, x

, L, ζ) is satisfied.

Proof. Necessity. Let f be L

-subdifferentiable at x

∈ dom f , and let ℓ ∈ ∂

k

f (x

). Then ℓ(x) = min

hl

, xi and (1) holds. Actually (1) is a homo-

geneous linear system with k − 1 equations, hence of rank at most k − 1. Taking

into account that x

also solves (1), we can find an (n + 1 − k)-dimensional sub-

space L ⊂ R

such that x

∈ L and ℓ

:= ℓ|

∈ L

. Restricting the inequality

f(x) − f (x

) ≥ ℓ(x) − ℓ(x

), x ∈ R

, to L, we get ℓ

∈ ∂f |

(x

). Using this

inequality and the representation ℓ

(x) = hζ, xi, x ∈ L, we get

Calm ˜ f

(x

+ z) = inf

x∈Rn x6=x0+z

f ˜

(x) − ˜ f

(x

+ z) kx − x

− zk

≥ min



 inf

x∈Rn x6=x0+z

f (x) − f (x

) − hζ, zi

kx − x

− zk , inf

x=x0+w, w∈L w6=z

f ˜

(x) − f (x

) − hζ, zi kx − x

− zk





≥ min



 inf

x∈Rn x6=x0+z

ℓ(x) − ℓ(x

) − hζ, zi kx − x

− zk , inf

w∈L w6=z

hζ, w − zi kw − zk





≥ min



− max

1≤i≤k

kl

k , − kζk

 .

The right-hand side of this inequality is finite and does not depend on z, whence condition C(f, x

, L, ζ) is satisfied.

Sufficiency. Due to condition C(f, x

, L, ζ) there exists a constant C > 0 such that

(2) inf

z∈L

Calm ˜ f

(x

+ z) ≥ −C > −∞ .

Consider the subspace M = {x ∈ R

| hl, xi = 0 for all l ∈ L} of R

orthogonal to the subspace L. Since M is a (k − 1) -dimensional subspace, we can find k vectors m

, . . . , m

such that their convex hull S, which is a simplex, contains the ball B = {x ∈ M : kxk ≤ 1}. Let q(x) = max

hm

, xi be the support function of S. Since S ⊃ B and the support function of B is equal to kxk, it follows that

(3) q(x) := max

1≤i≤k

hm

, xi ≥ kxk, x ∈ M .

Fix x ∈ R

and let ¯ x be the orthogonal projection of x on L. Then ¯ x =

n+1−k

X

i=1

hu

, xi u

, where {u

, . . . , u

} is an orthonormal basis of L. Since ¯ x = x

+ (¯ x − x

) ∈ x

+ L, we have

(4) f ˜

(¯ x) = f (x

) + hζ, ¯ x − x

i . Since ¯ x ∈ L, from (2) we have

f ˜

(x) − ˜ f

(¯ x) ≥ −C kx − ¯ xk . Due to (3) and x − ¯ x ∈ M we get

kx − ¯ xk ≤ max

1≤i≤k

hm

, x − ¯ xi ,

so that

f ˜

(x) − ˜ f

(¯ x) ≥ − C kx − ¯ xk ≥ − C max

1≤i≤k

hm

, x − ¯ xi .

Since m

∈ M, i = 1, . . . , k, and ¯ x belongs to the subspace L being orthogonal to M, it follows that hm

, xi = 0 for i = 1, . . . , k. Using these equalities and (4) we ¯ obtain

f (x) ≥ ˜ f

(x) =  ˜ f

(x) − ˜ f

(¯ x) 

+ ˜ f

(¯ x)

≥ − C max

1≤i≤k

hm

, xi + f (x

) + hζ, ¯ x − x

i

≥ − C max

1≤i≤k

hm

, xi + f (x

) +

n+1−k

X

i=1

hu

, xi hζ, u

i − hζ, x

i , or equivalently

(5) f (x) − f (x

) ≥ min

1≤i≤k

h − C m

+

n+1−k

X

i=1

hζ, u

i u

, x i − hζ, x

i .

Here we have used the inequality f (x) ≥ ˜ f

(x) which needs to be explained only when x = x

+ z, z ∈ L. Then this inequality reduces to

f (x

+ z) − f (x

) ≥ hζ, zi , z ∈ L ,

which is true by definition since ζ ∈ ∂f |

(x

) is a subgradient of the convex function f |

.

Put now

l

= − C m

+

n+1−k

X

i=1

hζ, u

i u

, i = 1, . . . , k ,

and observe that these vectors do not depend on x (from here on x could be considered an arbitrary vector). Define the functional ℓ : R

→ R by ℓ(x) = min

hl

, xi. We have obviously

hl

, x

i = h − C m

, x

i +

n+1−k

X

i=1

hζ, u

i hu

, x

i

= h

n+1−k

X

i=1

hζ, u

i u

, x

i = h¯ ζ, x

i , i = 1, . . . , k ,

where ¯ ζ = P

i=1

hζ, u

i u

is the orthogonal projection of ζ on L. These equal- ities show that ℓ ∈ L

(x

) and

ℓ(x

) = h¯ ζ, x

i = hζ, x

i − hζ − ¯ ζ, x

i = hζ, x

i . Now inequality (5) can be written as

f (x) − f (x

) ≥ ℓ(x) − ℓ(x

) ,

which shows that ℓ ∈ ∂

k(x⁰)

, that is f is L

-subdifferentiable at x

.

The next two theorems characterize the L

-subdifferentiability in the case k ≥ n + 1. For shortness the proofs are omitted.

Theorem 2. The function f : R

→ R

is L

-subdifferentiable at 0 (provided 0 ∈ dom f ) if and only if Calm f (0) > −∞. It is L

-subdifferentiable at 0 with k > n + 1 if and only if it is L

-subdifferentiable at 0.

Theorem 3. The function f : R

→ R

is L

-subdifferentiable with k ≥ n + 1 at x

∈ dom f , x

6= 0, if and only if f is L

-subdifferentiable at x

.

The following example shows that in Theorem 1 condition C(f, x

, L, ζ) can- not be substituted by Calm ˜ f

(x

+ z) > −∞ , ∀z ∈ L.

Example 1. The function f : R

→ R

given by

f (x

, x

) =



 

 

 

 

 

 

−p|x

x

| , x

≥ x

and |x

| ≥ x

, p|x

x

| , x

≤ −x

and |x

| ≥ x

,

0 , x

x

= 0 , +∞ , otherwise .

is calm at any x ∈ dom f , but not L

-subdifferentiable at any nonzero point x

of the coordinate axes (at such a point, choosing L and ζ as in Theorem 1, we have L = {tx

| t ∈ R}, hζ, zi = 0 when z = tx

∈ L, ˜ f

(x) = f(x) whence Calm ˜ f

(x

+ z) = Calm f (x

+ z) > −∞ for z ∈ L, but inf

Calm ˜ f

(x

+ z) = −∞).

REFERENCES

[

] Crespi G. P., I. Ginchev, M. Rocca, A. Rubinov. J. Convex Anal., 14, 2007, No 1, 185–204.

[

] Pallaschke D., S. Rolewicz. Foundation of mathematical optimization (Convex analysis without linearity), Dordrecht, Kluwer Academic Publishers, 1997.

[

] Rockafellar R. T., R. J.-B. Wets. Variational analysis, Berlin, Springer, 1998.

[

] Rubinov A. M. Abstract convexity and global optimization, Dordrecht, Kluwer Academic Publishers, 2000.

[

] Shveidel A. P. Optimization, 52, 2003, 571–580.

[

] Shveidel A. P. Optimization, 56, 2007, 129–147.

[

] Singer I. Abstract convex analysis, New York, Wiley-Interscience Publication, 1997.

Department of Economics, University of Insubria Via Monte Generoso 71

21100 Varese, Italy

e-mail: ivan.ginchev@uninsubria.it