Khóa Luận: Phương Pháp Số Giải Bài Toán Tối Ưu Phi Tuyến

Khóa luận về phương pháp số giải bài toán tối ưu phi tuyến. Nghiên cứu các thuật toán hiệu quả, ứng dụng trong toán tin và tối ưu hóa.

• Tác giả: Mai Đức Thanh
• Người hướng dẫn: TS. Trịnh Công Diệu
• Trường học: Trường Đại học Sư Phạm - TP Hồ Chí Minh
• Chuyên ngành: Toán - Tin
• Đề tài: Một Vài Phương Pháp Số Giải Bài Toán Tối Ưu Phi Tuyến
• Loại tài liệu: Luận văn tốt nghiệp
• Năm xuất bản: 2002
• Địa điểm: TP Hồ Chí Minh

Mục lục chi tiết

• MỤC LỤC
• I. Chương mở đầu
• I.1. Bài toán tối tu và phương pháp số
• I.2. Phương pháp số cho bai toán tối ưu phi tuyến không điều kiện
• 1. CHƯƠNG I : Phương pháp Gradient
• 1.1. Phương pháp giảm nhanh
• 1.2. Biến thể phương pháp
• 1.3. Phương pháp Gradient mở rộng
• 2. Chương II : Phương pháp Newton
• 2.1. Phương pháp Newton
• 2.2. Biến thể phương pháp
• 3. Chương III : Một số áp dụng
• 3.1. Cực tiểu hóa ham bậc hai
• 3.2. Tinh khoảng cách trong không gian Euclit n chiều
• 4. Chương IV : Thuật toán hóa các phương pháp và một số chương trình máy tính
• 4.1. Thuật toán hóa các phương pháp
• 4.2. Một số chương trình bằng ngôn ngữ Pascal
• Kết luận
• Tài liệu tham khảo

Tóm tắt

I. Tối Ưu Phi Tuyến Là Gì Tổng Quan Về Phương Pháp Số Giải

Tối ưu phi tuyến là một nhánh quan trọng của vận trù học và toán học ứng dụng, tập trung vào việc tìm giá trị cực tiểu hoặc cực đại của một hàm mục tiêu (objective function) mà trong đó, hàm mục tiêu hoặc các ràng buộc (hoặc cả hai) đều không phải là tuyến tính. Khác với tối ưu tuyến tính có thể giải quyết bằng các thuật toán hiệu quả như Simplex, bài toán tối ưu hóa phi tuyến thường phức tạp hơn đáng kể. Các bài toán này xuất hiện trong hầu hết mọi lĩnh vực, từ kỹ thuật, tài chính, logistics cho đến ứng dụng tối ưu hóa trong học máy. Do tính phức tạp của chúng, việc tìm ra nghiệm giải tích chính xác thường là bất khả thi. Đây là lúc các phương pháp số phát huy vai trò. Phương pháp số không tìm kiếm một nghiệm chính xác tuyệt đối mà thay vào đó, xây dựng một dãy các điểm xấp xỉ {x_k} hội tụ về điểm cực tiểu cần tìm. Quá trình này được thực hiện lặp đi lặp lại, mỗi bước cải thiện giá trị của hàm mục tiêu cho đến khi đạt được một tiêu chí dừng thỏa đáng. Hiệu quả của một phương pháp số được đánh giá dựa trên các yếu tố quan trọng như tốc độ hội tụ của thuật toán, chi phí tính toán ở mỗi vòng lặp và khả năng xử lý các loại hàm và ràng buộc khác nhau. Trong phạm vi bài viết này, chúng ta sẽ tập trung vào các phương pháp số giải bài toán tối ưu phi tuyến không ràng buộc, một nền tảng cơ bản để hiểu các vấn đề phức tạp hơn.

1.1. Khái niệm cốt lõi về bài toán tối ưu hóa phi tuyến

Một bài toán tối ưu hóa phi tuyến không ràng buộc có dạng tổng quát là tìm giá trị nhỏ nhất của hàm số f(x), hay min{f(x) : x ∈ ℝⁿ}, trong đó f là một hàm phi tuyến từ không gian ℝⁿ vào ℝ. Hàm f được gọi là hàm mục tiêu. Điểm x* mà tại đó f(x*) đạt giá trị nhỏ nhất được gọi là điểm cực tiểu. Việc giải bài toán này đòi hỏi các công cụ từ giải tích số và lý thuyết tối ưu. Một trong những thách thức chính là sự tồn tại của nhiều điểm cực tiểu. Các thuật toán cần có khả năng phân biệt giữa cực tiểu toàn cục và cực tiểu địa phương. Cực tiểu địa phương là điểm mà giá trị hàm số nhỏ hơn tất cả các điểm lân cận, trong khi cực tiểu toàn cục là điểm có giá trị hàm số nhỏ nhất trên toàn bộ miền xác định. Hầu hết các phương pháp số chỉ đảm bảo tìm thấy cực tiểu địa phương. Tuy nhiên, trong nhiều ứng dụng thực tế, một điểm cực tiểu địa phương đủ tốt đã mang lại giá trị sử dụng cao.

