Tìm hiểu thuật toán giải gần đúng phương trình bằng phương pháp Newton-Raphson

Các phương pháp bậc hai hội tụ tốt hơn so với các phương pháp bậc một và được sử dụng nhiều trong các phần mềm giải bài toán tối ưu. Tuy nhiên, trong một số ứng dụng như trong máy học, mạng truyền thông thì phương pháp bậc hai không được áp dụng nhiều như các phương pháp bậc một do khối lượng tính toán trong một lần cập nhật phức tạp. Ví dụ như phương pháp Newton phải tính nghịch đảo của đạo hàm bậc hai. Đồng thời, với các bài toán kích thước lớn, phương pháp bậc hai khó thực hiện tính toán phân tán và song song. Hai phần tiếp theo đây sẽ trình bày hai phương pháp bậc hai phổ biến là Newton và log barrier.

Xét bài toán tối ưu \[\begin{aligned}
\min_x f[x],\end{aligned}\] trong đó \[f[x]\] là hàm lồi và có đạo hàm bậc hai trên mọi điểm. Cập nhật theo phương pháp Newton có dạng sau: \[\begin{aligned}
x^{[k]} = x^{[k – 1]} – [\nabla^2 f[x^{[k – 1]}]]^{-1} \nabla f[x^{[k – 1]}]. \end{aligned}\]

Nhắc lại, cập nhật theo gradient descent là chọn điểm \[x^{[k]}\] để cực tiểu hàm toàn phương xấp xỉ hàm \[f[x]\] trong lân cận điểm \[x^{[k-1]}\]: \[\begin{aligned}
f[y] \approx f[x^{[k-1]}] + \nabla^Tf[x^{[k-1]}] [y – x] + \frac{1}{2t}\|y – x^{[k-1]}\|^2_2,\end{aligned}\] và \[\begin{aligned}
x^{[k]} = arg\min_y f[x^{[k-1]}] + \nabla^Tf[x^{[k-1]}] [y – x] + \frac{1}{2t}\|y – x^{[k-1]}\|^2_2.\end{aligned}\] Hàm toàn phương trong phương pháp Newton là xấp xỉ Taylor, tốt hơn trong GD: \[\begin{aligned}
f[y] \approx f[x^{[k-1]}] + \nabla^Tf[x^{[k-1]}] [y – x] + \frac{1}{2}[y-x^{[k-1]}]^T \nabla^2 f[x^{[k-1]}][y-x^{[k-1]}],\end{aligned}\] do đó, \[\begin{aligned}
x^{[k]} = arg\min_y f[x^{[k-1]}] + \nabla^Tf[x^{[k-1]}] [y – x] + \frac{1}{2}[y-x^{[k-1]}]^T \nabla^2 f[x^{[k-1]}][y-x^{[k-1]}].\end{aligned}\]

Ví dụ áp dụng phương pháp GD và Newton để tìm cực tiểu hàm số: \[\begin{aligned}
f[x_1, x_2] = \frac{10x_1^2 + x_2^2}{2} + 5\log[1 + e^{-x_1-x_2}].\end{aligned}\] Gradient và Hessian được cho bởi:

\[\begin{aligned} \nabla f[x_1, x_2] = \begin{bmatrix} 10x_1 – \frac{5e^{-x_1-x_2}}{1 + e^{-x_1-x_2}}\\ x_2 – \frac{5e^{-x_1-x_2}}{1 + e^{-x_1-x_2}} \end{bmatrix} \qquad \nabla^2 f[x_1, x_2] = \begin{bmatrix} 10 + \frac{e^{-x_1-x_2}}{[1 + e^{-x_1-x_2}]^2} & \frac{e^{-x_1-x_2}}{[1 + e^{-x_1-x_2}]^2}\\ \frac{e^{-x_1-x_2}}{[1 + e^{-x_1-x_2}]^2} & 1 + \frac{e^{-x_1-x_2}}{[1 + e^{-x_1-x_2}]^2}

\end{bmatrix} \end{aligned}\]

Hình 1 cho thấy phương pháp Newton có số vòng lặp nhỏ hơn GD rất nhiều. Đặc biệt tìm cực tiểu hàm toàn phương, phương pháp Newton hội tụ chỉ trong 1 bước lặp.

Lưu ý là phương pháp Newton thuần túy không dùng step size. Trong thực tế, ta có thể thực hiện cập nhật Newton với step size:\[\begin{aligned}
x^{[k]} = x^{[k – 1]} – t_k[\nabla^2 f[x^{[k – 1]}]]^{-1} \nabla f[x^{[k – 1]}], \end{aligned}\]trong đó step size \[t_k\] có thể được xác định bằng backtracking line search.

Bạn đọc có thể viết chương trình áp dụng phương pháp Newton cho linear regression hay logistic regression dễ dàng dựa theo những code Python ví dụ đã trình bày trước đây.

Một ưu điểm quan trọng của phương pháp Newton là cập nhật bất biến với biến đổi tuyến tính.

Giả sử ma trận \[A \in \mathbb{R}^{n \times n}\] có tồn tại ma trận nghịch đảo. Đặt \[g[x]=f[Ax]\] và \[y = Ax\]. Ta có \[\begin{aligned}
\nabla g[x] = A^T \nabla f[y]; \qquad \nabla^2 g[x] = A^T \nabla^2 f[y] A; \end{aligned}\]

Cập nhật Newton tại \[x\] để tìm cực tiểu hàm \[g[x]\] có dạng:

\[\begin{aligned} x^{[k]} &= x^{[k – 1]} – [\nabla^2 g[x^{[k – 1]}]]^{-1} \nabla g[x^{[k – 1]}]\\ &= x^{[k – 1]} – A^{-1} [\nabla^2 f[y]]^{-1}[A^{T}]^{-1} A^T \nabla f[y] \\

& = x^{[k – 1]} – A^{-1} [\nabla^2 f[y]]^{-1} \nabla f[y]\end{aligned}\]

Vì vậy \[\begin{aligned}
Ax^{[k]} = Ax^{[k – 1]} – [\nabla^2 f[y]]^{-1} \nabla f[y],\end{aligned}\] Chính là cập nhật Newton để tìm cực tiểu hàm \[f[Ax]\].

Tính chất này không có trong phương pháp gradient descent. Ví dụ như trong bài toán linear regression \[\|Ax-b\|_2^2\], trong đó ma trận \[A^TA\] là ill-conditioned, phương pháp gradient descent rất chậm. Muốn cho phương pháp gradient descent hội tụ nhanh, ta cần scale lại dữ liệu trước khi huấn luyện.

Ghi chú: Một ma trận là ill-conditioned nếu \[\frac{\textrm{|trị đặc trưng lớn nhất|}}{\textrm{|trị đặc trưng nhỏ nhất|}}\] có giá trị lớn, ví dụ

\[\begin{bmatrix} 100 & 0\\ 0 & 1

\end{bmatrix}\]

Tài liệu tham khảo:

• Stephen P. Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
• Convex optimization lectures. Available at www.stat.cmu.edu/\[\sim\]ryantibs/convexopt/.