Bỏ qua

Chương 56: Tối ưu nhiều biến và ràng buộc

Câu hỏi mở đầu

Ta đã có đủ công cụ: đạo hàm, xác suất, vector, ma trận. Giờ dùng chúng để quyết định: khi muốn làm tốt nhất một điều mà bị ràng buộc bởi nguồn lực có hạn, chọn thế nào?

Xuống núi trong sương mù

Một người lạc trên sườn đồi giữa sương mù dày. Họ muốn xuống đáy thung lũng nhưng không nhìn thấy gì, chỉ cảm nhận được độ dốc dưới chân. Nên bước về hướng nào?

Mặt đất là một hàm hai biến (function of two variables): tại vị trí \((x; y)\), độ cao là \(z = f(x; y)\). Bản đồ địa hình vẽ hàm ấy trên giấy bằng các đường mức (level curve): mỗi đường gồm những điểm có cùng một độ cao, \(f(x; y) = c\), như các đường cong trong mặt phẳng tọa độ của Chương 23. Một địa hình ba chiều thành một bức tranh hai chiều, và hàm \(f(x; y) = x^2 + 3y^2\), một cái bát dài, có các đường mức là những đường bầu dục lồng nhau.

Tại một điểm, người trong sương mù có thể thử hai việc đơn giản: bước một chút theo hướng đông để xem độ cao đổi bao nhiêu, rồi bước một chút theo hướng bắc. Mỗi phép thử là một đạo hàm một biến như ở Chương 34, với biến kia giữ nguyên, và gọi là một đạo hàm riêng (partial derivative). Với \(f = x^2 + 3y^2\) tại \((1; 1)\), giữ \(y\) thì \(f\) thay đổi như \(x^2 + 3\), có đạo hàm \(2x = 2\); giữ \(x\) thì \(f\) thay đổi như \(1 + 3y^2\), có đạo hàm \(6y = 6\). Hai con số ghép thành vector \((2; 6)\), gọi là gradient (gradient) của \(f\) tại \((1; 1)\).

Điều bất ngờ là hai phép thử theo hai trục đã đủ cho mọi hướng. Theo xấp xỉ tuyến tính của Chương 34, áp dụng cho từng biến,

\[ f(1 + h; 1 + k) \approx 4 + 2h + 6k = 4 + (2; 6) \cdot (h; k), \]

và bạn có thể kiểm tra: \(f(1 + h; 1 + k) = 4 + 2h + 6k + h^2 + 3k^2\), phần thừa rất nhỏ khi \(h\), \(k\) nhỏ. Bước đi một đoạn \((h; k)\) thì độ cao đổi xấp xỉ bằng tích vô hướng của gradient với bước đi (Chương 49). Trong mọi bước cùng độ dài, tích vô hướng ấy lớn nhất khi bước cùng hướng với \((2; 6)\), nhỏ nhất khi ngược hướng, và bằng 0 khi vuông góc. Vậy gradient chỉ hướng dốc lên nhất, ngược gradient là hướng dốc xuống nhất, và hướng vuông góc với gradient là hướng đi ngang, dọc theo đường mức.

Các đường mức hình bầu dục của x bình phương cộng ba y bình phương và các mũi tên gradient vuông góc với chúng
Bản đồ đường mức của \(f = x^2 + 3y^2\). Tại mỗi điểm, gradient (mũi tên cam) vuông góc với đường mức đi qua điểm ấy và chỉ hướng lên dốc nhất; nét đứt tại \((1; 1)\) là hướng đi ngang, \((3; -1)\).

Người trong sương mù vì thế có một chiến lược: đo gradient dưới chân, bước một bước nhỏ ngược hướng gradient, rồi lặp lại. Đó là hạ gradient (gradient descent), cách mà máy tính dùng để huấn luyện mạng nơ-ron (Chương 24), nơi \(f\) đo mức sai của mạng và có hàng triệu biến thay cho hai.

Nhưng thường ta không được đi tùy ý. Muốn rào một mảnh đất hình chữ nhật có diện tích lớn nhất, hai cạnh \(x\), \(y\) không được chọn tự do: tổng \(x + y\) bị giới hạn bởi lượng lưới có sẵn, như bài hàng rào của Chương 28. Một điều kiện như thế, mà mọi lựa chọn phải thỏa, gọi là một ràng buộc (constraint). Ta chỉ được đi trên một con đường, và câu hỏi thành: điểm nào trên con đường ấy cao nhất? Tại điểm cao nhất, con đường không thể cắt ngang một đường mức, vì nếu cắt thì đi tiếp một chút theo đường sẽ lên cao hơn. Con đường chỉ chạm vào đường mức, tức tiếp xúc với nó.

Vì sao cấu trúc này phải xuất hiện, dù chưa ai đặt tên cho nó? Vì khi một đại lượng phụ thuộc vào nhiều lựa chọn, thông tin cục bộ duy nhất ta có là nó thay đổi thế nào khi từng lựa chọn thay đổi một chút, và theo xấp xỉ tuyến tính, những con số ấy tự ghép thành một vector trả lời câu hỏi "hướng nào lên". Tương tự, tại một điểm tối ưu có ràng buộc, mọi bước nhỏ được phép phải không làm \(f\) tăng ở bậc nhất, nên gradient của \(f\) phải vuông góc với mọi hướng được phép, tức cùng phương với gradient của điều kiện ràng buộc. Cả hai cấu trúc đều bị ép ra bởi hình học của xấp xỉ bậc nhất.

Ký hiệu

