TECHNICAL NOTE

Fenchels Duality Theorem for Nearly Convex Functions 1

R. I. BOT 2, S. M. GRAD3, AND G. WANKA4

Communicated by J-P. Crouzeix

The authors are grateful to the Associated Editor for helpful suggestions and remarks which

improved the quality of the paper

Assistant Professor, Faculty of Mathematics, Chemnitz University of Technology, Chemnitz,

Germany.

Ph. D. Student, Faculty of Mathematics, Chemnitz University of Technology, Germany.

Professor, Faculty of Mathematics, Chemnitz University of Technology, Chemnitz, Germany.

Abstract. We present an extension of Fenchels duality theorem by weakening

the convexity assumptions to near convexity. These weak hypotheses are automat-

ically fullled in the convex case. Moreover we show by a counterexample that a

further extension to closely convex function is not possible under these hypotheses.

Key Words. Fenchel duality, conjugate functions, nearly convex functions.

Introduction and Preliminaries

Fenchels duality theorem (cf. Ref. 1) asserts that for f : Rn R a proper con-

vex function and for g : Rn R a proper concave function fullling ri(dom(f ))

ri(dom(g )) = there is strong duality between the primal problem inf xRn f (x) g (x) and its Fenchel dual supuRn g (u) f (u) . There were attempts to extend it, for instance see Ref. 2.

In this note we give another extension of Fenchels duality theorem, for a primal

problem having as objective the dierence between a nearly convex function and a

nearly concave one. The nearly convex functions were introduced by Aleman (Ref.

3) as p-convex (see also Ref. 4), while the nearly convex sets are due to Green and

Gustin (Ref. 5). As the name nearly convex has been used in the literature also

for other concepts, we followed the terminology used in some relevant optimization

papers (Refs. 6-8). Nearly convex functions generalize the older midconvex functions

(cf. Ref. 9) (obtained for p = 1/2).

When X Rn we use the classical notations cl(X ), a(X ), ri(X ) and X for

its closure, ane hull, relative interior and indicator function, respectively. For a 3

convex function f : Rn R we consider the following denitions: eective domain

dom(f ) = x Rn : f (x) < + , epigraph epi(f ) = (x, r) Rn R : f (x) r ,

f is proper if dom(f ) = and f (x) > x Rn , lower semicontinuous envelope

f : Rn R such that epi(f ) = cl(epi(f )) and conjugate function f : Rn R,

f (p) = supxRn pT x f (x) . Similar notions are dened for a concave function g : Rn R: dom(g ) = x

Rn : g (x) > , hyp(g ) = (x, r) Rn R : g (x) r , g is proper if dom(g ) =

and g (x) < + x Rn , its upper semicontinuous envelope g and g : Rn R,

g (p) = inf xRn pT x g (x) . We denote these notions in the same way for both convex and concave functions as the meaning arises from the context. For nearly

convex functions these notions are considered in the convex sense, while for nearly

concave ones they are taken like for concave functions. For f : Rn R and its

convex conjugate, respectively for g : Rn R and its concave conjugate, there is the

Young-Fenchel inequality f (u) + f (x) uT x g (u) + g (x) u, x Rn .

The following result coming from the convex analysis will be used later.

Lemma 1.1. (see Ref. 6) For a convex set C Rn and any set S Rn satisfying

S C we have ri(C ) S if and only if ri(C ) = ri(S ).

A set S Rn is called nearly convex if there is an (0, 1) such that for each

x, y S it follows that x + (1 )y S . Every convex set is nearly convex,

while Q is nearly convex (with = 1/2), but not convex. We give now some results

concerning nearly convex sets.

Lemma 1.2. (see Ref. 3) For every nearly convex set S Rn one has

(i) ri(S ) is convex (may be empty),

(ii) cl(S ) is convex,

(iii) for every x cl(S ) and y ri(S ) we have tx +(1 t)y ri(S ) for each 0 t < 1.

