Welcome To Sherry Forex Group: August 2014

Optimization – Giới thiệu

Cập nhật 10/10/2010: Download bản PDF dễ đọc hơn.

1. Mathematical Programming, Optimization và Operational Research

George Dantzig (1914 – 2005), cùng với Leonid Kantorovich và John von Neumann, được coi là cha đẻ của các chương trình tuyến tính (Linear Programming). Bản thân Dantzig cũng có vài “truyền kì” hay ho, nhưng thôi từ từ để sau hẵng kể.

Trở lại với Linear Programming, chữ programming ở đây không nên nhầm lẫn với chương trình máy tính ngày nay. Linear Programming nói một cách đơn giản, là lĩnh vực nghiên cứu các phương pháp toán học để tìm kết quả tốt nhất trong một mô hình toán học cho trước, trong đó mô hình và các ràng buộc được biểu diễn bằng các hàm tuyến tính. Trong trường hợp tổng quát với hàm mục tiêu và các ràng buộc bất kì, lĩnh vực này được gọi chung là Mathematical Programming (vào thời của Dantzig, chương trình máy tính được gọi là codes).

Bắt đầu từ những năm 1930, đến thế chiến thứ 2 thì những nghiên cứu này chỉ phục vụ chủ yếu trong quân đội. Sau khi chiến tranh kết thúc, các ngành công nghiệp cũng bất đầu quan tâm và ứng dụng rộng rãi các kĩ thuật này.

Ngày nay, ta gọi nó là Optimization. Nói rộng hơn, lĩnh vực nghiên cứu cấu hình tối ưu cho các hệ thống phức tạp, trong điều kiện tài nguyên hạn chế, được gọi là Operational Research. Như vậy Mathematical Programming (hay ngày nay gọi là Optimization) là một lĩnh vực nhỏ trong Operational Research. Operational Research được ứng dụng rộng rãi trong kinh tế, quốc phòng… chứ không chỉ gói gọn trong khoa học máy tính. Chẳng hạn bài toán tối ưu lịch trình giao hàng đến đại lí là một ví dụ tiêu biểu cho Operational Research.

Nói chung các vấn đề trong Operational Research đều có chung “vòng đời” gồm các bước như sau:

1. Định nghĩa bài toán

2. Mô hình hóa bằng toán học, định nghĩa các biến, hàm mục tiêu và các ràng buộc, thông thường bài toán sẽ có dạng $\min f\left(x\right) \text{s.t.} x \in X$ .

3. Tối ưu mô hình, sử dụng phương pháp thích hợp.

4. Kiểm tra (validate) mô hình, xem lời giải của bước 3 có đúng không. Nếu sai thì sửa mô hình và giải lại.

5. Cài đặt, ứng dụng mô hình

Rất nhiều phương pháp optimization khác nhau đã được phát triển để áp dụng trong bước 2 và 3 của vòng đời này. Ta sẽ lần lượt nghiên cứu chúng.

2. Dạng tổng quát của bài toán tối ưu

Có rất nhiều cách phát biểu dạng chung của một bài toán tôi ưu, tuy nhiên ta sẽ sử dụng dạng sau:

$\left(P\right)\begin{cases}\begin{array}{lll}{\displaystyle \min_{x \in \mathcal{R}^{n}}} & f\left(x\right) & \text{Objective function} \\ \text{subject to:} & h\left(x\right)=\mathbf{0} & \text{Equality contraints} \\ \; & g\left(x\right) \leq \mathbf{0} & \text{Inequality contraints} \\ \; & x \in \mathcal{X} & \text{Variable domain}\end{array}\end{cases}$

Trong đó:

$\mathbf{x}\in\mathcal{R}^n$ là biến cần tối ưu,
$f: \mathcal{R}^n \rightarrow \mathcal{R}$ , $h: \mathcal{R}^n \rightarrow \mathcal{R}^m$ , $g: \mathcal{R}^n \rightarrow \mathcal{R}^l$ , $\mathcal{X}\subseteq\mathcal{R}^n$ .

Thông thường các hàm f, g và h phải khả vi và “mượt” (theo tiêu chuẩn Lipschitz chẳng hạn) để đảm bảo các tính chất tốt của các thuật toán tối ưu.

Ngoài ra, đương nhiên $\max_{x\in\mathcal{R}^n}f\left(x\right)=-\min_{x\in\mathcal{R}^n}-f\left(x\right)$ , do đó tìm x sao cho f(x) cực đại cũng chính là tìm x để -f(x)cực tiểu. Do đó trong dạng chuẩn của bài toán tối ưu, ta sẽ chỉ xét bài toán tìm cực tiểu.

Ta còn có thể biểu diễn tương đương dạng chung của bài toán tối ưu theo cách sau:

