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

Learn & Enjoy …

Archive for Tháng Tư, 2008

« Những bài viết trước

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)

Đăng bởi tqlong 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} và \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) là

    \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

Vì \displaystyle f là hà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)]

Vì \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 \lambda là giá 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 là

\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^*\| là

    \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}} } và \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) là

    \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.

Đăng trong Giải tích lồi, Quy hoạch lồi, Quy hoạch phi tuyến | Tagged: , , | Leave a Comment »

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

Đăng bởi tqlong 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) và \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 mà

    \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.

Đăng trong Quy hoạch phi tuyến | Tagged: , , , , , | Leave a Comment »

« Những bài viết trước