4. Thuật toán giảm đạo hàm (Gradient Descent) copy

Xét hàm số $f: \mathbb{R}^n \rightarrow \mathbb{R}$ và bài toán tối ưu $\min_x f(x)$.

Giả sử nghiệm tối ưu của bài toán trên đạt được tại $x^*$ là $f(x^*) = f^* = min_x f(x)$

Thuật toán Gradient Descent giúp ta tính gần đúng giá trị $x^*$.

• Bước 1: Chọn giá trị khởi tạo $x_0 \in \mathbb{R}^n$.
• Bước 2: Thực hiện dãy lặp: $$x^{(k)} = x^{(k-1)} + \alpha_k \nabla f(x^{(k-1)}), \quad k = 1, 2, 3,...$$ Trong đó, $\alpha_k$ là bước nhảy của thuật toán, có thể thay đổi theo từng bước hoặc cố định tùy yêu cầu.

Giả sử $f$ lồi và khả vi, $\nabla f(x)$ liên tục Lipschitz với hằng số $L > 0$, nghĩa là:

Khi đó, với bước nhảy $\alpha < L$ cố định, sai số tại mỗi bước nhảy được đánh giá bởi công thức:

▸ VÍ DỤ

Cho hàm $f(x) = x^2$. Hãy áp dụng 3 bước đầu của thuật toán Gradient Descent với $x_0 = 4$ và bước nhảy $\alpha = 0.25$

Có $f'(x) = 2x$

Công thức lặp: $x^{(k)} = x^{(k-1)} - \alpha \cdot 2x^{(k-1)}$

Ta kẻ bảng cho dễ quan sát

Vậy sau 3 lần lặp, giá trị xấp xỉ của $x^*$ là $0.5$.