Convex Optimization · Problem 6.12

Statistical estimation — Boyd & Vandenberghe

Mathematics — Optimization · interpolation-monotone-functions

Problem

Interpolation with monotone functions. A function

f : \mathbf{R}^k \to \mathbf{R}

is monotone nondecreasing (with respect to

\mathbf{R}^k_+

) if

f(u) \geq f(v)

whenever

u \succeq v

. (a) Show that there exists a monotone nondecreasing function

f : \mathbf{R}^k \to \mathbf{R}

, that satisfies

f(u_i) = y_i

for

i = 1, \ldots, m

, if and only if

y_i \geq y_j \text{ whenever } u_i \succeq u_j, \quad i,\ j = 1, \ldots, m.

(b) Show that there exists a convex monotone nondecreasing function

f : \mathbf{R}^k \to \mathbf{R}

, with

\mathbf{dom}\, f = \mathbf{R}^k

, that satisfies

f(u_i) = y_i

for

i = 1, \ldots, m

, if and only if there exist

g_i \in \mathbf{R}^k

i = 1, \ldots, m

, such that

g_i \succeq 0, \quad i = 1, \ldots, m, \qquad y_j \geq y_i + g_i^T(u_j - u_i), \quad i,\ j = 1, \ldots, m.