Nhà toán học lỗi lạc R. Tyrrell Rockafellar từng đưa ra một đúc kết kinh điển làm thay đổi hoàn toàn diện mạo của lý thuyết tối ưu hiện đại: "Ranh giới phân chia cốt lõi trong tối ưu không nằm ở sự phân biệt giữa bài toán tuyến tính và phi tuyến, mà nằm ở ranh giới giữa tính lồi và phi lồi."

Ở Bài 00, ta đã giải một bài toán đơn giản bằng cách tính đạo hàm rồi cho triệt tiêu về 0. Cách tiếp cận giải tích cổ điển đó vận hành trơn tru khi bài toán không có bất kỳ ràng buộc nào. Thế nhưng trong thế giới thực, các bài toán luôn bị bủa vây bởi các giới hạn: Năng lượng pin có hạn, ngân sách đầu tư cố định, độ trễ mạng viễn thông, hay xác suất dự đoán phải nằm trong đoạn $[0,1]$. Khi đưa các ràng buộc vào mô hình, hàng loạt câu hỏi hóc búa lập tức xuất hiện:

• Điểm dừng vừa tìm được có thực sự là nghiệm tốt nhất trên toàn bộ miền khảo sát hay chỉ là một cực tiểu cục bộ trong một thung lũng hẹp?
• Nếu nghiệm tối ưu bị đẩy ra tận đường biên của thì làm sao kiểm chứng khi không còn bằng 0?
• Làm thế nào để thuật toán tránh rơi vào trạng thái dừng cục bộ tại các điểm yên ngựa hoặc cực tiểu địa phương kém chất lượng?

Chương này mở rộng phân tích sang một họ bài toán có cấu trúc toán học đặc biệt: Bài toán tối ưu lồi (Convex Optimization). Với bài toán tối ưu lồi, ta có một bảo đảm toán học vững chắc: Mọi cực tiểu cục bộ đều là cực tiểu toàn cục. Để làm chủ công cụ này, chúng ta sẽ khảo sát hai trụ cột gắn kết hữu cơ:

1. Hình học của (Convex Sets): Không gian dung chứa các quyết định và phương án khả thi.
2. Giải tích của (Convex Functions): Thước đo đánh giá mục tiêu mất mát hoặc chi phí cần tối thiểu hóa.

---

1. Cấu trúc chương học và Hướng dẫn tiếp cận

Nội dung chương được cấu trúc thành 25 chủ đề chuyên sâu, phân bổ mạch lạc trong bốn phần:

• Phần I (Chủ đề 1–2): Ngôn ngữ chuẩn tắc của bài toán tối ưu hóa và hai dạng bài toán nền tảng.
• Phần II (Chủ đề 3–16): Hình học không gian , các khối hình cơ bản, phép toán bảo toàn tính lồi và định lý siêu phẳng phân tách.
• Phần III (Chủ đề 17–22): Giải tích , bất đẳng thức Jensen, điều kiện vi phân bậc nhất, bậc hai và bộ quy tắc nhận diện hàm lồi.
• Phần IV (Chủ đề 23–25): Nguyên lý cực tiểu toàn cục, điều kiện tối ưu trên miền ràng buộc và ứng dụng trực tiếp trong các mô hình học máy.

Mỗi chủ đề đều trang bị phần giải thích bản chất trực quan, câu hỏi đào sâu tư duy và bài tập kèm lời giải chi tiết.

25 chủ đề · tổng cộng khoảng 590 phút đọc

I. Bài toán tối ưu

Viết đúng một bài toán trước khi nghĩ tới chuyện giải nó.

1. 1Bài toán tối ưu và những gì cần viết raMuốn nói một phương án là tốt nhất, ta phải mô tả chính xác những đối tượng nào?Khoảng 40 phút
2. 2Bình phương tối thiểu và quy hoạch tuyến tínhHai lớp bài toán quen thuộc này có điểm chung gì mà người ta giải được chúng một cách đáng tin cậy?Khoảng 38 phút

II. Hình học của tập lồi

Các khối hình cơ bản, cách lắp ghép chúng và những định lý hình học dùng lại suốt môn học.

1. 3Đường thẳng, đoạn thẳng và tập affineĐiều kiện “các hệ số cộng lại bằng 1” mô tả loại hình học nào?Khoảng 49 phút
2. 4Chiều affine và nội tương đốiMột hình vuông nằm phẳng trong không gian ba chiều có “phần trong” hay không?Khoảng 9 phút
3. 5Tập lồi, tổ hợp lồi và bao lồiKhi buộc mọi hệ số phải không âm, đường thẳng qua hai điểm còn lại phần nào?Khoảng 36 phút
4. 6Nón và nón lồiBỏ điều kiện tổng bằng 1 nhưng vẫn giữ hệ số không âm thì ta thu được hình gì?Khoảng 27 phút
5. 7Siêu phẳng và nửa không gianMột phương trình tuyến tính duy nhất chia không gian ra sao?Khoảng 35 phút
6. 8Quả cầu và ellipsoidMột ma trận đối xứng xác định dương vẽ ra hình gì trong không gian?Khoảng 20 phút
7. 9Quả cầu chuẩn và nón chuẩnVì sao quả cầu đơn vị của mọi chuẩn đều lồi, còn “quả cầu” của ‖x‖ với p = 1/2 thì không?Khoảng 10 phút
8. 10Đa diện và đơn hìnhNên mô tả một đa giác bằng các cạnh hay bằng các đỉnh của nó?Khoảng 24 phút
9. 11Nón các ma trận nửa xác định dươngTập hợp các ma trận cũng có một hình dạng mà ta có thể hình dung được không?Khoảng 24 phút
10. 12Các phép toán giữ tính lồi của tậpLàm thế nào chứng minh một tập phức tạp là lồi mà không phải kiểm tra từng đoạn thẳng?Khoảng 22 phút
11. 13Phép phối cảnh và hàm phân tuyến tínhNhìn một vật lồi qua máy ảnh lỗ kim, ảnh thu được có còn lồi?Khoảng 19 phút
12. 14Nón chính quy và bất đẳng thức tổng quátKhi so sánh hai vector, “nhỏ hơn” nên được hiểu theo nghĩa nào?Khoảng 18 phút
13. 15Siêu phẳng phân tách và siêu phẳng tựaHai tập lồi rời nhau có luôn ngăn được bằng một siêu phẳng không?Khoảng 21 phút
14. 16Nón đối ngẫu và lựa chọn ParetoNhững hướng nào nhìn toàn bộ một nón từ cùng một phía, và điều đó giúp gì khi phải cân nhiều tiêu chí?Khoảng 19 phút

