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

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

,

trong đó

1. gọi là hàm mục tiêu.
2. là các ràng buộc bất đẳng thức.
3. là các ràng buộc đẳng thức.
4. là miền xác định.
5. 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, , được gọi tắt là tập nghiệm.
   Khi tập nghiệm , ta nói thỏa được.
6. Nếu bị chặn dưới trên tập nghiệm, ta nói bị chặn.
7. Giá trị tối ưu của hàm mục tiêu
   nếu thỏa được.
   nếu thỏa được nhưng không bị chặn.
   nếu không thỏa được.
8. Nghiệm tối ưu của là nghiệm chấp nhận được sao cho . Bài toán quy hoạch 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 có thể biến thành .
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

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

1. là tập lồi.
2. 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àm này phải là hàm tuyến tính trên , 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 , 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. Vì lồi nên tập 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 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 thỏa mãn điều kiện Slater (Slater conditions) nếu tồn tại sao cho . Tức là các ràng buộc đều thỏa mãn tại bằng bất đẳng thức thật sự.