Khóa Luận Tốt Nghiệp: Điều Kiện Tối Ưu Trong Bài Toán Cực Trị

Khóa luận trình bày các điều kiện tối ưu cho bài toán cực trị trong toán tin, giúp nâng cao hiểu biết và ứng dụng trong nghiên cứu.

• Tác giả: Nguyễn Minh Hiểu
• Người hướng dẫn: TS. Phạm Duy Khánh
• Trường học: Trường Đại Học Sư Phạm Thành Phố Hồ Chí Minh
• Chuyên ngành: Toán - Tin Học
• Đề tài: Điều Kiện Tối Ưu Trong Bài Toán Cực Trị
• Loại tài liệu: khóa luận tốt nghiệp
• Năm xuất bản: 2023
• Địa điểm: Thành Phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CÁM ƠN
• LỜI MỞ ĐẦU
• 1. CHƯƠNG 1: MỘT SỐ KIẾN THỨC CHUẨN BỊ
• 1.1. Giới hạn ngoài của tập hợp
• 1.2. Nón pháp tuyến
• 1.3. Dưới vi phân
• 1.3.1. Dưới vi phân Fréchet
• 2. CHƯƠNG 2: ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN KHÔNG RÀNG BUỘC VÀ CÓ RÀNG BUỘC TÙY Ý
• 3. CHƯƠNG 3: ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN CÓ RÀNG BUỘC PHIẾM HÀM
• 4. CHƯƠNG 4: KẾT QUẢ ĐẠT ĐƯỢC VÀ ĐỊNH HƯỚNG NGHIÊN CỨU TƯƠNG LAI
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Điều Kiện Tối Ưu Trong Bài Toán Cực Trị

Điều kiện tối ưu trong bài toán cực trị là một trong những khái niệm quan trọng trong toán học ứng dụng. Các bài toán này thường liên quan đến việc tìm cực tiểu hoặc cực đại của một hàm số dưới các điều kiện nhất định. Việc hiểu rõ về điều kiện tối ưu không chỉ giúp giải quyết các bài toán lý thuyết mà còn có ứng dụng thực tiễn trong nhiều lĩnh vực như kinh tế, kỹ thuật và khoa học máy tính.

1.1. Khái Niệm Cơ Bản Về Điều Kiện Tối Ưu

Điều kiện tối ưu được định nghĩa là các điều kiện cần và đủ để một điểm là cực trị của hàm số. Các điều kiện này thường được xây dựng dựa trên các đạo hàm của hàm số và có thể áp dụng cho nhiều loại hàm khác nhau.

1.2. Lịch Sử Phát Triển Của Bài Toán Cực Trị

Bài toán cực trị đã xuất hiện từ rất lâu trong lịch sử toán học. Các nhà toán học như Lagrange và Kuhn-Tucker đã đóng góp nhiều vào việc phát triển các phương pháp giải quyết bài toán này, tạo nền tảng cho các nghiên cứu hiện đại.

II. Vấn Đề Và Thách Thức Trong Việc Xác Định Điều Kiện Tối Ưu

Một trong những thách thức lớn nhất trong việc xác định điều kiện tối ưu là tính khả vi của hàm số. Nhiều bài toán thực tế có hàm mục tiêu không khả vi tại một số điểm, điều này làm cho việc áp dụng các điều kiện cổ điển trở nên khó khăn.

2.1. Các Vấn Đề Liên Quan Đến Hàm Không Khả Vi

Hàm không khả vi có thể gây khó khăn trong việc áp dụng các điều kiện tối ưu truyền thống. Việc tìm ra các phương pháp thay thế như dưới vi phân là cần thiết để giải quyết các bài toán này.

2.2. Thách Thức Trong Việc Xây Dựng Điều Kiện Chính Quy

Điều kiện chính quy là một yếu tố quan trọng trong việc xác định nghiệm chấp nhận được của bài toán. Việc tìm ra các điều kiện này phụ thuộc vào tập ràng buộc và có thể thay đổi theo từng bài toán cụ thể.

III. Phương Pháp Giải Quyết Bài Toán Cực Trị Với Điều Kiện Tối Ưu

Có nhiều phương pháp khác nhau để giải quyết bài toán cực trị, bao gồm phương pháp Lagrange và phương pháp gradient. Mỗi phương pháp có ưu điểm và nhược điểm riêng, phù hợp với từng loại bài toán.

3.1. Phương Pháp Lagrange Trong Bài Toán Cực Trị

Phương pháp Lagrange là một trong những phương pháp phổ biến nhất để tìm cực trị của hàm số có ràng buộc. Phương pháp này sử dụng các đa thức Lagrange để xây dựng hàm mục tiêu mới từ hàm gốc và các ràng buộc.

3.2. Phương Pháp Gradient Và Ứng Dụng Của Nó

Phương pháp gradient là một kỹ thuật mạnh mẽ trong tối ưu hóa, cho phép tìm kiếm cực trị bằng cách sử dụng thông tin về độ dốc của hàm số. Phương pháp này thường được áp dụng trong các bài toán lớn và phức tạp.

IV. Ứng Dụng Thực Tiễn Của Điều Kiện Tối Ưu Trong Nghiên Cứu

Điều kiện tối ưu không chỉ có giá trị lý thuyết mà còn có nhiều ứng dụng thực tiễn trong các lĩnh vực như kinh tế, kỹ thuật và khoa học máy tính. Việc áp dụng các điều kiện này giúp tối ưu hóa quy trình và nâng cao hiệu quả.

4.1. Ứng Dụng Trong Kinh Tế

Trong kinh tế, điều kiện tối ưu được sử dụng để tối đa hóa lợi nhuận hoặc tối thiểu hóa chi phí. Các nhà kinh tế học thường sử dụng các mô hình toán học để phân tích và dự đoán hành vi của thị trường.

4.2. Ứng Dụng Trong Kỹ Thuật

Trong kỹ thuật, điều kiện tối ưu giúp thiết kế các hệ thống hiệu quả hơn. Các kỹ sư sử dụng các phương pháp tối ưu hóa để cải thiện hiệu suất và giảm thiểu chi phí sản xuất.

V. Kết Luận Về Điều Kiện Tối Ưu Trong Bài Toán Cực Trị

Điều kiện tối ưu là một khái niệm quan trọng trong toán học và có nhiều ứng dụng thực tiễn. Việc hiểu rõ về các điều kiện này giúp giải quyết hiệu quả các bài toán cực trị và mở ra nhiều hướng nghiên cứu mới.

5.1. Tương Lai Của Nghiên Cứu Về Điều Kiện Tối Ưu

Nghiên cứu về điều kiện tối ưu vẫn đang tiếp tục phát triển. Các nhà toán học đang tìm kiếm các điều kiện mới và mạnh mẽ hơn để áp dụng cho các bài toán phức tạp hơn.

5.2. Tầm Quan Trọng Của Điều Kiện Tối Ưu Trong Toán Học

Điều kiện tối ưu không chỉ là một phần của lý thuyết toán học mà còn là công cụ quan trọng trong nhiều lĩnh vực khác nhau. Việc nắm vững các điều kiện này là cần thiết cho bất kỳ ai làm việc trong lĩnh vực toán học ứng dụng.

Nội dung chính

Bối cảnh và vấn đề nghiên cứu

Trong lịch sử toán học, lý thuyết tối ưu và bài toán tìm cực trị (cực tiểu hoặc cực đại địa phương và toàn cục của một hàm số với các điều kiện ràng buộc) giữ vị trí trung tâm trong toán ứng dụng lẫn toán lý thuyết. Đối với các bài toán quy hoạch phi tuyến (Nonlinear Programming - NLP), các phương pháp giải tích cổ điển phần lớn dựa trên công cụ đạo hàm riêng cấp một và cấp hai của các hàm khả vi liên tục ($C^1, C^2$). Tuy nhiên, giả thiết hàm mục tiêu và các hàm ràng buộc phải khả vi liên tục trên toàn miền xác định khiến phạm vi ứng dụng của giải tích cổ điển bị thu hẹp đáng kể, không thể áp dụng trực tiếp cho các lớp bài toán không trơn (nondifferentiable/nonsmooth) hoặc có tập ràng buộc phức tạp.

Để khắc phục hạn chế này, giải tích biến phân hiện đại đã phát triển các công cụ hình học và giải tích tổng quát như nón pháp tuyến (Fréchet, limiting) và dưới vi phân (subdifferential) nhằm thay thế vai trò của đạo hàm cổ điển. Khi bài toán có thêm các ràng buộc phiếm hàm, việc khảo sát nghiệm tối ưu đòi hỏi phải thiết lập các điều kiện tối ưu bậc nhất, tiêu biểu là hệ điều kiện Karush-Kuhn-Tucker (KKT). Tuy nhiên, điều kiện KKT chỉ trở thành điều kiện cần tại một nghiệm chấp nhận được khi nghiệm đó thỏa mãn một điều kiện chính quy (Constraint Qualification - CQ) thích hợp. Việc phân tích mối quan hệ cấu trúc giữa các điều kiện chính quy như LICQ, MFCQ, PLICQ và tiếp cận bài toán ràng buộc dưới góc nhìn bài toán hợp thành (composite optimization) là một hướng nghiên cứu lý thuyết quan trọng.

Khóa luận tốt nghiệp của tác giả Nguyễn Minh Hiếu (ngành Toán học, Trường Đại học Sư phạm Thành phố Hồ Chí Minh, thực hiện dưới sự hướng dẫn của TS. Phạm Duy Khánh và ThS. Võ Thành Phát vào tháng 4 năm 2023) tập trung giải quyết các nhiệm vụ nghiên cứu cụ thể:

