CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Quy hoạch nón (Conic programming) (1) – Thứ tự trên các véc tơ (partial order)

Posted by Trần Quốc Long on Tháng Một 11, 2009

Ta biết rằng bài toán quy hoạch tuyến tính dạng tổng quát

\displaystyle \min_x \{f(x)=c^T x : Ax \geq b \}

có hàm mục tiêu tuyến tính \displaystyle c^Tx  và các ràng buộc \displaystyle a_i^Tx\geq b_i, \forall i=1,\ldots,m. Để tổng quát hóa thành bài toán quy hoạch phi tuyến, có nhiều cách:

  • Cách 1: Phi tuyến hóa hàm mục tiêu \displaystyle f(x) và các ràng buộc \displaystyle a_i(x)\leq 0. Đây là cách làm trực quan và đơn giản nhất tuy nhiên, bài toán quy hoạch

    \displaystyle \min_x \{f(x) : a_i(x) \leq 0,\forall i=1,\ldots m \}

    quá tổng quát và không thể hiện được cấu trúc bên trong của bài toán quy hoạch. Với dạng biểu diễn này, ta chỉ có thể áp dụng các phương pháp tối ưu hóa tổng quát dùng đạo hàm (hoặc đạo hàm bậc 2). Hơn nữa, để ý rằng, ta không cần phải phi tuyến hóa hàm mục tiêu vì bài toán quy hoạch có thể chuyển thành

    \min_{x,t} \{t : f(x)\leq t, a_i(x)\leq 0,\forall i=1,\ldots m\}

    và nếu hàm f(x) lồi thì ràng buộc f(x)\leq t  vẫn là ràng buộc lồi.

  • Cách 2: Từ năm 1995, một phương pháp phi tuyến hóa bài toán quy hoạch tuyến tính được đưa ra. Ý tưởng của phương pháp này là thay vì sử dụng bất đẳng thức \displaystyle Ax\geq b (so sánh 2 véctơ theo từng thành phần) bằng một loại thứ tự khác. Một cách ngạc nhiên, phương pháp này cho phép tổng quát hóa bài toán quy hoạch tuyến tính thành lớp rất rộng bài toán quy hoạch phi tuyến lồi. Đồng thời, nó còn cho phép ta khai thác cấu trúc của các bài toán quy hoạch để giải chúng một cách hiệu quả.

Để ý rằng, phép so sánh 2 véctơ theo từng thành phần \displaystyle a,b\in \mathbb{R}^m:

\displaystyle a\geq b \Leftrightarrow a_i\geq b, \forall i=1,\ldots,m

là một quan hệ thứ tự (không đầy đủ – partial order) trên \displaystyle \mathbb{R}^m, nghĩa là phép so sánh này thỏa mãn các tính chất:

  1. Phản xạ: \displaystyle a\in \mathbb{R}^m \Rightarrow a\geq a
  2. Phản đối xứng: \displaystyle a,b\in \mathbb{R}^m, a\geq b~\&~ b\geq a \Rightarrow a=b
  3. Bắc cầu: \displaystyle a,b,c\in \mathbb{R}^m, a\geq b~\&~ b\geq c \Rightarrow a\geq c
  4. Đồng thời, phép so sánh này còn phù hợp với phép cộng véctơ và phép nhân véctơ với số thực không âm:

  5. Phép cộng véctơ: \displaystyle a,b,cd\in \mathbb{R}^m, a\geq b~\&~ c\geq d \Rightarrow a+c\geq b+d
  6. Phép nhân véctơ với số thực không âm: \displaystyle a,b\in \mathbb{R}^n,\lambda\geq 0, a\geq b \Rightarrow \lambda a\geq \lambda b

Người ta nhận thấy rằng các tính chất tuyệt vời (trong lý thuyết cũng như trong thực hành) về cấu trúc của bài toán quy hoạch tuyến tính phần lớn là nhờ vào các tính chất của quan hệ thứ tự này. Vì vậy, người ta hi vọng rằng, nếu thay phép so sánh từng thành phần của 2 véctơ bằng một quan hệ thứ tự khác cũng thỏa mãn các tính chất trên, bài toán quy hoạch thu được vẫn có cấu trúc tương tự và có thể lợi dụng để giải một cách hiệu quả.

Định nghĩa: Ta gọi một quan hệ thứ tự trên \displaystyle \mathbb{R}^mtốt nếu nó thỏa mãn các tính chất 1, 2, 3, 4, 5.

Ta kí hiệu quan hệ thứ tự như vậy là \displaystyle \succcurlyeq và nói \displaystyle a “lớn hơn” \displaystyle b bằng ký hiệu \displaystyle a\succcurlyeq b.

Bây giờ ta tìm hiểu điều kiện để một quan hệ thứ tự là quan hệ thứ tự tốt.

Định lý: Một quan hệ thứ tự \displaystyle \succcurlyeq tốt trên \displaystyle \mathbb{R}^m hoàn toàn xác định bởi tập \displaystyle K=\{a:a\succcurlyeq 0\}, khi đó

\displaystyle a\succcurlyeq b \Leftrightarrow a-b\succcurlyeq 0

Chứng minh: Nếu \displaystyle a\succcurlyeq b, ta có \displaystyle -b\succcurlyeq -b, suy ra \displaystyle a-b = a+(-b)\succcurlyeq b+(-b) = 0.

Nếu \displaystyle a-b\succcurlyeq 0, ta có \displaystyle b\succcurlyeq b, suy ra \displaystyle a = a-b + b \succcurlyeq 0+b = b.

Định lý: Một quan hệ thứ tự \displaystyle \succcurlyeq tốt trên \displaystyle \mathbb{R}^m khi và chỉ khi tập \displaystyle K=\{a: a\succcurlyeq 0\} là tập nón lồi khác rỗng có đỉnh, nghĩa là

  • \displaystyle K đóng với phép cộng véctơ và phép nhân véctơ với số không âm.
  • \displaystyle K khác rỗng
  • \displaystyle K có đỉnh: Nếu \displaystyle a,-a\in K thì \displaystyle a=0

Nhận xét: Như vậy, để xác định một quan hệ thứ tự tốt, ta chỉ cần xác định một tập nón lồi các véctơ “lớn hơn” véctơ \displaystyle {0}. Ta còn kí hiệu \displaystyle a\geq_K b.

Ví dụ:

  1. Phép so sánh 2 véctơ qua từng thành phần được định nghĩa bởi nón lồi \displaystyle K = \{x: x\geq 0\}.

Với quan hệ thứ tự mới này, ta có thể phát biểu bài toán quy hoạch nón (conic programming) như sau: Cho nón lồi có đỉnh \displaystyle K\neq \emptyset, tìm

\displaystyle \min_x \{c^Tx: Ax\geq_K b\}

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: