Journal of Convex Analysis Volume 3 (1996), No.1, 55–61

A Note on the Characterization of the Global Maxima of a (Tangentially) Convex Function Over a Convex Set

J.-B. Hiriart-Urruty

Université Paul Sabatier 118, route de Narbonne, 31062 Toulouse cedex, France. e-mail: jbhu@cict.fr

Yuri S. Ledyaev

Steklov Mathematics Institute, Vavilov St. 42, Moscow 117966, Russia. e-mail: ledyaev@de.mian.su

Received May 31, 1994 Revised manuscript received February 1, 1995

Dedicated to R. T. Rockafellar on his 60th Birthday

We consider the problem of characterizing points x̄ in a convex set C which globally maximize an objective function f over C. When f is convex, we show how the first order necessary condition extended to those x ∈ C at the same level as x̄ is necessary and sufficient for x̄ being a global maximum of f over C.This improves a recent result by A. Strekalovski who was the first to propose such type of global optimality condition, but whose characterization required to scan all the points (even out of C) at the same level as x̄. Next we extend the obtained characterization to the case where the objective function is just tangentially convex and an appropriate qualification condition holds.

1. Characterizing the global maxima of a convex function over a convex set

Let X be a (real) Banach space, X^{∗} its topological dual space ; when s ∈ X^{∗} and x ∈ X, we use the notation ⟨s, x⟩ for s(x). Let f : X ⟶ IR ∪ {+∞} be a lower semicontinuous convex function, and let C be a nonempty closed convex set contained in the interior of the domain of f. We are interested in characterizing those x̄ in C maximizing globally f on C, i.e. satisfying :

f(x) ≤ f(x̄) for all x ∈ C.  (1)

The convexity of C is not so important here since we know that the maximum of a convex function (resp. of a continuous convex function) over a set S is unaltered if we substitute the convex hull of S (resp. the closed convex hull of S) for S.

If x̄ ∈ C is a maximum (even local) of f on C and if f is Gâteaux- differentiable at x̄, then Df(x̄) (the Gâteaux derivative of f at x̄) necessarily lies in the normal cone to C at x̄ :

ISSN 0944-6532 / $ 2.50 ◯^{c} Heldermann Verlag

56 J.-B. Hiriart-Urruty, Yu. S. Ledyaev / On the characterization of the global maxima

Df(x̄) ∈ N(C, x̄).  (2)

This necessary condition for maximality holds true whenever f is differentiable at x̄, be it convex or not. When, like in our case, f is convex, we have

∂f(x̄) ⊂ N(C, x̄)  (3)

at any maximum (even local) x̄ of f on C (here, ∂f(x̄) denotes as usual the subdifferential of f at x̄). Already at this stage the convexity of f has played its role : a natural extension of (2) would be ∂f(x̄) ∩ N(C, x̄) ≠ ∅, while we get in (3) much more : the whole subdifferential of f at x̄ is contained in N(C, x̄).

Condition (3) is not sufficient - far from it- for x̄ being a maximum (even local) of f on C. To characterize a global maximum of f on C, we need “to globalize” (3) somehow or other. The first approach in that direction is treated in [2] where the global maxima of f on C are characterized with the help of “ε - enlargements” of the subdifferential of f and of the normal cone to C. Indeed, denoting by ∂_{ε}f(x̄) the ε - subdifferential of f at x̄ and by N_{ε}(C, x̄) the set of ε - normal directions to C at x̄, we have : x̄ ∈ C is a global maximum of f on C if and only if :

∂_{ε}f(x̄) ⊂ N_{ε}(C, x̄) for all ε > 0.  (4)

Since ∂f(x̄) = ⋂_{ε>0} ∂_{ε}f(x̄) and N(C, x̄) = ⋂_{ε>0}N_{ε}(C, x̄), the condition (3) is precisely the

limiting case ε ↓ 0 in (4). In (4) the parameter ε > 0 helped to globalize the (purely local) condition (3).

It turns out there is another way of globalizing the local condition (3) : by imposing the same condition as (3) to all the points x in the level-surface of f at level f(x̄). This approach is due to A. Strekalovski ([3], [4]) and his characterization can be stated as follows. Consider x̄ ∈ C such that

−∞ ≤ inf_{X} f < f(x̄); then x̄ is a global maximum of f on C if only if
∂f(x) ⊂ N(C, x) for all x satisfying f(x) = f(x̄).

(5)

The trouble in that formulation is that one needs to consider, a priori, normal cones to C at points x which do not necessarily lie in C (d ∈ N(C, x) still means in that case : ⟨d, c − x⟩ ≤ 0 for all c ∈ C), which is unnatural. The improvement of Strekalovski’s result we propose below consists in showing that a global maximum x̄ of f on C is still characterized by (5) restricted to those x in C at the same level as x̄.

Theorem 1.1. Consider a point x̄ ∈ C such that

−∞ ≤ inf_{C} f < f(x̄).

Then x̄ is a global maximum of f on C if and only if

∂f(x) ⊂ N(C, x) for all x in C satisfying f(x) = f(x̄).  (6)

Proof. [Condition (6) is necessary]. Let s ∈ ∂f(x) we have :

⟨s, x′ − x⟩ ≤ f(x′) − f(x) for all x′ ∈ X.

If x ∈ C and f(x) = f(x̄), we necessarily have ⟨s, x′ − x⟩ ≤ f(x′) − f(x̄) ≤ 0 for all x ∈ C, that is : s ∈ N(C, x̄).

[Condition (6) is sufficient]. We will use here an equivalent form of condition (6) : for all x in C satisfying f(x) = f(x̄), we have sup_{c∈C} f′(x, c − x) ≤ 0, (*)

i.e., there is no direction d tangent to C at x for which f′(x, d) > 0 (here, f′(x, .) denotes the directional derivative of f at x ; the assumptions made ensure that f′(x, .) is a continuous function).

Suppose the contrary holds : there is some x̃ ∈ C for which f(x̃) > f(x̄). We aim at contradicting (*).

Due to the assumption inf_{C} f < f(x̄), there exists x_{∗} ∈ C such that

f(x_{∗}) < f(x̄). Connect x_{∗} and x̃ by a line-segment. Since f restricted to this line remains convex (continuous) and f(x_{∗}) < f(x̄) < f(x̃), there is a unique point x_{0} on the interval (x_{∗}, x̃) at which f(x_{0}) = f(x̄). Moreover, the restriction of f to the interval (x_{∗}, x̃) obviously increases with a positive right-derivative, in particular f′(x_{0}, x̃ − x_{0} > 0. We therefore have found x_{0} in C such that f(x_{0}) = f(x̄) and sup_{c∈C} f′(x_{0}, c − x_{0}) > 0, which

contradicts (*).

Strekalovski’s condition (5) has been substantially improved in (6) by only considering the points at the same level f(x̄) which lie in C. There is however a slight difference in the assumptions : Strekalovski’s condition, applied for x̄, requires there exists some x_{o} ∈ X such that f(x_{o}) < f(x̄), while our condition requires there exist c_{o} ∈ C such that f(c_{o}) < f(x̄). Both requirements are very mild and easily understandable. They cannot be removed : if, for example, x̄ is the unique minimum on X of a differentiable f and if x̄ lies in the interior of C, condition (5) (or (6)) is obviously satisfied. The next simple example shows the difference between the two assumptions.

Example 1.2. Let f : (ξ_{1}, ξ_{2}) ∈ R^{2} ↦ f(ξ_{1}, ξ_{2}) = ξ2 2−ξ_{1}+1 and let C := {0}×[−1, +1]. Consider x̄ = (0, 0) ; we have : f(x̄) = inf_{C} f > inf_{R^{2}}f.

It is easy to verify that our condition (6) is satisfied, but Theorem 1.2 cannot be invoked; indeed x̄ is not a global maximum of f on C. As for condition (5), it is not satisfied : at x = (1, 1) which is at the same level f(x̄) (but not in C), the gradient of f at x (actually the unique element of ∂f(x)) does not belong to N(C, x).

2. Extending the characterization of global maxima to tangentially convex objective functions

In this section we extend Theorem 1.2 to (global) maximization problems with possibly nonconvex objective functions. More precisely we remove the convexity condition on f and replace it by the following one : f is locally Lipschitz and strictly tangentially convex (or regular in Clarke’s terminology [1, p.39]) on the interior of its domain, i.e. : for all x in the interior of the domain of f,

(i) The usual one-sided directional derivative d ↦ f′(x, d) exists ; (ii) f′(x, .) is the support function of Clarke’s generalized gradient ∂f(x) of f at x. As simple examples show it, one cannot get away from the convexity (and continuity) of the “tangent approximations” d ↦ f′(x, d) of f at x, at least if one wishes to have the same condition be necessary and sufficient for global optimality.

We assume moreover X is a (real) Hilbert space ; we denote by ⟨., .⟩ the inner product in X and by ||.|| the associated norm.

Theorem 2.1. Assume the following qualification condition holds at x̄ ∈ C : (QC)x̄ For all x ∈ C such that f(x) = f(x̄), it there is c_{x} ∈ C such that

f′(x, c_{x} − x) < 0.

Then x̄ is a global maximum of f on C if and only if

∂f(x) ⊂ N(C, x)for all x in C satisfying f(x) = f(x̄).  (6)′

The difference between (6) and (6)′ is that, now, ∂f(x) stands for the generalized gradient of f at x. The statement of Theorem 2.1 is similar to that of Theorem 1.1 but the lack of convexity of f compels us to use different techniques in the proof. Before going further, some comments on (QC)x̄ are in order :

• What does (QC)x̄ mean ? It means that from any point x in C at the same level as x̄, there is a direction of descent (for f) directed towards a point of C. It is clear that (QC)x̄ cannot be completely removed : suppose, for example, f is strictly differentiable at a point x̄ lying in the interior of C, there is no other point in C at the same level as x̄, and Df(x̄) = 0 ; then (6)′ is satisfied but x̄ need not necessarily be a maximum of f over C.

• (QC)x̄ is truly a generalization of the qualification condition encountered in section 1 for convex f. Indeed, if f is convex and if there is some c_{o} ∈ C such that f(c_{o}) < f(x̄), then

f′(x, c_{o} − x) ≤ f(c_{o}) − f(x) = f(c_{o}) − f(x̄)

for all x in C at the same level as x̄.

• Suppose f is continuously differentiable on the interior of its domain. Then (QC)x̄ and (6)′ take respectively the following form :

inf_{c∈C} ⟨Df(x), c⟩ < ⟨Df(x), x⟩

and

⟨Df(x), x⟩ = max_{c∈C}⟨Df(x), c⟩

(for all x ∈ C at the same level as x̄). Hence, under (QC)x̄, for all x in C at the same level as a global maximum x̄ of f on C, the width of C in the Df(x) direction is non-null.

Proof of Theorem 2.1. [Condition (6)′ is necessary]. Let x ∈ C satisfy f(x) = f(x̄). Since x is also a global maximum of f on C,

f(x + t(c − x)) ≤ f(x) for all 0 < t ≤ 1 and c ∈ C.

Consequently

f′(x, c − x) ≤ 0 for all c ∈ C,

and because f′(x, .) is the support function of ∂f(x)

⟨s, c − x⟩ ≤ 0 for all c ∈ C and s ∈ ∂f(x)

i.e.,

∂f(x) ⊂ N(C, x).

[Condition (6)′ is sufficient]. Suppose for contradiction there is some x̃ ∈ C such that f(x̃) > f(x̄) and let D := C ∩ {x ∈ X | f(x) ≤ f(x̄)}. We consider the following minimization problem :

Minimize \frac{1}{2} ∥ x − x̃ ∥^{2} subject to x ∈ D.

In general this problem has no solution since D is only a closed subset of X. But, according to Ekeland’s variational principle (see [1, p. 266] for example), for any ε > 0 there exists x̂_{ε} ∈ D such that the function

φ_{ε} : x ⟼ φ_{ε}(x) := \frac{1}{2}||x − x̃||^{2} + ε||x − x̂_{ε}||

attains its minimum on D at x̂_{ε}.

Claim 1 : f(x̂_{ε}) = f(x̄) for ε > 0 small enough. If not there exists (ε_{k})_{k} ↓ 0 such that x̂_{k} := x̂_{ε_{k}} satisfies

f(x̂_{k}) < f(x̄) for all k.  (7)

We set x_{k,t} := x̂_{k} + t(x̃ − x̂_{k}) for 0 < t ≤ 1. Since x_{k,t} ∈ C (because both x̂_{k} and x̃ are in C and C is convex) and f(x_{k,t}) ≤ f(x̄) for t small enough (because of the continuity of f at x̂_{k} and (7)), we can say :

∃t̄_{k} > 0 such that x_{k,t} ∈ D for all 0 < t ≤ t̄_{k}.

But x̂_{k} is, by definition, a minimum of the function x ⟼ \frac{1}{2}||x − x̃||^{2} + ε||x − x̂_{k}|| on D ; thus :

\frac{1}{2}||x_{k,t} − x̃||^{2} + ε_{k}||x_{k,t} − x̂_{k}|| ≥ \frac{1}{2}||x̂_{k} − x̃||^{2} for all 0 < t ≤ t̄_{k}.  (8)

By plugging the expression x_{k,t} = x̂_{k} + t(x̃ − x̂_{k}) into (8), we derive :

\frac{1}{2}(1 − t)^{2}||x̂_{k} − x̃||^{2} + tε_{k}||x̃ − x̂_{k}|| ≥ \frac{1}{2}||x̂_{k} − x̃||^{2}

or

\frac{1}{2}t^{2}||x̂_{k} − x̃||^{2} − t||x̂_{k} − x̃||^{2} + tε_{k}||x̃ − x̂_{k}|| ≥ 0 for all 0 < t ≤ t̄_{k}.

Since ||x̂_{k} − x̃|| > 0 it follows that for t > 0 small enough

||x̂_{k} − x̃|| ≤ ε_{k} + \frac{t}{2}||x̂_{k} − x̃||.

By letting t ↓ 0 we obtain ||x̂_{k} − x̃|| ≤ ε_{k}. Now, since x̂_{k} satisfies (7) and (x̂_{k})_{k} converges to x̃ , the continuity of f implies that f(x̃) ≤ f(x̄), which contradicts the choice of x̃. Thus we have proved that f(x̂_{ε}) = f(x̄) for ε > 0 small enough. We henceforth consider such ε > 0.

Claim 2 : ∂f(x̂_{ε} ⊂ N(C, x̂_{ε}) leads to a contradiction.

Consider for that the function

g : x ⟼ g(x) := max{φ_{ε}(x) − φ_{ε}(x̂_{ε}), f(x) − f(x̄)}.

We have : g(x̂_{ε}) = 0 and g(x) ≥ 0 for all x ∈ C ; we reformulate that by saying that x̂_{ε} solves the following minimization problem :

(P̂) Minimize g(x) subject to x ∈ C.

Then a necessary condition is as follows : there exists λ_{0} ≥ 0 and λ ≥ 0 adding up to 1 such that

λ_{0}φε^{′}(x̂_{ε}, c − x̂_{ε}) + λf′(x̂_{ε}, c − x̂_{ε}) ≥ 0 for all c ∈ C

We claim that λ_{0} > 0 necessarily. If not we would have

f′(x̂_{ε}, c − x̂_{ε}) ≥ 0 for all c ∈ C,

which contradicts (QC)x̄.

Thus

\frac{λ}{λ_{0}} f′(x̂_{ε}, c − x̂_{ε}) ≥ −φ′_{ε}(x̂_{ε}, c − x̂_{ε}) for all c ∈ C  (9)

The calculation of φ′_{ε}(x, .) at x = x̂_{ε} is easy :

∀d ∈ H, φ′_{ε}(x̂_{ε}, d) =< x̂_{ε} − x̃, d > +ε||d||.

Now, by choosing c = x̃ in (9) we get at

\frac{λ}{λ_{0}} f′(x̂_{ε}, x̃ − x̂_{ε}) ≥ ||x̃ − x̂_{ε}||^{2} − ε||x̃ − x̂_{ε}||.  (10)

But since f′(x̂_{ε}, c − x̂_{ε}) ≤ 0 for all c ∈ C (as said earlier this is an equivalent form of the inclusion ∂f(x̂_{ε}) ⊂ N(C, x̂_{ε})), the inequality (10) implies that ||x̂_{ε} − x̃|| ≤ ε. So again lim_{ε↓0}x̂_{ε} = x̃ , whence f(x̃) ≤ f(x̄), which contradicts the inquality f(x̃) > f(x̄) assumed from the beginning.

Remark 2.2. The second part of the proof above shows that if f is just locally Lipschitz (not necessarily strictly tangentially convex) and if we assume (QC)x̄ (expressed with Clarke’s generalized directional derivative of f instead of f), then (6)′ is a sufficient condition for x̄ being a global maximum of f on C.

To end this note we mention a global optimality condition in nonconvex optimization of a similar philosophy to the ones presented here. Suppose X is a (real) Banach space, C a closed convex set of X, and f : C → IR is continuous (actually more general X and C could be considered, C just connected for example). Consider x̄ ∈ C satisfying the following :

Every x ∈ C for which f(x) = f(x̄) is a local maximum of f on C.  (11)

Then x̄ is a global maximum of f on C. Thus (11) is a necessary and sufficient condition for x̄ being a global maximum. The proof is left as an exercise to the reader.

Acknowledgment. We would like to thank the referees for the comments and improvements they suggested. In particular, the present proof of Theorem 1.1, shorter than our earlier one, is due to one of them.

References

[1] F. H. Clarke: Optimization and Nonsmooth Analysis, J. Wiley, New York 1983.

[2] J.-B. Hiriart-Urruty: From convex optimization to nonconvex optimization. Part I : Necessary and sufficient conditions for global optimality, in Nonsmooth Optimization and Related Topics, Plenum Press (1989) 219–239.

[3] A. Strekalovski: On questions of global extremum in nonconvex extremal problems, Izvestia Vyssh. Uchebnyh Zavedenii 8 (1990) 74–80 [in Russian].

[4] A. Strekalovski: On search of global maximum of convex functions on a constraint set, J. of Comp. Mathematics and Math. Physics 33 (1993) 349–363 [in Russian, to be translated into English].

[5] P.-J. Laurent: Approximation et Optimisation, Hermann, Paris 1972.

62 J.-B. Hiriart-Urruty, Yu. S. Ledyaev / On the characterization of the global maxima HIER :

Leere Seite