1. Tổng hợp và hệ thống hóa các kiến thức cơ bản về giải tích biến phân trong không gian hữu hạn chiều, bao gồm giới hạn ngoài của dãy tập hợp, nón tiền pháp tuyến Fréchet, nón pháp tuyến limiting và các dạng dưới vi phân (Fréchet, Mordukhovich/basic, singular).
2. Thiết lập và chi tiết hóa các chứng minh cho điều kiện tối ưu bậc nhất của bài toán tối ưu không ràng buộc và bài toán có tập ràng buộc tùy ý thông qua công cụ dưới vi phân và hàm chỉ.
3. Phân tích bài toán tối ưu có ràng buộc phiếm hàm dưới mô hình bài toán composite; chứng minh mối liên hệ tương đương giữa điểm dừng dưới vi phân và hệ điều kiện Karush-Kuhn-Tucker (KKT).
4. Khảo sát, so sánh và làm rõ mối quan hệ giữa các điều kiện chính quy bậc nhất phổ biến gồm LICQ, MFCQ và PLICQ (điều kiện chính quy dưới vi phân hàm chỉ) thông qua các định lý toán học và hệ thống phản ví dụ cụ thể.

• Đối tượng nghiên cứu: Điều kiện tối ưu bậc nhất (dạng cần và đủ), nón pháp tuyến Fréchet và limiting, dưới vi phân Fréchet và Mordukhovich, bài toán composite, điều kiện KKT và các điều kiện chính quy (LICQ, MFCQ, PLICQ).
• Phạm vi nghiên cứu: Không gian Euclid hữu hạn chiều $\mathbb{R}^n$, các lớp hàm mở rộng nhận giá trị trong $\overline{\mathbb{R}} = (-\infty, +\infty]$ thỏa mãn tính nửa liên tục dưới, tính Lipschitz địa phương hoặc tính khả vi liên tục cấp một ($C^1$).

Cơ sở lý thuyết và phương pháp

Khóa luận được xây dựng dựa trên nền tảng của Giải tích biến phân (Variational Analysis), Giải tích lồi (Convex Analysis) và Lý thuyết quy hoạch phi tuyến (Nonlinear Programming). Tác giả khai thác các mô hình và khái niệm chuẩn mực từ các công trình chuyên khảo giải tích hiện đại (chẳng hạn tài liệu của B. S. Mordukhovich, R. T. Rockafellar, R. J-B. Wets):

• Khung khái niệm và công cụ giải tích:
  • Giới hạn ngoài của dãy tập hợp: $\limsup_{k \to \infty} C^k$.
  • Nón pháp tuyến: Nón tiền pháp tuyến Fréchet $\widehat{N}(x, C)$ và nón pháp tuyến limiting $N(x, C)$.
  • Dưới vi phân: Dưới vi phân Fréchet $\widehat{\partial}\varphi(x)$, dưới vi phân Mordukhovich/basic $\partial\varphi(x)$, và dưới vi phân singular $\partial^\infty\varphi(x)$.
  • Hàm chỉ của tập hợp: $\delta(x, \Omega)$ với giá trị bằng $0$ khi $x \in \Omega$ và $+\infty$ khi $x \notin \Omega$.
  • Hàm Lagrange và tập chỉ số ràng buộc hoạt động: $L(x, y) = \varphi_0(x) + \sum_{i=1}^m y_i \varphi_i(x)$ và $I(x) = {i \in {1, \dots, s} : \varphi_i(x) = 0}$.
  • Mô hình bài toán composite: $\min \varphi_0(x) + (\theta \circ g)(x)$, trong đó $\theta = \delta(\cdot, \Omega)$ là hàm chỉ trên tập nón trực giao $\Omega = \mathbb{R}_-^s \times {0}^{m-s}$.
• Phương pháp nghiên cứu: Tác giả sử dụng phương pháp nghiên cứu toán học thuần túy bao gồm:
  • Phương pháp phân tích - tổng hợp lý thuyết: Thu thập, đối chiếu và hệ thống hóa các định lý, mệnh đề giải tích biến phân từ các công trình nghiên cứu chuyên sâu.
  • Phương pháp diễn dịch logic và suy luận giải tích: Trình bày chi tiết từng bước chứng minh toán học, lấp đầy các khoảng trống suy luận trong tài liệu tham khảo gốc, kết nối lý thuyết giải tích lồi với trường hợp không lồi/không trơn.
  • Phương pháp xây dựng phản ví dụ (Counterexamples) và ví dụ phân tích: Thiết kế các bài toán tối ưu giải tích cụ thể trên $\mathbb{R}$ và $\mathbb{R}^2$ để kiểm tra tính khả thi, phân định ranh giới áp dụng giữa các điều kiện cần, điều kiện đủ và làm rõ tính không tương đương giữa các điều kiện chính quy.