III. Hàm lồi

Nối hình học của tập lồi với giải tích: Dây cung, tiếp tuyến, độ cong và các quy tắc lắp ghép hàm.

1. 17Hàm lồi và bất đẳng thức dây cungĐồ thị nằm dưới mọi dây cung thì nói lên điều gì về một hàm số?Khoảng 18 phút
2. 18Điều kiện bậc nhất: Tiếp tuyến nằm dưới đồ thịChỉ biết giá trị và đạo hàm tại một điểm, ta suy ra được gì về toàn bộ hàm?Khoảng 18 phút
3. 19Điều kiện bậc hai và độ congHessian nửa xác định dương mang ý nghĩa hình học gì?Khoảng 26 phút
4. 20Những hàm lồi thường gặpChuẩn, hàm max, log-sum-exp và log det lồi hay lõm, và ta chứng minh điều đó thế nào?Khoảng 15 phút
5. 21Epigraph, tập mức dưới và bất đẳng thức JensenNhìn một hàm lồi như một tập hợp thì ta được thêm những công cụ gì?Khoảng 24 phút
6. 22Các phép toán giữ tính lồi của hàmTừ vài hàm lồi đã biết, ta lắp ghép được những hàm lồi mới nào và cần cẩn thận ở đâu?Khoảng 20 phút

IV. Tính lồi trong bài toán tối ưu

Ghép miền lồi với hàm mục tiêu lồi để có những bảo đảm mà tối ưu tổng quát không có.

1. 23Cực tiểu cục bộ và cực tiểu toàn cụcTrong bài toán lồi, một điểm tốt nhất trong vùng lân cận có chắc là tốt nhất trên toàn miền?Khoảng 19 phút
2. 24Điều kiện tối ưu bậc nhất trên miền lồiKhi nghiệm nằm trên biên và gradient khác 0, ta kiểm chứng nó tối ưu bằng cách nào?Khoảng 18 phút
3. 25Nhận diện tính lồi trong mô hình học máyHàm mất mát của hồi quy logistic là lồi, vậy còn mạng nơ-ron hai tầng thì sao?Khoảng 21 phút

---

2. Ba lộ trình học tập tùy biến

Tùy theo mục tiêu nghiên cứu và nền tảng cá nhân, người học có thể lựa chọn một trong ba lộ trình tiếp cận sau:

Lộ trình 1: Khung xương cốt lõi (Core Track)

Dành cho lần đọc đầu tiên để nắm bắt nhanh định lý trung tâm và các công cụ thực chiến:

• Chủ đề 1. Bài toán tối ưu và những gì cần viết ra
• Chủ đề 2. Bình phương tối thiểu và quy hoạch tuyến tính
• Chủ đề 3. Đường thẳng, đoạn thẳng và tập affine
• Chủ đề 5. Tập lồi, tổ hợp lồi và bao lồi
• Chủ đề 7. Siêu phẳng và nửa không gian
• Chủ đề 12. Các phép toán giữ tính lồi của tập
• Chủ đề 17. Hàm lồi và bất đẳng thức dây cung
• Chủ đề 18. Điều kiện bậc nhất
• Chủ đề 19. Điều kiện bậc hai và độ cong
• Chủ đề 23. Cực tiểu cục bộ và cực tiểu toàn cục
• Chủ đề 24. Điều kiện tối ưu bậc nhất trên miền lồi

Lộ trình 2: Nhãn quan hình học không gian (Geometric Track)

Dành cho người muốn thấu suốt nguồn gốc không gian của các và chuẩn bị nền móng vững chắc cho lý thuyết đối ngẫu Lagrange:

• Chủ đề 4. Chiều affine và nội tương đối
• Chủ đề 6. Nón và nón lồi
• Chủ đề 8–11. Quả cầu và ellipsoid, Quả cầu chuẩn và nón chuẩn, Đa diện và đơn hình, Nón ma trận nửa xác định dương PSD
• Chủ đề 13–14. Phép phối cảnh, Bất đẳng thức tổng quát qua nón
• Chủ đề 15–16. Siêu phẳng phân tách và siêu phẳng tựa, Nón đối ngẫu

Lộ trình 3: Trọng tâm Trí tuệ nhân tạo & Học máy (Machine Learning Track)

Tập trung trực tiếp vào các hàm mất mát, kiến trúc mô hình và bài toán tối ưu thường gặp trong AI hiện đại:

• Bình phương tối thiểu và quy hoạch tuyến tính cùng Chuẩn L1 thúc đẩy nghiệm thưa
• Độ phân kỳ KL qua điều kiện bậc nhất cùng Hàm Softmax và Log-Sum-Exp
• Bất đẳng thức Jensen và Cận dưới biến phân ELBO cùng Nhận diện tính lồi của hàm mất mát
• Phân tích tính lồi trong các mô hình học máy

---

3. Bức tranh tổng thể

Sơ đồ sau minh họa sự liên kết logic xuyên suốt giữa các chủ đề:

• Phần I: Thiết lập ngôn ngữ toán học chuẩn mực: Biến quyết định, hàm mục tiêu, hệ thống ràng buộc đẳng thức và bất đẳng thức. Chỉ ra ba trạng thái suy biến khiến bài toán không có nghiệm: Không khả thi (miền rỗng), không bị chặn dưới, hoặc giá trị tối ưu chỉ đạt được ở vô cực (không đạt cận).
• Phần II: Xây dựng nền tảng hình học của từ tổ hợp affine, tới tổ hợp nón. Giới thiệu các khối hình cơ sở cấu thành miền ràng buộc thực tế: Siêu phẳng, nửa không gian, ellipsoid, đa diện và nón . Thiết lập hai định lý hình học nền tảng: Siêu phẳng phân tách và siêu phẳng tựa.
• Phần III: Chuyển giao từ hình học sang giải tích. được định nghĩa qua bất đẳng thức dây cung, tương đương với việc phần trên đồ thị () tạo thành một . Trang bị ba công cụ nhận diện tính lồi: Định nghĩa gốc, điều kiện vi phân bậc nhất (mặt phẳng tiếp tuyến luôn là cận dưới toàn cục), và điều kiện bậc hai ( khắp nơi).
• Phần IV: Hội tụ hai thế giới hình học và giải tích. Chứng minh định lý trung tâm: Cực tiểu cục bộ trên miền lồi luôn là cực tiểu toàn cục. Mở rộng điều kiện tối ưu sang trường hợp nghiệm nằm trên biên của miền ràng buộc qua bất đẳng thức biến phân $\mathrm{\nabla }{f}_0(x^{\ast }{)}^T(y-x^{\ast })\ge 0$. Cuối cùng, làm sáng tỏ câu hỏi cốt tử trong AI: Tại sao bài toán hồi quy Logistic lồi theo trọng số, trong khi mạng nơ-ron sâu lại phi lồi.

---

4. Hệ thống Bài tập Tự luyện & Vận dụng Chuyên sâu

Bài tập 1: Nhận diện bốn thành phần và Cải dạng bài toán tối ưu

1. Một robot tự hành cần lựa chọn vận tốc di chuyển $v\in \mathbb{R}$ sao cho tiến gần nhất tới vận tốc tham chiếu $v_{\mathrm{ref}}$, đồng thời tiết kiệm năng lượng và không vượt quá giới hạn an toàn động cơ:
   $$\underset{v}{min}(v-v_{\mathrm{ref}}{)}^2+\lambda v^2\text{s.t.}|v|\le v_{max},$$
   với $\lambda >0$ và $v_{max}>0$. Hãy xác định tường minh: Dữ kiện bài toán, biến quyết định, hàm mục tiêu và . Xác định nghiệm tối ưu giải tích $v^{\ast }$ theo các .
2. Xét ba bài toán tối ưu sau, phân tích xem bài toán nào là bài toán lồi hoặc có thể đưa về bài toán lồi:
   • Bài toán A: Cực tiểu hóa $\underset{x}{min}\parallel Ax-b{\parallel }_1+\parallel x{\parallel }_2^2$ với điều kiện $x⪰0$.
   • Bài toán B: Cực đại hóa $\underset{x}{max}{x}_1{x}_2$ với điều kiện $x_1+x_2=4$ và $x\succ 0$.
   • Bài toán C: Cực tiểu hóa $\underset{x}{min}\underset{i=1,\dots ,m}{max}|a_i^{T}x-b_i|$.

Lời giải

1. Phân tích các thành phần mô hình:

   • Dữ kiện bài toán (Problem data): Vận tốc tham chiếu $v_{\mathrm{ref}}\in \mathbb{R}$, trọng số điều chuẩn năng lượng $\lambda >0$, và giới hạn vận tốc $v_{max}>0$.
   • Biến quyết định (Optimization variable): Vận tốc $v\in \mathbb{R}$ (vô hướng 1 chiều).
   • Hàm mục tiêu (Objective function):
     $$f(v)=(v-v_{\mathrm{ref}}{)}^2+\lambda v^2=(1+\lambda )v^2-2v_{\mathrm{ref}}v+v_{\mathrm{ref}}^2.$$
   • (Feasible set): Đoạn đóng $\mathcal{C}=[-v_{max},v_{max}]$, là một compact khác rỗng.

   Tìm nghiệm giải tích: Đạo hàm $f^{\prime }(v)=2(1+\lambda )v-2v_{\mathrm{ref}}=0$ cho nghiệm tự do (không ràng buộc):

   $$v_{\mathrm{free}}=\frac{v_{\mathrm{ref}}}{1+\lambda }.$$

   Vì $f^{″}(v)=2(1+\lambda )>0$, lồi ngặt trên $\mathbb{R}$. Nghiệm tối ưu có ràng buộc là hình chiếu của $v_{\mathrm{free}}$ lên đoạn $[-v_{max},v_{max}]$:

   $$v^{\ast }=\mathrm{clip}(\frac{v_{\mathrm{ref}}}{1+\lambda },-v_{max},v_{max})=\{\begin{array}{ll}-v_{max}& \text{if }\frac{v_{\mathrm{ref}}}{1+\lambda }<-v_{max},\\ \frac{v_{\mathrm{ref}}}{1+\lambda }& \text{if }\left|\frac{v_{\mathrm{ref}}}{1+\lambda }\right|\le v_{max},\\ v_{max}& \text{if }\frac{v_{\mathrm{ref}}}{1+\lambda }>v_{max}.\end{array}$$

2. Cải dạng bài toán:

   • Bài toán A: Là bài toán lồi chính tắc do hàm mục tiêu là tổng của $\parallel Ax-b{\parallel }_1$ và hàm lồi ngặt $\parallel x{\parallel }_2^2$, trên nón không âm $x⪰0$ ().
   • Bài toán B: Hàm mục tiêu $x_1{x}_2$ không lõm trên ${\mathbb{R}}^2$, nhưng với $x\succ 0$, việc cực đại hóa $x_1{x}_2$ tương đương cực đại hóa $\log (x_1{x}_2)=\log x_1+\log x_2$. Vì hàm logarit lõm, bài toán chuyển thành quy hoạch lồi và có nghiệm duy nhất $x_1^{\ast }=x_2^{\ast }=2$.
   • Bài toán C: Là vì là giá trị lớn nhất (pointwise maximum) của các hàm lồi $|a_i^{T}x-b_i|$. Chuyển về Quy hoạch tuyến tính (LP) bằng kỹ thuật : Đặt $\underset{x,t}{min}t$ với điều kiện $-t\le a_i^{T}x-b_i\le t$ với mọi $i=1,\dots ,m$.

Bài tập 2: Tập lồi, Phản ví dụ và Ba cấp độ Bảo đảm Tối ưu

1. Với mỗi sau trong ${\mathbb{R}}^2$, xác định hay không lồi. Nếu không lồi, hãy chỉ ra một phản ví dụ số học tường minh:
   • Tập hộp: $C_1=[-1,1]\times [0,2]$.
   • $C_2=\{x\in {\mathbb{R}}^2\mid \parallel x{\parallel }_2=1\}$.
   • $C_3=\{x\in {\mathbb{R}}^2\mid x_1+x_2=1\}$.
2. Phân biệt ba cấp độ bảo đảm trong lý thuyết tối ưu hóa: Bảo đảm tồn tại nghiệm, bảo đảm cực tiểu cục bộ là toàn cục, và bảo đảm nghiệm duy nhất. Cho biết vì sao tính lồi đơn độc không đủ để khẳng định nghiệm tồn tại và duy nhất.

Lời giải

1. Kiểm tra tính lồi:
   • $C_1$ là vì là tích Descartes của hai đoạn đóng, tương đương giao của bốn nửa không gian đóng.
   • $C_2$ không lồi: Lấy hai điểm $x=(1,0{)}^T\in C_2$ và $y=(-1,0{)}^T\in C_2$. Trung điểm của chúng là:
     $$m=\frac{1}{2}x+\frac{1}{2}y=(0,0{)}^T.$$
     Ta có $\parallel m{\parallel }_2=0\ne 1$, suy ra $m\notin C_2$.
   • $C_3$ là vì là một siêu phẳng (tập affine). Với mọi $x,y\in C_3$ và $\theta \in [0,1]$, thỏa mãn:
     $$$$

(\theta x_1 + (1-\theta)y_1) + (\theta x_2 + (1-\theta)y_2) &= \theta(x_1 + x_2) + (1-\theta)(y_1 + y_2) \ &= \theta(1) + (1-\theta)(1) = 1. \end

$$2.\ast \ast Bacấpđộbảođảm\ast \ast :-\ast \ast Bảođảmtồntạinghiệm(Existence)\ast \ast :DựatrênĐịnhlýWeierstrass:Hàmmụctiêuliêntụctrênmiềnkhảthiđóngvàbịchặn(compact)khácrỗngthìluônđạtgiátrịnhỏnhấttoàncục.-\ast \ast Bảođảmcựctiểucụcbộlàtoàncục(Globaloptimalityoflocalminima)\ast \ast :Dựatrên\ast \ast tínhlồi\ast \ast :Nếuhàmmụctiêulồitrênmiềnkhảthilồi,mọiđiểmcựctiểucụcbộđềutựđộnglàcựctiểutoàncục.Tuynhiên,bàitoánlồivẫncóthểkhôngcónghiệm(miềnkhôngbịchặnvàhàmgiảmdầnravôcực,như\$min{e}^x\$).-\ast \ast Bảođảmtínhduynhất(Uniqueness)\ast \ast :Dựatrên\ast \ast tínhlồingặt(strictlyconvex)\ast \ast hoặclồimạnh:Hàmlồingặttrênmiềnlồicónhiềunhấtmộtđiểmcựctiểutoàncục.\ast Kếtluậnsưphạm\ast :Tínhlồichỉbảođảm"nếucócựctiểucụcbộthìđólàtoàncục",nhưngkhôngbảođảmcựctiểuđótồntạihayduynhất.Đểcónghiệmduynhất,tacầnkếthợpđiềukiệntồntại(tậpmứcdướicompact)vớiđiềukiệnduynhất(lồingặt).$$

Bài tập 3: Bài toán điều khiển tối ưu một bước với giới hạn chấp hành

Xét bài toán điều khiển một bước cho xe tự hành: Trạng thái hiện tại là $s=2$. Sau khi áp dụng lực điều khiển $u$, trạng thái tiếp theo trở thành $s+u$. Ta muốn triệt tiêu độ lệch trạng thái về 0 nhưng đồng thời phải tiết kiệm năng lượng, và cơ cấu chấp hành có giới hạn vật lý:

$$\underset{u}{min}\frac{1}{2}(2+u{)}^2+\frac{1}{2}{u}^2\text{s.t.}|u|\le 0.5.$$

1. Chứng minh bài toán trên là bài toán tối ưu lồi.
2. Tìm nghiệm tối ưu $u^{\ast }$ và kiểm chứng bằng điều kiện tối ưu bậc nhất trên miền lồi.
3. Nếu cơ cấu chấp hành không bị giới hạn ($u\in \mathbb{R}$ tự do), nghiệm tối ưu sẽ thay đổi ra sao?

Lời giải

1. Tính lồi: Hàm mục tiêu:

   $$f(u)=\frac{1}{2}(2+u{)}^2+\frac{1}{2}{u}^2=u^2+2u+2$$

   có đạo hàm bậc hai $f^{″}(u)=2>0$, do đó lồi ngặt trên $\mathbb{R}$. là đoạn thẳng $\mathcal{C}=[-0.5,0.5]$, là một đóng. Do đó đây là bài toán tối ưu lồi.

2. Tìm nghiệm và kiểm chứng: Đạo hàm bậc nhất là $f^{\prime }(u)=2u+2$. Trên đoạn $[-0.5,0.5]$, ta thấy $f^{\prime }(u)\ge 2(-0.5)+2=1>0$, nghĩa là đồng biến trên toàn bộ . Do đó, hàm số đạt giá trị nhỏ nhất tại điểm mút bên trái: $u^{\ast }=-0.5$. Giá trị mất mát tối ưu là:

   $$f(-0.5)=\frac{1}{2}(1.5{)}^2+\frac{1}{2}(-0.5{)}^2=1.125+0.125=1.25.$$

   Kiểm chứng qua điều kiện tối ưu bậc nhất trên miền lồi: Ta cần chỉ ra $\mathrm{\nabla }f(u^{\ast }{)}^T(y-u^{\ast })\ge 0$ với mọi $y\in \mathcal{C}$. Tại $u^{\ast }=-0.5$, ta có $f^{\prime }(-0.5)=1$. Với mọi $y\in [-0.5,0.5]$, ta có:

   $$f^{\prime }(u^{\ast })(y-u^{\ast })=1\cdot (y-(-0.5))=y+0.5\ge 0.$$

   Bất đẳng thức nghiệm đúng với mọi $y\in \mathcal{C}$. Điều này chứng minh chặt chẽ rằng $u^{\ast }=-0.5$ là nghiệm tối ưu toàn cục, dù đạo hàm tại đó khác 0 do nghiệm nằm trên biên ràng buộc.

3. Khi không có giới hạn: Ta giải phương trình đạo hàm triệt tiêu: $f^{\prime }(u)=2u+2=0⟺u=-1$. Lúc này giá trị mất mát tối ưu là $f(-1)=\frac{1}{2}(1{)}^2+\frac{1}{2}(-1{)}^2=1.0<1.25$. Giới hạn vật lý $|u|\le 0.5$ đã kích hoạt (ràng buộc chặt) và làm dịch chuyển điểm cân bằng tối ưu của hệ thống.

Bài tập 4: Hệ phương trình chuẩn tắc và Phân tích hình học phép chiếu OLS

Cho đặc trưng $X$ và nhãn mục tiêu $y$:

$$X=\left[\begin{array}{cc}1& 0\\ 1& 1\\ 1& 2\end{array}\right],y=\left[\begin{array}{c}0\\ 1\\ 3\end{array}\right].$$

1. Thiết lập Gram $X^{T}X$ và $X^{T}y$.
2. Tìm nghiệm $w^{\ast }$ bằng cách giải hệ phương trình chuẩn tắc (Normal Equations).
3. Tính dự đoán $\hat{y}=X{w}^{\ast }$ và vector phần dư $r=y-\hat{y}$. Kiểm chứng tính trực giao giữa phần dư và không gian cột của $X$: $X^{T}r=0$.
4. Tính tổng bình phương sai số nhỏ nhất $\parallel r{\parallel }_2^2$.

Lời giải

1. Thiết lập các đại lượng:
   $$$$

X^TX &= \begin{bmatrix} 1 & 1 & 1 \ 0 & 1 & 2 \end{bmatrix} \begin{bmatrix} 1 & 0 \ 1 & 1 \ 1 & 2 \end{bmatrix} = \begin{bmatrix} 3 & 3 \ 3 & 5 \end{bmatrix}, \ X^Ty &= \begin{bmatrix} 1 & 1 & 1 \ 0 & 1 & 2 \end{bmatrix} \begin{bmatrix} 0 \ 1 \ 3 \end{bmatrix} = \begin{bmatrix} 4 \ 7 \end{bmatrix}. \end

$$2.\ast \ast Giảihệphươngtrìnhchuẩntắc\ast \ast :Địnhthức\$det(X^{T}X)=15-9=6\ne 0\$.Matrậnkhảnghịch:$$

(X^TX)^{-1} = \frac{1}{6} \begin{bmatrix} 5 & -3 \ -3 & 3 \end{bmatrix}.

$$Nghiệmtốiưuduynhấtlà:$$

w^* = (X^TX)^{-1} X^Ty = \frac{1}{6} \begin{bmatrix} 5 \cdot 4 - 3 \cdot 7 \ -3 \cdot 4 + 3 \cdot 7 \end{bmatrix} = \frac{1}{6} \begin{bmatrix} -1 \ 9 \end{bmatrix} = \begin{bmatrix} -1/6 \ 3/2 \end{bmatrix}.

$$3.\ast \ast Dựđoán,phầndưvàkiểmchứngtrựcgiao\ast \ast :Vectordựđoántốiưu:$$

\hat{y} = Xw^* = \begin{bmatrix} 1 & 0 \ 1 & 1 \ 1 & 2 \end{bmatrix} \begin{bmatrix} -1/6 \ 3/2 \end{bmatrix} = \begin{bmatrix} -1/6 \ 4/3 \ 17/6 \end{bmatrix}.

$$Vectorphầndư:$$

r = y - \hat{y} = \begin{bmatrix} 0 - (-1/6) \ 1 - 4/3 \ 3 - 17/6 \end{bmatrix} = \begin{bmatrix} 1/6 \ -1/3 \ 1/6 \end{bmatrix} = \frac{1}{6} \begin{bmatrix} 1 \ -2 \ 1 \end{bmatrix}.

$$Kiểmchứngtínhtrựcgiao:$$

X^Tr = \frac{1}{6} \begin{bmatrix} 1 & 1 & 1 \ 0 & 1 & 2 \end{bmatrix} \begin{bmatrix} 1 \ -2 \ 1 \end{bmatrix} = \frac{1}{6} \begin{bmatrix} 1 - 2 + 1 \ 0 - 2 + 2 \end{bmatrix} = \begin{bmatrix} 0 \ 0 \end{bmatrix}.

$$Hệthức\$X^{T}r=0\$đượcthỏamãntuyệtđối,minhchứnghìnhhọcrằng\$\hat{y}\$chínhlàhìnhchiếutrựcgiaocủa\$y\$lênkhônggiancon\$\mathrm{col}(X)\$.4.\ast \ast Tổngbìnhphươngsaisố\ast \ast :$$

|r|_2^2 = \left(\frac{1}{6}\right)^2 + \left(-\frac{2}{6}\right)^2 + \left(\frac{1}{6}\right)^2 = \frac{1 + 4 + 1}{36} = \frac{6}{36} = \frac{1}{6}.

$$$$

Bài tập 5: Ma trận thiếu hạng và Cấu trúc Tập nghiệm Affine

Cho suy biến và mục tiêu:

$$X=\left[\begin{array}{cc}1& 1\\ 2& 2\end{array}\right],y=\left[\begin{array}{c}1\\ 2\end{array}\right].$$

1. Mô tả toàn bộ tập nghiệm tối ưu của bài toán $\underset{w}{min}\parallel Xw-y{\parallel }_2^2$.
2. Giải thích vì sao giá trị tối ưu đạt được hữu hạn ($p^{\ast }=0$) nhưng nghiệm tối ưu lại không duy nhất.

Lời giải

1. Mô tả tập nghiệm: Ta nhận thấy cột 2 của $X$ trùng với cột 1, do đó $Xw=(w_1+w_2)\left[\begin{array}{c}1\\ 2\end{array}\right]$. Biểu thức phần dư trở thành:
   $$\parallel Xw-y{\parallel }_2^2={\Vert (w_1+w_2-1)\left[\begin{array}{c}1\\ 2\end{array}\right]\Vert }_2^2=5(w_1+w_2-1{)}^2.$$
   Giá trị nhỏ nhất là $0$, đạt được khi và chỉ khi $w_1+w_2=1$. Do đó, tập nghiệm tối ưu là một đường thẳng affine một chiều trong ${\mathbb{R}}^2$:
   $$\mathcal{S}=\{(t,1-t{)}^T\mid t\in \mathbb{R}\}=\left[\begin{array}{c}0\\ 1\end{array}\right]+\mathrm{span}\left(\left[\begin{array}{c}-1\\ 1\end{array}\right]\right).$$
2. Bản chất giải tích: $X$ có cỡ $2\times 2$ nhưng chỉ có hạng bằng 1 ($\mathrm{rank}(X)=1<2$). Do đó:
   $$X^{T}X=\left[\begin{array}{cc}5& 5\\ 5& 5\end{array}\right]$$
   chỉ là (${\lambda }_1=10,{\lambda }_2=0$), không xác định dương. Hàm mục tiêu $f(w)=5(w_1+w_2-1{)}^2$ là nhưng không lồi ngặt (đồ thị có lòng máng phẳng kéo dài dọc theo hướng $(-1,1{)}^T$). Vì $y$ nằm trong không gian cột của $X$, giá trị tối ưu $p^{\ast }=0$ đạt được hoàn hảo, nhưng toàn bộ đáy máng đều là nghiệm, tạo nên vô số nghiệm khả thi.

Bài tập 6: Nghịch lý Mất mát Logistic khi Dữ liệu phân tách tuyến tính

Xét hàm mất mát logistic đơn biến:

$$L(w)=2\log (1+e^{-w}),w\in \mathbb{R}.$$

1. Tính đạo hàm bậc nhất $L^{\prime }(w)$ và đạo hàm bậc hai $L^{″}(w)$. Chứng minh $L(w)$ lồi ngặt trên $\mathbb{R}$.
2. Chứng minh rằng $\underset{w\in \mathbb{R}}{inf}L(w)=0$, nhưng bài toán tối ưu $\underset{w\in \mathbb{R}}{min}L(w)$ hoàn toàn không có nghiệm.
3. Giải thích vì sao tính lồi ngặt không bảo đảm sự tồn tại của nghiệm tối ưu.

Lời giải

1. Tính đạo hàm và chứng minh lồi ngặt:
   $$$$

L'(w) &= 2 \cdot \frac{-e^{-w}}{1 + e^{-w}} = -\frac{2}{1 + e^w} < 0 \quad \forall w \in \mathbb{R}. \ L''(w) &= -2 \cdot \frac{-(e^w)}{(1 + e^w)^2} = \frac{2e^w}{(1 + e^w)^2} > 0 \quad \forall w \in \mathbb{R}. \end

$$Vì\$L^{″}(w)>0\$vớimọi\$w\in \mathbb{R}\$,hàmmấtmát\$L(w)\$lồingặt(strictlyconvex)trêntoàntrụcsố.2.\ast \ast Giátrịtốiưuvàsựvắngmặtcủanghiệm\ast \ast :Vì\$L^{\prime }(w)<0\$khắpnơi,hàmsốnghịchbiếnnghiêmngặt.Khi\$w\to +\mathrm{\infty }\$:$$

\lim_{w \to +\infty} L(w) = \lim_{w \to +\infty} 2 \log(1 + e^{-w}) = 2 \log(1) = 0.

$$Mặtkhác,vớimọi\$w\$hữuhạn,taluôncó\$1+e^{-w}>1\$,dẫnđến\$L(w)>0\$.Dođó,giátrịcậndướiđúnglà\$\underset{w\in \mathbb{R}}{inf}L(w)=0\$,nhưngkhôngtồntạibấtkỳđiểm\$w^{\ast }\in \mathbb{R}\$nàođể\$L(w^{\ast })=0\$.Tậpnghiệmtốiưuhoàntoànrỗng(\${\mathcal{X}}^{\ast }=\mathrm{\varnothing }\$).3.\ast \ast ÝnghĩasưphạmtrongAI\ast \ast :Đâylàhiệntượngđặctrưngtronghồiquylogistickhidữliệuphântáchtuyếntínhhoànhảo:Thuậttoántốiưusẽđẩytrọngsố\$w\to +\mathrm{\infty }\$đểxácsuấtdựđoántiếntới100$$

Bài tập 7: Khắc phục bằng Điều chuẩn L2 trong Hồi quy Logistic

Xét bài toán hồi quy logistic có số hạng điều chuẩn trọng số $L_2$:

$$L_{\mu }(w)=\sum _{i=1}^n\log (1+e^{-y_i{a}_i^{T}w})+\frac{\mu }{2}\parallel w{\parallel }_2^2,\mu >0,w\in {\mathbb{R}}^d.$$

1. Tính ${\mathrm{\nabla }}^2{L}_{\mu }(w)$ và chứng minh $L_{\mu }(w)$ lồi mạnh (strongly convex).
2. Chứng minh rằng bài toán luôn luôn tồn tại nghiệm tối ưu duy nhất trên ${\mathbb{R}}^d$.

Lời giải

1. Tính và lồi mạnh: Đặt $z_i=-y_i{a}_i^{T}w$. Đạo hàm của hàm thành phần ${\ell }_i(w)=\log (1+e^{-y_i{a}_i^{T}w})$ cho ma trận Hessian:

   $${\mathrm{\nabla }}^2{\ell }_i(w)=\frac{e^{-y_i{a}_i^{T}w}}{(1+e^{-y_i{a}_i^{T}w}{)}^2}{a}_i{a}_i^T=d_i{a}_i{a}_i^T,$$

   với $d_i=\sigma (y_i{a}_i^{T}w)(1-\sigma (y_i{a}_i^{T}w))>0$. Vì $a_i{a}_i^T⪰0$, của phần mất mát dữ liệu luôn :

   $$\sum _{i=1}^n{\mathrm{\nabla }}^2{\ell }_i(w)⪰0.$$

   Thành phần điều chuẩn $\frac{\mu }{2}\parallel w{\parallel }_2^2$ có bằng $\mu I$. Do đó:

   $${\mathrm{\nabla }}^2{L}_{\mu }(w)=\sum _{i=1}^n{d}_i{a}_i{a}_i^T+\mu I⪰\mu I\succ 0.$$

   Điều này chứng minh $L_{\mu }(w)$ lồi mạnh với $m=\mu >0$.

2. Chứng minh nghiệm tồn tại và duy nhất:

   • Tính duy nhất: Do mạnh kéo theo lồi ngặt, bài toán có nhiều nhất một điểm cực tiểu toàn cục.
   • Tính tồn tại: Vì $\log (1+e^z)>0$, ta có đánh giá chặn dưới:
     $$L_{\mu }(w)\ge \frac{\mu }{2}\parallel w{\parallel }_2^2.$$
     Khi $\parallel w{\parallel }_2\to \mathrm{\infty }$, ta có $L_{\mu }(w)\to \mathrm{\infty }$. Do đó, tập mức dưới:
     $$\mathcal{S}=\{w\in {\mathbb{R}}^d\mid L_{\mu }(w)\le L_{\mu }(0)\}$$
     là một tập đóng và bị chặn (compact) trong ${\mathbb{R}}^d$. Theo Định lý Weierstrass, hàm liên tục $L_{\mu }$ đạt giá trị nhỏ nhất trên tập compact $\mathcal{S}$. Mọi điểm ngoài $\mathcal{S}$ đều có giá trị lớn hơn $L_{\mu }(0)$, do đó điểm đạt giá trị nhỏ nhất trên $\mathcal{S}$ cũng chính là cực tiểu toàn cục trên toàn không gian ${\mathbb{R}}^d$.

   Kết hợp tính tồn tại và tính duy nhất, nghiệm tối ưu $w^{\ast }$ tồn tại và duy nhất. Điều chuẩn $L_2$ đã hóa giải hoàn toàn nghịch lý trôi dạt trọng số ở Bài 6!

Bài tập 8: Mô hình hóa Hệ thống Phân bố Công suất Chiếu sáng

Một hệ thống gồm $m$ bóng đèn được dùng để chiếu sáng $n$ khu vực. Gọi $p\in {\mathbb{R}}^m$ là công suất của các đèn. Độ rọi đo được tại $n$ khu vực được mô hình hóa qua hệ thức tuyến tính:

$$I=Ap(A\in {\mathbb{R}}_{+}^{n\times m}).$$

Mục tiêu là điều chỉnh công suất $p$ sao cho độ rọi thực tế $I$ bám sát độ rọi mong muốn $I_{\mathrm{des}}\in {\mathbb{R}}^n$, dưới giới hạn công suất trần của từng bóng đèn $0\le p_j\le p_{max}$ và giới hạn tổng công suất toàn hệ thống ${\mathbf{1}}^{T}p\le P_{\mathrm{total}}$.

1. Thiết lập bài toán tối ưu dưới dạng chuẩn tắc với tiêu chuẩn sai số bình phương nhỏ nhất.
2. Chứng minh và hàm mục tiêu của bài toán là lồi.
3. Nêu điều kiện để bài toán có nghiệm tối ưu duy nhất.

Lời giải

1. Thiết lập mô hình:
   $$\begin{array}{rl}& \text{minimize}\parallel Ap-I_{\mathrm{des}}{\parallel }_2^2\\ & \text{subject to}0\le p_j\le p_{max},j=1,\dots ,m,\\ & \phantom{\text{subject to}}\sum _{j=1}^m{p}_j\le P_{\mathrm{total}}.\end{array}$$
2. Chứng nhận tính lồi:
   • Hàm mục tiêu: Khai triển dạng toàn phương:
     $$f_0(p)=\parallel Ap-I_{\mathrm{des}}{\parallel }_2^2=p^T(A^{T}A)p-2(A^T{I}_{\mathrm{des}}{)}^{T}p+\parallel I_{\mathrm{des}}{\parallel }_2^2.$$
     là ${\mathrm{\nabla }}^2{f}_0(p)=2A^{T}A⪰0$, do đó hàm mục tiêu là hàm toàn phương lồi.
   • : Là giao của hộp siêu lập phương $[0,p_{max}{]}^m$ (giao của $2m$ nửa không gian) và nửa không gian tổng công suất $\{p\mid {\mathbf{1}}^{T}p\le P_{\mathrm{total}}\}$. Do giao của các là tập lồi, miền khả thi là một đa diện lồi compact (đóng và bị chặn).
   • Vì hàm mục tiêu liên tục trên miền compact khác rỗng (với giả thiết $P_{\mathrm{total}}\ge 0$), nghiệm tối ưu luôn luôn tồn tại theo Định lý Weierstrass.
3. Điều kiện nghiệm duy nhất: Hàm mục tiêu lồi ngặt khi và chỉ khi dương xác định: $A^{T}A\succ 0$, tương đương với việc $A$ có hạng cột đầy đủ ($\mathrm{rank}(A)=m\le n$). Khi đó, không có hai tổ hợp công suất khác nhau nào tạo ra cùng một phân bố ánh sáng, bảo đảm nghiệm tối ưu $p^{\ast }$ là duy nhất.

Bài tập 9: Chuỗi lập luận tối ưu hóa cho hàm Log-Sum-Exp điều quy

Xét $f(x)=\log (e^{x_1}+e^{x_2})+\frac{1}{2}\parallel x{\parallel }_2^2$ xác định trên ${\mathbb{R}}^2$.

1. Chứng minh $f(x)$ lồi mạnh (strongly convex).
2. Tận dụng tính đối xứng của bài toán để dự đoán nghiệm cực tiểu $x^{\ast }$, sau đó kiểm chứng bằng .
3. Giải thích vì sao điểm tìm được là điểm cực tiểu toàn cục duy nhất của bài toán.

Lời giải

1. Chứng minh lồi mạnh: Hàm Softmax Log-Sum-Exp $g(x)=\log (e^{x_1}+e^{x_2})$ có ${\mathrm{\nabla }}^{2}g(x)⪰0$ trên toàn không gian ${\mathbb{R}}^2$. Thành phần điều quy $\frac{1}{2}\parallel x{\parallel }_2^2$ có ma trận Hessian đúng bằng đơn vị $I$. Do đó, ma trận Hessian của tổng là ${\mathrm{\nabla }}^{2}f(x)={\mathrm{\nabla }}^{2}g(x)+I⪰I$. Điều này chứng minh $f(x)$ lồi mạnh với $m=1$.
2. Dự đoán và kiểm chứng: Do vai trò của hai biến $x_1$ và $x_2$ hoàn toàn bình đẳng và đối xứng qua đường phân giác $x_1=x_2$, ta dự đoán nghiệm tối ưu thỏa mãn $x_1^{\ast }=x_2^{\ast }=t$. Khi đó hàm số trở thành hàm một biến:
   $$h(t)=\log (2e^t)+\frac{1}{2}(2t^2)=\log 2+t+t^2.$$
   Đạo hàm $h^{\prime }(t)=1+2t=0⟺t=-0.5$. Ta kiểm chứng lại trên không gian hai chiều: của là:
   $$\mathrm{\nabla }f(x)=\left[\begin{array}{c}\frac{e^{x_1}}{e^{x_1}+e^{x_2}}+x_1\\ \frac{e^{x_2}}{e^{x_1}+e^{x_2}}+x_2\end{array}\right]=\mathrm{softmax}(x)+x.$$
   Tại điểm $x^{\ast }=(-0.5,-0.5{)}^T$, ta có $\mathrm{softmax}(x^{\ast })=(0.5,0.5{)}^T$, do đó:
   $$\mathrm{\nabla }f(x^{\ast })=\left[\begin{array}{c}0.5\\ 0.5\end{array}\right]+\left[\begin{array}{c}-0.5\\ -0.5\end{array}\right]=\left[\begin{array}{c}0\\ 0\end{array}\right].$$
   Điểm dự đoán thỏa mãn chính xác phương trình đạo hàm triệt tiêu. Giá trị nhỏ nhất tương ứng là $f(x^{\ast })=\log 2-0.25\approx 0.4431$.
3. Tính duy nhất toàn cục: Vì $f(x)$ là khả vi trên toàn bộ không gian ${\mathbb{R}}^2$, điểm có triệt tiêu $\mathrm{\nabla }f(x^{\ast })=0$ tự động là điểm cực tiểu toàn cục. Hơn nữa, do $f(x)$ lồi mạnh nên dương xác định khắp nơi (${\mathrm{\nabla }}^{2}f(x)\succ 0$), suy ra lồi ngặt và điểm cực tiểu toàn cục là duy nhất.

---

Tóm tắt cốt lõi

1. Bản chất của bài toán lồi: là và hàm mục tiêu là . Tính chất này loại bỏ triệt để nguy cơ rơi vào cực tiểu cục bộ: Mọi cực tiểu cục bộ đều là cực tiểu toàn cục.
2. Khối hình và Phép toán bảo toàn: Các miền ràng buộc phức tạp trong thực tế được thiết lập từ các khối hình cơ sở (siêu phẳng, nửa không gian, quả cầu, đa diện, nón ) thông qua phép giao, ảnh affine và phép phối cảnh.
3. Điều kiện vi phân và Nhận diện: có tiếp diện luôn nằm dưới đồ thị ($\mathrm{\nabla }f(x{)}^T(y-x)\le f(y)-f(x)$) và luôn (${\mathrm{\nabla }}^{2}f(x)⪰0$).
4. Điều kiện tối ưu tổng quát: Khi bài toán có ràng buộc, nghiệm tối ưu $x^{\ast }$ được chứng nhận bởi bất đẳng thức $\mathrm{\nabla }{f}_0(x^{\ast }{)}^T(y-x^{\ast })\ge 0$ với mọi $y$, ngay cả khi nghiệm nằm ở đường biên và không triệt tiêu.

---

Tài liệu tham khảo và Đọc thêm

Dành cho người học muốn nghiên cứu chuyên sâu về lý thuyết và hình học tối ưu lồi:

• Stephen Boyd & Lieven Vandenberghe, Convex Optimization, Cambridge University Press. Đọc kỹ Chương 1 (Tổng quan), Chương 2 ( và nón lồi), Chương 3 (, phép toán bảo toàn tính lồi, bất đẳng thức Jensen), Chương 4 (Bài toán tối ưu lồi và phân loại) và Chương 7 (Mô hình hóa hình học trong thống kê).
• R. Tyrrell Rockafellar, Convex Analysis, Princeton University Press. Tác phẩm kinh điển đặt nền móng giải tích hiện đại cho , và vi phân dưới (subgradient).

Tiếp theo: Bài 02: Phân loại các bài toán tối ưu lồi: LP, QP, SOCP và SDP.