$\displaystyle \left(P\right) \min_{x}\left\{f\left(x\right) \vert x\in \Omega\right\}$

với $\Omega = \left\{x\in\mathcal{X} \vert h\left(x\right)=\mathbf{0}, g\left(x\right)\leq \mathbf{0}\right\}$ gọi là feasible set.

Các cách biểu diễn này là tương đương nhau, và ta sẽ sử dụng dạng thứ 2 trong suốt bài này.

3. Phân loại các bài toán tối ưu

Tùy theo dạng hàm mục tiêu và các ràng buộc, và tùy theo tiêu chí, có rất nhiều cách phân loại các bài toán tối ưu. Sở dĩ phải phân loại bài toán tối ưu là vì các phương pháp tối ưu hiện có chỉ làm việc tốt trên một dạng bài toán nhất định. Do đó việc phân loại là cần thiết để chọn phương pháp giải thích hợp cho mỗi bài toán. Ở đây ta sẽ phân loại theo 2 tiêu chí là dựa vào tính chất của đáp án và dựa vào cách mô hình hóa bài toán.

Dựa vào đáp án của bài toán tối ưu, ta có thể chia làm 4 loại như sau:

Bài toán có lời giải tối ưu: đó là khi tập giá trị của f(x) với x thuộc feasible set $\left\{f\left(x\right)\vert x\in \Omega\right\}$ bị chặn dưới.

Ví dụ xét bài toán $\min_\mathbf{x}\left\{f\left(\mathbf{x}\right)=\mathbf{x}_1^2 + \mathbf{x}_2^2 \vert \mathbf{x} \geq \mathbf{0}\right\}$ . Với $\mathbf{x}\geq\mathbf{0}$ thì $f\left(\mathbf{x}\right)=\mathbf{x}_1^2 + \mathbf{x}_2^2 \geq 0$ nên bài toán có lời giải tối ưu là $f\left(\mathbf{x}\right)=0$ khi $\mathbf{x}_1 = \mathbf{x}_2 = \mathbf{0}$ .

Bài toán bất khả thi (infeasible problem): khi feasible set $\Omega$ là tập rỗng.

Xét bài toán $\min_x\left\{f\left(\mathbf{x}\right)=\mathbf{x}_1^2+\mathbf{x}_2^2\vert \mathbf{x}_1 + \mathbf{x}_2 \leq -1, \mathbf{x}\geq 0\right\}$ , rõ ràng khi $x \geq 0$ thì $x_1 + x_2$ luôn lớn hơn 0, do đó feasible set trong trường hợp này là tập rỗng, bài toán không có lời giải.

Unbounded problem: khi tập $\left\{f\left(x\right)\vert x\in\Omega\right\}$ không bị chặn dưới.

Xét bài toán $\min_\mathbf{x}\left\{f\left(\mathbf{x}\right)=-\mathbf{x}_1^2 - \mathbf{x}_2^2 \vert \mathbf{x} \geq \mathbf{0}\right\}$ . Rõ ràng vì $x \geq 0$ nên x càng lớn thì $f\left(\mathbf{x}\right)=-\mathbf{x}_1^2 - \mathbf{x}_2^2$ càng nhỏ, tập giá trị của $f\left(x\right)$ vì thế không bị chặn dưới, do đó mặc dù feasible set không rỗng nhưng bài toán này không có lời giải hữu hạn.

Tồn tại ít nhất một điểm tối ưu toàn cục: điều này được đảm bảo nếu f là hàm liên tục và $\Omega$ là tập compact.

Tuy nhiên một cách phân loại phổ biến hơn là dựa vào cách mô hình hóa bài toán, vì theo đó ta có thể chọn phương pháp tối ưu phù hợp. Theo đó có thể chia thành các dạng bài toán tối ưu sau:

Linear programming:

$\displaystyle \left(P\right) \min_{x}\left\{c^Tx\vert x\in \Omega\right\}$

$\displaystyle \Omega = \left\{x\in \mathcal{R}^n\vert Ax=b,l\leq x\leq u\right\}$

Trong dạng này, cả hàm f(x) và ràng buộc Ax=b đều có dạng tuyến tính, do đó mới có tên là chương trình tuyến tính. Đây chính là dạng đầu tiên mà Dantzig đã công bố những năm 1930, 1940.

Linear Network Flow Problem:

$\displaystyle \left(P\right) \min_{x}\left\{c^Tx\vert x\in \Omega\right\}$

$\displaystyle \Omega = \left\{x\in \mathcal{R}^n\vert Ax=b,l\leq x\leq u, A \text{ is the arc-node matrix of a graph}\right\}$

Giống trường hợp ở trên, nhưng khi A là ma trận biểu diễn một đồ thị nào đó, thì nhờ một số tính chất của đồ thị, ta có thể có những phương pháp giải tốt hơn nhiều. Các bài toán đường đi ngắn nhất, lát cắt cực tiểu v.v… trong đồ thị thuộc loại này, và đã được nghiên cứu nhiều trong Lí thuyết đồ thị.