1.2. Tại sao cần phương pháp số cho lập trình phi tuyến

Đối với các hàm đơn giản, việc tìm cực tiểu có thể được thực hiện bằng cách giải phương trình đạo hàm bằng không (f'(x) = 0). Tuy nhiên, trong lập trình phi tuyến, hệ phương trình này thường rất phức tạp và không có lời giải giải tích. Ngay cả khi tìm được điểm dừng (điểm có đạo hàm bằng 0), việc kiểm tra xem nó là cực tiểu, cực đại hay điểm yên ngựa cũng đòi hỏi phân tích ma trận Hessian (ma trận đạo hàm cấp hai), vốn rất tốn kém về mặt tính toán. Các phương pháp số cung cấp một cách tiếp cận thực tế và hiệu quả hơn. Chúng bắt đầu từ một điểm dự đoán ban đầu và di chuyển từng bước theo một hướng làm giảm giá trị của hàm mục tiêu. Quá trình này được lặp lại cho đến khi sự cải thiện không còn đáng kể. Cách tiếp cận này đặc biệt hữu ích khi có sự hỗ trợ của máy tính, cho phép giải quyết các bài toán quy mô lớn mà phương pháp giải tích không thể xử lý.

II. Thách Thức Lớn Nhất Của Tối Ưu Phi Tuyến Không Ràng Buộc

Giải quyết các bài toán tối ưu phi tuyến không chỉ đơn thuần là áp dụng một công thức. Quá trình này tiềm ẩn nhiều thách thức đòi hỏi sự hiểu biết sâu sắc về cấu trúc của bài toán và bản chất của các thuật toán. Thách thức đầu tiên và phổ biến nhất là vấn đề cực tiểu địa phương. Các thuật toán lặp, đặc biệt là những thuật toán dựa trên gradient, có xu hướng 'đi xuống dốc' và dễ dàng bị kẹt tại một thung lũng gần nhất, vốn có thể không phải là điểm thấp nhất trên toàn bộ 'bản đồ'. Vấn đề này đặc biệt nghiêm trọng trong các lĩnh vực như huấn luyện mạng nơ-ron sâu, nơi không gian lời giải có vô số cực tiểu địa phương. Thách thức thứ hai là tốc độ hội tụ của thuật toán. Một số phương pháp có thể hội tụ rất chậm, đòi hỏi hàng ngàn, thậm chí hàng triệu vòng lặp để đạt được độ chính xác mong muốn, gây tốn kém thời gian và tài nguyên máy tính. Ngược lại, các phương pháp hội tụ nhanh hơn thường yêu cầu tính toán phức tạp hơn ở mỗi bước, chẳng hạn như tính toán và nghịch đảo ma trận Hessian. Sự đánh đổi giữa tốc độ hội tụ và chi phí tính toán mỗi vòng lặp là một yếu tố cốt lõi khi lựa chọn phương pháp tối ưu. Cuối cùng, sự ổn định của thuật toán cũng là một vấn đề. Việc lựa chọn các tham số như kích thước bước (learning rate) không phù hợp có thể khiến thuật toán phân kỳ hoặc dao động quanh điểm tối ưu mà không bao giờ hội tụ.

2.1. Phân biệt cực tiểu toàn cục và cực tiểu địa phương

Trong một bài toán tối ưu, một điểm x* được gọi là cực tiểu địa phương nếu tồn tại một lân cận U của x* sao cho f(x*) ≤ f(x) với mọi x thuộc U. Ngược lại, x* được gọi là cực tiểu toàn cục nếu f(x*) ≤ f(x) với mọi x trong toàn bộ miền xác định. Hầu hết các thuật toán kinh điển như Gradient Descent chỉ đảm bảo tìm được điểm dừng, mà điểm này có thể là một cực tiểu địa phương. Việc tìm kiếm cực tiểu toàn cục trong một bài toán phi lồi tổng quát là một vấn đề NP-hard. Các kỹ thuật để giải quyết vấn đề này bao gồm khởi tạo thuật toán từ nhiều điểm khác nhau, hoặc sử dụng các phương pháp xác suất như Simulated Annealing hay thuật toán di truyền. Trong các bài toán tối ưu lồi (convex optimization), mọi cực tiểu địa phương cũng chính là cực tiểu toàn cục, giúp đơn giản hóa bài toán đáng kể.

2.2. Đánh giá tốc độ hội tụ của thuật toán tối ưu

Tốc độ hội tụ mô tả mức độ nhanh chóng mà dãy lặp {x_k} tiến gần đến nghiệm tối ưu x*. Có ba loại tốc độ hội tụ chính. Tốc độ hội tụ tuyến tính (linear rate) có dạng ||x_{k+1} - x*|| ≤ q * ||x_k - x*|| với 0 < q < 1. Đây là tốc độ hội tụ của phương pháp Gradient Descent trong điều kiện thông thường. Tốc độ siêu tuyến tính (superlinear rate) có q_k → 0, nghĩa là tốc độ hội tụ ngày càng nhanh. Các phương pháp tựa-Newton (Quasi-Newton) như thuật toán BFGS thường đạt được tốc độ này. Cuối cùng, tốc độ bậc hai (quadratic rate) có dạng ||x_{k+1} - x*|| ≤ C * ||x_k - x*||², nghĩa là số chữ số chính xác tăng gấp đôi sau mỗi vòng lặp. Phương pháp Newton-Raphson cổ điển có thể đạt được tốc độ hội tụ bậc hai khi ở đủ gần nghiệm, nhưng đòi hỏi chi phí tính toán cao.

III. Phương Pháp Gradient Descent Hướng Dẫn Giải Tối Ưu Phi Tuyến

Phương pháp Gradient Descent, hay còn gọi là phương pháp giảm nhanh nhất (Steepest Descent), là một trong những thuật toán lặp đơn giản và phổ biến nhất để giải bài toán tối ưu phi tuyến không ràng buộc. Ý tưởng cốt lõi của phương pháp này rất trực quan: tại một điểm bất kỳ, thuật toán sẽ di chuyển theo hướng ngược lại với vector gradient của hàm mục tiêu tại điểm đó. Vector gradient f'(x) luôn chỉ về hướng mà hàm số tăng nhanh nhất, do đó, di chuyển theo hướng -f'(x) sẽ đảm bảo giá trị hàm số giảm nhanh nhất (ít nhất là trong một lân cận đủ nhỏ). Công thức cập nhật của thuật toán có dạng: x_{k+1} = x_k - α_k * f'(x_k). Trong đó, x_k là điểm hiện tại, f'(x_k) là vector gradient tại x_k, và α_k là một số dương được gọi là kích thước bước (step size) hay tốc độ học (learning rate). Việc lựa chọn α_k là một khâu cực kỳ quan trọng. Nếu α_k quá nhỏ, thuật toán sẽ hội tụ rất chậm. Nếu α_k quá lớn, thuật toán có thể 'vọt' qua điểm cực tiểu và thậm chí gây ra phân kỳ. Phương pháp Gradient Descent được chứng minh là hội tụ về một điểm dừng dưới các điều kiện khá rộng của hàm mục tiêu, chẳng hạn như hàm bị chặn dưới và có đạo hàm thỏa mãn điều kiện Lipschitz. Tuy nhiên, tốc độ hội tụ của nó chỉ là tuyến tính, có thể không hiệu quả đối với các bài toán có độ cong lớn.

3.1. Nguyên lý hoạt động của phương pháp giảm nhanh nhất

Nguyên lý của phương pháp giảm nhanh nhất dựa trên khai triển Taylor bậc nhất. Trong lân cận của điểm x_k, giá trị của hàm có thể được xấp xỉ bởi f(x) ≈ f(x_k) + <f'(x_k), x - x_k>. Để f(x) nhỏ hơn f(x_k), ta cần tích vô hướng <f'(x_k), x - x_k> là một số âm. Điều này đạt được hiệu quả nhất khi vector dịch chuyển (x - x_k) ngược hướng với vector gradient f'(x_k). Do đó, hướng di chuyển p_k = -f'(x_k) được chọn. Sau khi xác định hướng, bước tiếp theo là xác định độ dài bước đi α_k. Có nhiều chiến lược để chọn α_k, từ việc chọn một hằng số cố định, đến các phương pháp tìm kiếm theo đường thẳng (line search) để tìm α_k tối ưu nhằm cực tiểu hóa hàm f(x_k + α * p_k). Thuật toán sẽ dừng lại khi norm của vector gradient ||f'(x_k)|| đủ nhỏ, cho thấy đã tiến gần đến một điểm dừng.

3.2. Biến thể và phương pháp Gradient mở rộng

Để cải thiện hiệu suất, nhiều biến thể của Gradient Descent đã ra đời. Stochastic Gradient Descent (SGD) và Mini-batch Gradient Descent là các biến thể phổ biến trong học máy, giúp tăng tốc độ tính toán bằng cách ước tính gradient trên một mẫu dữ liệu nhỏ thay vì toàn bộ tập dữ liệu. Các phương pháp như Momentum và Adam thêm vào các thành phần 'quán tính' để giúp thuật toán vượt qua các điểm yên ngựa và các vùng 'cao nguyên' phẳng. Ngoài ra, tài liệu của Mai Đức Thanh (2002) còn đề cập đến 'Phương pháp Gradient mở rộng', trong đó hướng di chuyển được xác định bởi p_k = -F * f'(x_k), với F là một ma trận đối xứng xác định dương. Khi F là ma trận đơn vị, ta có phương pháp Gradient thông thường. Việc lựa chọn ma trận F một cách thông minh có thể cải thiện đáng kể tốc độ hội tụ của thuật toán, đóng vai trò như một cầu nối đến các phương pháp tựa-Newton.

IV. Bí Quyết Tăng Tốc Tối Ưu Phi Tuyến Bằng Phương Pháp Newton

Trong khi Gradient Descent sử dụng thông tin đạo hàm cấp một, phương pháp Newton-Raphson tận dụng cả thông tin đạo hàm cấp hai để tăng tốc quá trình tối ưu. Phương pháp này xây dựng một mô hình bậc hai của hàm mục tiêu tại điểm hiện tại x_k bằng cách sử dụng khai triển Taylor: f(x) ≈ f(x_k) + <f'(x_k), x - x_k> + 1/2 * <f''(x_k)(x - x_k), x - x_k>. Sau đó, thuật toán tìm điểm cực tiểu của mô hình xấp xỉ này. Điểm cực tiểu này được dùng làm điểm tiếp theo trong dãy lặp, x_{k+1}. Công thức cập nhật của phương pháp Newton là: x_{k+1} = x_k - [f''(x_k)]⁻¹ * f'(x_k). Trong đó, f''(x_k) là ma trận Hessian tại x_k. Ưu điểm lớn nhất của phương pháp Newton là tốc độ hội tụ của thuật toán rất nhanh. Dưới các điều kiện nhất định (hàm lồi nghiêm ngặt, điểm xuất phát đủ gần nghiệm), nó đạt được tốc độ hội tụ bậc hai. Tuy nhiên, phương pháp này có những nhược điểm đáng kể. Việc tính toán, lưu trữ và nghịch đảo ma trận Hessian ở mỗi vòng lặp là cực kỳ tốn kém, đặc biệt với các bài toán có số chiều lớn. Ngoài ra, nếu ma trận Hessian không xác định dương, bước nhảy Newton có thể chỉ đến một điểm cực đại hoặc điểm yên ngựa, khiến thuật toán không ổn định.

4.1. Vai trò của ma trận Hessian trong phương pháp Newton

Ma trận Hessian f''(x) chứa thông tin về độ cong của hàm mục tiêu. Nó cho biết hàm số 'lõm' hay 'lồi' tại một điểm và mức độ cong theo các hướng khác nhau. Trong phương pháp Newton, nghịch đảo của Hessian, [f''(x_k)]⁻¹, đóng vai trò như một ma trận biến đổi, điều chỉnh hướng và độ lớn của bước nhảy. Nó giúp 'kéo' bước đi về phía đáy của 'thung lũng' một cách hiệu quả hơn so với việc chỉ đi theo hướng dốc nhất của Gradient Descent. Khi Hessian xác định dương, bước nhảy Newton được đảm bảo là một hướng giảm. Tuy nhiên, tính toán ma trận này có độ phức tạp O(n²) và việc nghịch đảo nó là O(n³), khiến phương pháp Newton không thực tế cho các bài toán n lớn.

4.2. Phương pháp tựa Newton Quasi Newton Giải pháp tối ưu

Để khắc phục nhược điểm về chi phí tính toán của phương pháp Newton, các phương pháp tựa-Newton (Quasi-Newton) đã được phát triển. Các phương pháp này tránh việc tính toán và nghịch đảo ma trận Hessian trực tiếp. Thay vào đó, chúng xây dựng một ma trận B_k xấp xỉ cho ma trận Hessian (hoặc H_k xấp xỉ cho nghịch đảo của nó) và cập nhật ma trận này ở mỗi vòng lặp bằng cách sử dụng thông tin từ gradient. Thuật toán BFGS (Broyden–Fletcher–Goldfarb–Shanno) là một trong những thuật toán tựa-Newton phổ biến và hiệu quả nhất. Nó duy trì một ma trận xấp xỉ xác định dương, đảm bảo hướng đi luôn là hướng giảm. Các phương pháp này thường đạt được tốc độ hội tụ siêu tuyến tính, nhanh hơn đáng kể so với Gradient Descent nhưng lại không yêu cầu chi phí tính toán cao như phương pháp Newton, tạo ra một sự cân bằng tuyệt vời giữa hiệu quả và chi phí.

V. Top Ứng Dụng Tối Ưu Hóa Trong Học Máy Và Vận Trù Học

Lý thuyết về tối ưu phi tuyến không chỉ dừng lại ở các bài báo khoa học mà còn là nền tảng cho vô số ứng dụng thực tiễn, đặc biệt trong các lĩnh vực đòi hỏi ra quyết định tối ưu. Một trong những lĩnh vực hưởng lợi nhiều nhất là học máy. Hầu hết các bài toán học máy có giám sát đều có thể được quy về việc cực tiểu hóa một hàm mất mát (loss function). Hàm mất mát này đo lường sự khác biệt giữa dự đoán của mô hình và giá trị thực tế. Bằng cách sử dụng các thuật toán như phương pháp Gradient Descent, mô hình điều chỉnh các tham số của nó để giảm thiểu sai số này, từ đó 'học' được từ dữ liệu. Lĩnh vực vận trù học (operations research) cũng sử dụng rộng rãi các kỹ thuật tối ưu hóa phi tuyến để giải quyết các bài toán phức tạp như lập kế hoạch sản xuất, quản lý chuỗi cung ứng, tối ưu hóa danh mục đầu tư tài chính, và thiết kế mạng lưới viễn thông. Các phương pháp số cho phép các doanh nghiệp tìm ra phương án hoạt động hiệu quả nhất, tiết kiệm chi phí và tối đa hóa lợi nhuận. Ngay cả trong các ngành kỹ thuật, việc thiết kế một cây cầu vững chắc nhất với lượng vật liệu ít nhất hay tìm quỹ đạo tối ưu cho một con tàu vũ trụ cũng là những bài toán tối ưu hóa phi tuyến.

5.1. Giải bài toán tối ưu trong các mô hình học máy

Trong học máy, từ hồi quy logistic, mạng nơ-ron cho đến máy vector hỗ trợ (SVM), tất cả đều dựa trên nguyên tắc tối ưu hóa một hàm mục tiêu. Ví dụ, trong huấn luyện một mạng nơ-ron, hàm mục tiêu thường là tổng sai số bình phương hoặc hàm cross-entropy. Các thuật toán như Adam, một biến thể tiên tiến của Gradient Descent, được sử dụng để tìm bộ trọng số tối ưu cho hàng triệu tham số của mạng. Tối ưu hóa có ràng buộc cũng xuất hiện, ví dụ như trong SVM, nơi ta cần tối đa hóa lề trong khi vẫn phân loại đúng các điểm dữ liệu, dẫn đến việc sử dụng các kỹ thuật như nhân tử Lagrange và điều kiện Karush-Kuhn-Tucker (KKT). Việc hiểu rõ các phương pháp tối ưu là chìa khóa để thiết kế và huấn luyện các mô hình học máy hiệu quả.

5.2. Cực tiểu hóa hàm bậc hai và các bài toán thực tế

Một lớp bài toán đặc biệt quan trọng là cực tiểu hóa hàm bậc hai, có dạng f(x) = 1/2 * xᵀAx + bᵀx + c, với A là ma trận đối xứng. Nếu A xác định dương, hàm này lồi và có một điểm cực tiểu toàn cục duy nhất. Nhiều bài toán thực tế có thể được mô hình hóa hoặc xấp xỉ dưới dạng này. Luận văn của Mai Đức Thanh (2002) đã trình bày ứng dụng của các phương pháp Gradient và Newton để giải bài toán này. Một ứng dụng thú vị khác là tính khoảng cách trong không gian Euclidean, ví dụ như tìm khoảng cách ngắn nhất từ một điểm đến một mặt cong. Bài toán này có thể được quy về việc cực tiểu hóa bình phương khoảng cách, vốn thường là một hàm đa thức (một dạng hàm phi tuyến). Các phương pháp số như Gradient Descent có thể được áp dụng để tìm ra cặp điểm gần nhất một cách hiệu quả.

VI. Hướng Dẫn Thực Hành Tối Ưu Phi Tuyến Bằng Python Và MATLAB

Việc hiểu lý thuyết là quan trọng, nhưng khả năng áp dụng các phương pháp số vào giải quyết vấn đề thực tế còn quan trọng hơn. Ngày nay, các nhà khoa học và kỹ sư không cần phải lập trình các thuật toán tối ưu từ đầu. Thay vào đó, họ có thể tận dụng các thư viện mạnh mẽ được xây dựng sẵn trong các ngôn ngữ lập trình phổ biến như Python và MATLAB. Các thư viện này cung cấp các bộ giải (solver) đã được tối ưu hóa, kiểm thử kỹ lưỡng và có khả năng xử lý nhiều loại bài toán tối ưu hóa khác nhau, từ không ràng buộc đến có ràng buộc phức tạp. Việc sử dụng các công cụ này không chỉ tiết kiệm thời gian mà còn đảm bảo độ tin cậy và hiệu quả của lời giải. Nắm vững cách sử dụng các hàm tối ưu trong thư viện SciPy Optimize của Python hay Optimization Toolbox của MATLAB là một kỹ năng cần thiết cho bất kỳ ai làm việc trong lĩnh vực khoa học dữ liệu, kỹ thuật tính toán hay vận trù học. Các công cụ này cho phép người dùng định nghĩa hàm mục tiêu, gradient, và ma trận Hessian (nếu có), sau đó lựa chọn thuật toán phù hợp như thuật toán BFGS hay Newton-CG để tìm ra lời giải tối ưu một cách nhanh chóng và chính xác.

6.1. Sử dụng thư viện SciPy Optimize để giải bài toán

Python, với hệ sinh thái khoa học dữ liệu phong phú, là một lựa chọn hàng đầu cho việc thực hành tối ưu hóa. Thư viện SciPy, cụ thể là module scipy.optimize, cung cấp một bộ sưu tập đa dạng các thuật toán tối ưu. Hàm minimize() là giao diện chính, cho phép người dùng lựa chọn nhiều phương pháp khác nhau. Ví dụ, để giải một bài toán tối ưu không ràng buộc, người dùng có thể gọi minimize(fun, x0, method='BFGS'), trong đó fun là hàm mục tiêu cần tối ưu, x0 là điểm khởi tạo, và 'BFGS' là tên của thuật toán tựa-Newton được chọn. Thư viện này cũng hỗ trợ cung cấp hàm Jacobian (gradient) và Hessian để tăng tốc độ và độ chính xác, cũng như xử lý các bài toán tối ưu hóa có ràng buộc thông qua các phương pháp như SLSQP (Sequential Least Squares Programming).

6.2. Giải bài toán tối ưu bằng MATLAB và Optimization Toolbox

MATLAB từ lâu đã là một công cụ tiêu chuẩn trong giới kỹ thuật và khoa học cho các tác vụ tính toán số. Optimization Toolbox của MATLAB cung cấp một môi trường mạnh mẽ để mô hình hóa và giải bài toán tối ưu. Hàm fminunc được thiết kế đặc biệt cho các bài toán tối ưu không ràng buộc, cho phép người dùng lựa chọn giữa các thuật toán như phương pháp tựa-Newton (Quasi-Newton) hoặc 'trust-region'. Đối với các bài toán có ràng buộc, hàm fmincon là công cụ chính, hỗ trợ các thuật toán mạnh mẽ như phương pháp điểm trong (interior-point methods) và SQP. Ưu điểm của MATLAB là cú pháp gần với ngôn ngữ toán học và khả năng tích hợp liền mạch với các toolbox khác như Symbolic Math Toolbox để tính toán đạo hàm tự động, giúp quá trình triển khai trở nên trực quan và hiệu quả.

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

CHƯƠNG 1: PHƯƠNG PHÁP GRADIENT LPhuong pháp giảm nhanh; TY cách chon vectơ px thoả man <f(x„).px> < 0, trong phương pháp này ta chọn px = - f(x). Day {xxl có dang Xx-1 = Xk ~ ax. Để chon a, thoả man BDT: f(Xx„:) — fad <. Ta đùng thuật toán sau (gọi la phương pháp lặp chọn a,): Cho a một giá trị cho trước (vd: lấy a = 1).

+Bước 2:Tinh fix) = fix, - a. +Bước 3:Kiém tra BĐT: flx) - fix) <-e. | f(x |? +Bước 4:Nếu bước 3 kiểm tra BĐT cho kết quả sai. Ta giảm a bằng cách nhân a với t (O<t<1) rối lặp lại các bước cho đến khi BĐT bước 3 đúng.

Khi kiểm tra BĐT bước 3 đã đúng, ta chon a, = a. Phương pháp chon vectd p„ như trên được gọi là phương pháp giảm nhanh hay phương pháp gradient.1: Giả sử ham f bị chặn dưới, đạo ham f thoả man diéu kiện: |f(x)- f(y) ls R.yeIR° Khi đó với phương pháp giảm nhanh, có a, được chọn bang Chứng minh: Từ định lý giá trị trung bình, ta có: f(x) - Í(xy) = <f(Xxc). <> fx) - fx) = <f(xx),x - xe> + < Ẩ(Xục) - f(xx),X — Xx> Mà x = Xx = -a. Ì xe:- xf => f(x) — ix.

Ífxy)Í? + Rix - x1? Trang Š LUẬN VAN TỐT NGHIỆP PHƯƠNG PHÁP GRADIENT ee = -a.a) Vay để BĐT fx) - fix,) <-c. Íf(xy) Í?, ta cản chọn a sao cho: (1 ~ Ra) >e ca < = Điều nảy chứng tỏ sau một số bước hữu hạn giảm a. thuật toản chon ax sẽ đứng. tức là thuật toán thực hiện được.

Mặt khác doa chon ban đầu ban đấu là | va doa < = thi ở « bước 3 BĐT được kiểm tra là đúng, nén a, > min[1.` Êi Ta có: fxx.„) x Do ham f{x) bị chặn dưới nên day [f(xy)| bị chan dưới, ma day \{{x,)) là day giảm nén hội tu.¡) ~O khi k-»œ a My) M0) _ 0 khí ke Ea, —lf(x)Í 40 khi k—>. Vậy định lý đã được chứng mính.1 khẳng định sự thực hiện được của thuật toán chọn a, và dây {xx} hội tụ tại điểm đừng x” (ma trận đạo ham f(x’) bang 0). Kết quả thu được có thể là điểm cực tiểu địa phương. điểm yên ngựa (nếu có) chứ không phải là điểm cực tiểu.

Tuy nhiên trong thực tế ta chỉ cắn biết giá trị hàm mục tiêu khá bé so với giá trị đã biết ban đảu la đã sử dụng được. Do đó phương pháp trên có thể áp dụng được vào thực tế. Khi ham f bị chặn dưới.Íx- yl chỉ cần đúng với mọi x.y nằm trong một lan can rất lớn của x, vì dãy (xy! sé hội tụ trước khi vượt ra khỏi lan cận đó. Do đó lớp ham áp dụng được phương pháp này khá rộng.

Trang 6 LUẬN VĂN TỐT NGHIỆP PHƯƠNG PHÁP GRADIENT pháp lập thi với mọi giá trị ban đầu của x, các day |xạl, |f(xx)l hội tụ vẻ x’. Chứng minh: Từ < f(x)y. theo ly thuyết ham lôi, ta có f là ham lôi nghiêm ngặt, nên ham f có duy nhất điểm cực tiểu x" là điểm dừng. Do đó theo định lý 1.

Theo công thức Taylor ta có: fix’) = fx) + < fx).lx- xl- „mlx- xt? (1) Mat khac: f(x) = fx) + < f(x).x - x'> = fix) + be fxe)(x - x)x=x'> (vi f(x) = 0) © fbg - fix) = 2< F'txa)x ~ x’).x ~ x> = 3 |x- x'|? < flx) - fix) < Ix xI° ) (1).ta có: Từ ^ lx- x'Í? < fix) - fixva Xi x |? < lf(x)l.lx- xl- „mlx i fe => mix- x l*< Ifpal. lx x'l olx-x'ls Lirpal (2) m Trang 7 LUẬN VĂN TỐT NGHIỆP PHƯƠNG PHÁP GRADIENT Tử fix) - fix’) < six x1? = Ix- xl? 2 2 (ft - fx)) (3) Thể (2).ay m{1 + ME) -fx) — t4) Với thuật toán thi x - x, = -a f(x;),ta có: fix) - fxd = < F+). f(xx)> s -a(l-TM) | roa? Vay khi a-S) >cœa< _— thi BĐT chon a, thoả man do đó nếu .—8 < 1 thì tương tự định lý 1.1 ta chứng minh được: azt 24-8) (mg M Từ (4) và (5) .a*2 Trang 8 LUẬN VĂN TỐT NGHIỆP PHƯƠNG PHÁP GRADIENT ”=~. Vậy định lý da được chứng minh.

+Nhận xét: Định lý 1.1 chỉ chứng minh sự thực hiện được của thuật toản nhưng chưa chỉ ra được tốc độ hội tụ của các day (xx). (f(x) đồng thời chưa khẳng định được sự hoi tụ của day |x„j vẻ điểm đạt cực tiểu.2 tuy áp dụng cho lớp ham hẹp hơn so với định ly 1.1 nhưng đã khắc phục được các nhược điểm nảy. Tốc độ hội tụ của các day (xx).— rr (1 + um Nếu ta coi t, M, m là những hằng số cho trước thi khi đó gia trị q nhỏ nhất khi c. Tử BĐT Cosi ta có #1—£) < F nén Nếu ta coi t, e là những hằng số do ta chon thi q cảng nhỏ khi ti số = cảng gan 1.

Nếu tỉ số = << | thi q rất gan 1, khi dé phương pháp không hiệu quả vi tốc độ hội ty rất cham. Ở phản | ta đã đưa ra thuật toản chọn p„=-f(xx) và cách chon a, thoả BĐT : f(xx. 1 f(xy) |? bằng phương pháp lặp.2 ta đã chứng minh được BĐT trên luôn thỏa man khi a, < x hoặc a,< ae °). Như vậy nếu ta xác định trước hang số R hoặc M thì ta có thé chon a, là hằng số a với a < na hoặc as *{~®), với cách chon ay là hằng số nay số lượng phép tính may tính cắn làm sẽ giảm đi rất nhiều so với phương pháp ban đâu.

Ixu| được ước lượng bởi: Ix¿- x`Í< q*.MII M-m 2 va q nhỏ nhất 1a: Qmin= HN đạt được khi NET mm LUẬN VĂN TỐT NGHIỆP PHƯƠNG PHÁP GRADIENT Chứng minh: Ta có : Íx;- x`Í? = <xx-af(xu)- x".¡-X` > Theo công thức Lagrange : f{xy)- (x) =f" (xn) x-x) Với x„.= Xx + OF xx-x) , 0e|O, 1|.ffx)Ï thì Íxu¿¿- x 1s q.MI| = nể In) 3 | M.(I - Ma) | - M-m M+m M+m M+m 2 Dấu bằng xảy ra khi va chỉ khi 1-m.a]) © a = M+m Vay qmin = ts —: M+m M+m Vậy định ly đã được chứng minh. Một biến thé khác của phương pháp Gradient lả ta chon a, thoả man [{{x,.;) đạt giá trị nhỏ nhất của hàm f theo phương px tại fixy) : fixe. Ta có thể dùng ngay phương pháp giảm nhanh để chọn ay. khi k-> », với mọi điểm x, ban dau.

Chứng minh : Như định lý 1.1 ta đã chứng minh được ?„). | f(xy) Í? là ham bác hai theo a đạt giá trị nhỏ nhất tại ane Trang 10 LUẬN VĂN TỐT NGHIỆP PHƯƠNG PHÁP GRADIENT ma f(xw.) Vi day {flx,)} là day giảm ,bị chan nên hội tụ => Í[xy)- f(Xy.¡) => O khi ko = lf(xujÍ +» 0 khi kx Vay định ly đã được chứng minh.5 Nếu ham f thoả điểu kiện định lý 1. với phương pháp Gradient có ay được chọn sao cho : Fixer) = [Ấx, — ay.f(xv)> 4 -aÏlf(xy) |? + ÌM I f(x) 1? 2 1 < -(a - 2M) I ft) 1? Như định ly 1.2 ta có: If(x)!?> mu + x09 - fx-)) : = fWx.i) fx) < flyxer) fx) < woos (fx) - fixe) Tương tự định lý 1.2 ta chứng minh được: Trang 11 LUẬN VĂN TỐT NGHIỆP PHƯƠNG PHÁP GRADIENT Ixkei- xbs ——. Dx xe Tứ đó ta có diéu phải chứng minh.Phương Pháp Gradient mở rộng: Cho F la một ma trận đối xứng tuỷ ý thỏa man điều kiện : 3p>0: plyl? < <Fy .y>s Plyl? ,V yeIR° (e) Tử cách chọn vectơ px, ta cỏ thể chon px = -F.

