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

Learn & Enjoy …

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

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

Ta đã biết, dưới các điều kiện khá đơn giản và thường gặp (hàm mục tiêu khả vi liên tục, bị chặn dưới, quỹ đạo bị chặn), phương pháp xuống đồi theo hướng đạo hàm (StD hoặc ArD) hội tụ về các điểm KKT. Trong bài này, ta sẽ xem xét tốc độ hội tụ của các phương pháp tối ưu theo hướng đạo hàm này. Các kết quả chủ yếu là:

  1. Trong trường hợp tổng quát, hàm sai số \displaystyle \epsilon(t)=\|\nabla f(x_t)\|^2 hội tụ về \displaystyle 0 chậm hơn tuyến tính.
  2. Trong trường hợp hàm mục tiêu là hàm lồi (cực tiểu cục bộ là cực tiểu toàn cục), hàm sai số \displaystyle \epsilon(t)=f(x)-\mathrm{Opt}(P) hội tụ về \displaystyle 0 chậm hơn tuyến tính.
  3. Trong trường hợp hàm mục tiêu là hàm lồi chặt (chỉ có 1 cực tiểu duy nhất), cả hai hàm sai số \displaystyle \epsilon(t)=f(x)-\mathrm{Opt}(P)\displaystyle \epsilon(t)=\|x_t-x^*\| đều hội tụ về \displaystyle 0 với tốc độ hội tụ tuyến tính.

Định nghĩa (lớp hàm \displaystyle C^{1,1}): Hàm \displaystyle f(x):\mathrm{R}^n\rightarrow \mathrm{R} là hàm thuộc lớp \displaystyle C^{1,1} nếu \displaystyle f(x) khả vi liên tục với đạo hàm liên tục Lipschitz, nghĩa là

\displaystyle \|\nabla f(x)-\nabla f(y)\|\leq L_f \|x-y\|, \forall x,y\in \mathrm{R}^n

Khi đó \displaystyle L_f>0 là hệ số Lipschitz của hàm \displaystyle \nabla f(x).

Lưu ý: Hàm liên tục Lipschitz là hàm liên tục nhưng mệnh đề ngược lại chưa chắc đúng.

Định lý (cận trên của hàm thuộc lớp \displaystyle C^{1,1}): Nếu \displaystyle f\in C^{1,1} thì

\displaystyle f(x+d)\leq f(x) + d^T\nabla f(x)+\frac{L_f}{2}\|d\|^2,\forall x,d\in \mathrm{R}^n

trong đó \displaystyle L_f là hệ số Lipschitz của \displaystyle \nabla f(x)

Nhận xét: Định lý cho phép ước lượng hàm \displaystyle f(x+d) quanh điểm \displaystyle x bằng một hàm bậc 2 của \displaystyle d.

Chứng minh: Đặt \displaystyle \phi(t)=f(x+td), ta có

\displaystyle \phi'(t) = d^T\nabla f(x+td)

\displaystyle \phi'(a)-\phi'(b)=d^T[\nabla f(x+ad)-\nabla f(x+bd)]\displaystyle \leq \|d\|L_f|a-b|\|d\|=L_f|a-b|\|d\|^2

Suy ra

\displaystyle f(x+d)-f(x)-d^T\nabla f(x)=\phi(1)-\phi(0)-\phi'(0)\displaystyle =\int_0^1 \phi'(t)dt -\phi'(0)=\int_0^1 (\phi'(t)-\phi'(0))dt\displaystyle \leq \int_0^1L_f t \|d\|^2dt = \frac{L_f}{2}\|d\|^2

Định lý (tốc độ hội tụ của thuật toán StD): Nếu hàm mục tiêu \displaystyle f\in C^{1,1} và sai số \displaystyle \epsilon(t)=\|\nabla f(x_t)\|^2 thì với thuật toán StD, tại bước lặp thứ \displaystyle N ta có

\displaystyle \min_{0\leq t< N} \epsilon(t)\leq \frac{2L_f}{N} [f(x_0)-\mathrm{Opt}(P)]

trong đó \displaystyle x_0 là nghiệm ban đầu, \displaystyle \mathrm{Opt}(P) là giá trị tối ưu.

Nhận xét: Định lý không cho ước lượng sai số tại bước lặp thứ \displaystyle N mà ước lượng sai số nhỏ nhất trong \displaystyle N bước lặp đầu tiên.

Chứng minh: Trường hợp tồn tại \displaystyle t\in[0,N] sao cho \displaystyle \nabla f(x_t)=0 thì định lý hiển nhiên đúng. Vậy giả sử \displaystyle \nabla f(x_t)\neq 0, \forall t\in[0,N].

Ta có \displaystyle f(x_{t+1})=\min_{\gamma>0} f(x_t-\gamma\nabla f(x_t)). Theo định lý trên

\displaystyle f(x_t-\gamma\nabla f(x_t)) \leq f(x_t)-\gamma\|\nabla f(x_t)\|^2+\frac{L_f}{2}\gamma^2\|\nabla f(x_t)\|^2

Suy ra

\displaystyle \displaystyle f(x_{t+1}) \leq f(x_t)+\|\nabla f(x_t)\|^2\min_{\gamma>0}\left[-\gamma+\frac{L_f}{2}\gamma^2\right]

Hàm bậc 2 \displaystyle -\gamma+\frac{L_f}{2}\gamma^2 nhận giá trị cực tiểu bằng \displaystyle -\frac{1}{2L_f} tại

\displaystyle \gamma=\frac{1}{L_f} >0

vậy ta có

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

\displaystyle f(x_t)-f(x_{t+1})\geq \frac{1}{2L_f} \|\nabla f(x_t)\|^2=\frac{1}{2L_f}\epsilon(t)

Suy ra

\displaystyle f(x_0)-\mathrm{Opt}(P)\geq f(x_0)-f(x_N) \displaystyle =\sum_{t=0}^{N-1}[f(x_t)-f(x_{t+1}]\geq \frac{1}{2L_f} \sum_{t=0}^{N-1}\epsilon(t)\geq \frac{N}{2L_f} \min_{0\leq t<N}\epsilon(t)

Kết luận

\displaystyle \min_{0\leq t<N}\epsilon(t)\leq \frac{2L_f}{N} [f(x_0)-\mathrm{Opt}(P)]

Định lý (tốc độ hội tụ của thuật toán ArD): Với hàm mục tiêu \displaystyle f\in C^{1,1}, hàm sai số \displaystyle \epsilon(t)=\|\nabla f(x_t)\|^2 và thuật toán ArD với tham số \displaystyle 0<\epsilon<1,\nu>1, tại bước lặp thứ \displaystyle N ta có

\displaystyle \min_{0\leq t< N} \epsilon(t)\leq \frac{\nu L_f}{2\epsilon(1-\epsilon) N} [f(x_0)-\mathrm{Opt}(P)]

Chứng minh: Đầu tiên, ta sẽ ước lượng bước nhảy Armijo, tại bước lặp thứ \displaystyle t, bước nhảy Armijo phải thỏa mãn (bước nhảy tốt nhất):

\displaystyle f(x_t-\nu\gamma_t\nabla f(x_t))-f(x_t)>-\epsilon\nu\gamma_t \|\nabla f(x_t)\|^2

Nhưng, từ định lý trên, ta có

\displaystyle f(x_t-\nu\gamma_t\nabla f(x_t))-f(x_t)\leq -\nu\gamma_t\|\nabla f(x_t)\|^2+\frac{L_f}{2}\nu^2\gamma_t^2\|\nabla f(x_t)\|^2

Vậy

\displaystyle -\epsilon\nu\gamma_t \|\nabla f(x_t)\|^2<-\nu\gamma_t\|\nabla f(x_t)\|^2+\frac{L_f}{2}\nu^2\gamma_t^2\|\nabla f(x_t)\|^2

\displaystyle (1-\epsilon)\nu\gamma_t \|\nabla f(x_t)\|^2<\frac{L_f}{2}\nu^2\gamma_t^2\|\nabla f(x_t)\|^2

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

Hơn nữa, do là \displaystyle \gamma_t bước nhảy thích hợp:

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

\displaystyle f(x_t)-f(x_{t+1}) \geq \gamma_t \|\nabla f(x_t)\|^2 >\frac{2(1-\epsilon)}{\nu L_f} \|\nabla f(x_t)\|^2

Tiếp tục như định lý về độ hội tụ của thuật toán StD, ta có

\displaystyle \min_{0\leq t< N} \epsilon(t)\leq \frac{\nu L_f}{2\epsilon(1-\epsilon)N} [f(x_0)-\mathrm{Opt}(P)]

Nhận xét:

  1. Như vậy nếu \displaystyle \nabla f(x_t)\neq 0,\forall t thì chắc chắn tồn tại dãy con \displaystyle \{x_{t_i}\}_{i=1}^\infty

    \displaystyle \lim_{i\rightarrow \infty} \nabla f(x_{t_i})=0

  2. Các chứng minh trên đều tìm cách ước lượng bước nhảy \displaystyle \gamma_t, để ý là các ước lượng này chỉ phụ thuộc vào \displaystyle L_f,\epsilon,\nu mà không phụ thuộc \displaystyle t.
  3. Các ước lượng này là cơ sở của các định lý về tốc độ hội tụ của các phương pháp xuống đồi theo hướng đạo hàm khi hàm mục tiêu là hàm lồi ở bài sau.
  4. Như vậy, trong trường hợp tổng quát, hàm sai số \displaystyle \epsilon(t)=\|\nabla f(x_t)\|^2 giảm tương đương \displaystyle O\left(\frac{1}{N}\right), tức là chậm hơn tuyến tính.
  5. Lưu ý là ta không có ước lượng tốc độ hội tụ của \displaystyle \epsilon(t)=f(x_t)-\mathrm{Opt}(P) hay \displaystyle \epsilon(t)=\|x-x^*\| vì trong trường hợp tổng quát, ta chỉ có thể đảm bảo thuật toán hội tụ đến một điểm KKT nào đó (có thể là cực tiểu cục bộ) chứ không có đảm bảo hội tụ đến cực tiểu toàn cục.

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: