Tối ưu hóa (toán học)

Posted on 28.03.2011 by Tuấn Lê

Tối ưu hóa (toán học)

(Nguồn: wikipedia)

Trong toán học, thuật ngữ tối ưu hóa chỉ tới việc nghiên cứu các bài toán có dạng

Cho trước: một hàm f : A \to R từ tập hợp A tới tập số thực
Tìm: một phần tử x0 thuộc A sao cho f(x0) ≤ f(x) với mọi x thuộc A (“cực tiểu hóa”) hoặc sao cho f(x0) ≥ f(x) với mọi x thuộc A (“cực đại hóa”).

Một phát biểu bài toán như vật đôi khi được gọi là một quy hoạch toán học (mathematical program). Nhiều bài toán thực tế và lý thuyết có thể được mô hình theo cách tổng quát trên.

Miền xác định A của hàm f được gọi là không gian tìm kiếm. Thông thường, A là một tập con của không gian Euclid Rn, thường được xác định bởi một tập các ràng buộc, các đẳng thức hay bất đẳng thức mà các thành viên của A phải thỏa mãn. Các phần tử của A được gọi là các lời giải khả thi. Hàm f được gọi là hàm mục tiêu, hoặc hàm chi phí. Lời giải khả thi nào cực tiểu hóa (hoặc cực đại hóa, nếu đó là mục đích) hàm mục tiêu được gọi là lời giải tối ưu.

Thông thường, sẽ có một vài cực tiểu địa phương và cực đại địa phương, trong đó một cực tiểu địa phương x* được định nghĩa là một điểm thỏa mãn điều kiện:

với giá trị δ > 0 nào đó và với mọi giá trị x sao cho

\|\mathbf{x}-\mathbf{x}^*\|\leq\delta;

công thức sau luôn đúng

f(\mathbf{x}^*)\leq f(\mathbf{x})

Nghĩa là, tại vùng xung quanh x*, mọi giá trị của hàm đều lớn hơn hoặc bằng giá trị tại điểm đó. Cực đại địa phương được định nghĩa tương tự. Thông thường, việc tìm cực tiểu địa phương là dễ dàng – cần thêm các thông tin về bài toán (chẳng hạn, hàm mục tiêu là hàm lồi) để đảm bảo rằng lời giản tìm được là cực tiểu toàn cục.

Mục lục

Ký hiệu

Các bài toán tối ưu hóa thường được biểu diễn bằng các ký hiệu đặc biệt. Ví dụ:

\min_{x\in\mathbb R}\; x^2 + 1

Bài toán trên yêu cầu tìm giá trị nhỏ nhất cho biểu thức x2 + 1, trong đó x chạy trên tập số thực R. Giá trị nhỏ nhất trong trường hợp này là 1, xảy ra tại x = 0.

\max_{x\in\mathbb R}\; 2x

Bài toán trên yêu cầu tìm giá trị lớn nhất cho biểu thức 2x, trong đó x chạy trên tập số thực. Trong trường hợp này, không có giá trị lớn nhất do biểu thức không bị chặn trên, vậy kết quả là “giá trị vô cùng” hoặc “không xác định”.

\operatorname{argmin}_{x\in[-\infty,-1]}\; x^2 + 1

Bài toán trên yêu cầu tìm các giá trị của x trong đoạn [−∞, −1] để cực tiểu hóa biểu thức x2 + 1. (Giá trị nhỏ nhất của biểu thức không quan trọng.) Trong trường hợp này, kết quả là x = −1.

\operatorname{argmax}_{x\in[-5,5],\;y\in\mathbb R}\; x\cdot\cos(y)

Bài toán trên yêu cầu tìm cặp (x, y) làm cực đại giá trị của biểu thức x·cos(y), với ràng buộc rằng x nằm trong đoạn [−5, 5]. (Một lần nữa, giá trị nhỏ nhất của biểu thức không quan trọng.) Trong trường hợp này, kết quả là các cặp có dạng (5, 2πk) và (−5, (2k + 1)π), với k chạy trên tập số nguyên.

Các lĩnh vực con chính

  • Quy hoạch tuyến tính (Linear programming) nghiên cứu các trường hợp khi hàm mục tiêu f là hàm tuyến tính và tập A được mô tả chỉ bằng các đẳng thức và bất đẳng thức tuyến tính (A được gọi là một khúc lồi).
  • Quy hoạch số nguyên (Integer programming) nghiên cứu các quy hoạch tuyến tính trong đó một số hoặc tất cả các biến có giới hạn là các số nguyên.
  • Quy hoạch bậc hai (hay quy hoạch toàn phương) (Quadratic programming) cho phép hàm mục tiêu có các toán hạng bậc hai, trong khi tập A phải mô tả được bằng các đẳng thức và bất đẳng thức tuyến tính (A được gọi là một khúc lồi).
  • Quy hoạch phi tuyến (Nonlinear programming) nghiên cứu trường hợp tổng quát khi hàm mục tiêu hay các ràng buộc hoặc cả hai chứa các thành phần không tuyến tính.
  • Quy hoạch ngẫu nhiên (Stochastic programming) nghiên cứu các trường hợp khi một số ràng buộc phụ thuộc vào các biến ngẫu nhiên.
  • Quy hoạch động (Dynamic programming) nghiên cứu các trường hợp khi chiến lược tối ưu hóa dựa trên việc chia bài toán thành các bài toán con nhỏ hơn (nguyên lý quy hoạch động).
  • Tối ưu hóa tổ hợp (Combinatorial optimization) quan tâm đến các bài toán trong đó tập các lời giải khả thi là rời rạc hoặc có thể được rút gọn về một tập rời rạc.
  • Infinite-dimensional optimization nghiên cứu trường hợp khi tập các lời giải khả thi là một tập con của một không gian vô số chiều, chẳng hạn không gian các hàm số (ví dụ bài toán điều khiển tối ưu).
  • Constraint satisfaction nghiên cứu trường hợp khi hàm mục tiêu f là hằng số – đây là vấn đề quan trọng của ngành Trí tuệ nhân tạo, đặc biệt là lĩnh vực Suy luận tự động (Automated reasoning).

Các kỹ thuật

Đối với các hàm khả vi hai lần (twice-differentiable), có thể giải các bài toán không ràng buộc bằng cách tìm các điểm mà tại đó đạo hàm của hàm mục tiêu bằng 0 (điểm dừng) và sử dụng ma trận Hesse để xác định xem đó là cực tiểu, cực đại, hay điểm yên ngựa.

Ta có thể tìm các điểm dừng bằng cách bắt đầu từ một điểm dự đoán là điểm dừng rồi tiến về điểm dừng bằng cách lặp đi lặp lại các phương pháp như

Nếu hàm mục tiêu là hàm lồi trong vùng quan tâm thì cực tiểu địa phương sẽ là cực tiểu toàn cục. Có các phương pháp số nhanh chóng và hiệu quả cho việc tối ưu hóa các hàm lồi khả vi hai lần.

Các bài toán ràng buộc thường có thể được biến đổi thành một bài toán không có ràng buộc bằng phương pháp nhân tử Lagrange (Lagrange multiplier).

Dưới đây là một số phương pháp thông dụng:

Ứng dụng

Các bài toán trong động lực học vật rắn (cụ thể là động lực học vật rắn chính xác) thường đòi hỏi các kỹ thuật quy hoạch toán học, do ta có thể coi động lực học vật rắn như là việc giải các phương trình vi phân thường (ordinary differential equation) trên một đa tạp ràng buộc (constraint manifold); các ràng buộc là các ràng buộc hình học không tuyến tính đa dạng, chẳng hạn “hai điểm này phải luôn trùng nhau”, “bề mặt này không được xuyên qua các bề mặt khác”, hoặc “điểm này phải nằm đâu đó trên đường cong này”. Ngoài ra, vấn đề tính toán các lực tiếp xúc có thể được thực hiện bằng cách giải một bài toán bù tuyến tính (linear complementarity problem). Dạng bài nài cũng có thể được coi là bài toán quy hoạch bậc hai.

Nhiều bài toán thiết kế cũng có thể được biểu diễn dưới dạng các chương trình tối ưu hóa. Áp dụng này được gọi là tối ưu hóa thiết kế. Một lĩnh vực con mới phát triển trong thời gian gần đây là multidisciplinary design optimization. Nó hữu ích cho nhiều bài toán và đã được áp dụng cho các bài toán kỹ nghệ hàng không (aerospace engineering).

Vận trù học (operations research) là lĩnh vực sử dụng rất nhiều đến các kỹ thuật tối ưu hóa.

Xem thêm

Tham khảo

Liên kết ngoài

Phần mềm:

Trang tiếng Việt về Toán tối ưu

http://etintin.com/csstudyfun/

http://csstudyfun.wordpress.com/

http://dangcnd.wordpress.com/bai-giang/quy-hoach-tuyen-tinh/

————–&&————–

Filed under: Toán tối ưu |

« »

Bình luận về bài viết này

  • Since 2010

    • 1 653 697 hits