#assignment #sdsc6015

作业初稿

SDSC6015 - Assignment 1

Problem 1: Jensen’s inequality

Let f be convex, x1,…,xm∈dom⁡(f),λ1,…,λm∈R+x_{1},\ldots, x_{m}\in\operatorname{dom}(f),\lambda_{1},\ldots,\lambda_{m}\in R_{+} such that ∑i=1mλi=1\sum_{i=1}^{m}\lambda_{i}=1 . Show that

f(∑i=1mλixi)≤∑i=1mλif(xi)f\left( \sum_{i=1}^m \lambda_i x_i \right) \leq \sum_{i=1}^m \lambda_i f(x_i)

Proof.

  1. 对于m=2m=2:
    令 λ1+λ2=1\lambda_1 + \lambda_2 = 1，有：

    f(λ1x1+λ2x2)≤λ1f(x1)+λ2f(x2)f(λ1x1+(1−λ1)x2)≤λ1f(x1)+(1−λ1)f(x2)\begin{align*} f(\lambda_1 x_1 + \lambda_2 x_2) & \leq \lambda_1 f(x_1) + \lambda_2 f(x_2) \\ f(\lambda_1 x_1 + (1 - \lambda_1) x_2) & \leq \lambda_1 f(x_1) + (1 - \lambda_1) f(x_2) \end{align*}

    对于凸函数ff，∀x,y∈dom⁡(f)\forall x, y \in \operatorname{dom}(f) 和 θ∈[0,1]\theta \in [0,1]，有：

    f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta) f(y)

    使用m=2m = 2时成立

  2. 假设对于 m=km=k 成立
    即对于 m=km=k, λ1,…,λm∈R+\lambda_{1},\ldots,\lambda_{m}\in R_{+} such that ∑i=1mλi=1\sum_{i=1}^{m}\lambda_{i}=1, 有：

f(∑i=1kλixi)≤∑i=1kλif(xi)f\left( \sum_{i=1}^k \lambda_i x_i \right) \leq \sum_{i=1}^k \lambda_i f(x_i)

  1. 对于 m=k+1m=k+1，有：

a. 对于λk+1=1\lambda_{k+1}=1：

则有：

f(xi)≤f(xi) f\left(x_i \right) \leq f(x_i)

恒成立。

b. 对于λk+1<1\lambda_{k+1}\lt1：

则有：

f(∑i=1k+1λixi)=f(∑i=1kλixi+λk+1xk+1)=f((1−λk+1)∑i=1kλi1−λk+1xi+λk+1xk+1)f(∑i=1k+1λixi)≤(1−λk+1)f(∑i=1kλi1−λk+1xi)+λk+1f(xk+1)∵f(∑i=1kλixi)≤∑i=1kλif(xi)∴(1−λk+1)f(∑i=1kλi1−λk+1xi)≤(1−λk+1)∑i=1kλi1−λk+1f(xi)=∑i=1kλif(xi)∴f(∑i=1k+1λixi)≤∑i=1kλif(xi)+λk+1f(xk+1)=∑i=1k+1λif(xi) \begin{align*} f\left( \sum_{i=1}^{k+1} \lambda_i x_i \right) & = f\left( \sum_{i=1}^{k} \lambda_i x_i + \lambda_{k+1} x_{k+1} \right)\\ & = f\left( (1 - \lambda_{k+1})\sum_{i=1}^{k} \frac{\lambda_i}{1 - \lambda_{k+1}} x_i + \lambda_{k+1} x_{k+1} \right) \\ f\left( \sum_{i=1}^{k+1} \lambda_i x_i \right) & \leq (1 - \lambda_{k+1}) f\left(\sum_{i=1}^{k} \frac{\lambda_i}{1 - \lambda_{k+1}} x_i\right) + \lambda_{k+1}f(x_{k+1})\\ \because f\left( \sum_{i=1}^k \lambda_i x_i \right) &\leq \sum_{i=1}^k \lambda_i f(x_i)\\ \therefore (1 - \lambda_{k+1}) f\left(\sum_{i=1}^{k} \frac{\lambda_i}{1 - \lambda_{k+1}} x_i\right) & \leq (1 - \lambda_{k+1}) \sum_{i=1}^{k} \frac{\lambda_i}{1 - \lambda_{k+1}} f\left(x_i\right) = \sum_{i=1}^{k} \lambda_i f\left(x_i\right)\\ \therefore f\left( \sum_{i=1}^{k+1} \lambda_i x_i \right) & \leq \sum_{i=1}^{k}\lambda_i f(x_i) + \lambda_{k+1}f(x_{k+1}) = \sum_{i=1}^{k+1}\lambda_i f(x_i) \\ \end{align*}

不等式对 m=k+1m=k+1 成立。

由数学归纳法，Jensen 不等式得证。

Problem 2

(i) Let f1,f2,…,fmf_{1}, f_{2},\ldots, f_{m} be convex functions, λ1,λ2,…,λm∈R+\lambda_{1},\lambda_{2},\ldots,\lambda_{m}\in R_{+} . Show that f:=∑i=1mλifif:=\sum_{i=1}^{m}\lambda_{i} f_{i} is convex on dom⁡(f):=⋂i=1mdom⁡(fi)\operatorname{dom}(f):=\bigcap_{i=1}^{m}\operatorname{dom}\left(f_{i}\right) .

由于每个 fif_i 是凸函数，对于任意 ii，有：

