42.3. SUBGRADIENTS 1389

whenever (y,a) ∈C1 and (y1,a1) ∈C2.Claim: β > 0.Proof of claim: If β < 0 let

a = φ 1 (x)− x∗ (x− x)−φ 1 (x)+1,

a1 = φ 2 (x)−φ 2 (x) , and y = y1 = x.

Then from 42.3.25

β (φ 1 (x)− x∗ (x− x)−φ 1 (x)+1)≥ β (φ 2 (x)−φ 2 (x)) .

Dividing by β yields

φ 1 (x)− x∗ (x− x)−φ 1 (x)+1≤ φ 2 (x)−φ 2 (x)

and soφ 1 (x)+φ 2 (x)− (φ 1 (x)+φ 2 (x))+1≤ x∗ (x− x)

≤ φ 1 (x)+φ 2 (x)− (φ 1 (x)+φ 2 (x)),

a contradiction. Therefore, β ≥ 0.Now suppose β = 0. Letting

a = φ 1 (x)− x∗ (x− x)−φ 1 (x)+1,

(x,a) ∈ int(C1) ,

and so there exists an open set U containing 0 and η > 0 such that

x+U× (a−η ,a+η)⊆C1.

Therefore, 42.3.25 applied to (x+ z,a) ∈C1 and (x,φ 2 (x)−φ 2 (x)) ∈C2 for z ∈U yields

w∗ (x+ z)≥ w∗ (x)

for all z ∈U . Hence w∗ (z) = 0 on U which implies w∗ = 0, contradicting 42.3.24. Thisproves the claim.

Now with the claim, it follows β > 0 and so, letting z∗ = w∗/β , 42.3.25 and Lemma18.2.15 implies

z∗ (y)+a≥ z∗ (y1)+a1 (42.3.26)

whenever (y,a) ∈C1 and (y1,a1) ∈C2. In particular,

(y,φ 1 (y)−φ 1 (x)− x∗ (y− x)) ∈C1 (42.3.27)

becauseφ 1 (y)−φ 1 (x)− x∗ (y− x)≤ φ 1 (y)− x∗ (y− x)−φ 1 (x)

and(y1,φ 2 (x)−φ 2 (y1)) ∈C2. (42.3.28)