• Nguồn dữ liệu: Các định lý, bổ đề, quy tắc tính toán giải tích và bài toán cực trị mẫu trong các tài liệu tham khảo giải tích toán học quốc tế.

Nội dung chính theo từng chương

Chương 1: Một số kiến thức chuẩn bị

Chương này trình bày hệ thống công cụ giải tích nền tảng phục vụ cho việc thiết lập các điều kiện tối ưu ở các chương tiếp theo.

• Giới hạn ngoài của tập hợp: Định nghĩa giới hạn ngoài của dãy tập hợp ${C^k}$ trong $\mathbb{R}^n$ là tập $\limsup_{k \to \infty} C^k = {x \mid \exists N \in \mathcal{N}\infty, \exists x^k \in C^k (k \in N): x^k \to x}$. Tác giả chứng minh Mệnh đề 1.6: tập giới hạn ngoài luôn là tập đóng và chỉ phụ thuộc vào bao đóng của các tập thành phần ($\operatorname{cl}(C^k) = \operatorname{cl}(D^k), \forall k \in \mathbb{N} \Rightarrow \limsup{k \to \infty} C^k = \limsup_{k \to \infty} D^k$).
• Nón pháp tuyến Fréchet và limiting: Định nghĩa nón tiền pháp tuyến Fréchet $\widehat{N}(\bar{x}, C)$ thông qua $\limsup_{x \xrightarrow{C} \bar{x}} \frac{\langle x^*, x - \bar{x} \rangle}{|x - \bar{x}|} \le 0$ và nón pháp tuyến limiting $N(\bar{x}, C) = \limsup_{x \to \bar{x}} \widehat{N}(x, C)$. Đối với điểm cô lập, tác giả đưa ra phân tích và quy ước $\widehat{N}(\bar{x}, C) = N(\bar{x}, C) = \mathbb{R}^n$. Tác giả tính toán chi tiết cho mặt cầu $C = {x \in \mathbb{R}^n \mid |x| = M}$ với $M > 0$, chứng minh rằng tại mọi $x \in C$, $\widehat{N}(x, C) = N(x, C) = {ax \mid a \in \mathbb{R}}$, tương ứng với đường thẳng đi qua $x$ và gốc tọa độ. Khi tập $C$ lồi địa phương quanh $\bar{x}$, nón pháp tuyến quy về nón pháp tuyến trong giải tích lồi.
• Dưới vi phân Fréchet và Mordukhovich: Dưới vi phân Fréchet $\widehat{\partial}\varphi(\bar{x})$ được định nghĩa qua giới hạn dưới $\liminf$, trong khi dưới vi phân Mordukhovich $\partial\varphi(\bar{x}) = {v \in \mathbb{R}^n \mid (v, -1) \in N((\bar{x}, \varphi(\bar{x})), \operatorname{epi}\varphi)}$ được định nghĩa thông qua nón pháp tuyến limiting của biểu đồ epigraph. Tác giả chứng minh các kết quả quan trọng:
  • Khi $\varphi$ lồi, cả hai dạng dưới vi phân đều trùng với dưới vi phân cổ điển của giải tích lồi.
  • Đối với hàm chỉ $\delta(\cdot, \Omega)$, $\widehat{\partial}\delta(\bar{x}, \Omega) = \widehat{N}(\bar{x}, \Omega)$ và $\partial\delta(\bar{x}, \Omega) = N(\bar{x}, \Omega)$.
  • Định lý liên hệ giới hạn: $\partial\varphi(\bar{x}) = \limsup_{x \xrightarrow{\varphi} \bar{x}} \widehat{\partial}\varphi(x)$.
  • Các quy tắc cộng (Sum Rule): Khi $\psi$ khả vi thì $\widehat{\partial}(\psi + \varphi)(\bar{x}) = \nabla\psi(\bar{x}) + \widehat{\partial}\varphi(\bar{x})$; khi $\psi$ khả vi liên tục $C^1$ thì $\partial(\psi + \varphi)(\bar{x}) = \nabla\psi(\bar{x}) + \partial\varphi(\bar{x})$.

Chương 2: Điều kiện tối ưu bậc nhất

Chương 2 áp dụng các cấu trúc dưới vi phân vào hai lớp bài toán tối ưu:

• Bài toán không có ràng buộc ($\min \varphi(x), x \in \mathbb{R}^n$): Định lý Fermat tổng quát khẳng định nếu $\bar{x}$ là cực tiểu địa phương của $\varphi$ thì $0 \in \widehat{\partial}\varphi(\bar{x})$ và $0 \in \partial\varphi(\bar{x})$. Khi $\varphi$ là hàm lồi, điều kiện này trở thành điều kiện cần và đủ cho cực tiểu toàn cục. Tác giả đưa ra ví dụ hàm $\varphi(x) = \begin{cases} 1, & x > 0 \ 0, & x = 0 \ -1, & x < 0 \end{cases}$ để minh họa rằng tại $x=0$, $0 \in \partial\varphi(0)$ nhưng $0$ không phải là cực tiểu địa phương, chứng minh rằng với hàm không lồi, điều kiện dừng dưới vi phân chỉ là điều kiện cần.
• Bài toán có ràng buộc tùy ý ($\min \varphi(x), x \in \Omega$): Bằng cách chuyển bài toán về dạng không ràng buộc tương đương $\min \varphi(x) + \delta(x, \Omega)$, tác giả thiết lập:
  • Nếu $\bar{x}$ là nghiệm địa phương và $\varphi$ khả vi tại $\bar{x}$ thì $-\nabla\varphi(\bar{x}) \in \widehat{N}(\bar{x}, \Omega)$.
  • Nếu $\varphi$ khả vi trong một lân cận của $\bar{x}$ thì $-\nabla\varphi(\bar{x}) \in N(\bar{x}, \Omega)$.
  • Khi $\varphi$ và $\Omega$ cùng lồi, điều kiện $-\nabla\varphi(\bar{x}) \in N(\bar{x}, \Omega)$ (hay $\langle \nabla\varphi(\bar{x}), x - \bar{x} \rangle \ge 0, \forall x \in \Omega$) là điều kiện cần và đủ cho nghiệm toàn cục.
  • Tác giả mở rộng kết quả cho hàm không khả vi: chứng minh hàm chỉ $\delta(x, \Omega)$ là Lipschitz địa phương tại $\bar{x} \in \Omega$ khi và chỉ khi $\bar{x} \in \operatorname{int}(\Omega)$. Kết hợp với luật cộng cho hàm Lipschitz, nếu $\varphi$ Lipschitz địa phương tại $\bar{x}$ và $\Omega$ đóng địa phương quanh $\bar{x}$ thì điều kiện cần cho nghiệm địa phương là $0 \in \partial\varphi(\bar{x}) + N(\bar{x}, \Omega)$.

Chương 3: Điều kiện tối ưu bậc nhất cho bài toán có ràng buộc phiếm hàm

Chương 3 tập trung vào bài toán quy hoạch phi tuyến có ràng buộc bất đẳng thức và đẳng thức: $$\min \varphi_0(x) \quad \text{với } \varphi_i(x) \le 0 ; (i=1,\dots,s), \quad \varphi_i(x) = 0 ; (i=s+1,\dots,m)$$ trong đó các hàm $\varphi_i$ thuộc lớp $C^1$.

• Góc nhìn bài toán composite: Bài toán được đưa về dạng $\min \varphi_0(x) + \delta(g(x), \Omega)$ với $\Omega = \mathbb{R}_-^s \times {0}^{m-s}$ và $g(x) = (\varphi_1(x), \dots, \varphi_m(x))^T$. Dưới vi phân của hàm chỉ trên tập tích $\Omega$ được tính cụ thể: $$\partial\delta(g(\bar{x}), \Omega) = N(g(\bar{x}), \Omega) = F_1(\varphi_1(\bar{x})) \times \dots \times F_m(\varphi_m(\bar{x}))$$ với $F_i(\varphi_i(\bar{x})) = [0, +\infty)$ nếu $\varphi_i(\bar{x}) = 0$ ($i=1,\dots,s$), $F_i = {0}$ nếu $\varphi_i(\bar{x}) < 0$ ($i=1,\dots,s$), và $F_i = \mathbb{R}$ ($i=s+1,\dots,m$).
• Điều kiện chính quy dưới vi phân hàm chỉ (PLICQ): Điều kiện chính quy được định nghĩa là $\partial\delta(g(\bar{x}), \Omega) \cap \ker \nabla g(\bar{x})^* = {0}$, tương đương với: $$\sum_{i \in I(\bar{x}) \cup {s+1,\dots,m}} \alpha_i \nabla\varphi_i(\bar{x}) = 0 \quad \text{và} \quad \alpha_i \ge 0 ; (\forall i \in I(\bar{x})) \implies \alpha_i = 0 ; (\forall i \in I(\bar{x}) \cup {s+1,\dots,m})$$
• Điều kiện Karush-Kuhn-Tucker (KKT): Tác giả chứng minh Mệnh đề 3.13: Nếu $\bar{x}$ thỏa mãn điều kiện chính quy PLICQ thì điều kiện điểm dừng $0 \in \partial(\varphi_0 + \delta(g(\cdot), \Omega))(\bar{x})$ tương đương với việc tồn tại vector nhân tử Lagrange $\bar{y} \in \mathbb{R}+^s \times \mathbb{R}^{m-s}$ sao cho: $$\nabla_x L(\bar{x}, \bar{y}) = \nabla\varphi_0(\bar{x}) + \sum{i=1}^m \bar{y}_i \nabla\varphi_i(\bar{x}) = 0 \quad \text{và} \quad \langle \bar{y}, g(\bar{x}) \rangle = 0 \quad (\bar{y}_i \varphi_i(\bar{x}) = 0, ; \forall i=1,\dots,m)$$
• Phân tích các điều kiện chính quy (LICQ, MFCQ, PLICQ):
  • LICQ (Linear Independence CQ): Hệ vector gradient ${\nabla\varphi_i(\bar{x})}_{i \in I(\bar{x}) \cup {s+1,\dots,m}}$ độc lập tuyến tính.
  • MFCQ (Mangasarian-Fromovitz CQ): ${\nabla\varphi_i(\bar{x})}_{i=s+1}^m$ độc lập tuyến tính và tồn tại $u \in \mathbb{R}^n$ sao cho $\langle \nabla\varphi_i(\bar{x}), u \rangle < 0$ ($\forall i \in I(\bar{x})$), $\langle \nabla\varphi_i(\bar{x}), u \rangle = 0$ ($\forall i = s+1,\dots,m$).
  • Tác giả chứng minh rằng $LICQ \implies MFCQ \iff PLICQ$. Chiều ngược lại không đúng trong trường hợp có ràng buộc bất đẳng thức, được minh chứng qua các ví dụ cụ thể (như bài toán với $\varphi_1(x) = x \le 0, \varphi_2(x) = 2x \le 0$ tại $x=0$, thỏa PLICQ và MFCQ nhưng vi phạm LICQ).
  • Tác giả xây dựng ví dụ bài toán bình phương ràng buộc $(\min x_1 + x_2$ với $(x_1^2 + x_2^2 - 1)^2 = 0$) để chỉ ra rằng khi điều kiện chính quy vi phạm, hệ KKT trở nên vô nghiệm dù bài toán có cực tiểu địa phương rõ ràng.

