CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Tối ưu không ràng buộc (5) – Tốc độ hội tụ của phương pháp đạo hàm (hàm lồi)

Posted by Trần Quốc Long on Tháng Tư 25, 2008

Ta biết, hàm lồi có các tính chất rất “đẹp” đối với các thuật toán tối ưu hóa. Đặc biệt, cực tiểu cục bộ của hàm lồi cũng là cực tiểu toàn cục. Tính chất này cho phép ước lượng các sai số như \displaystyle \epsilon(t)=f(x_t)-\mathrm{Opt}(P) hay \displaystyle \epsilon(t)=\|x_t-x^*\|, đồng thời còn đảm bảo các thuật toán tối ưu hoạt động khá hiệu quả trên hàm lồi như ta sẽ thấy dưới đây.

Định lý (tốc độ hội tụ của thuật toán ArD): Nếu \displaystyle f\in C^{1,1}\displaystyle f là hàm lồi thì với thuật toán ArD (với tham số \displaystyle 0.5\leq \epsilon<1,\nu>1), ta có

  1. Quỹ đạo \displaystyle \{x_t\}_{t=1}^\infty hội tụ đến một cực tiểu toàn cục \displaystyle \bar{x}\in X^* nào đó.
  2. Tốc độ hội tụ của sai số \displaystyle \epsilon(t)=f(x_t)-\mathrm{Opt}(P)

    \displaystyle \epsilon(N)\leq \frac{\nu L_f \|x_0-\bar{x}\|^2}{4(1-\epsilon)N}

    trong đó \displaystyle L_f là hệ số Lipschitz của \displaystyle \nabla f(x), \displaystyle x_0 là nghiệm ban đầu.

Chứng minh (1): Để cho tiện, đặt

\displaystyle d_t = \|x_t-x^*\|^2

với \displaystyle x^*\in X^* bất kì (lưu ý là \displaystyle x^* có thể khác \displaystyle \bar{x}). Ta có

\displaystyle d_{t+1}=\|x_{t+1}-x^*\|^2=\|x_t-\gamma_t\nabla f(x_t)-x^*\|^2\displaystyle =\|x_t-x^*\|^2-2\gamma_t(x_t-x^*)^T\nabla f(x_t)+\gamma_t^2\|\nabla f(x_t)\|^2\displaystyle =d_t-2\gamma_t(x_t-x^*)^T\nabla f(x_t)+\gamma_t^2\|\nabla f(x_t)\|^2

\displaystyle fhàm lồi nên xấp xỉ Taylor bậc 1 là cận dưới của hàm, ta có

\displaystyle f(x^*)\geq f(x_t)+(x^*-x_t)\nabla f(x_t)

\displaystyle (x_t-x^*)\nabla f(x_t)\geq f(x_t)-f(x^*)=\epsilon(t)

Hơn nữa, do \displaystyle \gamma_t là bước nhảy Armijo nên

\displaystyle \epsilon\gamma_t\|\nabla f(x_t)\|^2\leq f(x_t)-f(x_{t+1})

\displaystyle \gamma_t^2\|\nabla f(x_t)\|^2\leq \frac{\gamma_t}{\epsilon}(\epsilon(t)-\epsilon(t+1))

Vậy, ta có

\displaystyle d_{t+1}\leq d_t - 2\gamma_t\epsilon(t) + \frac{\gamma_t}{\epsilon}(\epsilon(t)-\epsilon(t+1))\displaystyle = d_t-\gamma_t[(2-\epsilon^{-1})\epsilon(t)+\epsilon^{-1}\epsilon(t+1)]

Hơn nữa, ta lại có ước lượng của bước nhảy Armijo

\displaystyle \gamma_t\geq \frac{2(1-\epsilon)}{\nu L_f}

nên nếu \displaystyle \epsilon\geq 0.5 hay \displaystyle 2-\epsilon^{-1}\geq 0 thì

\displaystyle d_{t+1}\leq d_t - \frac{2(1-\epsilon)}{\nu L_f} [(2-\epsilon^{-1})\epsilon(t)+\epsilon^{-1}\epsilon(t+1)]\leq d_t

Tức là khoảng cách \displaystyle \|x_t-x^*\|  không tăng theo \displaystyle t, nói cách khác quỹ đạo \displaystyle \{x_t\}_{t=1}^\infty bị chặn. Theo định lý về tính hội tụ của các phương pháp sử dụng đạo hàm, các điểm giới hạn \displaystyle \bar{x} của quỹ đạo \displaystyle \{x_t\}_{t=1}^\infty thỏa mãn tính chất \displaystyle \nabla f(x^*)=0. Nhưng do \displaystyle f là hàm lồi nên \displaystyle \bar{x} cũng là cực tiểu toàn cục của \displaystyle f. Ngoài ra, do \displaystyle \bar{x} là điểm giới hạn của quỹ đạo nên có 1 dãy con hội tụ về \displaystyle \bar{x}, nhưng do khoảng cách \displaystyle \|x_t-\bar{x}\| không tăng theo \displaystyle t nên