Lemma 1.3. (see Ref. 6) Let = S Rn be a nearly convex. Then ri(S ) = if

and only if ri(cl(S )) S , in this case ri(S ) = ri(cl(S )).

Closely related to the notion of a nearly convex set we consider similar notions

for functions. A function f : Rn R is nearly convex if there is an (0, 1) such

that for all x, y dom(f ) = {x Rn : f (x) < +} we have

f (x + (1 )y ) f (x) + (1 )f (y ). 5

A function g : Rn R is said to be nearly concave when f is nearly convex.

Nearly convex/concave functions have nearly convex domains and any convex

function is also nearly convex, but there are nearly convex functions that are not

convex as shown below.

Example 1.1. Let F : R R be any discontinuous solution of Cauchys functional

equation F (x + y ) = F (x) + F (y ) x, y R. For each of these functions, whose

existence is guaranteed in Ref. 10, one has F ((x + y )/2) = (F (x)+ F (y ))/2 x, y R,

i.e. these functions are nearly convex. None of them is convex because of the absence

of continuity.

The following lemma extends to the nearly convex setting a well-known result

from the convex analysis.

Lemma 1.4. Let the functions f, g : Rn R. Then f is nearly convex if and

only if epi(f ) is nearly convex and g is nearly concave if and only if hyp(g ) is nearly

convex.

Remark 1.1. Since epi(f ) = cl(epi(f )), by Lemma 1.2 (ii) and Lemma 1.4 one has

that the lower semicontinuous envelope f of a nearly convex function f is convex.

Theorem 1.1. Let f : Rn R be a proper nearly convex function fullling

ri(epi(f )) = . Then

(a) ri(epi(f )) = ri(epi(f )) and ri(dom(f )) = ri(dom(f ));

(b) f (x) = f (x), x ri(dom(f )),

(c) f is proper.

Proof. Since ri(epi(f )) = , by Lemma 1.3 it follows ri(epi(f )) = ri(cl(epi(f )) =

ri(epi(f )). Denoting by Pr : Rn R Rn the projection operator dened by

Pr(x, r) = x, we have by Theorem 6.6 in Ref. 1 that

ri(dom(f )) = ri(Pr(epi(f )) = Pr(ri(epi(f )) = Pr(ri(epi(f ))) Pr(epi(f )) = dom(f ).

On the other hand, as dom(f ) dom(f ) and the latter is a convex set, by Lemma

1.1 follows ri(dom(f )) = ri(dom(f )). )). By Lemma 7.3 in Ref. 1, we have that for all > 0, Take an x from ri(dom(f (x) + ) ri(epi(f )) epi(f ), so f (x) f (x) + . Letting tend to 0 it follows (x, f (x). Since the opposite inequality is always true, (ii) follows. f (x) f is also not identical +. Assuming As f is not identical + it follows that f 7

(x ) = , we would have (cf. Corollary 7.2.1 there exists an x Rn such that f (x) = x dom(f ). As f (x) = f (x) x ri(dom(f )) this in Ref. 1) that f is a proper function. contradicts the properness of f . Thus f

Remark 1.2. For F a discontinuous solutions of Cauchys functional equation

(cf. Example 1.1) we have that ri(dom(F )) = R, but ri(epi(F )) = . Assuming (x) = F (x) x ri(dom(F )). As the latter set ri(epi(F )) = , this would imply F and so F is convex, which is not the case. coincides with R, one gets F = F

Extension of the Fenchel Duality Theorem

For a proper convex function f : Rn R and a proper concave one g : Rn R

Fenchel dualitys theorem states that if ri(dom(f )) ri(dom(g )) = , then

xRn

g (u) f (u) . inf f (x) g (x) = max n

We weaken the conditions imposed in Ref. 1 without altering the conclusion by

considering f nearly convex and g nearly concave.

Theorem 2.1. Let f : Rn R be a proper nearly convex function and let

g : Rn R be a proper nearly concave function. If the following conditions are

simultaneously satised

(i) ri(dom(f )) ri(dom(g )) = ,

(ii) ri(epi(f )) = ,

(iii) ri(hyp(g )) = ,

then one has g (u) f (u) . inf f (x) g (x) = max n

xRn

Proof. One can notice that the relations (a)-(c) in Theorem 1.1 are fullled.

Similarly it follows that g is a proper concave and upper semicontinuous function

such that g (x) = g (x) x ri(dom( g )) and ri(dom( g )) = ri(dom(g )). (x) g (x) : x Rn . Since Denote by v := inf f (x) g (x) : x Rn inf f g f is convex, by Corollary 7.3.1 in Ref. 1 we have

(x) g inf f (x) : x Rn

(x) g g = inf f (x) : x ri(dom(f ))]

(x) g ) dom( = inf f (x) : x ri(dom(f g ))]. 9

) and dom( The sets dom(f g )) are convex and the intersection of their relative interior )) ri(dom( is not empty, since ri(dom(f )) ri(dom(g )) = ri(dom(f g )). By Theorem ) dom( 6.5 in Ref. 1, the latter set is equal to ri(dom(f g )). Thus

(x) g inf f (x) : x Rn

(x) g )) ri(dom( = inf f (x) : x ri(dom(f g ))]

= inf f (x) g (x) : x ri(dom(f )) ri(dom(g ))] v.