fi(θx+(1−θ)y)≤θfi(x)+(1−θ)fi(y)λifi(θx+(1−θ)y)≤λiθfi(x)+λi(1−θ)fi(y)∑i=1mλifi(θx+(1−θ)y)≤θ∑i=1mλifi(x)+(1−θ)∑i=1mλifi(y)∴f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)\begin{align*} f_i(\theta x + (1-\theta)y) &\leq \theta f_i(x) + (1-\theta) f_i(y) \\ \lambda_i f_i(\theta x + (1-\theta)y) &\leq \lambda_i \theta f_i(x) + \lambda_i (1-\theta) f_i(y) \\ \sum_{i=1}^m \lambda_i f_i(\theta x + (1-\theta)y) &\leq \theta \sum_{i=1}^m \lambda_i f_i(x) + (1-\theta) \sum_{i=1}^m \lambda_i f_i(y) \\ \therefore f(\theta x + (1-\theta)y) &\leq \theta f(x) + (1-\theta) f(y) \end{align*}

因此，ff 是凸函数。

(ii) Let f be a convex function with dom⁡(f)⊆Rd,g:Rm→Rd\operatorname{dom}(f)\subseteq R^{d}, g: R^{m}\rightarrow R^{d} an affine function, meaning that g(x)=Ax+bg(x)=A x+b , for some matrix A∈Rd×mA\in R^{d\times m} and some vector b∈Rdb\in R^{d} . Show that the function f∘gf\circ g (that maps x to f(Ax+b))f(A x+b)) is convex on dom⁡(f∘g):={x∈Rm:g(x)∈dom⁡(f)}\operatorname{dom}(f\circ g):=\left\{x\in R^{m}:g(x)\in\operatorname{dom}(f)\right\} .

(f∘g)(θx+(1−θ)y)=f(g(θx+(1−θ)y))(f \circ g)(\theta x + (1-\theta)y) = f(g(\theta x + (1-\theta)y))

由于 gg 是仿射函数：

g(θx+(1−θ)y)=A(θx+(1−θ)y)+b=θ(Ax+b)+(1−θ)(Ay+b)=θg(x)+(1−θ)g(y)f(θg(x)+(1−θ)g(y))≤θf(g(x))+(1−θ)f(g(y))∴(f∘g)(θx+(1−θ)y)≤θ(f∘g)(x)+(1−θ)(f∘g)(y)\begin{align*} g(\theta x + (1-\theta)y) &= A(\theta x + (1-\theta)y) + b \\ &= \theta (Ax + b) + (1-\theta)(Ay + b) \\ &= \theta g(x) + (1-\theta) g(y) \\ f(\theta g(x) + (1-\theta) g(y)) &\leq \theta f(g(x)) + (1-\theta) f(g(y)) \\ \therefore (f \circ g)(\theta x + (1-\theta)y) &\leq \theta (f \circ g)(x) + (1-\theta) (f \circ g)(y) \end{align*}

f∘gf \circ g 是凸函数。

Problem 3

Show that the quadratic function f(x)=x⊤Qx+b⊤x+cf(x)=x^{\top}Q x+b^{\top} x+c , with symmetric matrix Q, is smooth with parameter 2||Q||.

∥∇f(x)−∇f(y)∥≤2∥Q∥∥x−y∥\| \nabla f(x) - \nabla f(y) \| \leq 2 \|Q\| \| x - y \|

计算梯度：

∇f(x)=2Qx+b\nabla f(x) = 2 Q x + b

因此：

∇f(x)−∇f(y)=2Q(x−y)∥∇f(x)−∇f(y)∥=∥2Q(x−y)∥≤2∥Q∥∥x−y∥\begin{align*} \nabla f(x) - \nabla f(y) &= 2 Q (x - y) \\ \| \nabla f(x) - \nabla f(y) \| &= \| 2 Q (x - y) \| \leq 2 \|Q\| \| x - y \| \end{align*}

即ff 是光滑的，参数 L=2∥Q∥L = 2 \|Q\|。

Problem 4

Consider the projected gradient descent algorithm with a convex differentiable function f:X→Rf: X\rightarrow R . Suppose that for some t⩾0,xt+1=xtt\geqslant 0, x_{t+1}=x_{t} . Prove that in this case, xtx_{t} is a minimizer of f over the closed and convex set X.

给定 xt+1=xtx_{t+1} = x_t，所以：

∵xt+1=xt∴xt=ΠX(xt−η∇f(xt))\begin{align*} &\because x_{t+1} = x_t \\ &\therefore x_t = \Pi_X (x_t - \eta \nabla f(x_t)) \\ \end{align*}

令 z=xt−η∇f(xt)z = x_t - \eta \nabla f(x_t), y=xty = x_t，所以：

⟨xt−(xt−η∇f(xt)),x−xt⟩≥0∀x∈X⟨η∇f(xt),x−xt⟩≥0∀x∈X⟨∇f(xt),x−xt⟩≥0∀x∈X\begin{align*} \langle x_t - (x_t - \eta \nabla f(x_t)), x - x_t \rangle &\geq 0 \quad \forall x \in X \\ \langle \eta \nabla f(x_t), x - x_t \rangle &\geq 0 \quad \forall x \in X \\ \langle \nabla f(x_t), x - x_t \rangle &\geq 0 \quad \forall x \in X \end{align*}

因此，xtx_t 是 ff 在 XX 上的最小化点。