\displaystyle \lim_{t\rightarrow \infty} \|x_t-\bar{x}\|=0

hay \displaystyle \lim_{t\rightarrow \infty}x_t = \bar{x}\in X^*.

Chứng minh (2): Thay \displaystyle \bar{x}=x^*, ta có

\displaystyle \frac{2(1-\epsilon)}{\nu L_f} [(2-\epsilon^{-1})\epsilon(t)+\epsilon^{-1}\epsilon(t+1)]\leq d_t - d_{t+1}

\displaystyle d_0-d_N=\sum_{t=0}^{N-1} d_t-d_{t+1}\geq \frac{2(1-\epsilon)}{\nu L_f} \sum_{t=0}^{N-1}[(2-\epsilon^{-1})\epsilon(t)+\epsilon^{-1}\epsilon(t+1)]

\displaystyle \epsilon(t)\geq \epsilon(N),\forall t\leq N (do thuật toán luôn làm giảm hàm mục tiêu) nên

\displaystyle \|x_0-\bar{x}\|^2=d_0\geq d_0-d_N\geq \frac{2(1-\epsilon)N}{\nu L_f} 2\epsilon(N)

\displaystyle \epsilon(N)\leq \frac{\nu L_f\|x_0-\bar{x}\|^2}{4(1-\epsilon)N}

Như vậy, hàm sai số \displaystyle \epsilon(t)=f(x_t)-\mathrm{Opt}(P) hội tụ về \displaystyle 0 chậm hơn tuyến tính. Tuy nhiên, nếu hàm lồi \displaystyle f có cận trên và cận dưới là một hàm bậc 2 thì ta có kết quả mạnh hơn, đó là tốc độ hội tụ của thuật toán ArD là tuyến tính.

Định nghĩa (hàm lồi mạnh): Hàm lồi \displaystyle f gọi là hàm lồi mạnh (strongly convex) với tham số \displaystyle (l_f,L_f)>0 nếu \displaystyle f khả vi liên tục và

\displaystyle f(x)+d^T\nabla f(x)+\frac{l_f}{2}\|d\|^2\leq f(x+d)\leq f(x)+ d^T\nabla f(x)+\frac{L_f}{2}\|d\|^2

Định lý (tính chất của hàm lồi mạnh): Nếu \displaystyle f là hàm lồi mạnh với tham số \displaystyle (l_f,L_f) thì

  1. Tập \displaystyle \{x:f(x)\leq a\} là tập compact với mọi \displaystyle a\in \mathbb{R}.
  2. Hàm \displaystyle f là hàm lồi chặt và có cực tiểu toàn cục duy nhất.
  3. Hàm \displaystyle f là hàm thuộc lớp \displaystyle C^{1,1} với tham số \displaystyle L_f.

Bổ đề: Hàm \displaystyle f là hàm lồi mạnh với tham số \displaystyle (l_f,L_f) nếu và chỉ nếu

\displaystyle l_f\leq \lambda \leq L_f

với \displaystyle \lambdagiá trị riêng (eigenvalue) bất kì của ma trận Hessian của \displaystyle f tại \displaystyle x.

Chứng minh:

\displaystyle \Rightarrow“: Nếu \displaystyle f là hàm lồi mạnh với tham số \displaystyle (l_f,L_f), đặt \displaystyle \phi(t)=f(x+td), ta có

\displaystyle \phi(t)\leq \phi(0)+t\phi'(0)+\frac{L_f}{2}t^2\|d\|^2

\displaystyle \phi(0)\leq \phi(t)-t\phi'(t)+\frac{L_f}{2}t^2\|d\|^2

Suy ra

\displaystyle \frac{\phi'(t)-\phi'(0)}{t}\leq L_f\|d\|^2

Cho \displaystyle t\rightarrow 0 ta được \displaystyle \phi''(0)=d^T\nabla^2 f(x)d\leq L_f\|d\|^2,\forall x,d. Nếu chọn \displaystyle d là vectơ riêng ứng với giá trị riêng \displaystyle \lambda thì

\displaystyle d^T\nabla^2 f(x)d=\lambda \|d\|^2\leq L_f\|d\|^2

hay \displaystyle \lambda\leq L_f. Tương tự, ta cũng có \displaystyle \lambda\geq l_f.

\displaystyle \Leftarrow“: Giả sử