Chương 4: Tổng kết và bàn luận

Chương 4 tổng kết các kết quả đạt được trong toàn bộ khóa luận và đề xuất định hướng nghiên cứu tiếp theo về lý thuyết tối ưu phi tuyến.

Kết quả và đóng góp

Khóa luận đã thu được các kết quả lý thuyết và ví dụ giải tích sau:

1. Tổng hợp có hệ thống các công cụ dưới vi phân: Làm rõ mối quan hệ giữa nón tiền pháp tuyến Fréchet, nón pháp tuyến limiting và dưới vi phân Mordukhovich; thiết lập các công thức giải tích cho hàm chỉ trên tập đóng và tập lồi.
2. Thiết lập điều kiện tối ưu thống nhất cho bài toán phiếm hàm: Chứng minh thành công tính tương đương giữa điều kiện dừng dưới vi phân của bài toán composite và hệ điều kiện Karush-Kuhn-Tucker thông qua hàm Lagrange.
3. Phân định rõ ràng mối quan hệ giữa các điều kiện chính quy bậc nhất: Tổng hợp và chứng minh đầy đủ các mối liên hệ logic giữa ba điều kiện chính quy quan trọng (LICQ, MFCQ, PLICQ) tùy thuộc vào cấu trúc của tập ràng buộc:

Loại bài toán ràng buộc	Mối quan hệ giữa các điều kiện chính quy
Có cả ràng buộc đẳng thức và bất đẳng thức	$\text{LICQ} \implies \text{MFCQ} \iff \text{PLICQ}$ (Chiều ngược lại $\text{PLICQ} \implies \text{LICQ}$ không đúng)
Chỉ có ràng buộc bất đẳng thức	$\text{LICQ} \implies \text{MFCQ} \iff \text{PLICQ}$ (Chiều ngược lại không đúng)
Chỉ có ràng buộc đẳng thức	$\text{LICQ} \iff \text{MFCQ} \iff \text{PLICQ}$ (Các điều kiện tương đương nhau)

4. Đóng góp về mặt trình bày và minh họa: Tác giả đã chi tiết hóa các bước chứng minh toán học vốn được viết cô đọng hoặc lược bớt trong các tài liệu tham khảo gốc, đồng thời xây dựng hệ thống ví dụ giải tích và phản ví dụ tường minh (trên không gian $\mathbb{R}$ và $\mathbb{R}^2$), giúp làm rõ bản chất hình học của nón pháp tuyến và cơ chế kiểm tra tính chính quy của nghiệm.

Hạn chế và hướng nghiên cứu tiếp

