Tìm kiếm mẫu

Bách khoa toàn thư mở Wikipedia
Ví dụ về hội tụ của phương pháp tìm kiếm trực tiếp trên hàm Broyden

Tìm kiếm mẫu (tiếng Anh: pattern search) là một họ phương pháp tối ưu số không đòi hỏi građien của bài toán cần tối ưu do đó có thể áp dụng với các hàm không liên tục hoặc khả vi. Các phương pháp tối ưu như thế cũng được biết đến với tên gọi tìm kiếm trực tiếp (direct-search), không vi phân (derivative-free), hoặc hộp đen (black-box).

Tên gọi tìm kiếm mẫu được đặt bởi Hooke và Jeeves [1]. Một biến thể tìm kiếm mẫu sớm và đơn giản là của Fermi và Metropolis khi họ làm việc ở Phòng Thí nghiệm Quốc gia Los Alamos. Davidon [2] đã tóm tắt thuật toán này như sau:

Họ biến thiên mỗi lần một tham số lý thuyết với những bước cùng độ lớn và khi không tồn tại phép thêm bớt nào với từng tham số có thể cải thiện độ khớp với dữ liệu thực nghiệm, họ chia đôi bước nhảy và lặp lại quá trình đến khi thấy các bước đủ nhỏ.

Sự hội tụ[sửa | sửa mã nguồn]

Một phương pháp tìm kiếm mẫu hội tụ được đề xuất bởi Yu - người đã chứng minh sự hội tụ của nó bằng lý thuyết cơ sở dương (positive basis).[3] Sau đó, Torczon, Lagarias, và các đồng tác giả[4][5] đã sử dụng kỹ thuật cơ sở dương để chứng minh sự hội tụ của một phương pháp tìm kiếm mẫu khác, trong một lớp hàm cụ thể. Ngoài các lớp đó, tìm kiếm mẫu là một phương pháp heuristic mà có thể cho lời giải xấp xỉ hữu ích với một số bài toán nhưng thất bại với các bài toán khác. Ngoài các lớp đó, tìm kiếm mẫu không phải một phương pháp lặp hội tụ đến lời giải, thực tế, tìm kiếm mẫu có thể hội tụ đến những điểm không ổn định trong một số tame problems.[6] [7]

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Hooke, R.; Jeeves, T.A. (1961). “'Direct search' solution of numerical and statistical problems”. Journal of the Association for Computing Machinery (ACM). 8 (2): 212–229. doi:10.1145/321062.321069.
  2. ^ Davidon, W.C. (1991). “Variable metric method for minimization”. SIAM Journal on Optimization. 1 (1): 1–17. doi:10.1137/0801001.
  3. ^ *Yu, Wen Ci. 1979. "Positive basis and a class of direct search techniques". Scientia Sinica [Zhongguo Kexue]: 53—68.
    • Yu, Wen Ci. 1979. "The convergent property of the simplex evolutionary technique". Scientia Sinica [Zhongguo Kexue]: 69–77.
  4. ^ Torczon, V.J. (1997). “On the convergence of pattern search algorithms”. SIAM Journal on Optimization. 7 (1): 1–25. doi:10.1137/S1052623493250780.
  5. ^ Dolan, E.D.; Lewis, R.M.; Torczon, V.J. (2003). “On the local convergence of pattern search”. SIAM Journal on Optimization. 14 (2): 567–583. doi:10.1137/S1052623400374495.
  6. ^
    • Powell, Michael J. D. 1973. "On Search Directions for Minimization Algorithms." Mathematical Programming 4: 193—201.
    • McKinnon, K.I.M. (1999). “Convergence of the Nelder–Mead simplex method to a non-stationary point”. SIAM J Optimization. 9: 148–158. doi:10.1137/S1052623496303482. (algorithm summary online).
  7. ^ ÇěĚĈćĆËĐģĞĞ
Lấy từ “https://vi.wikipedia.org/w/index.php?title=Tìm_kiếm_mẫu&oldid=61775701”