In conclusion,

(x) g v = inf f (x) g (x) : x Rn = inf f (x) : x Rn .

and g Fenchels duality theorem (Theorem 31.1 in Ref. 1) yields for f that

xRn

) (u) . (x) g ( g ) (u) ( f (x) = max inf f n

) and g = ( As f = (f g ) (cf. Ref. 1) one has (x) g g (u) f (u) . (x) = max inf f (x) g (x) = infn f n
xR uR

xRn

Remark 2.1. The assumptions of near convexity for f and of near concavity for g

do not require the same near convexity constant for both of these functions. convex, g Remark 2.2. If f and g are proper, f concave and (i) holds, one has

xRn

(x) g g (u) f (u) . (x) = max inf f n

(1)

10

The question whether

xRn

(x) g inf f (x) g (x) = infn f (x)

(2)

is true or not under weaker hypotheses than in Theorem 2.1, like relaxing the near

convexity assumptions to close convexity, arises naturally. A function with the closure

of the epigraph convex is called closely convex (cf. Ref. 7) and analogously one denes

closely concave functions. The next example shows that (2) may fail when f is closely

convex, g is closely concave and the assumptions (i)-(iii) in Theorem 2.1 hold.

Example 2.1. Consider the sets

X = {(x, y )T R2 : x 0, y 0, x Q, y Q, x + y < 1}

{(x, y )T R2 : x 0, y 0, 1 x + y 2}

and Y

= {(x, y )T R2 : x 0, y 0, x R\Q, y R\Q, x + y < 1}

{(x, y )T R2 : x 0, y 0, 1 x + y 2},

and f, g : R2 R, if (x, y ) X, x, y, if (x, y ) Y, f (x, y ) = and g (x, y ) = +, otherwise, , otherwise. 11

Obviously f and g are proper and (3/4, 3/4) ri(dom(f )) ri(dom(g )), (3/4, 3/4, 1)

ri(epi(f )) and (3/4, 3/4, 1) ri(hyp(g )), whence hypotheses (i)-(iii) in Theorem

2.1 are valid. X and Y are not nearly convex, thus, as dom(f ) = X and dom(g ) = Y ,

f is not nearly convex and g is not nearly concave. On the other hand we have

cl(epi(f )) = {(x, y, r)T R3 : x 0, y 0, x + y 2, x r}

and cl(hyp(g )) = {(x, y, r)T R3 : x 0, y 0, x + y 2, y r}

and these sets are convex. Hence f is closely convex and g is closely concave. There-

fore, with (i) in Theorem 2.1 fullled, (1) is valid. One has if (x, y ) Z, y, if (x, y ) Z, x, and g (x, y ) = f (x, y ) = + , otherwise , , otherwise, where Z = {(x, y )T R2 : x 0, y 0, x + y 2}, thus

(x,y )R2

(x, y ) g inf [f (x, y )] = inf {x + y : x 0, y 0, x + y 2} = 0.

Thus by Fenchels duality theorem,

(x,y )R2

inf

(x, y ) g f (x, y ) = max 2 g (u, v ) f (u, v ) = 0.

12

Simple calculations lead to

(x,y )R2

inf [f (x, y ) g (x, y )] = inf {x + y : x 0, y 0, 1 x + y 2} = 1.

Therefore (2) is obviously violated, thus Fenchels duality theorem does not hold when

its hypotheses are further weakened by taking the functions involved only closely

convex, respectively closely concave.

Remark 2.3. If f is proper convex and g is proper concave, (ii) and (iii) are

automatically fullled and Theorem 2.1 becomes Fenchels duality theorem.

Giving Theorem 2.1 for F, G : Rn Rm R, F (x, y ) = f (x)+ {xRn :Ax=y} (x) and G(x, y )=g (y ), we extend to near convexity Fenchels duality result for the composition

with a linear mapping A : RnRm , generalizing Corollary 31.2.1 in Ref. 1.

Theorem 2.2. Let f be proper nearly convex on Rn , let g be proper nearly

concave on Rm , and let A be a linear mapping from Rn to Rm . If one has

(i) x ri(dom(f )) such that Ax ri(dom(g )),

(ii) ri(epi(f )) = ,

(iii) ri(hyp(g )) = , 13

it follows g (v ) f (A v ) . inf f (x) g (Ax) = max m

xRn

Remark 2.4. By Remark 2.3, the assertion of Corollary 31.2.1 in Ref. 1 is valid

under the condition x ri(dom(f )) such that Ax ri(dom(g )), without any

closedness assumption concerning f or g as taken in the mentioned book.

14

References

1. Rockafellar, R. T., Convex analysis, Princeton University Press, Princeton,

1970.

2. Penot, J. P., and Volle, M., On quasi-convex duality, Mathematics of Op-

erations Research, Vol. 15, No. 4, pp. 597625, 1987.

3. Aleman, A., On some generalizations of convex sets and convex functions,

Mathematica - Revue dAnalyse Num erique et de la Th eorie de lApproximation,

Vol. 14, pp. 16, 1985.

4. Cobzas , S ., and Muntean, I., Duality relations and characterizations of best

approximation for p-convex sets, Revue dAnalyse Num erique et de Th eorie de

lApproximation, Vol. 16, No. 2, pp. 95108, 1987.

5. Green, J. W., and Gustin, W., Quasiconvex sets, Canadian Journal of Math-

ematics, Vol. 2, pp. 489507, 1950.

6. Bot , R. I., Kassay, G., and Wanka, G., Strong duality for generalized convex

optimization problems, Journal of Optimization Theory and Applications, Vol. 15

127, No. 1, pp. 4570, 2005.

7. Breckner, W. W., and Kassay, G., A systematization of convexity concepts

for sets and functions, Journal of Convex Analysis, Vol. 4, pp. 109127, 1997.

8. Jeyakumar, V., and Gwinner, J., Inequality systems and optimization, Jour-

nal of Mathematical Analysis and Applications, Vol. 159, pp. 5171, 1991.

9. Roberts, A. W., and Varberg, D. E., Convex functions, Pure and Applied

Mathematics, Vol. 57, Academic Press, New York-London, 1973.

10. Hamel, G., Eine Basis aller Zahlen und die unstetigen L osungen der Funk-

tionalgleichung: f (x + y ) = f (x) + f (y ), Mathematische Annalen, Vol. 60, pp.

459462, 1905.

16