7H (Optimisation)

A set is convex when it contains every segment joining two of its points. A function on a convex set is convex when

f (t x + (1 - t) y) \leq t f (x) + (1 - t) f (y)

for all

x, y

and

0 \leq t \leq 1

b

Take

(t, x), (s, y)

and

0 \leq α \leq 1

, and put

T = α t + (1 - α) s

. Then

\frac{αx + ( 1 - α ) y}{T} = \frac{α t}{T} \frac{x}{t} + \frac{( 1 - α ) s}{T} \frac{y}{s} .

Convexity of

f

, followed by multiplication by

T

, proves convexity of its perspective

g (t, x) = t f (x / t)

Let

z = t x + (1 - t) y

. Apply the hypothesis with first argument

z

and second argument successively

x, y

f (z) - f (x) \leq (1 - t) λ (z)^{T} (y - x),

f (z) - f (y) \leq t λ (z)^{T} (x - y) .

Multiply these inequalities by

t

and

1 - t

respectively and add. The right sides cancel, leaving

f (z) \leq t f (x) + (1 - t) f (y)

There are no discussions about this article yet.

There are currently no matching articles.