If (xl? < 0 vậy ta có thể xay dung day |xx| dạng : Xksi = Xe — Ay.Khi đó day 1 (Fy '| thỏa man : mlyl? < <Fy ,y> s Milyl? với my = ¬. Vay ta cùng có thé xáy đựng day (xy) với py = -Fy' f(x : Xker = Xk — 8w. Day là phương pháp Gradient mở rộng vi khi ta lấy Fy = | thì sé trở thanh phương pháp Gradient. Vẻ cách chon a, ta vẫn làm tương tự như phương pháp Gradient với các cách : « Chon a, bằng phương pháp lặp thỏa man BDT : f[xx.

« Chon a bằng hang số thỏa BĐT trên « Chon a, sao cho fixx+:) đạt cự tiểu của ham f theo phương px tại fix.6 : Với phương pháp Gradient mở rộng va ax được chon bằng phương pháp lặp. Chứng minh : Tương tự Định lý 1.p„> + Ra? | pl? Ra’ S$ a.Px> Trang 12 LUẬN VĂN TỐT NGHIỆP PHƯƠNG PHÁP GRADIENT — = (1- = ) a.px> (vi px=Fx '. Tương tự định lý 1.1 taco: với ay < ee thi BDT: f(xx.px> đúng va ta chứng minh được Íf(x„)Ï—» O .khi k + © theo BDT : f(x,)-Í[Xk.Px> = -eAv<FxPx.) ma, Vay Định ly da được chứng minh Dinh lý 1.7 : Với phương pháp mở rộng định lý 1. Chứng minh : Nếu X = Xx + ap, ma py = -Fy'.px> + >< '(Xwc}Px.Px > < -p| px Ì? => f(x) - fad < a<f(Xx),p„> (1- = ) vậy BDT fixx.> van thỏa man khi 1.

TMM :c@œa« Mì tương tự định lý 1.1 ta chứng minh 2. M vậy với điều kiện của định lý 1.7 thuật toán chon a, vẫn thực hiện được tức lả a, thỏa mãn : f[Xx.px> ma <f(Xx.px)> 4 -m) | fbx) |? Í? = fXx.i) - fla) < -£ ax mụ Í ft(x¿) như định lý 1.2 da chứng minh : If (x1? > m.(1+ x ) If(x) - f[x)] Trang 13 LUẬN VĂN TỐT NGHIỆP PHƯƠNG PHÁP GRADIENT “———ễ Ầ XFXF F_ => flxx.) - fix) < -£ ay mym(1+ m } Iftxy) - fx") => fxx.m M 1+ m JI Ifxx) - 1x") 20-2 41+ & ) = fxs) - fe) < q(f64) - fx Đặt q = I- ) => fix) - fix) < q*{fixo) - ftx)) ma Ix, -x'l < [24 fxs) - f(x))]!⁄2 <[=.q'? : vậy định lý được chứng minh va qoun= 1- ee = (¡+ + ) khi c= Ì 2 Nhận xét : a Với phương pháp Gradient mở rộng ta thấy kết quả các định ly 1.2 vẫn đúng nghĩa là tính chất của phương pháp này cũng giống như phương pháp trước. Tuy nhiên tốc độ hội tụ của day (xx). |f(x„)| trong phương pháp này là cấp số nhân ti số q bé nhất khi Eel.

với phương pháp nay trong trưỡng hợp dãy {F¿| tuỳ ý thỏa diéu kiện đả cho thì tốc độ hội tụ còn chậm hơn so với phương pháp trước. a Ta cũng có hai biến thể chon a, là hằng số khi biết R hoặc M là: a, < TP ¡ 8ụ s 2(1-e).p va bién thé chon a, theo diéu kiện : {Xk + 4x.p„) Hoàn toản tương tự định lý 1.5 ta chứng minh được định lý sau : thi day {x,J hội tụ về điểm đạt cực tiểu x’ với tốc độ một cấp số nhân.