## Flavio M. Menezes and Paulo K. Monteiro

Print publication date: 2004

Print ISBN-13: 9780199275984

Published to Oxford Scholarship Online: April 2005

DOI: 10.1093/019927598X.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2017. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in OSO for personal use (for details see http://www.oxfordscholarship.com/page/privacy-policy). Subscriber: null; date: 26 February 2017

# (p.165) Appendix D Convexity

Source:
An Introduction to Auction Theory
Publisher:
Oxford University Press

In this section, we consider a few results on convex functions that are used in Chapter 6. We begin with the convex hull.

Definition 28 The convex hull of a function f(·) is the greatest convex function that is pointwise smaller than f. That is, if f:[0,1] → ℝ then g:[0,1] → ℝ is the convex hull of f if:

1. 1. g is convex;

2. 2. gf, that is g(x) ≤ f(x), for all x ∈ [0,1];

3. 3. if h is a convex function and h ≤ f then h ≤ g.

The convex hull of a function exists and has an explicit expression (see Rockafellar: 36). We do not consider here the more general case.

Proposition 11 If h:[0,1] → ℝ is continuous then the function g defined below is the convex hull of h:

(D.1)
$Display mathematics$

Proof: The minimum is attained since h is continuous. It is immediate that g(q) ≤ h(q) for every q. Now if fh is a convex function then for any convex combination $q = ∑ l = 1 n λ l r l$ we have that

$Display mathematics$
(p.166) Hence f(q) ≤ g(q). It remains to prove that g is convex. Suppose λ ∈ (0,1) and q 1,q 2 ∈ [0,1]. Then there exists ωl,rl,ω′l,r′l such that
$Display mathematics$
We have that
$Display mathematics$
and
$Display mathematics$
Thus,
$Display mathematics$

Lemma 14 If g(x) < f(x) then g′(y) = g′(x) in a neighborhood of x.

Proof: Suppose g(x) < f(x). There are λl ≥ 0, ∑lλl = 1,xl ∈ [0,1], x = ∑lλl xl such that g(x) = ∑lλl f(xl). Since

$Display mathematics$
we conclude that g(xl) = f(xl) for every l. We first show that there is a θ ∈ [0,1] such that g(x) = θf(ak) + (1 − θ)f(al) and θak + (1 − θ)al = x. To see this (p.167) note that if λ* is a solution of
$Display mathematics$
$Display mathematics$
then for some μ real
$Display mathematics$
and in this case ∑lλl bl = μx for every λ and therefore for some λ with λl = 0 as well. Now consider the problem
$Display mathematics$
$Display mathematics$
and consider the solution λ* with the greatest number of zero coefficients λ*l. From the previous case we see that n = 2. Define α = ak and β = al, we may write
$Display mathematics$
Without loss of generality α < x < β. Now consider y,y′ such that α < y < x < y′ < β. There are a,b ∈ (0,1) such that aα + (1 − a)x = y and bx + (1 − b)β = y′. Namely a = (xy)/(x − α) and b = (β − y′)/(β − x). Then
$Display mathematics$
Moreover, $r : = y ′ − x y ′ − y ∈ ( 0 , 1 )$ is such that ry + (1 − r)y′ = x. Then
(D.2)
$Display mathematics$
and thus,
$Display mathematics$
Thus the inequalities in (D.2) are equalities and this ends the proof. □

(p.168) We now consider the one-sided derivative of a convex function.

Proposition 12 If g:[0,1) → ℝ is convex then for every x ∈ [0,1) there exists

(D.3)
$Display mathematics$
Moreover, the function x → g+(x) is increasing.

Proof: First note that if a < b and c < d,ac,bd then

$Display mathematics$
To see this consider first a = c. That is a = c < bd. Then if r = (db)/(da) we have that
$Display mathematics$
The case b = d is analogous. Thus we have that
$Display mathematics$
Therefore, the ratio (g(b) − g(a))/(ba) decreases with b > a for every a. The same is therefore true of (g(d) − g(c))/(dc). We see from (D.3) that (g(d) − g(c))/(dc) has a lower bound (namely (g(b) − g(a))/(ba)). Therefore there exists
$Display mathematics$
We see also from (D.3) that g+(a) ≤ g+(c) whenever a < c.