Duplicate

Lecture 5 | Optimization Review

형태
Math
수강 일자
2022/09/19

Directional Derivative in Multivariate Functions

Duf(x0):=lim⁡ϵ→0f(x9+ϵu)−f(x0)ϵD_u f(x_0):= \lim_{\epsilon \rarr 0} \frac{f(x_9+\epsilon u)-f(x_0)}{\epsilon}

Gradient and Partial Derivative

∇f(x):=(∂f(x)∂x1⋮∂f(x)∂xn)\nabla f(x):= \begin{pmatrix} \frac{\partial f(x)}{\partial x_1} \\ \vdots \\ \frac{\partial f(x)}{\partial x_n} \end{pmatrix}

Jacobian

•
f:Rn→Rmf: {\mathbb R}^n \rarr {\mathbb R}^m 의 derviate matrix
J=[∂f∂x1…∂f∂xn]=[∇Tf1⋮∇Tfm]=[∂f1∂x1…∂f1∂xn⋮⋱⋮∂fm∂x1…∂fm∂xn]J = \begin{bmatrix} \frac{\partial f}{\partial x_1} & \dots & \frac{\partial f}{\partial x_n} \end{bmatrix}= \begin{bmatrix} \nabla^T f_1 \\ \vdots \\ \nabla^T f_m \\ \end{bmatrix} = \begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \dots & \frac{\partial f_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial f_m}{\partial x_1} & \dots & \frac{\partial f_m}{\partial x_n} \end{bmatrix}

Hessian Matrix

•
f:Rn→Rf: \mathbb R^n \rarr \mathbb R 의 second derivative matrix
Hf=∇2f(x):=[∂2f(x)∂x1∂x1…∂2f(x)∂x1∂xn⋮⋱⋮∂2f(x)∂xn∂x1…∂2f(x)∂xn∂xn]H_f=\nabla^2f(x):= \begin{bmatrix} \frac{\partial^2 f(x)}{\partial x_1\partial x_1} & \dots & \frac{\partial^2 f(x)}{\partial x_1\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial^2 f(x)}{\partial x_n\partial x_1} & \dots & \frac{\partial^2 f(x)}{\partial x_n\partial x_n} \end{bmatrix}

Taylor Series

•
함수를 polynomial 로 근사하는 방법론
f(x)=f(a)+f′(a)1!(x−a)+f′′(a)2!(x−a)2+⋯=∑n=0∞f(n)(a)n!(x−a)nf(x)=f(a) + \frac{f'(a)}{1!}(x-a) + \frac{f''(a)}{2!}(x-a)^2 + \dots = \sum_{n=0}^{\infty}\frac{f^{(n)}(a)}{n!}(x-a)^n
•
Multivariable Function ff 의 2nd-order approximation
f(x)≈f(x0)+⟨∇f(x0),x−x0⟩+⟨∇2f(x0)(x−x0),x−x0⟩/2f(x) \approx f(x_0)+ \left\langle \nabla f(x_0),x-x_0\right\rangle + \left\langle \nabla^2 f(x_0)(x-x_0),x-x_0\right\rangle/2
◦
f(x)≈c+bTx+12xTAxf(x) \approx c + b^Tx + \frac{1}{2}x^TAx 형태

Optimization Problem

•
minimize f(x)f(x) subject to gi(x)<0g_i(x)<0, hj(x)=0h_j(x)=0 과 같은 문제들

Convex Functions

•
A function f:X→Rf: X \rarr \mathbb R is called convex if and only if:
∀t,x1,x2    s.t    0≤t≤1,x1,x2∈Xf(tx1+(1−t)x2)≤tf(x1)+(1−t)f(x2)\forall t,x_1,x_2 \thickspace \thickspace {\rm s.t} \thickspace \thickspace 0\le t \le 1, x_1,x_2 \in X \\ f(tx_1 + (1-t)x_2)\le tf(x_1) + (1-t)f(x_2)
•
함숫값의 평균이 평균의 함숫값보다 큼!
•
Convexity of a Function (다음 4 개는 동치)
1.
A function f:X→Rf: X \rarr \mathbb R is called convex
2.
The epigraph of f is a convex set
epi f={(x,t)∣x∈X,f(x)≤t}{\rm epi}\ f = \{ (x,t) | x\in X, f(x) \le t\}
3.
Jensen’s inequality satisfies
•
x,y∈Xx, y \in X 이고 0≤α≤10\le\alpha \le 1 인 x,y,αx,y,\alpha 에 대해서
f(αx+(1−α)y)≤αf(x)+(1−α)f(y)f(\alpha x + (1-\alpha)y)\le \alpha f(x) + (1-\alpha)f(y)
4.
ff 가 두 번 미분가능하고, Hessian ∇2f(x)\nabla^2 f(x) 가 모든 x∈Xx \in X 에 대해서 positive semidefinite
zT∇2f(x)z≥0z^T \nabla^2 f(x) z \ge 0

How to Recognize a Minimum

•
ff 가 전 범위에서 differentiable 하고 unconstrained 하면 다음과 같은 세 경우가 있음
◦
Strictly Convex → Global Minimum 을 가짐
◦
Neither Concave nor Convex → Saddle-Point or Local Minimum/Maximum
◦
Strictly Concave → Global Maximum 을 가짐

Gradient Descent

•
Initial point x(0)x^{(0)} 에서 gradient 의 negative 방향으로 iterative 하게 갱신해가는 방법론
x(k+1)=x(k)−∇f(x(k))x^{(k+1)} = x^{(k)} - \nabla f(x^{(k)})
◦
∥∇f(x(k))∥<ϵ\| \nabla f(x^{(k)}) \| < \epsilon 을 만족할 때까지 반복함
◦
Convergence 가 보장되지는 않으며, 이를 위해서는 부가적인 line search 가 필요함
◦
Line search: gradient direction 앞에 붙을 상수 α\alpha 를 heuristic 하게 구하는 과정
▪
α=1\alpha=1 부터 시작해서 0.5 씩 곱해가면서 다음을 만족할 때까지 진행함
▪
β=10−4∈(0,1)\beta = 10^{-4} \in (0,1) 정도로 설정함
▪
β\beta 가 0에 가까우면 큰 horizontal step 을 허용
▪
β\beta 가 1에 가까우면 작은 horizontal step 만을 허용
f(x+αd)≤f(x)+β[∇f(x)]T(αd)f(x+\alpha d) \le f(x)+\beta[\nabla f(x)]^T (\alpha d)

Newton’s Method for Root-Finding

•
f(x)=0f(x)=0 을 만족하는 xx 를 구하는 방법론
•
Initial point x0x^0 에서 시작하여 다음과 같은 iterative update 를 사용함
xk+1=xk−f(xk)∇f(xk)x^{k+1} = x^k - \frac{f(x^k)}{\nabla f(x^k)}
◦
특정 점에서 xx 의 linearization 이 abscissa 와 만나는 지점을 새로운 xx 로 변경
•
Optimization 문제에서 ∇f(x∗)=0\nabla f(x^*) =0 을 만족하는 x∗x^* 을 찾으려고 하는 것이니, ff 의 derivative 에 Newton’s Method 를 적용하는 것을 생각할 수 있음!
x(k+1)=x(k)−[∇2f(x(k))]−1∇f(x(k))x^{(k+1)} = x^{(k)} - [\nabla^2 f(x^{(k)})]^{-1}\nabla f(x^{(k)})
◦
Iterative Minimization of 2nd degree Taylor Series 로도 생각할 수 있음
x=z−H−1∇f(z)x = z-{\rm H}^{-1}\nabla f(z)
◦
Gradient descent 와 마찬가지로 부가적인 line search 가 필요할 수 있음
◦
Gradient descent 에 비교해서의 장점은 적은 iteration 으로 수렴할 수 있다는 것임
◦
다만, inverse of Hessian 이 필요하고, 이는 computationally expensive (O(n3)O(n^3))
◦
다른 방법으로는 Quasi-Newton Methods, Conjugate Gradient Method 등이 있지만, 여기서 다루지는 않음

Least-Squares Problem

minimize    12∑j=1mrj2(x){\rm minimize }\thickspace\thickspace \frac{1}{2}\sum_{j=1}^m r_j^2(x)
•
Analytic Solutions
◦
Cholesky Factorization
◦
QR Factorization
◦
SVD
•
Non-linear Least-Squares: via iterative methods
◦
Gauss-Newton Method: A modified Newton’s method
◦
Levenberg-Marquardt Method: Trust-region strategy
Linear Least-Squares Problem
•
A∈Rm×nA \in \mathbb R^{m\times n} 와 b∈Rmb\in \mathbb R^m 에 대해서 다음을 만족하는 xx 를 찾는 문제
minimize    f(x)=12∥Ax−b∥22{\rm minimize }\thickspace\thickspace f(x) = \frac{1}{2}\| Ax-b \|_2^2
•
m≥nm\ge n 을 가정하면 다음과 같이 변형할 수 있음
f(x)=12∥Ax−b∥22=12(Ax−b)T(Ax−b)=12(xTAT−bT)(Ax−b)=12(xTATAx−xTATb−bTAx−bTb)=12(xTATAx−2xTATb−bTb)\begin{align*} f(x) &= \frac{1}{2} \| Ax-b\|_2^2 = \frac{1}{2}(Ax-b)^T(Ax-b) \\ &=\frac{1}{2} (x^TA^T-b^T)(Ax-b) \\ &= \frac{1}{2} (x^TA^TAx-x^TA^Tb-b^TAx-b^Tb) \\ &= \frac{1}{2} (x^TA^TAx-2x^TA^Tb-b^Tb) \end{align*}
•
최솟값을 구하기 위해 xx 로 미분하는 것을 생각해볼 수 있음!
◦
∂xTAx∂x=(A+AT)x\frac{\partial x^TAx}{\partial x} = (A+A^T)x
◦
∂uTAv∂x=∂u∂xAv+∂v∂xATu\frac{\partial u^TAv}{\partial x} = \frac{\partial u}{\partial x}Av + \frac{\partial v}{\partial x}A^Tu
∇f(x)=ATAx−ATb\nabla f(x)=A^TAx-A^Tb
◦
Hessian 을 계산하면 ∇2f(x)=ATA\nabla^2 f(x) = A^TA 인데, 이는 positive semidefinite 함
xTATAx=∥Ax∥22≥0x^TA^TAx = \|Ax\|_2^2 \ge 0
◦
즉, f(x)f(x) 는 convex function
◦
가능한 solution 은 다음과 같음
x=(ATA)−1ATbx = (A^TA)^{-1}A^Tb
▪
A†=(ATA)−1ATA^{\dagger} = (A^TA)^{-1}A^T: Pesudo-inverse of A

Homogeneous Least-squares

•
Ax=bAx=b 가 아닌, Ax=0Ax=0 의 문제는 homogeneous least-squares 문제로 부름
•
A∈Rm×nA \in \mathbb R^{m\times n} 와 b∈Rmb\in \mathbb R^m 에 대해서 다음을 만족하는 xx 를 찾는 문제
minimize    f(x)=12∥Ax∥22{\rm minimize }\thickspace\thickspace f(x) = \frac{1}{2}\| Ax \|_2^2
•
m≥nm\ge n, ∥x∥=1\|x\|=1 (trivial solution 을 제거하기 위해) 을 가정
•
Lagrange Multiplier 를 사용하여 다음과 같이 변형할 수 있음
minimize    L(x,λ)=xTATAx+λ(1−xTx){\rm minimize }\thickspace\thickspace L(x,\lambda) = x^TA^TAx + \lambda(1-x^Tx)
•
이후 SVD 를 사용해 A=UΣVTA=U\Sigma V^T 로 변형하여 VV 의 마지막 column 을 찾으면 됨! (증명은 16강 PCA 에 있음!)