Thuật toán tối ưu cần biết điều gì xảy ra khi đi từ $x$ sang $x+h$. Thay vì biến đổi trực tiếp một hàm nhiều biến, ta theo dõi giá trị mục tiêu dọc một đường đi có một tham số. Quy tắc chuỗi biến thao tác này thành một bài đạo hàm một biến.

1. Xấp xỉ nghiệm và khoảng cách

Với bài min $f(x)$ trên $D$, giả sử tồn tại nghiệm $x^{\star }$. Một điểm $x\in D$ xấp xỉ nghiệm theo khoảng cách với dung sai $\epsilon >0$ nếu

$$\parallel x-x^{\star }{\parallel }_2\le \epsilon .$$

Khoảng cách Euclid được tính bằng

$$\begin{array}{rl}\parallel x-y{\parallel }_2^2& =(x_1-y_1{)}^2+\cdots +(x_n-y_n{)}^2,\\ \parallel x-y{\parallel }_2& ={(\sum _{i=1}^n(x_i-y_i{)}^2)}^{1/2}.\end{array}$$

Một thuật toán lặp chọn $x_0$, rồi tạo $x_1,x_2,\dots$. Khi viết $x_k\to x^{\star }$, ta khẳng định khoảng cách đến nghiệm tiến về không, điều phải được chứng minh dưới giả thiết phù hợp, không tự có từ việc các giá trị mục tiêu giảm.

Vì chưa biết $x^{\star }$, tiêu chuẩn khoảng cách thường không kiểm trực tiếp được. Chuẩn gradient nhỏ là một tiêu chuẩn dừng khác. Không đồng nhất sai số nghiệm, sai số mục tiêu và chuẩn gradient nếu chưa có quan hệ định lượng giữa chúng.

2. Công thức một biến với điểm trung gian

Định lý giá trị trung bình cho

$$\begin{array}{rl}f(x+h)& =f(x)+f^{\prime }(x+{\theta }_{1}h)h,\\ & 0<{\theta }_1<1.\end{array}$$

Công thức đúng với cả $h>0$ và $h<0$, vì $x+{\theta }_{1}h$ luôn nằm giữa hai đầu. Nếu hàm thuộc $C^2$ trên một lân cận của đoạn, Taylor bậc hai cho

$$\begin{array}{rl}f(x+h)& =f(x)+f^{\prime }(x)h+\frac{1}{2}{f}^{″}(x+{\theta }_{2}h)h^2,\\ & 0<{\theta }_2<1.\end{array}$$

Hai điểm trung gian ${\theta }_1,{\theta }_2$ có thể khác nhau.

3. Quy tắc chuỗi một biến

Cho $f:\mathbb{R}\to \mathbb{R}$ và $g:\mathbb{R}\to \mathbb{R}$. Chuỗi ánh xạ là

$$x⟼f(x)⟼g(f(x)).$$

Nếu các hàm khả vi tại các điểm tương ứng,

$$(g\circ f{)}^{\prime }(x)=g^{\prime }(f(x))f^{\prime }(x).$$

Đạo hàm của hàm ngoài được lấy tại đầu ra của hàm trong. Bỏ vị trí đánh giá này là một lỗi ký hiệu có thể làm tính sai.

4. Hàm trong có nhiều thành phần

Cho $F:{\mathbb{R}}^n\to {\mathbb{R}}^m$ và $g:{\mathbb{R}}^m\to \mathbb{R}$. Viết

$$\begin{array}{rl}F(x)& =(F_1(x),\dots ,F_m(x)),\\ G(x)& =(g\circ F)(x)\\ & =g(F_1(x),\dots ,F_m(x)).\end{array}$$

Với hai thành phần của hàm trong, đạo hàm theo $x_i$ là

$$\frac{\partial G}{\partial x_i}(x)=\frac{\partial g}{\partial y_1}(F(x))\frac{\partial F_1}{\partial x_i}(x)+\frac{\partial g}{\partial y_2}(F(x))\frac{\partial F_2}{\partial x_i}(x).$$

Mỗi số hạng đi qua một nhánh trung gian. Cộng tất cả $m$ nhánh cho công thức tổng quát

$$\frac{\partial G}{\partial x_i}(x)=\sum _{j=1}^m\frac{\partial g}{\partial y_j}(F(x))\frac{\partial F_j}{\partial x_i}(x).$$

Không viết $\partial g/\partial x_i$ nếu $g$ thực sự nhận các biến $y_j$. Hàm hợp $G$ mới nhận biến $x_i$.

5. Đạo hàm dọc một đường cong

Cho đường cong khả vi $\phi :I\to {\mathbb{R}}^n$,

$$\phi (t)=({\phi }_1(t),\dots ,{\phi }_n(t)).$$