\displaystyle 0<l_f\leq \lambda \leq L_f

trong đó \displaystyle \lambda là giá trị riêng bất kì của \displaystyle \nabla^2 f(x) với mọi \displaystyle x.

Ta có khai triển Taylor bậc 2 của \displaystyle f(x+d) tại \displaystyle x

\displaystyle f(x+d)=f(x)+d^T\nabla f(x)+\frac{1}{2} d^T\nabla^2 f(\psi)d

với \displaystyle \psi\in [x,x+d]. Ta lại có

\displaystyle \frac{l_f}{2}\|d\|^2\leq \frac{1}{2} d^T\nabla^2 f(\psi)d\leq \frac{L_f}{2}\|d\|^2

Vậy ta có điều phải chứng minh.

Chứng minh (1): Ta sẽ chứng minh \displaystyle f bị chặn dưới. Thật vậy, cố định \displaystyle x, ta có

\displaystyle f(x+d) \geq f(x)+d^T\nabla f(x)+\frac{l_f}{2}\|d\|^2\displaystyle \geq f(x)-\|d\|\|\nabla f(x)\|+\frac{l_f}{2}\|d\|^2,\forall d

Vế phải là hàm bậc hai của \displaystyle \|d\| với hệ số ở lũy thừa 2 dương nên bị chặn dưới, do đó \displaystyle f(x+d) bị chặn dưới với mọi \displaystyle d. Đặt \displaystyle c=\inf f(x), và xét \displaystyle x\in \{x:f(x)\leq a\}, ta có

\displaystyle a-c\geq f(y)-f(x)\geq (y-x)^T\nabla f(x)+\frac{l_f}{2} \|y-x\|^2 \displaystyle \geq -\|y-x\|\|\nabla f(x)\|+\frac{l_f}{2} \|y-x\|^2,\forall y\in \{x:f(x)\leq a\}

Vế phải là hàm bậc 2 với hệ số ở lũy thừa 2 dương nên chỉ bị chặn trên khi \displaystyle \|y-x\| bị chặn trên. Vậy tập \displaystyle \{x:f(x)\leq a\} bị chặn. Hơn nữa, do tính liên tục của \displaystyle f(x), tập \displaystyle \{x:f(x)\leq a\} là tập đóng nên cũng là tập compact.

Chứng minh (2): Tập \displaystyle \{x:f(x)\leq a\} là tập compact nên phải tồn tại cực tiểu của \displaystyle f(x) trong tập này. Rõ ràng, đây cũng là cực tiểu toàn cục của \displaystyle f(x). Hơn nữa \displaystyle f là hàm lồi chặt nên cực tiểu này là duy nhất (ma trận Hessian xác định dương do \displaystyle l_f>0).

Chứng minh (3): Ta có

\displaystyle \|\nabla f(x+d)-\nabla f(x)\|=\|\nabla^2 f(\psi)d\|

với \displaystyle \psi\in [x,x+d]. Theo bổ đề trên, ta lại có

\displaystyle \|\nabla^2 f(\psi)d\|^2=d^T(\nabla^2f(\psi))^2d\leq L_f^2\|d\|^2

Vậy

\displaystyle \|\nabla f(x+d)-\nabla f(x)\|\leq L_f \|d\|

Tức là \displaystyle L_f là hệ số Lipschitz của \displaystyle \nabla f(x), điều phải chứng minh.

Định lý (tốc độ hội tụ của thuật toán ArD khi hàm mục tiêu lồi mạnh): Nếu \displaystyle f là hàm lồi mạnh với tham số \displaystyle (l_f,L_f) thì với thuật toán ArD (với tham số \displaystyle 0.5\leq \epsilon<1,\nu>1), ta có

  1. Quỹ đạo \displaystyle \{x_t\}_{t=0}^\infty hội tụ về cực tiểu duy nhất \displaystyle x^*.
  2. Tốc độ hội tụ của hàm sai số \displaystyle \epsilon_1(t)=\|x_t-x^*\|

    \displaystyle \epsilon_1(N)\leq \theta^N \epsilon_1(0)

    với \displaystyle \theta=\sqrt{\frac{Q_f-(2-\epsilon^{-1})(1-\epsilon)\nu^{-1}}{Q_f+(\epsilon^{-1}-1)\nu^{-1}} }\displaystyle Q_f=\frac{L_f}{l_f} gọi là tỉ số điều kiện (condition number) của hàm \displaystyle f.

  3. Tốc độ hội tụ của hàm sai số \displaystyle \epsilon(t)=f(x_t)-\mathrm{Opt}(P)

    \displaystyle \epsilon(N)\leq \theta^{2N}Q_f\epsilon(0)

