Phương pháp gradient đơn giản nhất. Phương pháp tối ưu hóa không bị giới hạn Gradient

Phương pháp này dựa trên sửa đổi lặp đi lặp lại sau đây của công thức

x k +1 = x k + a k s (x k),

x k + 1 = x k - a k Ñ f (x k), trong đó

a - hệ số dương đã cho;

Ñ ​​f (x k) - gradient hàm mục tiêuđơn hàng đầu tiên.

Flaws:

sự cần thiết phải chọn một giá trị thích hợp của ;

hội tụ chậm đến điểm cực tiểu do độ nhỏ của f (x k) trong vùng lân cận của điểm này.

Phương pháp đi xuống dốc nhất

Giải phóng khỏi nhược điểm đầu tiên của phương pháp gradient đơn giản nhất, vì a k được tính bằng cách giải bài toán cực tiểu Ñ f (x k) dọc theo hướng Ñ f (x k) bằng cách sử dụng một trong các phương pháp tối ưu một chiều x k + 1 = x k - a k Ñ f (x k).

Phương pháp này đôi khi được gọi là phương pháp Cauchy.

Thuật toán được đặc trưng bởi một tỷ lệ hội tụ thấp trong việc giải quyết các vấn đề thực tế. Điều này được giải thích bởi thực tế là sự thay đổi của các biến phụ thuộc trực tiếp vào độ lớn của gradient, có xu hướng bằng không trong vùng lân cận của điểm cực tiểu và không có cơ chế gia tốc ở các lần lặp cuối cùng. Do đó, có tính đến tính ổn định của thuật toán, phương pháp dốc nhất thường được sử dụng làm thủ tục ban đầu để tìm lời giải (từ các điểm nằm ở khoảng cách đáng kể so với điểm cực tiểu).

Phương pháp hướng kết hợp

Bài toán tổng quát của lập trình phi tuyến tính không có ràng buộc như sau: cực tiểu f (x), x E n, trong đó f (x) là hàm mục tiêu. Khi giải bài toán này, chúng ta sử dụng các phương pháp cực tiểu dẫn đến một điểm đứng yên f (x) được xác định bởi phương trình f (x *) = 0. Phương pháp hướng liên hợp đề cập đến các phương pháp tối thiểu hóa không giới hạn sử dụng các đạo hàm. Nhiệm vụ: tối thiểu f (x), x E n, trong đó f (x) là hàm mục tiêu của n biến độc lập. Một tính năng quan trọng là sự hội tụ nhanh do thực tế là khi chọn hướng, ma trận Hessian được sử dụng, ma trận này mô tả khu vực cấu trúc liên kết của bề mặt phản ứng. Đặc biệt, nếu hàm mục tiêu là bậc hai thì điểm cực tiểu có thể đạt được không quá một số bước bằng thứ nguyên của bài toán.

Để áp dụng phương pháp vào thực tế, nó phải được bổ sung các quy trình kiểm tra tính hội tụ và tính độc lập tuyến tính của hệ thống hướng. Phương pháp đặt hàng thứ hai

Phương pháp Newton

Việc áp dụng liên tiếp sơ đồ xấp xỉ bậc hai dẫn đến việc thực hiện phương pháp tối ưu hóa Newton theo công thức

x k +1 = x k - Ñ 2 f (x k -1) Ñ f (x k).

Nhược điểm của phương pháp Newton là không đủ độ tin cậy khi tối ưu hóa các hàm mục tiêu không bậc hai. Do đó, nó thường được sửa đổi:

x k +1 = x k - a k Ñ 2 f (x k -1) Ñ f (x k), trong đó

a k là tham số được chọn sao cho f (x k + 1) min.

2. Tìm cực trị của hàm số không giới hạn

Một số hàm f (x) được cho trên một khoảng mở (a, c) của sự thay đổi trong đối số x. Chúng tôi giả định rằng exst tồn tại trong khoảng thời gian này (phải nói rằng, trong trường hợp chung, điều này không thể được phát biểu trước về mặt toán học; tuy nhiên, trong các ứng dụng kỹ thuật, sự hiện diện của exst rất thường xuyên trong một khoảng biến thiên nhất định của biến thể đối số khoảng thời gian có thể được dự đoán từ các cân nhắc vật lý).

Định nghĩa của exst. Hàm f (x) đã cho trên khoảng (a, c) có tại điểm x * max (min), nếu điểm này có thể được bao quanh bởi một khoảng (x * -ε, x * + ε) chứa trong khoảng (a, c), mà với tất cả các điểm x thuộc khoảng (x * -ε, x * + ε), bất đẳng thức sau là:

f (x) ≤ f (x *) → cho max

f (x) ≥ f (x *) → trong phút

Định nghĩa này không đặt ra bất kỳ hạn chế nào đối với lớp của các hàm f (x), tất nhiên là rất có giá trị.

Nếu chúng ta tự giới hạn các hàm f (x) vào một lớp khá phổ biến, nhưng vẫn hẹp hơn của các hàm trơn (theo hàm trơn, chúng ta có nghĩa là các hàm liên tục cùng với các đạo hàm của chúng trên khoảng thay đổi của đối số), thì chúng ta có thể sử dụng định lý Fermat, đưa ra các điều kiện cần thiết cho sự tồn tại của exst.

Định lý Fermat. Cho hàm số f (x) xác định trong khoảng (a, b) nào đó và tại điểm “c” của khoảng này thì nó nhận giá trị lớn nhất (nhỏ nhất). Nếu có một đạo hàm hữu hạn hai phía tại thời điểm này, thì sự tồn tại của exst là cần thiết.

Ghi chú. Đạo hàm hai phía được đặc trưng bởi thuộc tính, nói cách khác, chúng tôi đang nói chuyện về thực tế là tại điểm "c" đạo hàm trong giới hạn giống nhau khi tiếp cận điểm "c" từ trái và phải, tức là f (x) - Chức năng mịn.

* Trong trường hợp min diễn ra, và khi → max. Cuối cùng, nếu tại x = x 0, thì việc sử dụng đạo hàm cấp 2 không giúp ích được gì và bạn cần phải sử dụng định nghĩa exst, chẳng hạn.

Khi giải quyết vấn đề I, các điều kiện cần thiết exst (nghĩa là, định lý Fermat) được sử dụng rất thường xuyên.

Nếu phương trình exst có các gốc thực, thì các điểm tương ứng với các gốc này là nghi ngờ đối với exst (nhưng không nhất thiết là bản thân các cực trị, vì chúng ta đang xử lý với các điều kiện cần và đủ). Vì vậy, ví dụ, tại điểm uốn X p diễn ra, tuy nhiên, như bạn biết, đây không phải là điểm cực trị.

Hãy cũng lưu ý rằng:

từ điều kiện cần thiết không thể nói loại cực trị nào được tìm thấy là cực đại hay cực tiểu: cần phải nghiên cứu thêm để xác định điều này;

Từ các điều kiện cần thiết không thể xác định được đây là cực trị toàn cầu hay cực cục bộ.

Do đó, khi các điểm đáng ngờ đối với exst được tìm thấy, chúng sẽ được điều tra bổ sung, ví dụ, dựa trên định nghĩa của exst hoặc đạo hàm thứ 2.

Phương pháp giảm dần độ dốc.

Hướng đi dốc nhất tương ứng với chiều giảm lớn nhất của hàm. Biết rằng chiều tăng lớn nhất của hàm hai biến u = f (x, y) được đặc trưng bởi gradient của nó:

trong đó e1, e2 - vectơ đơn vị(orts) theo hướng của các trục tọa độ. Do đó, hướng ngược lại với gradient sẽ chỉ ra hướng giảm lớn nhất của hàm. Các phương pháp dựa trên việc chọn một đường dẫn tối ưu hóa bằng cách sử dụng một gradient được gọi là dốc.

Ý tưởng đằng sau phương pháp gradient descent như sau. Chọn một số điểm bắt đầu

chúng tôi tính toán gradient của hàm được xem xét trong đó. Chúng tôi thực hiện một bước theo hướng ngược lại với gradient:

Quá trình tiếp tục cho đến khi đạt được giá trị nhỏ nhất của hàm mục tiêu. Nói một cách chính xác, sự kết thúc của tìm kiếm sẽ đến khi chuyển động từ điểm thu được với bất kỳ bước nào dẫn đến sự gia tăng giá trị của hàm mục tiêu. Nếu đạt đến mức tối thiểu của hàm bên trong vùng được xem xét, thì tại thời điểm này, gradient bằng 0, cũng có thể dùng như một tín hiệu về sự kết thúc của quá trình tối ưu hóa.

Phương pháp giảm độ dốc gradient có nhược điểm giống như phương pháp giảm độ cao tọa độ: với sự hiện diện của các khe núi trên bề mặt, sự hội tụ của phương pháp rất chậm.

Trong phương pháp được mô tả, cần phải tính toán gradient của hàm mục tiêu f (x) tại mỗi bước tối ưu hóa:

Các công thức cho đạo hàm riêng chỉ có thể nhận được một cách rõ ràng khi hàm mục tiêu được đưa ra một cách giải tích. Nếu không, các dẫn xuất này được tính bằng cách sử dụng phân biệt số:

Khi sử dụng gradient descent trong các bài toán tối ưu hóa, lượng tính toán chính thường rơi vào việc tính toán gradient của hàm mục tiêu tại mỗi điểm của quỹ đạo đi xuống. Vì vậy, nên giảm số điểm như vậy mà không ảnh hưởng đến giải pháp. Điều này đạt được trong một số phương pháp là sự thay đổi độ dốc của gradient. Một trong số đó là phương pháp dốc nhất. Theo phương pháp này, sau khi xác định hướng ngược lại với gradient của hàm mục tiêu tại điểm ban đầu, bài toán tối ưu hóa một chiều được giải quyết bằng cách tối ưu hóa hàm theo hướng này. Cụ thể, chức năng được tối thiểu hóa:

Để giảm thiểu một trong những phương pháp tối ưu hóa một chiều có thể được sử dụng. Cũng có thể chỉ cần di chuyển theo hướng ngược lại với gradient, trong khi không đi một bước mà là nhiều bước cho đến khi hàm mục tiêu ngừng giảm. Tại điểm mới được tìm thấy, hướng đi xuống một lần nữa được xác định (sử dụng một gradient) và một điểm cực tiểu mới của hàm mục tiêu được tìm thấy, v.v. Trong phương pháp này, sự giảm xuống xảy ra theo các bước lớn hơn nhiều và gradient của hàm được tính bằng ít hơnđiểm. Sự khác biệt là ở đây hướng của tối ưu hóa một chiều được xác định bởi gradient của hàm mục tiêu, trong khi gốc tọa độ được thực hiện ở mỗi bước dọc theo một trong các hướng tọa độ.

Phương pháp rút gọn bậc nhất cho trường hợp hàm hai biến z = f (x, y).

Đầu tiên, dễ dàng chứng minh rằng gradient của hàm số vuông góc với tiếp tuyến của đường cấp tại một điểm cho trước. Do đó, trong các phương pháp gradient, sự giảm xuống xảy ra dọc theo đường bình thường đến đường mức. Thứ hai, tại điểm đạt cực tiểu của hàm mục tiêu dọc theo hướng, đạo hàm của hàm theo hướng này biến mất. Nhưng đạo hàm của hàm số bằng 0 theo hướng của tiếp tuyến với đường cấp. Theo đó, gradient của hàm mục tiêu tại điểm mới vuông góc với hướng của tối ưu hóa một chiều ở bước trước đó, tức là, đường đi xuống ở hai bước liên tiếp được thực hiện theo các hướng vuông góc với nhau.

Tôi sẽ ném vào một số kinh nghiệm của tôi :)

Phương pháp gốc tọa độ

Ý tưởng của phương pháp này là tìm kiếm xảy ra theo hướng đi xuống của tọa độ trong lần lặp mới. Việc hạ độ cao được thực hiện dần dần theo từng tọa độ. Số lượng tọa độ trực tiếp phụ thuộc vào số lượng biến.
Để chứng minh phương pháp này hoạt động như thế nào, trước tiên bạn cần lấy hàm z = f (x1, x2,…, xn) và chọn bất kỳ điểm M0 (x10, x20,…, xn0) trong không gian n, điều này phụ thuộc vào số đặc điểm của hàm. Tiếp theo từng bước một cố định tất cả các điểm của hàm thành một hằng số, ngoại trừ điểm đầu tiên. Điều này được thực hiện để tìm kiếm tối ưu hóa đa biến giảm vấn đề tối ưu hóa một chiều, tức là tìm kiếm đối số x1, thành nghiệm của tìm kiếm trên một đoạn nào đó.
Để tìm giá trị của biến này, cần phải giảm xuống dọc theo tọa độ này để điểm mới M1 (x11, x21,…, xn1). Hơn nữa, hàm được phân biệt và sau đó chúng ta có thể tìm giá trị của điểm tiếp theo mới bằng cách sử dụng biểu thức này:

Sau khi tìm thấy giá trị của biến, bạn phải lặp lại lặp lại sửa chữa tất cả các đối số ngoại trừ x2 và bắt đầu giảm dần tọa độ mớiđến điểm mới tiếp theo M2 (x11, x21, x30…, xn0). Bây giờ giá trị của điểm mới sẽ xảy ra theo biểu thức:

Và một lần nữa, phép lặp với sự cố định sẽ được lặp lại cho đến khi tất cả các đối số từ xi đến xn kết thúc. Ở lần lặp cuối cùng, chúng ta sẽ tuần tự đi qua tất cả các tọa độ có thể có trong đó đã tìm thấy cực tiểu cục bộ, vì vậy hàm mục tiêu tại tọa độ cuối cùng sẽ đạt mức tối thiểu toàn cục. Một trong những ưu điểm của phương pháp này là bất cứ lúc nào cũng có thể ngắt đoạn xuống và điểm cuối cùng tìm được sẽ là điểm cực tiểu. Điều này rất hữu ích khi phương thức đi vào một vòng lặp vô hạn và tọa độ tìm thấy cuối cùng có thể được coi là kết quả của tìm kiếm này. Tuy nhiên, cài đặt mục tiêu của tìm kiếm tối thiểu chung trong khu vực có thể không đạt được do thực tế là chúng tôi đã làm gián đoạn tìm kiếm về mức tối thiểu (xem Hình 1).

Hình 1 - Hủy bỏ gốc tọa độ

Nghiên cứu của phương pháp này cho thấy rằng mỗi điểm tính toán được tìm thấy trong không gian là một điểm tối thiểu toàn cầu chức năng nhất định, và hàm z = f (x1, x2,…, xn) là hàm lồi và phân biệt.
Từ đó chúng ta có thể kết luận rằng hàm z = f (x1, x2,…, xn) là lồi và khả vi trong không gian, và mỗi điểm giới hạn tìm được trong dãy M0 (x10, x20,…, xn0) sẽ là một cực tiểu toàn cục điểm (xem Hình 2) của chức năng này bằng phương pháp giảm tọa độ.

Hình 2 - Các điểm cực tiểu cục bộ trên trục tọa độ

Có thể kết luận rằng thuật toán này đối phó tốt với nhiệm vụ đơn giản tối ưu hóa đa chiều, bằng cách giải liên tiếp n số bài toán tối ưu hóa một chiều, ví dụ, sử dụng phương pháp phần vàng.

Tiến trình của phương pháp giảm tọa độ xảy ra theo thuật toán được mô tả trong sơ đồ khối (xem Hình 3). Lặp lại quá trình thực thi phương thức này:
Ban đầu, một số tham số phải được nhập: độ chính xác Epsilon, phải hoàn toàn dương, điểm bắt đầu x1 mà ​​từ đó chúng ta sẽ bắt đầu thực hiện thuật toán của mình và đặt Lambda j;
Bước tiếp theo là lấy điểm xuất phát đầu tiên x1, sau đó phương trình một chiều thông thường với một biến được giải và công thức tìm điểm cực tiểu sẽ là, trong đó k = 1, j = 1:

Bây giờ, sau khi tính toán điểm cực trị, bạn cần kiểm tra số đối số trong hàm và nếu j nhỏ hơn n, thì bạn cần lặp lại bước trước đó và xác định lại đối số j = j + 1. Trong tất cả các trường hợp khác, Đến bước tiếp theo.
Bây giờ cần xác định lại biến x theo công thức x (k + 1) = y (n + 1) và thử thực hiện sự đồng tụ của hàm số với độ chính xác đã cho theo biểu thức:

Bây giờ, việc tìm điểm cực trị phụ thuộc vào biểu thức này. Nếu biểu thức này đúng, thì phép tính điểm cực trị giảm thành x * = xk + 1. Nhưng thường phải thực hiện thêm các lần lặp tùy thuộc vào độ chính xác, do đó giá trị của các đối số sẽ được xác định lại y (1 ) = x (k + 1), và giá trị của các chỉ số j = 1, k = k + 1.

Hình 3 - Sơ đồ khối của phương pháp giảm tọa độ

Kết quả là, chúng tôi có một thuật toán tối ưu hóa đa biến tuyệt vời và đa chức năng có thể tách nhiệm vụ khó khăn, thành nhiều cái một chiều lặp đi lặp lại liên tiếp. Có, phương pháp này khá đơn giản để thực hiện và có định nghĩa dễ dàng các điểm trong không gian, bởi vì phương pháp này đảm bảo sự hội tụ tới điểm địa phương tối thiểu. Nhưng ngay cả với những ưu điểm đáng kể như vậy, phương pháp này vẫn có thể đi vào vòng lặp vô tận do thực tế là nó có thể rơi vào một dạng khe núi.
Có các chức năng rãnh trong đó các chỗ lõm tồn tại. Thuật toán, khi rơi vào một trong những đáy này, không thể thoát ra được nữa, và nó sẽ tìm ra điểm tối thiểu đã có ở đó. Cùng một cách con số lớn việc sử dụng liên tiếp cùng một phương pháp tối ưu hóa một chiều có thể ảnh hưởng lớn đến yếu máy vi tính. Không chỉ sự hội tụ trong hàm này rất chậm, vì cần phải tính toán tất cả các biến và thường độ chính xác được chỉ định cao làm tăng thời gian giải bài toán lên nhiều lần, nhưng nhược điểm chính là thuật toán này- khả năng ứng dụng hạn chế.
Tiến hành nghiên cứu các thuật toán khác nhau để giải quyết các vấn đề tối ưu hóa, cần lưu ý rằng vai trò to lớnđóng vai trò chất lượng của các thuật toán dữ liệu. Ngoài ra, đừng quên những đặc điểm quan trọng, như thời gian và sự ổn định của quá trình thực thi, khả năng tìm thấy giá trị tốt nhất, giảm thiểu hoặc tối đa hóa hàm mục tiêu, dễ thực hiện giải quyết các vấn đề thực tiễn. Phương pháp gốc tọa độ rất dễ sử dụng, nhưng trong các bài toán tối ưu hóa đa biến, thường thì bạn cần thực hiện các phép tính phức tạp hơn là phân vùng. toàn bộ nhiệm vụ cho các nhiệm vụ phụ.

Phương pháp Nelder-Mead

Điều đáng chú ý là sự phổ biến của thuật toán này trong giới nghiên cứu các phương pháp tối ưu hóa đa chiều. Phương pháp Nelder-Mead là một trong số ít phương pháp dựa trên khái niệm về sự biến đổi tuần tự của một đơn giản có thể biến dạng xung quanh một điểm cực trị và không sử dụng thuật toán di chuyển theo hướng cực tiểu toàn cục.
Hình đơn giản này là hình đều và được biểu diễn dưới dạng một hình đa diện với các đỉnh cách đều của hình đơn giản trong Không gian N chiều. Trong các không gian khác nhau, simplex ánh xạ tới một tam giác đều R2 và tới R3 một tứ diện đều.
Như đã đề cập ở trên, thuật toán là sự phát triển của phương pháp đơn giản hóa Spendley, Hoekst và Himsworth, nhưng, không giống như phương pháp sau, cho phép sử dụng các phương pháp đơn giản không chính xác. Thông thường, một simplex có nghĩa là đa diện lồi với số đỉnh N + 1, trong đó N là số tham số mô hình trong không gian n chiều.
Để bắt đầu sử dụng phương pháp này, bạn cần xác định đỉnh cơ sở của tất cả các tập tọa độ có sẵn bằng cách sử dụng biểu thức:

Điều đáng chú ý nhất về phương pháp này là simplex có khả năng thực hiện độc lập các chức năng nhất định:
Phản xạ qua trọng tâm, phản xạ có nén hoặc giãn;
kéo dài;
Nén.
Sự ưu tiên trong số các thuộc tính này được trao cho sự phản chiếu, vì tham số này là chức năng - tùy chọn nhất. Từ bất kỳ đỉnh nào đã chọn, có thể tạo ra một phản xạ so với trọng tâm của hình đơn giản bằng biểu thức:.

Trong đó xc là trọng tâm (xem Hình 1).

Hình 1 - Phản xạ qua trọng tâm

Bước tiếp theo là tính toán các đối số của hàm mục tiêu tại tất cả các đỉnh của đơn giản phản ánh. Sau đó, chúng ta sẽ nhận được đầy đủ thông tin về cách thức đơn giản sẽ hoạt động trong không gian và do đó thông tin về hoạt động của hàm.
Để tìm kiếm điểm tối thiểu hoặc tối đa của hàm mục tiêu bằng các phương pháp đơn giản, bạn phải tuân thủ trình tự sau:
Ở mỗi bước, một simplex được xây dựng, tại mỗi điểm, cần phải tính toán tất cả các đỉnh của nó, rồi sắp xếp kết quả theo thứ tự tăng dần;
Bước tiếp theo là phản ánh. Cần phải cố gắng lấy các giá trị của simplex mới và bằng cách phản ánh, chúng ta có thể loại bỏ các giá trị không mong muốn cố gắng di chuyển simplex không hướng tới mức tối thiểu chung;
Để nhận các giá trị của simplex mới, từ các kết quả đã sắp xếp thu được, chúng ta lấy hai đỉnh có những giá trị tồi tệ nhất. Có thể sẽ không thể chọn ngay các giá trị phù hợp, khi đó bạn sẽ phải quay lại bước đầu tiên và nén đơn giản đến mức nhiều nhất giá trị nhỏ nhất;
Kết thúc của việc tìm kiếm một điểm cực trị là trọng tâm, với điều kiện là giá trị của hiệu giữa các hàm có giá trị nhỏ nhất tại các điểm của đơn giản.