Cho hàm hai biến \(f(x; y)\) và một điểm \((a; b)\).

  • Đạo hàm riêng theo \(x\), viết \(\frac{\partial f}{\partial x}(a; b)\) hay \(f_x(a; b)\), là đạo hàm của hàm một biến \(x \mapsto f(x; b)\) tại \(a\); đạo hàm riêng theo \(y\) định nghĩa tương tự, giữ \(x = a\).
  • Gradient là vector \(\nabla f(a; b) = \big(f_x(a; b); f_y(a; b)\big)\), đọc là "nabla \(f\)".
  • Với vector đơn vị \(u = (u_1; u_2)\), đạo hàm theo hướng (directional derivative) \(D_u f(a; b)\) là tốc độ thay đổi của \(f\) khi đi từ \((a; b)\) theo hướng \(u\), tức đạo hàm tại \(t = 0\) của hàm một biến \(t \mapsto f(a + tu_1; b + tu_2)\). Với những hàm trơn gặp trong sách, \(D_u f = \nabla f \cdot u\).
  • Điểm \((a; b)\) bên trong miền mà \(\nabla f(a; b) = (0; 0)\) gọi là điểm tới hạn, như ở Chương 36; đó là các ứng viên cho cực trị.
  • Hạ gradient với bước học (learning rate) \(\eta > 0\) là phép lặp (Chương 24) \(p_{k+1} = p_k - \eta \nabla f(p_k)\).

Một ràng buộc có thể là một đẳng thức \(g(x; y) = c\) hay một bất đẳng thức. Hàm cần làm lớn nhất hay nhỏ nhất gọi là hàm mục tiêu (objective function). Điều kiện tiếp xúc ở mục trước viết thành

\[ \nabla f = \lambda \nabla g \]

với một số \(\lambda\) nào đó, gọi là nhân tử Lagrange (Lagrange multiplier), theo tên nhà toán học Joseph-Louis Lagrange. Khi hàm mục tiêu và mọi ràng buộc đều tuyến tính, các ràng buộc bất đẳng thức cắt ra một miền đa giác, gọi là miền chấp nhận được (feasible region), và bài toán gọi là quy hoạch tuyến tính (linear programming).

Làm bằng tay

Ví dụ 1 (gradient và đạo hàm theo hướng). Với \(f = x^2 + 3y^2\), \(f_x = 2x\) và \(f_y = 6y\), nên \(\nabla f(1; 1) = (2; 6)\). Theo hướng \(u = \left(\frac35; \frac45\right)\), độ dốc là \(D_u f = (2; 6) \cdot \left(\frac35; \frac45\right) = \frac65 + \frac{24}{5} = 6\). Độ dốc lớn nhất là \(\lvert \nabla f \rvert = \sqrt{4 + 36} = \sqrt{40} \approx 6{,}32\), theo hướng \(\frac{(2; 6)}{\sqrt{40}}\). Hướng \((3; -1)\) vuông góc với gradient, vì \((2; 6) \cdot (3; -1) = 0\): đó là hướng của đường mức \(x^2 + 3y^2 = 4\) tại \((1; 1)\).

Ví dụ 2 (hạ gradient). Với \(f = x^2 + 3y^2\) và bước học \(0{,}1\), xuất phát từ \((1; 1)\):

\[ (1; 1) - 0{,}1 \cdot (2; 6) = (0{,}8; 0{,}4), \qquad (0{,}8; 0{,}4) - 0{,}1 \cdot (1{,}6; 2{,}4) = (0{,}64; 0{,}16), \]

rồi \((0{,}512; 0{,}064)\), và cứ thế. Tổng quát, mỗi bước nhân \(x\) với \(1 - 0{,}1 \cdot 2 = 0{,}8\) và nhân \(y\) với \(1 - 0{,}1 \cdot 6 = 0{,}4\), nên sau \(k\) bước điểm là \((0{,}8^k; 0{,}4^k)\), tiến về đáy \((0; 0)\). Với bước học \(0{,}35\), \(y\) bị nhân với \(1 - 0{,}35 \cdot 6 = -1{,}1\) mỗi bước: điểm nhảy qua nhảy lại hai bên trục hoành và ngày càng xa. Tổng quát, cần \(\lvert 1 - 6\eta \rvert < 1\) và \(\lvert 1 - 2\eta \rvert < 1\), tức \(0 < \eta < \frac13\) (Mệnh đề 4). Đây là phép lặp \(x \mapsto rx\) của Chương 24: hội tụ khi và chỉ khi \(\lvert r \rvert < 1\).

Đường đi của hạ gradient với bước nhỏ tiến về đáy, với bước lớn nhảy qua lại và văng ra
Hạ gradient trên \(x^2 + 3y^2\) từ \((1; 1)\). Trái: bước học \(0{,}1\), tám bước tiến dần về đáy (ngôi sao). Phải: bước học \(0{,}35\), theo hướng dốc hơn điểm bị hất qua lại và văng ra xa.

Bàn tương tác: hạ gradient trên bản đồ đường mức

Bàn mở ra như nửa trái của hình trên: hàm \(x^2 + 3y^2\), bước học \(0{,}1\), tám bước từ \((1; 1)\). Hãy tăng dần bước học. Từ đâu điểm bắt đầu nhảy qua lại, và từ đâu nó văng ra? Rồi thử cái bát tròn \(x^2 + y^2\) và địa hình có hai hố: kéo điểm xuất phát qua lại, điểm dừng ở hố nào?

Bàn tương tác cần trình duyệt bật JavaScript.

Điều bạn vừa thấy

