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

Learn & Enjoy …

Quy hoạch lồi (1) – Bài toán và các khái niệm cơ bản

Posted by Trần Quốc Long on Tháng Hai 14, 2008

Định nghĩa (Quy hoạch toán học): Bài toán quy hoạch toán học (P) (mathematical programming) là bài toán tìm cực trị

\mathrm{Opt}(P)=\displaystyle \min_x\left\{f(x):\begin{array}{r} g(x)=(g_1(x),\ldots,g_m(x))^T\leq 0\\h(x)=(h_1(x),\ldots,h_k(x))=0\\ x\in X\end{array}\right\}~~(P) ,

trong đó

  1. f(x) gọi là hàm mục tiêu.
  2. g(x)=(g_1(x),\ldots,g_m(x))^T\leq 0 là các ràng buộc bất đẳng thức.
  3. h(x)=(h_1(x),\ldots,h_k(x))=0 là các ràng buộc đẳng thức.
  4. X\subset\mathrm{R}^n là miền xác định.
  5. x\in X thỏa mãn tất cả các ràng buộc gọi là nghiệm chấp nhận được (hoặc gọi tắt là nghiệm).
    Tập tất cả các nghiệm chấp nhận được, S_P, được gọi tắt là tập nghiệm.
    Khi tập nghiệm S_P\neq\emptyset, ta nói (P) thỏa được.
  6. Nếu f(x) bị chặn dưới trên tập nghiệm, ta nói (P) bị chặn.
  7. Giá trị tối ưu của hàm mục tiêu
    \mathrm{Opt}(P)=\displaystyle \inf_{x\in S_P}f(x) nếu (P) thỏa được.
    \mathrm{Opt}(P)=-\infty nếu (P) thỏa được nhưng không bị chặn.
    \mathrm{Opt}(P)=+\infty nếu (P) không thỏa được.
  8. Nghiệm tối ưu của (P)nghiệm chấp nhận được x^* sao cho f(x^*)=\mathrm{Opt}(P). Bài toán quy hoạch (P) có nghiệm tối ưu gọi là bài toán giải được.

Nhận xét:

  1. Các ràng buộc dạng g(x)\leq f(x), g(x)=f(x) có thể biến thành g(x)-f(x)\leq 0, g(x)-f(x)=0.
  2. Ta cũng có thể phát biểu bài toán tìm cực đại với các khái niệm bị chặn, giá trị tối ưu thay đổi tương ứng.

Định nghĩa (Quy hoạch lồi): Bài toán quy hoạch toán học

\mathrm{Opt}(P) =\displaystyle \min_x\left\{f(x):\begin{array}{r} g(x)=(g_1(x),\ldots,g_m(x))^T\leq 0\\ x\in X\end{array}\right\}~~(P)

gọi là bài toán quy hoạch lồi (convex programming) nếu

  1. X\subset \mathrm{R}^n là tập lồi.
  2. f(x), g_1(x),\ldots,g_m(x) là các hàm lồi.
  3. Không có ràng buộc đẳng thức.

Nhận xét:

  1. Ta có thể đưa vào các ràng buộc đẳng thức, nhưng do tính lồi của hàm h_i(x), hàm này phải là hàm tuyến tính trên X, do đó các điều kiện này tương ứng với việc giới hạn tập nghiệm trên không gian affine con của \mathrm{R}^n, tức là không mất tính tổng quát, về mặt lý thuyết có thể giả sử không có ràng buộc đẳng thức.
  2. Trong thực hành, khi thiết kế thuật toán quy hoạch, không thể không tính đến các ràng buộc đẳng thức, khi đó thường người ta biến đổi thuật toán để nó hoạt động trên không gian affine tương ứng (sử dụng hệ cơ sở affine và các tọa độ trên hệ này).
  3. g_i(x) lồi nên tập \{x:g_i(x)\leq 0\} lồi (xem bài điều kiện cực tiểu của hàm lồi). Như vậy tập nghiệm S_P là tập lồi vì nó là giao của các tập lồi.

Điều kiện Slater: Bài toán quy hoạch lồi (P) thỏa mãn điều kiện Slater (Slater conditions) nếu tồn tại \bar{x}\in X sao cho g_i(\bar{x})<0,\forall i. Tức là các ràng buộc đều thỏa mãn tại \bar{x} bằng bất đẳng thức thật sự.

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: