Constrained optimization – Overview of algorithms

Như đã nói trong bài trước, các thuật toán tối ưu cục bộ đều có chung một tư tưởng để tìm lời giải tối ưu. Tuy nhiên tùy thuộc vào tính chất của hàm mục tiêu và của ràng buộc mà sẽ có các chiến lược khác nhau. Entry ngắn này liệt kê các phương pháp tối ưu cho từng trường hợp cụ thể. Các bài viết sau sẽ lần lượt trình bày các thuật toán này.

Tên bài toán Hàm mục tiêu Ràng buộc Thuật toán
Tổng quát
f\left(x\right)
Tuyến tính đẳng thức
Ax = b
Thuật toán A
Bậc 2
f\left(x\right) =\frac{1}{2}x^\top Qx + c^\top x
Tuyến tính đẳng thức
Ax = b
Thuật toán B
Tổng quát
f\left(x\right)
Tuyến tính bất đẳng thức
Ax \geq b
Active set
Tổng quát
f\left(x\right)
Tuyến tính đẳng thức và bị chặn
Ax = b
0 \leq x \leq \bar{x}
Murtagh-Saunders
 Linear programming Tuyến tính
f\left(x\right) = c^\top x
Tuyến tính đẳng thức và bị chặn
Ax = b
x\geq 0
Simplex method (bản rút gọn của
Murtagh-Saunders dành cho
linear programming)
Nonlinearly constrained Tổng quát
f\left(x\right)
Tổng quát
h\left(x\right)
Augmented Lagrangian,
Newton’s method…

Thuật toán A và thuật toán B chưa được đặt tên nên ta cứ tạm gọi tên như vậy.

Bảng này còn thiếu trong trường hợp tối ưu không ràng buộc, và cho các bài toán tối ưu rời rạc (gọi chung là integer programming). Hi vọng các bài sau sẽ lần lượt trình bày được các thuật toán này.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s