Hàm $f\circ \phi$ trả về mục tiêu tại từng vị trí trên đường đi. Khi $n=2$,

$$\frac{d}{dt}f(\phi (t))=f_{x_1}(\phi (t)){\phi }_1^{\prime }(t)+f_{x_2}(\phi (t)){\phi }_2^{\prime }(t).$$

Trong $n$ chiều, công thức là

$$\frac{d}{dt}f(\phi (t))=\sum _{i=1}^n{f}_{x_i}(\phi (t)){\phi }_i^{\prime }(t)=\mathrm{\nabla }f(\phi (t){)}^T{\phi }^{\prime }(t).$$

Gradient đo mức nhạy của mục tiêu với từng tọa độ, còn ${\phi }_i^{\prime }$ đo tốc độ thay đổi của tọa độ ấy. Tổng các đóng góp cho tốc độ thay đổi mục tiêu dọc đường.

6. Hạn chế lên đường thẳng

Cố định $x,h\in {\mathbb{R}}^n$ và đặt

$$\begin{array}{rl}\phi (t)& =x+th,\\ g(t)& =f(x+th).\end{array}$$

Các tọa độ của đường là $x_i+t{h}_i$ và đạo hàm của chúng bằng $h_i$. Do đó

$$g^{\prime }(t)=\sum _{i=1}^n{f}_{x_i}(x+th)h_i=\mathrm{\nabla }f(x+th{)}^{T}h.$$

Nếu $f\in C^2$, lấy đạo hàm lần nữa được

$$g^{″}(t)=\sum _{i=1}^n\sum _{j=1}^n{f}_{x_j{x}_i}(x+th)h_i{h}_j=h^T{\mathrm{\nabla }}^{2}f(x+th)h.$$

Để thấy rõ tổng kép, trong hai chiều nó gồm bốn số hạng:

$$g^{″}(t)=f_{x_1{x}_1}{h}_1^2+f_{x_2{x}_1}{h}_1{h}_2+f_{x_1{x}_2}{h}_2{h}_1+f_{x_2{x}_2}{h}_2^2.$$

Các đạo hàm trên đều được đánh giá tại $x+th$. Vì Hessian đối xứng, hai số hạng hỗn hợp có thể gộp. Ma trận $A$ được viết trong khai triển trên bảng chính là Hessian tại điểm dọc đường, không phải một ma trận hằng tùy ý.

7. Taylor nhiều biến

Áp dụng giá trị trung bình cho $g$ trên $[0,1]$:

$$\begin{array}{rl}g(1)& =g(0)+g^{\prime }({\theta }_1),\\ f(x+h)& =f(x)+\mathrm{\nabla }f(x+{\theta }_{1}h{)}^{T}h.\end{array}$$

Đây là công thức bậc một có điểm trung gian. Taylor bậc hai cho

$$f(x+h)=f(x)+\mathrm{\nabla }f(x{)}^{T}h+\frac{1}{2}{h}^T{\mathrm{\nabla }}^{2}f(x+{\theta }_{2}h)h.$$

Các đoạn đang xét phải nằm trong miền xác định, cùng các điều kiện khả vi liên tục tương ứng. Nếu thay $h$ bằng $td$,

$$f(x+td)=f(x)+t\mathrm{\nabla }f(x{)}^{T}d+\frac{t^2}{2}{d}^T{\mathrm{\nabla }}^{2}f(x+\theta td)d.$$

Số hạng bậc nhất tỷ lệ với $t$, còn số hạng bậc hai tỷ lệ với $t^2$. Vì vậy khi $t>0$ đủ nhỏ, dấu của tích $\mathrm{\nabla }f(x{)}^{T}d$ quyết định việc mục tiêu tăng hay giảm nếu tích này khác không.

8. Bài tập tự luyện

Bài tập: Tính dọc đường trước khi dùng ma trận

Cho $f(x,y)=x^2+2y^2$, điểm $(2,1)$ và hướng $h=(-4,-4)$. Khai triển trực tiếp $g(t)=f((2,1)+th)$ rồi so sánh $g^{\prime }(0)$ và $g^{″}(t)$ với công thức gradient, Hessian.

Lời giải

Khai triển được

$$\begin{array}{rl}g(t)& =(2-4t{)}^2+2(1-4t{)}^2\\ & =6-32t+48t^2,\\ g^{\prime }(0)& =-32,g^{″}(t)=96.\end{array}$$

Gradient tại $(2,1)$ là $(4,4{)}^T$, nên tích với $h$ bằng $-32$. Hessian là ma trận chéo với hai phần tử 2 và 4, nên $h^{T}Hh=2\cdot 16+4\cdot 16=96$. Hai cách khớp nhau.