Chứng minh (1): Dễ thấy vì các tính chất trên của hàm lồi mạnh nên các điều kiện của các định lý về tính hội tụ của thuật toán ArD với hàm mục tiêu lồi được thỏa mãn.

Chứng minh (2): Theo định lý trên, ta có

\displaystyle \frac{2(1-\epsilon)}{\nu L_f} [(2-\epsilon^{-1})\epsilon(t)+\epsilon^{-1}\epsilon(t+1)]\leq d_t - d_{t+1}

Với điều kiện hàm lồi mạnh, ta có thể ước lượng \displaystyle \epsilon(t) chính xác hơn

\displaystyle \epsilon(t)=f(x_t)-f(x^*)\geq \frac{l_f}{2}\|x_t-x^*\|=\frac{l_f}{2}d_t

do \displaystyle \nabla f(x^*)=0, vậy

\displaystyle d_t - d_{t+1}\geq \frac{(1-\epsilon)l_f}{\nu L_f} [(2-\epsilon^{-1})d_t+\epsilon^{-1}d_{t+1}]

\displaystyle d_{t+1}\leq \frac{Q_f-(2-\epsilon^{-1})(1-\epsilon)\nu^{-1}}{Q_f+(\epsilon^{-1}-1)\nu^{-1}} d_t

\displaystyle d_{t+1}\leq \theta^2 d_t

\displaystyle \epsilon_1(t+1)=\sqrt{d_{t+1}}\leq \theta \sqrt{d_t}=\theta \epsilon_1(t)

\displaystyle \epsilon_1(N) \leq \theta^N \epsilon_1(0)

Chứng minh (3): Ta có

\displaystyle \epsilon(N)=f(x_N)-f(x^*)\leq \frac{L_f}{2}d_N \leq \frac{L_f\theta^{2N}}{2}d_0

Ta lại có

\displaystyle d_0=\|x_0-x^*\|^2\leq \frac{2}{l_f}[f(x_0)-f(x^*)]=\frac{2}{l_f}\epsilon(0)

suy ra

\displaystyle \epsilon(N)\leq \frac{L_f\theta^{2N}}{l_f}\epsilon(0)=\theta^{2N}Q_f\epsilon(0)

Nhận xét:

  1. Trong trường hợp tổng quát, ta chỉ có thể đánh giá \displaystyle \epsilon_\nabla(t)=\|\nabla f(x_t)\|^2 do hàm mục tiêu có thể có nhiều cực tiểu cục bộ (và các điểm KKT khác).
  2. Trong trường hợp hàm lồi thuộc lớp \displaystyle C^{1,1}, ta có thể đánh giá được hàm \displaystyle \epsilon_f(t)=f(x_t)-\mathrm{Opt}(P) vì các điểm KKT là cực tiểu toàn cục của hàm mục tiêu. Tuy nhiên ta không thể đánh giá hàm \displaystyle \epsilon_x(t)=\|x_t-x^*\| vì có thể có rất nhiều cực tiểu toàn cục.
  3. Trong trường hợp hàm lồi mạnh, chỉ có một cực tiểu duy nhất nên ta có điều kiện ước lượng \displaystyle \epsilon_x(t)=\|x_t-x^*\|.
  4. Tuy tốc độ hội tụ trong trường hợp hàm mục tiêu lồi mạnh là tuyến tính, tỉ lệ hội tụ \displaystyle \theta phụ thuộc rất nhiều vào tỉ số điều kiện \displaystyle Q_f=\frac{L_f}{l_f} . Khi \displaystyle Q_f lớn thì \displaystyle \theta gần bằng \displaystyle 1 tức là thuật toán hội tụ rất chậm. Trường hợp này ta nói hàm \displaystyle f là hàm có điều kiện tồi (ill-conditioned).
  5. Những hàm thay đổi mạnh trên một hướng nhưng thay đổi rất ít trên hướng khác là những hàm có điều kiện tồi.
    Ví dụ: Thuật toán StD chạy trên hàm \displaystyle f(x)=5x_1^2+0.2x_2^2, tỉ số điều kiện \displaystyle Q_f=\frac{5}{0.2}=25

    Hàm có điều kiện tồi, tỉ số điều kiện = 25

  6. Như vậy, phương pháp tối ưu theo hướng đạo hàm phụ thuộc vào hệ tọa độ quy chiếu, trong ví dụ trên nếu ta đổi biến

    \displaystyle y_1=\sqrt{5}x_1, y_2=\sqrt{0.2}x_2

    thì \displaystyle f(y)=y_1^2+y_2^2, tỉ số điều kiện lúc này là \displaystyle Q_f=1 và thuật toán hội tụ rất nhanh.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: