Tìm kiếm mẫu

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. 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  đã tóm tắt thuật toán này như sau:

 Sự hội tụ 
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).*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. Sau đó, Torczon, Lagarias, và các đồng tác giả đã 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. Powell, Michael J. D. 1973. "On Search Directions for Minimization Algorithms." Mathematical Programming 4: 193—201.
  (algorithm summary online).
ÇěĚĈćĆËĐģĞĞ

 Xem thêm 
 Tìm kiếm ngẫu nhiên
 Tối ưu ngẫu nhiên

 Tham khảo 

Thể loại:Thuật toán tối ưu hóa
Thể loại:Tối ưu hóa (toán học)