• Hạn chế: Khóa luận chỉ dừng lại ở việc khảo sát không gian hữu hạn chiều $\mathbb{R}^n$; các điều kiện tối ưu chỉ xét ở bậc nhất (First-order optimality conditions); các hàm trong bài toán phiếm hàm chủ yếu yêu cầu tính khả vi liên tục cấp một ($C^1$) khi thiết lập KKT.
• Hướng nghiên cứu tiếp:
  • Mở rộng khảo sát điều kiện tối ưu bậc hai (Second-order optimality conditions) sử dụng dưới vi phân bậc hai và đạo hàm biến phân.
  • Nghiên cứu các điều kiện chính quy yếu hơn (chẳng hạn như NNAMCQ, CPLD, RCQ) cho bài toán quy hoạch phi tuyến.
  • Mở rộng các kết quả giải tích biến phân sang không gian vô hạn chiều (không gian Banach, Asplund) phục vụ bài toán điều khiển tối ưu.

Giá trị tham khảo

Khóa luận là tài liệu tham khảo hữu ích cho:

• Sinh viên, học viên cao học các ngành Toán học, Toán ứng dụng, Toán - Tin học đang học tập và nghiên cứu các học phần Giải tích biến phân, Giải tích lồi, Lý thuyết tối ưu và Quy hoạch phi tuyến.
• Người nghiên cứu muốn tìm kiếm tài liệu diễn giải chi tiết từng bước chứng minh từ các công trình kinh điển của Rockafellar, Wets và Mordukhovich.
• Các nội dung đáng tham khảo nhất bao gồm: phương pháp tính nón pháp tuyến cho mặt cầu và tập tích Descartes; kỹ thuật chuyển đổi bài toán phiếm hàm sang bài toán composite; và các phản ví dụ phân biệt LICQ, MFCQ, PLICQ trong Chương 3.

Câu hỏi thường gặp

1. Khóa luận quy ước nón pháp tuyến tại điểm cô lập của một tập hợp như thế nào và vì sao? Tại điểm cô lập $\bar{x}$ của tập $C$, do không thể chọn được dãy $u^k \to \bar{x}$ với $u^k \ne \bar{x}$ để lấy giới hạn theo định nghĩa, khóa luận phân tích và đưa ra quy ước $\widehat{N}(\bar{x}, C) = N(\bar{x}, C) = \mathbb{R}^n$.

2. Nón pháp tuyến của mặt cầu $C = {x \in \mathbb{R}^n \mid |x| = M}$ với $M > 0$ có dạng hình học như thế nào? Tại mọi điểm $x \in C$, cả nón tiền pháp tuyến Fréchet và nón pháp tuyến limiting đều trùng nhau và bằng đường thẳng đi qua $x$ cùng gốc tọa độ: $\widehat{N}(x, C) = N(x, C) = {ax \mid a \in \mathbb{R}}$.

3. Vì sao điều kiện $0 \in \partial\varphi(\bar{x})$ không đảm bảo $\bar{x}$ là cực tiểu địa phương đối với hàm tùy ý? Vì đối với hàm không lồi, điều kiện dừng dưới vi phân $0 \in \partial\varphi(\bar{x})$ chỉ là điều kiện cần. Khóa luận đưa ra ví dụ hàm dấu $\varphi(x) = \operatorname{sgn}(x)$ trên $\mathbb{R}$, tại $x=0$ có $\partial\varphi(0) = {0}$ chứa phần tử $0$, nhưng hàm không đạt cực tiểu địa phương tại điểm này.

4. Điều kiện chính quy PLICQ được định nghĩa như thế nào trong bài toán composite? Đối với bài toán composite $\min \varphi_0(x) + \delta(g(x), \Omega)$, điều kiện chính quy dưới vi phân hàm chỉ (PLICQ) tại nghiệm chấp nhận được $\bar{x}$ được định nghĩa bằng đẳng thức giao tập hợp: $\partial\delta(g(\bar{x}), \Omega) \cap \ker \nabla g(\bar{x})^* = {0}$.

5. Điều gì xảy ra khi áp dụng điều kiện KKT cho một bài toán không thỏa mãn điều kiện chính quy? Khi nghiệm cực tiểu địa phương vi phạm điều kiện chính quy, hệ điều kiện KKT có thể bị vô nghiệm (không tồn tại nhân tử Lagrange $\bar{y}$). Khóa luận minh họa điều này qua bài toán $\min x_1 + x_2$ với ràng buộc $(x_1^2 + x_2^2 - 1)^2 = 0$, tại nghiệm tối ưu $(-1/\sqrt{2}, -1/\sqrt{2})$ hệ KKT dẫn đến đẳng thức vô lý $1 = 0$.

Kết luận

Khóa luận tốt nghiệp của tác giả Nguyễn Minh Hiếu đã hệ thống hóa và làm sâu sắc cơ sở lý thuyết giải tích biến phân hiện đại thông qua các công cụ nón pháp tuyến và dưới vi phân. Tác giả đã chứng minh chặt chẽ các điều kiện tối ưu bậc nhất cho các lớp bài toán không ràng buộc, có ràng buộc tùy ý và ràng buộc phiếm hàm dưới mô hình bài toán composite. Đặc biệt, công trình đã phân tích toàn diện mối liên hệ thứ bậc giữa các điều kiện chính quy LICQ, MFCQ và PLICQ cùng vai trò quyết định của chúng đối với hệ điều kiện Karush-Kuhn-Tucker. Đây là một tài liệu chuyên khảo có giá trị sư phạm và học thuật cao cho việc nghiên cứu lý thuyết tối ưu không trơn.

Trích đoạn nội dung tài liệu

Chương 1 Một số kién thức chuẩn bị 1.1 Giới hạn ngoài của tập hợp Trong phần này, người làm trình bày những phần kiến thức cơ bản về giới hạn ngoài của tập hợp. Giới hạn ngoài của dãy tập hợp được sử dụng trong các khái niệm về nón pháp tuyên được định nghĩa cho tập tùy ý như một công cụ tính toán. Ta bắt đầu bằng các định nghĩa về giới hạn trong và giới hạn ngoài của dãy các tập hợp Định nghĩa 1.1 (Giới hạn ngoài của tập hợp) Cho một day các tập hợp (Ce là các tập con của R". Giới hạn ngoài (outer limit) của đấy này, ký hiệu limsup C* ` k—=©o là tập C* := {x| JN € .#⁄Š, 3x" € CÍ(k €N): x* > x}, limsup k=»os trong đó NZ ={N CN:N vô han}.2 Trong trường hợp C* # 0 với mọi k € N, các giới hạn trong và giới ae # a ca? = han ngoài có thé biéu điện như sau lim sup C* = {x| 3x* €C*(k EN): đấy này có đấy con hội tụ về x}.

k-»oo Ta xét ví dụ tính toán giới hạn ngoài của day các tập hợp như sau.3 Xét day tập hợp {C*}¿¿x cho bởi trong BR cho bởi công thức sau ke [0, k] ,klẻ ~ |Í[-œ&-—1),0] ,k chan’ Khi đó lim sup CẺ = R. GIỚI HAN NGOÀI CUA TAP HỢP Minh hoa hình hoc cho ví du này có thể tham khảo [4| Figure 4-1(b), Trang 110).C* fee ‹ Ä9Z/07/00)9////2/0000900000000900/7009/0//2077/05, c Khác với giới han về điểm, khi xét dãy các tập hợp C* = C cho trước, lim sup C* k=soo có thể khác tập Œ. Ta xem ví dụ sau.4 Xét đấy tập hợp {C*}, € {N} trong R cho bởi Ck = C = (0, 00),kK EN. Ta thấy rằng lim sup CÈ = {x| 3x* C*(k EN): đấy này có day con hội tụ về x} k- 00 = {x| 3(xŸ) CC: x* 4 x} =cl(C)=[0, co).

Dễ thấy rằng lim supC* éC. k=ce Trong cả hai ví dụ trên, ta thay rằng lim sup C* đều là tập đóng. Trong 4 Exercise k—co 4.2(b)-Trang 110] có để cập một tính chất chỉ ra rằng các tập giới hạn trong và ngoài là các tập đóng.5 Cho một day các tập hợp (CỄ);e;; là các tập con của R". Khi đó lim sup c* = a cl) ct.

k=00 NES, kEN Hon nữa, ta suy ra được tập gidi hạn ngoài la tập đóng. Từ Mệnh đẻ ta có thêm một kết quả quan trọng được trình bày ở (4) Propo- sition 4. NON PHÁP TUYẾN Mệnh dé 1.6 Với mọi day tập hợp (C*),<. là các tập con của IR", tập giới han ngoài lim sup CỄ là các tập đóng và chỉ phụ thuộc vào bao đóng của các tập C*, theo k=»eo nghĩa như sau cl(C*) = cl(D*), ¥KEN => lim sup C* = liminf D*.

k—»eo keo Kết quả này hiện tại với người làm phục vụ cho việc tính toán là chủ yếu, khi mà việc tính giới hạn của một dãy các tập hợp có thể thông qua một dãy các tập hợp khác có bao đóng trùng nhau. Chẳng hạn, nêu xét dãy tập hợp {CÝ}, € {N} trong I cho bởi qn(,e),k lẻ; 1 > C.k chan 1 s thì ta có thé tìm giới hạn day tập hop nói trên thông qua day {C*}, {N} trong IR cho bởi ct=| 7,00), ken.2 Nón pháp tuyên Trong phan này, người làm trình bày các định nghĩa về pháp tuyến Fréchet, nón tiền pháp tuyến, nón pháp tuyến limiting, cũng như một số tính chất liên quan các đối tượng này. Dé bắt đầu, trong phan này người làm sử dụng ký hiệu x 4 XxX, xEN Lưu ý với ký hiệu nay, x không nhất thiết phải khác X.