Tối ưu Không Ràng Buộc (1) – Bài Toán Và Các Khái Niệm Cơ Bản

Có thể bạn quan tâm

Định nghĩa: Bài toán tối ưu không ràng buộc (unconstrained optimization) là bài toán tìm cực tiểu sau

$\displaystyle \mathrm{Opt}(P)=\min_{x\in \mathbb{R}^n} f(x)$

trong đó $\displaystyle f:\mathbb{R}^n \rightarrow \mathbb{R}$ gọi làm hàm mục tiêu.

Nhận xét:

Tập nghiệm tối ưu (optimal solution) $\displaystyle X^*$ là tập
$\displaystyle X^*=\{x\in\mathbb{R}^n:f(x)=\mathrm{Opt}(P)\}$
Bất cứ một hàm nào chỉ nhận giá trị trên có thể coi là hàm đánh giá sai số (error measurement) của nghiệm so với nghiệm tối ưu. Ví dụ:
1. $\displaystyle \epsilon(x) = d(x,X^*)=\inf_{x^*\in X^*}\|x-x^*\|$
2. $\displaystyle \epsilon(x) = f(x)-\mathrm{Opt}(P)$
Nếu một thuật toán tối ưu (optimization algorithm/method) trong quá trình tìm kiếm nghiệm tối ưu sinh ra nghiệm $\displaystyle x_t$ tại bước lặp thứ $\displaystyle t$ thì đánh giá sai số của nghiệm $\displaystyle x_t$ là
$\displaystyle \epsilon(t)=\epsilon(x_t)$

Ta còn gọi dãy $\displaystyle \{x_t\}_{t=1}^\infty$ là quỹ đạo (trajectory) của thuật toán.
Một thuật toán tối ưu phải bảo đảm sai số tiến tới $\displaystyle 0$ khi số bước lặp ngày càng lớn
$\displaystyle \lim_{t\rightarrow \infty}\epsilon(t) = 0$

Phân loại các thuật toán tối ưu:

Các phương pháp bậc 0: các phương pháp chỉ sử dụng giá trị của hàm $\displaystyle f(x)$ .
Các phương pháp bậc 1: các phương pháp sử dụng giá trị của hàm $\displaystyle f(x)$ và đạo hàm (gradient) $\displaystyle f'(x)=\nabla f(x)$ .
Các phương pháp bậc 2: các phương pháp sử dụng giá trị của hàm $\displaystyle f(x)$ , đạo hàm $\displaystyle f'(x)$ và ma trận Hessian $\displaystyle f''(x)=\nabla^2 f(x)$ .

Tốc độ hội tụ (convergent rate) của các thuật toán tối ưu:

Định nghĩa: Thuật toán tối ưu có tốc độ hội tụ tuyến tính (linearly convergent) nếu

$\displaystyle \exists 0\leq C<\infty, 0<q<1: \epsilon(t)\leq Cq^t$

nghĩa là sai số $\displaystyle \epsilon(t)$ giảm tương đương với một chuỗi cấp số nhân nào đó. $\displaystyle q$ được gọi là tỉ lệ hội tụ.

Nhận xét:

Nếu $\displaystyle Cq^t\leq \delta$ hay $\displaystyle t\geq \ln\frac{C}{\delta}\frac{-1}{\ln q}$ thì $\displaystyle \epsilon(t)\leq \delta$ . Tức là sau $\displaystyle t=\ln\frac{C}{\delta}\frac{-1}{\ln q}$ bước lặp, ta có sai số $\displaystyle \epsilon(t)\leq\delta$ . Như vậy, nếu tốc độ hội tụ là tuyến tính thì số bước lặp tỉ lệ thuận (tuyến tính) với số bít để mô tả độ chính xác của nghiệm (lưu ý: số bít để mô tả độ chính xác của nghiệm là $\displaystyle \ln \frac{1}{\delta}$ ).
Nếu không tồn tại $\displaystyle q,C$ như vậy, ta nói thuật toán tối ưu có tốc độ hội tụ chậm hơn tuyến tính.

Ví dụ:

Nếu $\displaystyle \epsilon(t)=e^{-at}$ thì tốc độ hội tụ là tuyến tính với tỉ lệ $\displaystyle e^{-a}$ .
Nếu $\displaystyle \epsilon(t)=\frac{C}{t}$ thì tốc độ hội tụ chậm hơn tuyến tính.

Điều kiện đủ: Nếu $\displaystyle \overline{\lim_{t\rightarrow \infty}}\frac{\epsilon(t+1)}{\epsilon(t)}<q$ thì thuật toán có tốc độ hội tụ tuyến tính.

Chứng minh: Do $\displaystyle \overline{\lim_{t\rightarrow \infty}}\frac{\epsilon(t+1)}{\epsilon(t)}<q$ nên tồn tại $\displaystyle N$ sao cho $\displaystyle \forall t\geq N$

$\displaystyle \frac{\epsilon(t+1)}{\epsilon(t)}<q$

Suy ra

$\displaystyle \epsilon(t)\leq \epsilon(N)*q^{t-N}=\frac{\epsilon(N)}{q^N}q^t , \forall t\geq N$

Định nghĩa: Thuật toán tối ưu có tốc độ hội tụ nhanh hơn tuyến tính (super-linearly convergent) nếu

$\displaystyle \forall 0<q<1,\exists 0\leq C<\infty: \epsilon(t)\leq Cq^t$

nghĩa là sai số $\displaystyle \epsilon(t)$ giảm nhanh hơn bất cứ chuỗi cấp số nhân nào.

Ví dụ: Nếu $\displaystyle \epsilon(t)=e^{-at^2}$ thì tốc độ hội tụ nhanh hơn tuyến tính.

Điều kiện đủ: Nếu $\displaystyle \lim_{t\rightarrow \infty}\frac{\epsilon(t+1)}{\epsilon(t)}=0$ thì thuật toán tối ưu có tốc độ hội tụ nhanh hơn tuyến tính.

Chứng minh: Do $\displaystyle \lim_{t\rightarrow \infty}\frac{\epsilon(t+1)}{\epsilon(t)}=0$ nên với mọi $\displaystyle q>0$ , tồn tại $\displaystyle N$ sao cho $\displaystyle \forall t\geq N$

$\displaystyle \frac{\epsilon(t+1)}{\epsilon(t)}< q$

Tương tự như trên, ta có

$\displaystyle \forall q>0, \exists N: \epsilon(t)\leq \frac{\epsilon(N)}{q^N}q^t , \forall t\geq N$

Định nghĩa: Thuật toán tối ưu có tốc độ hội tụ bậc $\displaystyle p>1$ nếu:

$\displaystyle \exists C: \epsilon(t+1)\leq C\epsilon(t)^p$

Ví dụ: Nếu $\displaystyle \epsilon(t)=e^{-ap^t}$ thì tốc độ hội tụ có bậc $\displaystyle p$ .

Nhận xét:

Nói một cách nôm na thì tốc độ hội tụ chỉ ra số bước mà thuật toán tối ưu phải thực hiện để giảm được hàm $\displaystyle \epsilon(t)$ về $\displaystyle 0$ . Khi $\displaystyle \epsilon(t)\rightarrow 0$ thì các chữ số sau dấu phẩy của $\displaystyle \epsilon(t)$ cũng dần dần chuyển thành $\displaystyle 0$ .
Nếu thuật toán có tốc độ hội tụ tuyến tính thì số bước để chuyển chữ số thứ $\displaystyle n+1$ sau dấu phẩy của $\displaystyle \epsilon(t)$ thành $\displaystyle 0$ bằng số bước để chuyển chữ số thứ $\displaystyle n$ sau dấu phẩy của $\displaystyle \epsilon(t)$ thành $\displaystyle 0$ .
Nếu thuật toán có tốc độ hội tụ nhanh hơn tuyến tính thì số bước để chuyển chữ số thứ $\displaystyle n+1$ sau dấu phẩy của $\displaystyle \epsilon(t)$ thành $\displaystyle 0$ ít hơn số bước để chuyển chữ số thứ $\displaystyle n$ sau dấu phẩy của $\displaystyle \epsilon(t)$ thành $\displaystyle 0$ .
Nếu thuật toán có tốc độ hội tụ bậc 2 thì số bước để chuyển chữ số thứ $\displaystyle n+1$ sau dấu phẩy của $\displaystyle \epsilon(t)$ thành $\displaystyle 0$ bằng một nửa số bước để chuyển chữ số thứ $\displaystyle n$ sau dấu phẩy của $\displaystyle \epsilon(t)$ thành $\displaystyle 0$ .

Định nghĩa (hướng làm giảm hàm mục tiêu): Hướng $\displaystyle d$ là hướng làm giảm hàm mục tiêu (descent direction) $\displaystyle f(x)$ tại $\displaystyle x$ nếu tồn tại $\displaystyle t>0$ sao cho

$\displaystyle f(x+td)<f(x)$

Định lý: Nếu $\displaystyle d^T\nabla f(x)<0$ thì $\displaystyle d$ là hướng làm giảm hàm mục tiêu tại $\displaystyle x$ .

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

$\displaystyle \phi'(0) = d^T\nabla f(x) < 0$

$\displaystyle \phi(t) = \phi(0) + t\phi'(0) + \Theta(t^2)$

Với $\displaystyle t>0$ đủ nhỏ thì $\displaystyle |t\phi'(0)|>|\Theta(t^2)|$ . Vì vậy khi $\displaystyle t$ đủ nhỏ, ta có

$\displaystyle \phi(t) < \phi(0)$ do $\displaystyle t\phi'(0)+ \Theta(t^2) < 0$

Tức là $\displaystyle f(x+td)<f(x)$ .

Nhận xét: Mệnh đề ngược lại chưa chắc đã đúng tức là nếu tồn tại $\displaystyle t>0$ để $\displaystyle f(x+td)<f(x)$ thì vẫn có thể $\displaystyle d^T\nabla f(x)\geq 0$ . Tuy nhiên, nếu $\displaystyle f(x+td)<f(x),\forall t\in(0,\delta)$ thì ta có

$\displaystyle \frac{f(x+td)-f(x)}{t}<0,\forall t\in(0,\delta)$ $\displaystyle \Rightarrow \lim_{t\rightarrow 0^+}\frac{f(x+td)-f(x)}{t} = d^T\nabla f(x) \leq 0$

Hệ quả: Nếu $\displaystyle \nabla f(x)\neq 0$ thì

$\displaystyle -\nabla f(x)$ là hướng làm giảm hàm mục tiêu tại $\displaystyle x$ .
$\displaystyle -A\nabla f(x)$ là hướng làm giảm hàm mục tiêu tại $\displaystyle x$ với $\displaystyle A$ là ma trận đối xứng, xác định dương bất kì.

Chứng minh (1): Rõ ràng $\displaystyle -\nabla f(x)^T\nabla f(x)=-\|\nabla f(x)\|_2^2<0$ nếu $\displaystyle \nabla f(x)\neq 0$ .

Chứng minh (2): Dễ thấy $\displaystyle -(A\nabla f(x))^T\nabla f(x)=-\nabla f(x)^TA\nabla f(x)<0$ .

Lưu ý:

Các phương pháp tối ưu sử dụng hướng $\displaystyle -\nabla f(x)$ làm hướng giảm hàm mục tiêu gọi là các phương pháp xuống đồi theo hướng đạo hàm (gradient descent) (do hướng $\displaystyle -\nabla f(x)$ là hướng làm giảm hàm mục tiêu nhanh nhất trong tất cả các hướng tại $\displaystyle x$ ).
Để so sánh các hướng làm giảm hàm mục tiêu, người ta thường chuẩn hóa các hướng này sao cho $\displaystyle \|d\|=1$ .
Ở bài sau, ta sẽ xem xét các phương pháp tối ưu hóa hàm mục tiêu dọc theo một hướng cho trước, còn gọi là tìm kiếm trên đường thẳng (line search).

Định nghĩa (tập ứng cử viên): Nếu trong các bước lặp, thuật toán tối ưu luôn duy trì một tập $\displaystyle X_t$ sao cho

$\displaystyle X_t\cap X^*\neq \emptyset$ nếu $\displaystyle X^*\neq \emptyset$

thì $\displaystyle X_t$ gọi là tập ứng cử viên (localizer) tại bước $\displaystyle t$ .

Nhận xét:

Rõ ràng, mục tiêu của các thuật toán tối ưu là sau một số bước lặp, lý tưởng nhất là ta có $\displaystyle X_t\subset X^*$ (lưu ý: theo định nghĩa thì tập ứng cử viên luôn khác rỗng nếu $\displaystyle X^*$ khác rỗng).
Nếu không được như vậy, thì thuật toán tối ưu phải đảm bảo
$\displaystyle d(X_t)=\sup_{x,y\in X_t}\|x-y\|\rightarrow 0$

Khi đó $\displaystyle d(X_t)$ có thể coi là cận trên của $\displaystyle \epsilon(t)$ vì

$\displaystyle \epsilon(t)=\inf_{x^*\in X^*}\|x_t-x^*\|\leq \|x_t-y^*\|\leq d(X_t)$

với $\displaystyle y^*\in X_t\cap X^*$ và với mọi $\displaystyle x_t\in X_t$ .
Tốc độ hội tụ của $\displaystyle \epsilon(t)$ về $\displaystyle 0$ ít nhất là bằng tốc độ hội tụ của $\displaystyle d(X_t)$ về 0.

Ví dụ: Thuật toán chia đôi (bisection) nổi tiếng dùng để tìm nghiệm $\displaystyle f(x)=0$ trên đoạn $\displaystyle [a,b]$ mà $\displaystyle f(a)f(b)<0$ (giá trị hàm liên tục trái dấu ở hai đầu đoạn thẳng):

Bước $\displaystyle 0$ : Gán $\displaystyle [a_0,b_0]=[a,b]$

Bước $\displaystyle t$ : Ta có tập ứng cử viên $\displaystyle [a_t,b_t]$ với $\displaystyle f(a_t)f(b_t)<0$ . Đặt

$\displaystyle c_t = \frac{a_t+b_t}{2}$

Nếu $\displaystyle f(c_t)=0$ thì thông báo nghiệm $\displaystyle x=c_t$ .

Nếu $\displaystyle f(a_t)f(c_t)<0$ gán $\displaystyle [a_{t+1},b_{t+1}]=[a_t,c_t]$ , ngược lại, gán $\displaystyle [a_{t+1},b_{t+1}]=[c_t,b_t]$ . Chuyển sang bước $\displaystyle t+1$ .

Nhận xét:

Tại mỗi bước lặp, vì $\displaystyle f(a_t)f(b_t)<0$ , phải tồn tại $\displaystyle x\in [a_t,b_t]=X_t$ sao cho $\displaystyle f(x)=0$ . Nghĩa là $\displaystyle X_t\cap X^*\neq\emptyset$ (nếu ta đặt $\displaystyle X^*=\{x:f(x)=0\}$ ).
Ta có $\displaystyle d(X_t)=b_t-a_t=(b_0-a_0)\left(\frac{1}{2}\right)^t$ , suy ra, tốc độ hội tụ của thuật toán chia đôi là tuyến tính.
Thuật toán trên có thể áp dụng để tìm cực tiểu của hàm khả vi liên tục nếu ta biết $\displaystyle f'(a)<0, f'(b)>0$ và $\displaystyle f'(x)=0$ chỉ tại duy nhất một điểm $\displaystyle x^*\in [a,b]$ . Ta áp dụng thuật toán trên với hàm $\displaystyle f'(x)$ .