Linear Mixed Integer Programming:

$\left(P\right) \min_x\left\{c^Tx+d^Ty\vert \left[\begin{array}{c}x\\y\end{array}\right]\in \Omega\right\}$

$\Omega = \left\{x\in\mathcal{R}^{n_x},y\in\mathcal{Z}^{n_y}\vert Ax+Ty=b,l\leq\left[\begin{array}{c}x\\y\end{array}\right]\leq u\right\}$

Trong trường hợp này, tập xác định của x và y khác nhau nên ta gọi là mixed, ngoài ra do y thuộc không gian $\mathcal{Z}^n$ nên gọi là integer. Cuối cùng, hàm mục tiêu và điều kiện của bài toán đều là hàm tuyến tính nên gọi linear.

Nonlinear unconstrainted:

$\displaystyle \left(P\right) \min_{x\in\mathcal{R}^n}f\left(x\right)$

Trường hợp tổng quát, hàm mục tiêu f(x) không phải là tuyến tính thì ta gọi là nonlinear programming. Trong trường hợp này không có cả điều kiện ràng buọc nên gọi là unconstrainted.

Nonlinear with Simple Bounds:

$\displaystyle \left(P\right) \min_{x}\left\{f\left(x\right)\vert l\leq x \leq u\right\}$

Hàm mục tiêu tổng quát, biến bị chặn trên và chặn dưới.

Nonlinear with linear constraints:

$\displaystyle \left(P\right) \min_{x}\left\{f\left(x\right)\vert x\in\mathcal{X}\right\}; \mathcal{X}=\left\{x\in\mathcal{R}^n\vert Ax=b, l\leq x\leq u\right\}$

Hàm mục tiêu tổng quát, biến bị chặn và ràng buộc bằng hệ phương trình tuyến tính.

Nonlinear with general constraints:

$\displaystyle \left(P\right) \min_{x}\left\{f\left(x\right)\vert x\in\mathcal{X}\right\}; \mathcal{X}=\left\{x\in\mathcal{R}^n\vert h\left(x\right)=0, g\left(x\right)\leq 0\right\}$

Đây chính là trường hợp tổng quát, cả hàm mục tiêu và ràng buộc đều không tuyến tính.

4. Một số kĩ thuật biến đổi

Bài toán tối ưu trong thực tế thường không có dạng chuẩn mực như đã nói ở phần trên, tuy nhiên bằng một số biến đổi khéo léo, ta có thể đưa chúng về dạng chuẩn mực. Sau đây là một số kĩ thuật như vậy.

Đẳng thức -> Bất đẳng thức

Ta có thể chuyển một ràng buộc ở dạng đẳng thức thành 2 ràng buộc bất đẳng thức, và bài toán tối ưu mới vẫn tương đương với bài toán ban đầu.

Ví dụ ràng buộc

$\displaystyle 2x_1 + 3x_2 - x_3 = 5$

là tương đương với:

$\displaystyle 2x_1 + 3x_2 - x_3 \leq 5$ ,

$\displaystyle 2x_1 + 3x_2 - x_3 \geq 5$

Bất đẳng thức -> đẳng thức

Cũng có thể thực hiện theo chiều ngược lại bằng cách sử dụng thêm biến phụ.

Ví dụ ràng buộc

$\displaystyle 2x_1 + 3x_2 - x_3 \leq 5$

là tương đương với

$\displaystyle 2x_1 + 3x_2 - x_3 + w_1 = 5$ ,

$\displaystyle w_1 \geq 0$

Mỗi $w_1$ như thế gọi là một biến lỏng (slack variable), với mỗi đẳng thức ta sẽ thêm một biến như thế, và bài toán mới sẽ vẫn tương đương với bài toán ban đầu.

Biến tự do -> biến ràng buộc

Giả sử trong bài toán tối ưu có một biến tự do (không bị ràng buộc bởi bất kì đẳng thức/bất đẳng thức nào), ta vẫn có thể viết ràng buộc cho chúng bằng cách thêm biến phụ.

Giả sử $y_1$ là biến tự do (giá trị của nó biến thiên trong khoảng $-\infty$ đến $\infty$ ), ta có thể viết:

$y_1 = y_2 - y_3$ ,

$y_2,y_3 \geq 0$ .

Cực đại (Mamimize) -> cực tiểu (minimize)

Dạng chuẩn mực chỉ quan tâm đến tìm cực tiểu, nhưng ta biết rằng $\max f\left(x\right) = -\min -f\left(x\right)$ , do đó có thể chuyển 1 bài toán tối ưu cực đại thành cực tiểu một cách dễ dàng.