Trên một cái bát, mỗi bước nhân từng tọa độ với một số cố định: với \(x^2 + 3y^2\) là \(1 - 2\eta\) theo trục hoành và \(1 - 6\eta\) theo trục tung. Số nhân dương và nhỏ hơn 1 thì điểm trượt dần vào đáy; âm mà trị tuyệt đối vẫn nhỏ hơn 1 thì điểm nhảy qua lại hai bên trục trong lúc tiến vào; trị tuyệt đối lớn hơn 1 thì điểm văng ra. Trục mà cái bát dốc hơn hỏng trước, nên với \(x^2 + 3y^2\) chỉ những bước học nhỏ hơn \(\frac13\) mới đưa điểm về đáy từ mọi chỗ xuất phát, còn với cái bát tròn thì mọi bước học nhỏ hơn 1 đều được; riêng bước học \(0{,}5\) đưa điểm tới đáy chỉ sau một bước. Với địa hình hai hố và bước học nhỏ, điểm dừng ở hố nằm cùng phía với chỗ xuất phát, dù hố bên kia sâu hơn: hạ gradient chỉ biết độ dốc dưới chân.

Ví dụ 3 (một ràng buộc). Tìm \(x, y > 0\) với \(x + y = 10\) sao cho tích \(xy\) lớn nhất. Cách thứ nhất, thế \(y = 10 - x\): \(x(10 - x)\) là một parabol quay xuống, lớn nhất tại đỉnh \(x = 5\) (Chương 28), cho \(xy = 25\). Cách thứ hai, điều kiện Lagrange: với \(f = xy\) và \(g = x + y\), \(\nabla f = (y; x)\) và \(\nabla g = (1; 1)\), nên \((y; x) = \lambda(1; 1)\), tức \(x = y = \lambda\); cùng với \(x + y = 10\) được \(x = y = 5\) và \(\lambda = 5\). Hình dưới cho thấy đường mức \(xy = 25\) chạm đường \(x + y = 10\) đúng tại \((5; 5)\). Mảnh đất rào bằng lưới dài 40 m cũng vậy: nửa chu vi 20 m, và hình vuông \(10 \times 10\) cho diện tích lớn nhất, như Chương 28 đã tìm.

Các hyperbol xy bằng hằng số và đường thẳng x + y = 10 tiếp xúc hyperbol xy = 25 tại (5; 5)
Các đường mức \(xy = c\) (xanh) và đường ràng buộc \(x + y = 10\) (cam). Đường \(xy = 36\) không chạm tới ràng buộc; đường \(xy = 16\) cắt ngang nó, nên đi dọc ràng buộc còn lên cao được; đường \(xy = 25\) vừa chạm tại \((5; 5)\), nơi hai gradient cùng phương.

Con số \(\lambda = 5\) có ý nghĩa riêng. Nếu nguồn lực tăng từ 10 lên 11, giá trị lớn nhất tăng từ 25 lên \(5{,}5^2 = 30{,}25\), tức tăng \(5{,}25\), xấp xỉ \(\lambda\). Tổng quát, với \(x + y = c\) giá trị lớn nhất là \(\frac{c^2}{4}\), có đạo hàm \(\frac{c}{2}\), đúng bằng \(\lambda\) tại \(c\). Nhân tử Lagrange là giá của thêm một đơn vị nguồn lực: nó cho biết đáng trả bao nhiêu để nới ràng buộc.

Bàn tương tác: đường mức tiếp xúc ràng buộc

Kéo điểm dọc đường ràng buộc \(x + y = c\) và nhìn đường mức của \(xy\) đi qua nó. Khi nào đường mức cắt ngang ràng buộc, khi nào chỉ chạm vào? Ở chỗ chạm, hai gradient nằm thế nào? Đổi nguồn lực \(c\): giá trị lớn nhất và \(\lambda\) thay đổi ra sao?

Bàn tương tác cần trình duyệt bật JavaScript.

Điều bạn vừa thấy

Chừng nào đường mức còn cắt ngang ràng buộc, đoạn ràng buộc nằm giữa hai giao điểm cho \(xy\) lớn hơn, nên vẫn còn đi lên được. Đường mức chỉ chạm ràng buộc tại đúng một điểm, \(\left(\frac{c}{2}; \frac{c}{2}\right)\), và đó là điểm cao nhất; ở đó \(\nabla f\) và \(\nabla g\) cùng phương, với \(\lambda = \frac{c}{2}\). Nới ràng buộc thêm 1 đơn vị thì giá trị lớn nhất \(\frac{c^2}{4}\) tăng \(\frac{c}{2} + \frac14\), tức hơn \(\lambda\) đúng \(\frac14\), với mọi \(c\) chứ không riêng \(c = 10\).

Ví dụ 4 (quy hoạch tuyến tính). Một xưởng (số liệu giả định) làm hai loại sản phẩm theo lô: mỗi lô A lãi 3 triệu đồng, cần 1 ngày công và 2 tấn nguyên liệu; mỗi lô B lãi 2 triệu đồng, cần 1 ngày công và 1 tấn. Mỗi tuần có 4 ngày công và 6 tấn nguyên liệu, và lô có thể làm dở dang (số lô không cần nguyên). Với \(x\) lô A và \(y\) lô B, bài toán là

\[ \text{làm lớn nhất } 3x + 2y \quad \text{với} \quad x + y \leq 4, \quad 2x + y \leq 6, \quad x \geq 0, \quad y \geq 0. \]

Miền chấp nhận được là tứ giác với bốn đỉnh \((0; 0)\), \((3; 0)\), \((2; 2)\), \((0; 4)\); đỉnh \((2; 2)\) là giao của \(x + y = 4\) và \(2x + y = 6\). Các đường mức \(3x + 2y = c\) là những đường thẳng song song; đẩy đường ấy về phía \(c\) tăng, chỗ cuối cùng nó còn chạm miền là một đỉnh. Tính tại bốn đỉnh: \(0\), \(9\), \(10\), \(8\). Vậy xưởng nên làm 2 lô A và 2 lô B, lãi 10 triệu đồng. Thêm một ngày công (ràng buộc thành \(x + y \leq 5\)) thì đỉnh tối ưu dời tới \((1; 4)\) và lãi thành 11; thêm một tấn nguyên liệu thì đỉnh dời tới \((3; 1)\) và lãi cũng thành 11. Mỗi nguồn lực đáng giá 1 triệu đồng cho một đơn vị thêm, cùng ý nghĩa với nhân tử Lagrange.

Miền đa giác với bốn đỉnh và các đường mức song song của hàm lãi
Miền chấp nhận được (xanh) và các đường mức \(3x + 2y = 4, 8, 10\) (cam). Đường \(3x + 2y = 10\) chỉ còn chạm miền tại đỉnh \((2; 2)\): lãi lớn nhất.

Bàn tương tác: quy hoạch tuyến tính

Bàn mở ra với xưởng của Ví dụ 4: 4 ngày công và 6 tấn nguyên liệu mỗi tuần. Tăng dần mức lãi \(c\) để đẩy đường mức \(3x + 2y = c\) đi qua miền. Nó rời khỏi miền ở đâu? Rồi đổi số ngày công và số tấn: đỉnh tốt nhất dời đi thế nào, và thêm một đơn vị nguồn lực nào thì có lợi?

Bàn tương tác cần trình duyệt bật JavaScript.

Điều bạn vừa thấy

Các đường mức của hàm lãi song song với nhau. Đẩy đường mức về phía lãi tăng, phần của nó nằm trong miền ngắn dần rồi chỉ còn một đỉnh, đúng đỉnh có lãi lớn nhất trong bảng. Đổi nguồn lực thì miền đổi hình và đỉnh tốt nhất dời theo, nhưng nó vẫn là một đỉnh. Một nguồn lực chỉ đáng mua thêm khi nó đang giới hạn phương án tốt nhất: với 4 ngày công và 6 tấn, thêm một đơn vị của thứ nào cũng tăng lãi 1 triệu đồng; còn khi nguyên liệu đã thừa so với số ngày công (chẳng hạn 3 ngày công và 8 tấn), thêm nguyên liệu không tăng lãi chút nào.

Ví dụ 5 (gradient bằng 0 mà không là cực trị). Với \(f = x^2 - y^2\), \(\nabla f = (2x; -2y)\) bằng \((0; 0)\) tại gốc. Nhưng dọc trục hoành, \(f = x^2\) có cực tiểu tại gốc; dọc trục tung, \(f = -y^2\) có cực đại tại gốc. Gốc không phải cực trị: nó là một điểm yên ngựa (saddle point), thấp nhất theo một hướng và cao nhất theo hướng kia, như chỗ ngồi trên lưng ngựa hay một con đèo giữa hai đỉnh núi.

Mặt yên ngựa z = x bình phương trừ y bình phương
Mặt \(z = x^2 - y^2\): gradient bằng 0 tại gốc, nhưng dọc trục \(x\) (cam) gốc là đáy, dọc trục \(y\) (xanh) gốc là đỉnh.

Ranh giới

Gradient bằng 0 chưa phải cực trị. Như với hàm một biến ở Chương 36, điểm tới hạn chỉ là ứng viên: nó có thể là cực tiểu, cực đại hay điểm yên ngựa (Ví dụ 5). Kiểm tra theo từng đường thẳng qua điểm ấy cũng chưa đủ (bài C3).

Bước học phải vừa phải. Bước quá lớn làm hạ gradient dao động hay văng ra (Ví dụ 2); bước quá nhỏ thì đi mãi mới tới. Với \(x^2 + 3y^2\), giới hạn \(\frac13\) do hướng dốc nhất quyết định: cái bát càng hẹp theo một hướng, bước càng phải nhỏ.

Hạ gradient có thể mắc kẹt. Hạ gradient chỉ dùng thông tin cục bộ, nên nó dừng ở đáy của cái hố gần nhất. Hàm một biến \(f(x) = x^4 - 4x^2 + x\) có hai cực tiểu địa phương, gần \(x \approx 1{,}35\) (giá trị khoảng \(-2{,}62\)) và gần \(x \approx -1{,}47\) (giá trị khoảng \(-5{,}44\), giá trị nhỏ nhất). Xuất phát từ \(x = 1\), hạ gradient đi tới cực tiểu thứ nhất và dừng ở đó, không bao giờ biết có một đáy sâu hơn ở phía bên kia (bài B10). Tìm tối ưu toàn cục của một hàm nhiều hố nói chung là việc khó.

Điều kiện Lagrange là điều kiện cần. Nó lọc ra các ứng viên, không cho biết ứng viên nào là lớn nhất hay nhỏ nhất; trên đường tròn, cùng một điều kiện cho cả điểm cao nhất lẫn điểm thấp nhất (bài C2). Nó cũng cần \(\nabla g \neq 0\) tại điểm đang xét.

Quy hoạch tuyến tính có thể không có tối ưu. Nếu miền chấp nhận được không bị chặn, như chỉ có \(x \geq 0\), \(y \geq 0\), thì \(3x + 2y\) lớn tùy ý. Và nếu số lô bắt buộc phải nguyên, bài toán khó hơn hẳn: tối ưu thường không nằm ở một đỉnh có tọa độ nguyên, và làm tròn đỉnh tối ưu có thể ra một điểm không chấp nhận được hoặc không tốt nhất.

Phát biểu chặt chẽ

Định nghĩa 1. Cho \(f\) xác định gần \((a; b)\). Đạo hàm riêng \(f_x(a; b)\) là đạo hàm tại \(a\) của \(x \mapsto f(x; b)\), và \(f_y(a; b)\) là đạo hàm tại \(b\) của \(y \mapsto f(a; y)\), khi các đạo hàm ấy tồn tại. Gradient là \(\nabla f(a; b) = \big(f_x(a; b); f_y(a; b)\big)\). Với \(u\) là vector đơn vị, đạo hàm theo hướng \(D_u f(a; b)\) là đạo hàm tại \(t = 0\) của \(t \mapsto f(a + tu_1; b + tu_2)\).

Định lý 2 (điều kiện cần của cực trị). Nếu \(f\) đạt cực trị địa phương tại một điểm \((a; b)\) nằm bên trong miền, và hai đạo hàm riêng tồn tại tại đó, thì \(\nabla f(a; b) = (0; 0)\).

Chứng minh. Hàm một biến \(h(t) = f(a + t; b)\) đạt cực trị địa phương tại \(t = 0\), vì các giá trị của nó là giá trị của \(f\) trên một đoạn thẳng qua \((a; b)\). Theo định lý Fermat (Định lý 2 của Chương 36), \(h'(0) = 0\), mà \(h'(0) = f_x(a; b)\). Lập luận tương tự với \(t \mapsto f(a; b + t)\) cho \(f_y(a; b) = 0\). \(\square\)

Định lý 3 (hướng dốc nhất). Giả sử \(D_u f(a; b) = \nabla f(a; b) \cdot u\) với mọi vector đơn vị \(u\) (điều này đúng với mọi hàm trơn, và ta thừa nhận nó). Nếu \(\nabla f(a; b) \neq 0\) thì

\[ -\lvert \nabla f(a; b) \rvert \leq D_u f(a; b) \leq \lvert \nabla f(a; b) \rvert, \]

dấu bằng bên phải xảy ra khi và chỉ khi \(u = \frac{\nabla f(a; b)}{\lvert \nabla f(a; b) \rvert}\), bên trái khi và chỉ khi \(u = -\frac{\nabla f(a; b)}{\lvert \nabla f(a; b) \rvert}\); và \(D_u f(a; b) = 0\) khi và chỉ khi \(u\) vuông góc với gradient.

Chứng minh. Theo bất đẳng thức Cauchy–Schwarz (Định lý 4 của Chương 49), \(\lvert \nabla f \cdot u \rvert \leq \lvert \nabla f \rvert \lvert u \rvert = \lvert \nabla f \rvert\), với dấu bằng khi và chỉ khi \(u\) là một bội của \(\nabla f\). Vì \(\lvert u \rvert = 1\), hai bội có thể là \(\pm \frac{\nabla f}{\lvert \nabla f \rvert}\), cho \(D_u f = \pm \lvert \nabla f \rvert\). Khẳng định cuối là định nghĩa của vuông góc (Chương 49). \(\square\)

Nói riêng, dọc một đường mức \(f\) không đổi, nên đạo hàm theo hướng tiếp tuyến của đường mức bằng 0: gradient vuông góc với đường mức.

Mệnh đề 4 (hạ gradient trên một cái bát). Cho \(f(x; y) = ax^2 + cy^2\) với \(a, c > 0\) và bước học \(\eta > 0\). Hạ gradient từ \((x_0; y_0)\) cho \(p_k = \big((1 - 2a\eta)^k x_0; (1 - 2c\eta)^k y_0\big)\). Nó tiến về cực tiểu \((0; 0)\) từ mọi điểm xuất phát khi và chỉ khi \(\eta < \frac{1}{\max(a, c)}\).

Chứng minh. \(\nabla f = (2ax; 2cy)\), nên một bước biến \((x; y)\) thành \(\big((1 - 2a\eta)x; (1 - 2c\eta)y\big)\); quy nạp cho công thức của \(p_k\). Theo Mệnh đề 2 của Chương 31, \(r^k \to 0\) khi \(\lvert r \rvert < 1\); còn khi \(\lvert r \rvert \geq 1\) thì \(\lvert r^k x_0 \rvert \geq \lvert x_0 \rvert\), không tiến về 0 nếu \(x_0 \neq 0\). Vậy cần và đủ là \(\lvert 1 - 2a\eta \rvert < 1\) và \(\lvert 1 - 2c\eta \rvert < 1\), tức \(0 < \eta < \frac1a\) và \(\eta < \frac1c\). \(\square\)

Định lý 5 (nhân tử Lagrange; phát biểu). Cho \(f\), \(g\) trơn. Nếu trên đường \(g(x; y) = c\), hàm \(f\) đạt cực trị địa phương tại \(p\) và \(\nabla g(p) \neq 0\), thì có một số \(\lambda\) với \(\nabla f(p) = \lambda \nabla g(p)\).