Thuật toán Nelder-Mead cũng sử dụng các hàm simplex này theo các công thức sau:

Chức năng phản xạ qua trọng tâm của đơn giản được tính toán từ biểu hiện sau:

Sự phản xạ này được thực hiện nghiêm ngặt đối với điểm cực trị và chỉ qua trọng tâm (xem Hình 2).

Hình 2 - Sự phản xạ của simplex xảy ra qua trọng tâm

Hàm nén bên trong simplex được tính bằng biểu thức sau:

Để thực hiện nén cần xác định điểm có giá trị nhỏ nhất (xem hình 3).

Hình 3 - Đơn giản được nén thành đối số nhỏ nhất.

Hàm phản xạ co đơn giản được tính bằng biểu thức sau:

Để thực hiện phản xạ có nén (xem Hình 4), cần nhớ công việc của hai chức năng riêng biệt - đây là phản xạ qua trọng tâm và nén đơn giản đến giá trị nhỏ nhất.

Hình 4 - Phản xạ với nén

Hàm phản xạ giãn đơn giản (xem Hình 5) xảy ra bằng cách sử dụng hai hàm - phản xạ qua trọng tâm và giãn qua giá trị lớn nhất.

Hình 5 - Phản xạ với duỗi.

Để chứng minh hoạt động của phương pháp Nelder-Mead, cần tham khảo sơ đồ khối của thuật toán (xem Hình 6).
Trước hết, như trong các ví dụ trước, cần đặt tham số biến dạng ε, tham số này phải nghiêm ngặt Trên không, cũng như thiết lập các tham số cần thiết để tính toán α, β và a. Điều này sẽ cần thiết để tính hàm f (x0), cũng như để xây dựng đơn giản chính nó.

Hình 6 - Phần đầu tiên của phương pháp Nelder - Mead.

Sau khi xây dựng đơn giản, cần phải tính toán tất cả các giá trị của hàm mục tiêu. Như đã mô tả ở trên về việc tìm kiếm cực trị bằng cách sử dụng hàm simplex, cần phải tính hàm simplex f (x) tại tất cả các điểm của nó. Tiếp theo, chúng tôi sắp xếp điểm cơ sở sẽ ở đâu:

Bây giờ điểm cơ sở đã được tính toán, cũng như tất cả các điểm khác được sắp xếp trong danh sách, chúng tôi kiểm tra điều kiện khả năng tiếp cận để biết độ chính xác mà chúng tôi đã chỉ định trước đó:

Ngay sau khi điều kiện này trở thành đúng, thì điểm x (0) của đơn giản sẽ được coi là điểm mong muốn cực đoan. Nếu không, chúng ta chuyển sang bước tiếp theo, nơi chúng ta cần xác định giá trị mới của trọng tâm bằng công thức:

Nếu điều kiện này được đáp ứng, thì điểm x (0) sẽ là điểm nhỏ nhất, nếu không, bạn cần phải chuyển sang bước tiếp theo, trong đó bạn cần tìm kiếm đối số của hàm nhỏ nhất:

Từ hàm cần lấy giá trị nhỏ nhất của đối số để chuyển sang bước tiếp theo của thuật toán. Đôi khi có một vấn đề mà một số đối số cùng một lúc có cùng giá trị, được tính toán từ hàm. Giải pháp cho vấn đề này có thể là xác định lại giá trị của đối số lên đến phần nghìn.
Sau khi tính toán lại đối số tối thiểu, cần phải lưu trữ lại các giá trị mới thu được ở n vị trí đối số.

Hình 7 - Phần thứ hai của phương pháp Nelder - Mead.

Giá trị được tính từ hàm trước đó phải được thay thế vào điều kiện fmin< f(xN). При истинном выполнении данного условия, точка x(N) будет являться минимальной из группы тех, которые хранятся в отсортированном списке и нужно вернуться к шагу, где мы рассчитывали центр тяжести, в противном случае, производим сжатие симплекса в 2 раза и возвращаемся к самому началу с новым набором точек.
Các nghiên cứu về thuật toán này cho thấy rằng các phương pháp có độ đơn giản không đều (xem Hình 8) vẫn còn khá kém được nghiên cứu, nhưng điều này không ngăn cản chúng đối phó với nhiệm vụ của mình một cách hoàn hảo.
Các thử nghiệm sâu hơn cho thấy bằng thực nghiệm có thể chọn các tham số của các hàm kéo giãn, nén và phản xạ phù hợp nhất cho bài toán, nhưng bạn có thể sử dụng các tham số được chấp nhận chung của các hàm này là α = 1/2, β = 2, γ = 2 hoặc α = 1/4, β = 5/2, γ = 2. Do đó, trước khi loại bỏ phương pháp này để giải bài toán, bạn cần hiểu rằng đối với mỗi lần tìm kiếm mới cho điểm cực trị không điều kiện, bạn cần theo dõi chặt chẽ hành vi của simplex trong quá trình hoạt động và lưu ý giải pháp không tiêu chuẩn phương pháp.

Hình 8 - Quá trình tìm cực tiểu.

Thống kê đã chỉ ra rằng một trong những vấn đề phổ biến nhất trong hoạt động của thuật toán này là sự thoái hóa của đơn giản có thể biến dạng. Điều này xảy ra khi mỗi khi một số đỉnh của đơn giản rơi vào một không gian, thứ nguyên của nó không thỏa mãn nhiệm vụ.
Do đó, thứ nguyên trong quá trình hoạt động và thứ nguyên đã cho ném một số đỉnh của đơn giản vào một đường thẳng, đưa phương thức vào một vòng lặp vô hạn. Thuật toán trong sửa đổi này vẫn chưa được trang bị cách để thoát khỏi tình huống này và di chuyển một đỉnh sang một bên, vì vậy bạn phải tạo một đơn giản mới với các tham số mới để điều này không xảy ra trong tương lai.
Một tính năng khác của phương pháp này là nó không hoạt động chính xác với sáu hoặc nhiều đỉnh của đơn giản. Tuy nhiên, bằng cách sửa đổi phương pháp này, bạn có thể loại bỏ vấn đề này và thậm chí không làm giảm tốc độ thực thi, nhưng giá trị của bộ nhớ được cấp phát sẽ tăng lên đáng kể. Phương pháp này có thể được coi là chu kỳ vì nó hoàn toàn dựa trên các chu kỳ, đó là lý do tại sao nó được chú ý công việc không chính xác tại Với số lượng lớn các đỉnh.
Thuật toán Nelder-Mead đúng ra có thể được coi là một trong những thực hành tốt nhất tìm điểm cực trị bằng cách sử dụng simplex và rất hữu ích để sử dụng nó trong các loại bài toán kinh tế và kỹ thuật khác nhau. Ngay cả khi có tính chu kỳ, nó sử dụng một lượng bộ nhớ rất nhỏ so với cùng một phương pháp lấy tọa độ và để tìm ra điểm cực trị của chính nó, nó được yêu cầu chỉ tính các giá trị của trọng tâm và hàm. Một số lượng nhỏ nhưng đủ các tham số phức tạp làm cho phương pháp này được sử dụng rộng rãi trong các bài toán phức tạp về toán học và sản xuất thực tế.
Các thuật toán Simplex là cạnh, những chân trời mà chúng ta sẽ không sớm mở ra, nhưng giờ đây chúng đã đơn giản hóa cuộc sống của chúng ta một cách đáng kể với thành phần trực quan của chúng.

P.S. Văn bản hoàn toàn là của tôi. Tôi hy vọng ai đó thông tin này sẽ hữu ích.

Như chúng ta đã lưu ý, vấn đề tối ưu hóa là vấn đề tìm kiếm các giá trị như vậy của các yếu tố X 1 = X 1* , X 2 = X 2* , …, Xk = Xk * , mà hàm phản hồi ( tại) đạt đến một giá trị cực đoan tại= ext (tối ưu).

đã biết Các phương pháp khác nhau giải pháp của bài toán tối ưu hóa. Một trong những phương pháp được sử dụng rộng rãi nhất là phương pháp gradient, còn được gọi là phương pháp Box-Wilson và phương pháp leo dốc.

Xem xét bản chất của phương pháp gradient bằng cách sử dụng ví dụ về hàm phản hồi hai yếu tố y =f (x 1 , X 2 ). Trên hình. 4.3 trong các đường cong không gian nhân tố được hiển thị giá trị ngang nhau các chức năng đáp ứng (đường cong mức). Điểm có tọa độ X 1 *, X 2 * tương ứng với giá trị cực trị của hàm phản hồi tại máy lẻ

Nếu chúng ta chọn bất kỳ điểm nào của không gian nhân tố làm điểm ban đầu ( X 1 0 , X 2 0), sau đó con đường ngắn nhấtđến đỉnh của hàm phản hồi từ điểm này là đường đi dọc theo đường cong, tiếp tuyến mà tại mỗi điểm trùng với pháp tuyến của đường cong mức, tức là đây là đường dẫn theo hướng gradient của hàm phản hồi.

Gradient của một hàm đơn giá trị liên tục y =f(x 1 , X 2) là một vectơ được xác định bởi hướng của gradient với tọa độ:

ở đâu tôi,j là các vectơ đơn vị theo hướng của các trục tọa độ X 1 và X 2. Đạo hàm từng phần và nêu đặc điểm có hướng của vectơ.

Vì chúng tôi không biết loại phụ thuộc y =f(x 1 , X 2), chúng ta không thể tìm thấy các đạo hàm riêng và xác định hướng thực sự của gradient.

Theo phương pháp gradient, trong một số phần của không gian yếu tố, điểm bắt đầu (các mức ban đầu) được chọn X 1 0 , X hai mươi . Đối với các mức ban đầu này, một sơ đồ hai mức đối xứng của thử nghiệm được xây dựng. Hơn nữa, khoảng biến thiên được chọn quá nhỏ để mô hình tuyến tính là phù hợp. Người ta biết rằng bất kỳ đường cong nào trên một diện tích đủ nhỏ đều có thể được tính gần đúng bằng mô hình tuyến tính.

Sau khi xây dựng sơ đồ hai cấp đối xứng, bài toán nội suy được giải quyết, tức là đang xây dựng mô hình tuyến tính:

và kiểm tra tính đầy đủ của nó.

Nếu mô hình tuyến tính phù hợp với khoảng biến thiên đã chọn, thì hướng của gradient có thể được xác định:

Do đó, hướng của gradient của hàm đáp ứng được xác định bởi các giá trị của hệ số hồi quy. Điều này có nghĩa là chúng ta sẽ di chuyển theo hướng của gradient, nếu từ một điểm có tọa độ ( ) đi đến điểm có tọa độ:

ở đâu m- một số dương xác định lượng bước theo hướng của gradient.

Vì X 1 0 = 0 và X 2 0 = 0, sau đó .

Bằng cách xác định hướng của gradient () và chọn kích thước bước m, chúng tôi thực hiện trải nghiệm ở cấp độ ban đầu X 1 0 , X 2 0 .

Sau đó, chúng tôi thực hiện một bước theo hướng của gradient, tức là tiến hành thí nghiệm tại một điểm có tọa độ. Nếu giá trị của hàm phản hồi đã tăng lên so với giá trị của nó ở mức ban đầu, chúng ta thực hiện một bước khác theo hướng của gradient, tức là chúng tôi thực hiện thử nghiệm tại một điểm có tọa độ:

Chúng tôi tiếp tục di chuyển dọc theo gradient cho đến khi hàm phản hồi bắt đầu giảm. Trên hình. 4.3 chuyển động dọc theo gradient tương ứng với một đường thẳng đi ra khỏi điểm ( X 1 0 , X hai mươi). Nó dần dần lệch khỏi hướng thực của gradient, được hiển thị bằng đường đứt nét, do tính không tuyến tính của hàm phản hồi.

Ngay sau khi giá trị của hàm phản ứng giảm trong thí nghiệm tiếp theo, chuyển động dọc theo gradient bị dừng lại, thí nghiệm được thực hiện với gia trị lơn nhât các hàm phản hồi cho một cấp ban đầu mới, tạo ra một kế hoạch hai cấp đối xứng mới và một lần nữa giải quyết vấn đề nội suy.

Xây dựng mô hình tuyến tính mới , thực hiện Phân tích hồi quy. Đồng thời, nếu kiểm định mức độ ý nghĩa của các yếu tố cho thấy rằng ít nhất một hệ số

đủ, có nghĩa là chưa đạt đến vùng cực trị của hàm phản hồi (vùng tối ưu). Một hướng mới của gradient được xác định và chuyển động hướng tới vùng tối ưu bắt đầu.

Việc tinh chỉnh hướng của gradient và chuyển động dọc theo gradient tiếp tục cho đến khi, trong quá trình giải bài toán nội suy tiếp theo, việc kiểm tra ý nghĩa của các yếu tố cho thấy rằng tất cả các yếu tố đều không đáng kể, tức là tất cả các . Điều này có nghĩa là đã đạt được vùng tối ưu. Về quyết định này vấn đề tối ưu hóa dừng lại và lấy trải nghiệm với giá trị lớn nhất của hàm phản hồi làm giá trị tối ưu.

TẠI nhìn chung Chuỗi các hành động cần thiết để giải quyết vấn đề tối ưu hóa bằng phương pháp gradient có thể được biểu diễn dưới dạng lưu đồ (Hình 4.4).

1) mức ban đầu của các yếu tố ( Xj 0) nên được chọn càng gần điểm tối ưu càng tốt, nếu có một số thông tin tiên nghiệm về vị trí của nó;

2) khoảng biến thiên (Δ Xj) nên được chọn sao cho mô hình tuyến tính có thể phù hợp. Đường viền dưới Δ Xj trong trường hợp này, là giá trị nhỏ nhất của khoảng biến thiên mà tại đó hàm phản hồi vẫn có ý nghĩa;

3) giá trị bước ( t) khi di chuyển dọc theo gradient, chúng được chọn theo cách sao cho sản phẩm lớn nhất không vượt quá chênh lệch giữa mức trên và mức dưới của các yếu tố ở dạng chuẩn hóa

.

Do đó, . Với giá trị nhỏ hơn t sự khác biệt giữa hàm phản hồi ở mức ban đầu và tại điểm có tọa độ có thể không đáng kể. Tại ý nghĩa lớn hơn bước, có nguy cơ trượt tính năng tối ưu của chức năng phản hồi.

Phương pháp Gauss-Seidel

Phương pháp này bao gồm việc luân phiên tìm điểm cực trị riêng của hàm mục tiêu cho mỗi yếu tố. Đồng thời, ở mỗi giai đoạn, các yếu tố (k-1) được ổn định và chỉ có một yếu tố thứ i thay đổi

Quy trình tính toán: trong vùng cục bộ của không gian nhân tố, dựa trên các thí nghiệm sơ bộ, một điểm được chọn tương ứng với kết quả tốt nhất và từ đó chúng bắt đầu hướng tới điều tối ưu. Bước chuyển động của mỗi yếu tố do nhà nghiên cứu đặt ra. Đầu tiên, tất cả các yếu tố được cố định ở cùng một mức và một yếu tố được thay đổi cho đến khi có sự tăng (giảm) trong hàm phản ứng (Y), sau đó yếu tố kia được thay đổi trong khi các yếu tố khác ổn định, v.v. cho đến khi chúng nhận được kết quả như ý(Y). Điều chính là chọn bước phù hợp cho từng yếu tố.

Phương pháp này là đơn giản nhất, mang tính minh họa cao nhất, nhưng quá trình chuyển động đến điểm tối ưu là lâu và phương pháp này hiếm khi dẫn đến điểm tối ưu. Hiện tại, nó đôi khi được sử dụng trong thí nghiệm máy.

Những phương pháp này cung cấp chuyển động đến mức tối ưu dọc theo một đường thẳng vuông góc với các đường của phản ứng bằng nhau, tức là theo hướng của gradient của hàm phản ứng.

Phương pháp Gradient có một số loại khác nhau về quy tắc lựa chọn các bước biến thiên và các bước làm việc ở mỗi giai đoạn của chuyển động đến cực đại.

Bản chất của tất cả các phương pháp như sau: ban đầu, trên cơ sở các thí nghiệm sơ bộ, điểm cơ bản. Sau đó, ở mỗi giai đoạn, các thí nghiệm thử nghiệm được tổ chức xung quanh điểm cơ sở tiếp theo, kết quả đánh giá hướng mới của gradient, sau đó một bước làm việc được thực hiện theo hướng này.

Phương pháp gradient (bình thường) được thực hiện theo sơ đồ sau:

a) chọn một điểm cơ sở;

b) lựa chọn các bước chuyển động cho từng yếu tố;

c) xác định tọa độ của các điểm kiểm tra;

d) tiến hành các thí nghiệm tại các điểm kiểm tra. Kết quả là, các giá trị của tham số tối ưu hóa (Y) nhận được tại mỗi điểm.

e) dựa trên kết quả của các thí nghiệm, ước lượng các thành phần của vectơ gradient tại điểm M được tính cho mỗi hệ số thứ i:

trong đó H i là bước chuyển động dọc theo X i.

X i - tọa độ của điểm làm việc trước đó.

g) tọa độ của điểm làm việc này được lấy làm điểm cơ sở mới, xung quanh đó các thí nghiệm được thực hiện tại các điểm thử. Gradient được tính toán, v.v., cho đến khi đạt được thông số tối ưu hóa mong muốn (Y). Việc điều chỉnh hướng chuyển động được thực hiện sau mỗi bước.

Ưu điểm của phương pháp: đơn giản, tốc độ di chuyển cao hơn đến mức tối ưu.

Nhược điểm: độ nhạy nhiễu cao. Nếu đường cong có hình dáng phức tạp, phương pháp có thể không dẫn đến tối ưu. Nếu đường cong phản ứng bằng phẳng, phương pháp này không hiệu quả. Phương pháp không cung cấp thông tin về sự tương tác của các yếu tố.

a) Phương pháp leo dốc (Box-Wilson).

b) Ra quyết định sau khi leo dốc.

Trong) Phương pháp Simplex tối ưu hóa.

d) Ưu nhược điểm của các phương pháp.

5.7.3 Phương pháp leo dốc (Box-Wilson)

Phương pháp này là sự tổng hợp tính năng tốt nhất phương pháp gradient, phương pháp Gauss-Seidel và phương pháp PFE và DFE - như một phương tiện thu được mô hình toán học của quá trình. Lời giải của bài toán tối ưu bằng phương pháp này được thực hiện sao cho chuyển động bước được thực hiện theo chiều tăng (giảm) nhanh nhất của tham số tối ưu. Việc hiệu chỉnh hướng chuyển động (ngược lại với phương pháp gradient) không được thực hiện sau mỗi bước, mà khi đạt đến một điểm cực trị cụ thể của hàm mục tiêu. Hơn nữa, tại các điểm của một phần cực trị, một thử nghiệm giai thừa mới được thiết lập, một mô hình toán học và một lần nữa quá trình đi lên dốc được lặp lại cho đến khi đạt được mức tối ưu toàn cầu. Chuyển động dọc theo gradient bắt đầu từ điểm 0 (tâm của kế hoạch).

Phương pháp đi lên dốc liên quan đến việc di chuyển về phía tối ưu dọc theo một gradient.

Trong đó i, j, k là các vectơ đơn vị theo hướng của các trục tọa độ tương ứng.

Quy trình tính toán.

Dữ liệu ban đầu là một mô hình toán học của quá trình thu được bằng bất kỳ phương pháp nào (PFE, DFE, v.v.).

Các phép tính được thực hiện theo thứ tự sau:

a) tốt hơn nên chuyển phương trình hồi quy về dạng tự nhiên bằng cách sử dụng các công thức mã hóa biến số:

ở đâu x i -giá trị được mã hoá của biến x i;

X i - giá trị tự nhiên của biến x i;

X i C - cấp trung tâm của nhân tố ở dạng tự nhiên;

l i - khoảng biến thiên của thừa số x i ở dạng tự nhiên.

b) Tính các bước chuyển động sao cho tối ưu cho từng yếu tố.

Để làm điều này, hãy tính tích các hệ số của phương trình hồi quy ở dạng tự nhiên theo các khoảng biến thiên tương ứng

B i * .l I ,

Sau đó, từ các sản phẩm thu được, mô đun lớn nhất được chọn và hệ số tương ứng với sản phẩm này được lấy làm hệ số cơ sở (B a l a). Đối với yếu tố cơ bản, bạn nên đặt bước chuyển động, được khuyến nghị đặt nhỏ hơn hoặc bằng khoảng thời gian sự biến đổi của hệ số cơ sở

Dấu của bước chuyển động l a ’phải trùng với dấu của hệ số của phương trình hồi quy ứng với hệ số cơ sở (B a). Giá trị của các bước cho các yếu tố khác được tính theo tỷ lệ với cơ sở một theo công thức:

Dấu của các bước chuyển động cũng phải phù hợp với dấu của các hệ số tương ứng của phương trình hồi quy.

c) chức năng đáp ứng được tính toán ở trung tâm của kế hoạch, tức là, với các giá trị của các yếu tố bằng mức trung tâm của các yếu tố, vì chuyển động theo hướng tối ưu bắt đầu từ trung tâm của kế hoạch.

Tiếp theo, tham số tối ưu hóa được tính toán, tăng giá trị của các yếu tố bằng giá trị của bước chuyển động tương ứng, nếu bạn muốn Y max. Ngược lại, nếu cần lấy Y min, giá trị của các yếu tố sẽ giảm đi theo giá trị của bước chuyển động.

Quy trình được lặp lại, liên tiếp tăng số bước cho đến khi đạt được giá trị mong muốn của tham số tối ưu hóa (Y). Mỗi yếu tố sau g các bước sẽ quan trọng:

Nếu Y®max X i \ u003d X i c + gl i ''

nếu Y® min. X i \ u003d X i c -gl i `.(5.36)