Tối ưu không ràng buộc (2) – Tìm kiếm trên đường thẳng (line search)
Posted by Trần Quốc Long trên Tháng Tư 22, 2008
Giả sử khi cực tiểu hóa hàm , tại điểm
ta đã tìm được hướng làm giảm hàm mục tiêu
. Ta cần tìm bước nhảy (step size)
sao cho
,
trong đó . Việc tìm bước nhảy
được gọi là tìm kiếm trên đường thẳng (line search). Rõ ràng, lý tưởng nhất là ta tìm được bước nhảy
.
Việc tìm gọi là tìm kiếm chính xác (exact line search), còn nếu ta chỉ cần tìm
sao cho
thì ta gọi là tìm kiếm không chính xác (inexact line search).
Tìm kiếm chính xác: Bài toán chuyển về việc cực tiểu hóa hàm 1 biến . Ta có thể dễ dàng tìm
nếu
là hàm tuyến tính, đa thức bậc 2. Các trường hợp khác thường được quy về việc giải phương trình
và là một trong các nghiệm của phương trình trên. Một trường hợp khác có thể giải khá hiệu quả là khi
- Ta cần cực tiểu hóa hàm liên tục
trên đoạn
.
- Trên đoạn
, hàm
có dạng hình nón ngửa và chỉ có một cực tiểu duy nhất.
Phương pháp tìm cực tiểu của trong trường hợp này như sau:
- Chọn
bất kì sao cho
- Nếu
, rõ ràng
không thể nằm trong đoạn
vì nếu như vậy
Tức là hàm
không có dạng hình nón ngửa. Vậy
. Nói cách khác
là tập ứng cử viên mới.
- Nếu
, tương tự như trên, ta kết luận
là tập ứng cử viên mới.
- Trong cả hai trường hợp, ta đều giảm được tập ứng cử viên. Tiếp tục lặp lại bước 1 cho đến khi tập ứng cử viên đủ nhỏ.
Trong phương pháp trên, dễ thấy, ta hoàn toàn tự do khi lựa chọn . Một lựa chọn dễ thấy là chọn
để chia đoạn làm 3 đoạn thẳng bằng nhau. Để ý là tại mỗi bước lặp, ta phải tính toán giá trị
hai lần tại
. Nếu ta khéo léo lựa chọn
, ta có thể giảm được số lần tính toán
. Ý tưởng đơn giản như sau, tại mỗi bước lặp, ta lựa chọn
theo một tỉ lệ nhất định để trong lần lặp sau, một trong 2 giá trị của
đã được tính toán từ lần lặp trước. Tỉ lệ này như sau
Dễ thấy
Suy ra
Giải phương trình bậc 2 này ta được
Đây chính là tỉ lệ vàng (golden ratio) (có lúc người ta coi là tỉ lệ vàng). Để ý là, sau mỗi bước lặp, kích thước của tập ứng cử viên giảm đi theo tỉ lệ
nên phương pháp này còn được gọi là phương pháp phân chia theo tỉ lệ vàng (golden search). Tốc độ hội tụ của các phương pháp phân chia theo tỉ lệ cố định là tuyến tính.
Tìm kiếm không chính xác: Phép kiểm tra Armijo (Armijo’s test) cho phép kiểm tra bước nhảy có làm giảm hàm mục tiêu quá một ngưỡng cho trước hay không. Phép kiểm tra này như sau:
- Bước nhảy
được gọi là thích hợp (appropriate) nếu
với
.
- Bước nhảy
được gọi là tốt nhất (nearly maximal) nếu
với
.
- Bước nhảy
gọi là bước nhảy Armijo nếu nó thích hợp và tốt nhất.
Nhận xét:
- Nếu
, bước nhảy thích hợp chắc chắn sẽ làm giảm hàm mục tiêu vì
- Như vậy, khi
, bước nhảy Armijo
chắc chắn sẽ làm giảm hàm mục tiêu nhưng
không còn là bước nhảy thích hợp nữa (đây là lý do ta gọi bước nhảy Armijo là tốt nhất).
Thuật toán tìm bước nhảy Armijo: Ta đã biết, khi thì chắc chắn tồn tại
sao cho
. Thuật toán sau đây cho phép tìm ra bước nhảy Armijo (với tham số
) khi
bị chặn dưới và
:
- Bắt đầu với một bước nhảy
bất kì.
- Nếu
là bước nhảy thích hợp, lần lượt kiểm tra các bước nhảy
đến khi gặp một bước nhảy không thích hợp. Bước nhảy trước đó chính là bước nhảy Amijo.
- Nếu
không phải là bước nhảy thích hợp, lần lượt kiểm tra các bước nhảy
đến khi gặp một bước nhảy thích hợp. Bước nhảy này chính là bước nhảy Amijo.
Chứng minh: Nếu thuật toán chạy vào bước 2, việc kiểm tra các bước nhảy phải dừng vì nếu
và
thì do nên
, tức là
không bị chặn, mâu thuẫn.
Nếu thuật toán chạy vào bước 3, ta có
Do , nên khi
đủ nhỏ, ta có
Rõ ràng
nên đến một lúc nào đó sẽ đủ nhỏ để
tức là việc kiểm tra cũng dừng.
Trả lời