Giải thích hình học, không phải chứng minh đầy đủ: gần \(p\), đường ràng buộc là một đường cong có hướng tiếp tuyến \(u\) vuông góc với \(\nabla g(p)\) (đường ràng buộc là một đường mức của \(g\)). Tại một cực trị trên đường ấy, đạo hàm của \(f\) theo hướng \(u\) phải bằng 0, như Định lý 2 cho một biến, nên \(\nabla f(p) \cdot u = 0\). Trong mặt phẳng, hai vector cùng vuông góc với một vector khác 0 thì cùng phương, nên \(\nabla f(p)\) là một bội của \(\nabla g(p)\).

Mệnh đề 6 (tối ưu tuyến tính nằm ở đỉnh). Một hàm tuyến tính \(f(x; y) = \alpha x + \beta y\) trên một đa giác lồi (mọi đoạn thẳng nối hai điểm của nó nằm trọn trong nó) đạt giá trị lớn nhất tại một đỉnh.

Chứng minh. Trên một đoạn thẳng \(\{(1 - s)A + sB : 0 \leq s \leq 1\}\), hàm \(f\) có giá trị \((1 - s)f(A) + sf(B)\), không vượt quá \(\max(f(A), f(B))\). Với một điểm \(P\) bất kỳ của đa giác, đường thẳng qua \(P\) song song với một cạnh cắt biên tại hai điểm \(A\), \(B\) với \(P\) nằm giữa chúng, nên \(f(P) \leq \max(f(A), f(B))\). Mỗi điểm \(A\), \(B\) nằm trên một cạnh, và trên mỗi cạnh \(f\) không vượt quá giá trị tại một đầu mút của cạnh, tức một đỉnh. Vậy \(f(P)\) không vượt quá giá trị lớn nhất tại các đỉnh. \(\square\)

Sợi chỉ

  • S4. Cục bộ và toàn cục. Gradient là thông tin thuần cục bộ: nó chỉ nói hướng nào lên dốc ngay dưới chân. Hạ gradient nhờ nó mà đi xuống, nhưng cũng vì nó mà mắc kẹt ở đáy hố gần nhất; biết một điểm là tốt nhất trên toàn miền cần thêm cấu trúc, như cái bát lồi của Mệnh đề 4 hay đa giác lồi của Mệnh đề 6, giống hàm lồi ở Chương 36.
  • S6. Biểu diễn khác nhau của cùng một cấu trúc. Một địa hình ba chiều thành một bản đồ hai chiều các đường mức; gradient vuông góc với chúng, và điều kiện tối ưu có ràng buộc là một câu hình học: đường mức tiếp xúc đường ràng buộc.
  • S7. Xấp xỉ và sai số. Mọi thứ trong chương dựa trên xấp xỉ tuyến tính \(f(p + v) \approx f(p) + \nabla f(p) \cdot v\) (Chương 34); hạ gradient là một phép lặp xấp xỉ, đúng dần sau từng bước, với bước học đổi tốc độ lấy độ an toàn.

Tóm tắt

  • Hàm hai biến là một địa hình; đường mức vẽ nó thành bản đồ; đạo hàm riêng là độ dốc theo từng trục.
  • Gradient \(\nabla f = (f_x; f_y)\) gom hai độ dốc ấy: đi một bước nhỏ \(v\) thì \(f\) đổi xấp xỉ \(\nabla f \cdot v\); gradient chỉ hướng dốc lên nhất và vuông góc với đường mức.
  • Tại cực trị bên trong miền, \(\nabla f = 0\); nhưng gradient bằng 0 còn có thể là điểm yên ngựa.
  • Hạ gradient đi từng bước ngược gradient; bước học quá lớn làm dao động hay văng ra, và phương pháp có thể mắc kẹt ở cực tiểu địa phương.
  • Với ràng buộc \(g = c\), tại điểm tối ưu đường mức của \(f\) tiếp xúc đường ràng buộc: \(\nabla f = \lambda \nabla g\); nhân tử Lagrange \(\lambda\) là giá của thêm một đơn vị nguồn lực.
  • Trong quy hoạch tuyến tính, miền chấp nhận được là một đa giác lồi và tối ưu nằm ở một đỉnh.

Bài tập

A. Tư duy

A1. Vì sao gradient luôn vuông góc với đường mức đi qua điểm đang xét?

Lời giải

Dọc theo đường mức, \(f\) không đổi, nên tốc độ thay đổi của \(f\) theo hướng tiếp tuyến với đường mức bằng 0. Mà tốc độ ấy bằng \(\nabla f \cdot u\) với \(u\) là hướng tiếp tuyến (Định lý 3). Tích vô hướng bằng 0 nghĩa là \(\nabla f\) vuông góc với \(u\).

A2. Trên một bản đồ địa hình vẽ các đường mức cách nhau 10 m độ cao, chỗ nào các đường mức nằm sát nhau? Gradient ở đó lớn hay nhỏ?

Lời giải

Đường mức sát nhau nghĩa là chỉ cần đi một quãng ngắn trên mặt đất đã lên hay xuống được 10 m: sườn dốc đứng, gradient lớn. Đường mức thưa là đất thoải, gradient nhỏ. Độ lớn của gradient xấp xỉ bằng 10 m chia cho khoảng cách giữa hai đường mức liền nhau, đo theo hướng vuông góc với chúng.

A3. Tại một điểm bên trong miền, gradient bằng \((0; 0)\). Điểm ấy chắc chắn là cực tiểu không? Nêu ba khả năng, mỗi khả năng một ví dụ.

Lời giải

Không. Nó có thể là cực tiểu (\(x^2 + y^2\) tại gốc), cực đại (\(-x^2 - y^2\) tại gốc), hoặc điểm yên ngựa (\(x^2 - y^2\) tại gốc). Gradient bằng 0 chỉ nói rằng mặt đất phẳng ở bậc nhất; hình dạng thật do các số hạng bậc hai quyết định.

A4. Vì sao trong quy hoạch tuyến tính, nếu có tối ưu thì luôn có một tối ưu nằm ở đỉnh của miền chấp nhận được?

Lời giải

Các đường mức của một hàm tuyến tính là những đường thẳng song song. Đẩy đường mức theo hướng giá trị tăng, nó quét qua miền đa giác; ở vị trí cuối cùng còn chạm miền, nó chạm một đỉnh, hoặc cả một cạnh nếu cạnh ấy song song với nó (khi đó cả hai đầu mút cũng tối ưu). Mệnh đề 6 là chứng minh chặt chẽ của hình ảnh này.

B. Tính toán

B1. Tính các đạo hàm riêng và gradient của \(f(x; y) = x^2 y + 3xy^2\) tại \((1; 2)\).

Lời giải

\(f_x = 2xy + 3y^2\) và \(f_y = x^2 + 6xy\). Tại \((1; 2)\): \(f_x = 4 + 12 = 16\) và \(f_y = 1 + 12 = 13\), nên \(\nabla f(1; 2) = (16; 13)\).

B2. Với \(f = x^2 + 3y^2\), tính đạo hàm theo hướng \(u = (0{,}6; 0{,}8)\) tại \((2; 1)\), và độ dốc lớn nhất tại điểm ấy.

Lời giải

\(\nabla f(2; 1) = (4; 6)\). \(D_u f = 4 \cdot 0{,}6 + 6 \cdot 0{,}8 = 2{,}4 + 4{,}8 = 7{,}2\). Độ dốc lớn nhất là \(\lvert (4; 6) \rvert = \sqrt{52} \approx 7{,}21\), chỉ lớn hơn một chút, vì \(u\) gần cùng hướng với gradient.

B3. Làm ba bước hạ gradient trên \(f = x^2 + 3y^2\) với bước học \(0{,}1\), xuất phát từ \((2; -1)\).

Lời giải

Mỗi bước nhân \(x\) với \(0{,}8\) và \(y\) với \(0{,}4\) (Ví dụ 2): \((2; -1) \to (1{,}6; -0{,}4) \to (1{,}28; -0{,}16) \to (1{,}024; -0{,}064)\). Thành phần \(y\) co nhanh hơn, vì theo trục tung cái bát dốc hơn.

B4. Tìm điểm tới hạn của \(f(x; y) = x^2 + xy + y^2 - 3x\) và chứng tỏ đó là giá trị nhỏ nhất.

Lời giải

\(\nabla f = (2x + y - 3; x + 2y) = (0; 0)\) cho \(x = -2y\), rồi \(-4y + y = 3\), nên \(y = -1\), \(x = 2\), và \(f(2; -1) = 4 - 2 + 1 - 6 = -3\). Hoàn thành bình phương: \(f = \left(x + \frac{y}{2} - \frac32\right)^2 + \frac34 (y + 1)^2 - 3 \geq -3\), dấu bằng khi \(y = -1\), \(x = 2\). Vậy \(-3\) là giá trị nhỏ nhất.

B5. Dùng điều kiện Lagrange tìm giá trị lớn nhất của \(xy\) với \(x, y > 0\) và \(x + 2y = 8\). Kiểm tra bằng cách thế.

Lời giải

\((y; x) = \lambda(1; 2)\) cho \(y = \lambda\), \(x = 2\lambda\); thay vào \(x + 2y = 8\) được \(4\lambda = 8\), \(\lambda = 2\), nên \(x = 4\), \(y = 2\) và \(xy = 8\). Thế \(x = 8 - 2y\): \((8 - 2y)y = 8y - 2y^2\) lớn nhất tại \(y = 2\), cho 8. Ở đây \(\lambda = 2\): tăng vế phải từ 8 lên 9 thì giá trị lớn nhất tăng khoảng 2 (chính xác là từ 8 lên \(\frac{81}{8} = 10{,}125\)).

B6. Trong các hình chữ nhật có diện tích \(36 \ \text{m}^2\), hình nào có chu vi nhỏ nhất?

Lời giải

Làm nhỏ nhất \(2x + 2y\) với \(xy = 36\). Điều kiện Lagrange: \((2; 2) = \lambda(y; x)\), nên \(x = y\), và \(x^2 = 36\) cho \(x = y = 6\): hình vuông, chu vi 24 m. Kiểm tra: hình \(4 \times 9\) có chu vi 26 m, hình \(3 \times 12\) có chu vi 30 m.

B7. (Số liệu giả định.) Làm lớn nhất \(2x + 5y\) với \(x + y \leq 6\), \(x + 3y \leq 12\), \(x \geq 0\), \(y \geq 0\).

Lời giải

Các đỉnh của miền: \((0; 0)\), \((6; 0)\), \((0; 4)\), và giao của \(x + y = 6\) với \(x + 3y = 12\), tức \(2y = 6\), \(y = 3\), \(x = 3\). Giá trị: \(0\), \(12\), \(20\), \(6 + 15 = 21\). Lớn nhất là 21 tại \((3; 3)\).

B8. Với \(f = 5x^2 + y^2\), bước học lớn nhất để hạ gradient hội tụ từ mọi điểm là bao nhiêu? Điều gì xảy ra với bước học \(0{,}25\)?

Lời giải

Theo Mệnh đề 4 với \(a = 5\), \(c = 1\): cần \(\eta < \frac15 = 0{,}2\). Với \(\eta = 0{,}25\), \(x\) bị nhân với \(1 - 2 \cdot 5 \cdot 0{,}25 = -1{,}5\) mỗi bước: đổi dấu và lớn dần, trong khi \(y\) bị nhân với \(0{,}5\) và vẫn co về 0.

B9. Chứng tỏ gốc tọa độ là điểm yên ngựa của \(f(x; y) = xy\).

Lời giải

\(\nabla f = (y; x)\) bằng \((0; 0)\) tại gốc. Dọc đường \(y = x\), \(f = x^2 \geq 0\): gốc là đáy. Dọc đường \(y = -x\), \(f = -x^2 \leq 0\): gốc là đỉnh. Vậy gốc không phải cực trị. Mặt \(z = xy\) chính là mặt \(z = x^2 - y^2\) quay đi \(45^\circ\) và thu nhỏ theo chiều cao, vì \(xy = \frac{u^2 - v^2}{2}\) với \(u = \frac{x + y}{\sqrt2}\), \(v = \frac{x - y}{\sqrt2}\).

B10. Với \(f(x) = x^4 - 4x^2 + x\), làm hai bước hạ gradient với bước học \(0{,}05\) từ \(x = 1\). Dãy tiến về đâu? So sánh với giá trị nhỏ nhất của \(f\).

Lời giải

\(f'(x) = 4x^3 - 8x + 1\). \(f'(1) = -3\), nên \(x_1 = 1 + 0{,}05 \cdot 3 = 1{,}15\). \(f'(1{,}15) = 4 \cdot 1{,}520875 - 9{,}2 + 1 = -2{,}1165\), nên \(x_2 = 1{,}15 + 0{,}105825 \approx 1{,}2558\). Dãy tiến về nghiệm \(x \approx 1{,}347\) của \(f'(x) = 0\), một cực tiểu địa phương với \(f \approx -2{,}62\). Nhưng \(f\) còn một cực tiểu khác tại \(x \approx -1{,}473\) với \(f \approx -5{,}44\), sâu hơn nhiều; hạ gradient từ \(x = 1\) không bao giờ tới được đó, vì phải vượt qua đỉnh tại \(x \approx 0{,}126\).

C. Phản ví dụ và chứng minh

C1. Không dùng đạo hàm, chứng minh rằng trong mọi hình chữ nhật có cùng chu vi, hình vuông có diện tích lớn nhất.

Lời giải

Gọi hai cạnh là \(x\), \(y\) với \(x + y = s\) cố định. Vì \((x - y)^2 \geq 0\), ta có \((x + y)^2 - 4xy = (x - y)^2 \geq 0\), nên \(xy \leq \frac{s^2}{4}\), dấu bằng khi và chỉ khi \(x = y\). \(\square\) Đây là bất đẳng thức giữa trung bình cộng và trung bình nhân của hai số, và nó cho cùng kết luận với điều kiện Lagrange ở Ví dụ 3.

C2. Dùng điều kiện Lagrange tìm các ứng viên cực trị của \(f = x + y\) trên đường tròn \(x^2 + y^2 = 2\). Điều kiện ấy có tự cho biết điểm nào là lớn nhất không?

Lời giải

\(\nabla f = (1; 1) = \lambda(2x; 2y)\) cho \(x = y = \frac{1}{2\lambda}\), và \(x^2 + y^2 = 2\) cho \(x = y = \pm 1\). Hai ứng viên là \((1; 1)\) với \(f = 2\) và \((-1; -1)\) với \(f = -2\). Điều kiện Lagrange cho cả hai như nhau; phải so sánh giá trị mới biết \((1; 1)\) cho giá trị lớn nhất và \((-1; -1)\) cho giá trị nhỏ nhất. Điều kiện chỉ là điều kiện cần.

C3. Cho \(f(x; y) = (y - x^2)(y - 3x^2)\). Chứng minh rằng dọc mọi đường thẳng qua gốc, \(f\) có cực tiểu địa phương tại gốc, nhưng gốc không phải cực tiểu địa phương của \(f\).

Lời giải

Dọc trục tung (\(x = 0\)), \(f = y^2 \geq 0 = f(0; 0)\). Dọc đường \(y = mx\): \(f = (mx - x^2)(mx - 3x^2) = x^2 (m - x)(m - 3x)\). Nếu \(m = 0\) thì \(f = 3x^4 \geq 0\). Nếu \(m \neq 0\) thì khi \(x\) đủ gần 0, cả \(m - x\) lẫn \(m - 3x\) cùng dấu với \(m\), nên \(f > 0\) với \(x \neq 0\). Vậy trên mọi đường thẳng qua gốc, gốc là cực tiểu địa phương. Nhưng dọc parabol \(y = 2x^2\), nằm giữa hai parabol \(y = x^2\) và \(y = 3x^2\), \(f = (x^2)(-x^2) = -x^4 < 0\) với mọi \(x \neq 0\), và những điểm ấy gần gốc tùy ý. Vậy gốc không phải cực tiểu địa phương. \(\square\) Kiểm tra theo từng đường thẳng chưa đủ, vì cái hố có thể nằm dọc một đường cong.

Câu hỏi để ngỏ

Tối ưu khi biết chắc kết quả của mỗi lựa chọn thì còn dễ. Nhưng khi kết quả phụ thuộc may rủi, như đầu tư, mua bảo hiểm, chẩn đoán, thì "tốt nhất" nghĩa là gì?