phương pháp gradient. Tổng quan về các phương pháp Gradient trong các vấn đề tối ưu hóa toán học

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

Hướng của dốc xuống nhất tương ứng với hướng của hàm giảm lớn nhất. 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 thu được giá trị nhỏ nhất. 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.

phương pháp gradient

Các phương pháp tối ưu hóa không giới hạn gradient chỉ sử dụng các đạo hàm đầu tiên của hàm mục tiêu và là phương pháp xấp xỉ tuyến tính ở mỗi bước, tức là hàm mục tiêu ở mỗi bước được thay thế bằng một siêu phẳng tiếp tuyến với đồ thị của nó tại điểm hiện tại.

Trên giai đoạn thứ k phương pháp gradient, quá trình chuyển đổi từ điểm Xk đến điểm Xk + 1 được mô tả bằng quan hệ:

với k là kích thước bước, k là vectơ theo hướng Xk + 1-Xk.

Các phương pháp xuống dốc tốt nhất

Lần đầu tiên, một phương pháp như vậy được O. Cauchy xem xét và áp dụng vào thế kỷ 18. Ý tưởng của nó rất đơn giản: gradient của hàm mục tiêu f (X) tại bất kỳ điểm nào là một vectơ theo hướng tăng giá trị của hàm lớn nhất. Do đó, phản truyền tín hiệu sẽ hướng về hàm giảm lớn nhất và là hướng giảm xuống dốc nhất. Antigradient (và gradient) là trực giao với bề mặt mức f (X) tại điểm X. Nếu trong (1.2), chúng ta đưa ra hướng

thì đây sẽ là hướng xuống dốc nhất tại điểm Xk.

Chúng tôi nhận được công thức chuyển đổi từ Xk sang Xk + 1:

Anti-gradient chỉ cung cấp hướng đi xuống chứ không phải kích thước bước. TẠI trường hợp chung một bước không cho điểm tối thiểu, do đó phải áp dụng quy trình giảm dần nhiều lần. Tại điểm cực tiểu, tất cả các thành phần của gradient đều bằng không.

Tất cả các phương pháp gradient đều sử dụng ý tưởng trên và khác nhau ở các chi tiết kỹ thuật: tính toán đạo hàm bằng công thức phân tích hoặc xấp xỉ hiệu số hữu hạn; kích thước bước có thể không đổi, thay đổi theo một số quy tắc hoặc được chọn sau khi áp dụng các phương pháp tối ưu hóa một chiều theo hướng của phản truyền tín hiệu, v.v. vân vân.

Chúng tôi sẽ không đi sâu vào chi tiết, bởi vì. phương pháp dốc nhất thường không được khuyến nghị như một quy trình tối ưu hóa nghiêm túc.

Một trong những nhược điểm của phương pháp này là nó hội tụ về bất kỳ điểm đứng yên nào, kể cả điểm yên ngựa, không thể là một nghiệm.

Nhưng điều quan trọng nhất là sự hội tụ rất chậm của các dốc cao nhất trong trường hợp chung. Vấn đề là sự xuống dốc là "nhanh nhất" theo nghĩa địa phương. Nếu siêu không gian tìm kiếm được kéo dài mạnh mẽ ("khe núi"), thì phản truyền tín hiệu được hướng gần như trực giao đến đáy của "khe núi", tức là hướng tốt nhất để đạt mức tối thiểu. Theo nghĩa này, một bản dịch trực tiếp Thuật ngữ tiếng anh"dốc nhất", tức là sự xuống dốc dọc theo con dốc lớn nhất phù hợp với tình trạng của vấn đề hơn là thuật ngữ "nhanh nhất" được sử dụng trong các tài liệu chuyên ngành tiếng Nga. Một cách giải quyết trong tình huống này là sử dụng thông tin được cung cấp bởi các đạo hàm riêng thứ hai. Một cách khác là thay đổi thang đo của các biến.

gradient đạo hàm xấp xỉ tuyến tính

Phương pháp gradient liên hợp Fletcher-Reeves

Phương pháp gradient liên hợp xây dựng một chuỗi các hướng tìm kiếm là sự kết hợp tuyến tính của hướng đi xuống dốc nhất hiện tại và các hướng tìm kiếm trước đó, tức là

và các hệ số được chọn để làm cho các hướng tìm kiếm được liên hợp. Chứng minh rằng

và đây là một kết quả rất có giá trị cho phép bạn xây dựng một thuật toán tối ưu hóa nhanh chóng và hiệu quả.

Thuật toán Fletcher-Reeves

1. Trong X0 được tính.

2. Tại bước thứ k, sử dụng tìm kiếm một chiều theo hướng, tìm được cực tiểu của f (X), xác định điểm Xk + 1.

3. Tính f (Xk + 1) và.
4. Hướng được xác định từ tỷ lệ:

5. Sau lần lặp thứ (n + 1) (tức là với k = n), khởi động lại được thực hiện: X0 = Xn + 1 được giả định và chuyển sang bước 1 được thực hiện.
6. Thuật toán dừng khi

đâu là một hằng số tùy ý.

Ưu điểm của thuật toán Fletcher-Reeves là nó không yêu cầu đảo ma trận và tiết kiệm bộ nhớ máy tính, vì nó không cần ma trận được sử dụng trong phương pháp Newton, nhưng đồng thời hiệu quả gần như thuật toán gần Newton. Tại vì các hướng tìm kiếm là liên hợp lẫn nhau, khi đó hàm bậc hai sẽ có cực tiểu không quá n bước. Trong trường hợp chung, khởi động lại được sử dụng, cho phép bạn nhận được kết quả.

Thuật toán Fletcher-Reeves nhạy cảm với độ chính xác của tìm kiếm một chiều, vì vậy bất kỳ lỗi làm tròn nào có thể xảy ra phải được sửa chữa khi sử dụng nó. Ngoài ra, thuật toán có thể thất bại trong các tình huống mà Hessian bị mất điều kiện. Thuật toán không đảm bảo sự hội tụ luôn luôn và ở mọi nơi, mặc dù thực tế cho thấy rằng thuật toán hầu như luôn luôn đưa ra một kết quả.

Phương pháp Newton

Hướng tìm kiếm tương ứng với độ dốc cao nhất được liên kết với xấp xỉ tuyến tính chức năng mục tiêu. Các phương pháp sử dụng đạo hàm thứ hai phát sinh từ phép xấp xỉ bậc hai của hàm mục tiêu, tức là khi mở rộng hàm trong chuỗi Taylor, các số hạng của bậc ba trở lên bị loại bỏ.

ma trận Hessian ở đâu.

Mức tối thiểu của phía bên phải (nếu nó tồn tại) đạt được ở cùng một nơi với mức tối thiểu dạng bậc hai. Hãy viết công thức xác định hướng tìm kiếm:

Mức tối thiểu đạt được tại

Một thuật toán tối ưu hóa trong đó hướng tìm kiếm được xác định từ mối quan hệ này được gọi là phương pháp Newton, và hướng là hướng Newton.

Trong các bài toán tìm cực tiểu của một tùy ý hàm bậc hai với ma trận dương của đạo hàm cấp hai, phương pháp của Newton đưa ra một giải pháp trong một lần lặp, bất kể việc lựa chọn điểm xuất phát là gì.

Phân loại các phương pháp Newton

Trên thực tế, phương pháp Newton bao gồm một ứng dụng duy nhất của hướng Newton để tối ưu hóa hàm bậc hai. Nếu hàm số không phải là bậc hai thì định lý sau là đúng.

Định lý 1.4. Nếu ma trận Hessian của một hàm phi tuyến tính tổng quát f tại điểm nhỏ nhất X * là xác định dương, điểm bắt đầu được chọn đủ gần với X * và độ dài bước được chọn đúng, thì phương pháp Newton hội tụ thành X * với tốc độ bậc hai.

Phương pháp của Newton được coi là phương pháp tham khảo và tất cả các quy trình tối ưu hóa đã phát triển đều được so sánh với nó. Tuy nhiên, phương pháp của Newton chỉ hiệu quả đối với ma trận Hessian xác định dương và có điều kiện tốt (định thức của nó về cơ bản phải là Trên không, chính xác hơn, tỷ lệ của các giá trị riêng lớn nhất và nhỏ nhất phải gần với sự thống nhất). Để khắc phục khuyết điểm này, chúng tôi sử dụng phương pháp sửa đổi Newton, sử dụng các hướng Newton trong phạm vi có thể và chỉ đi chệch khỏi chúng khi cần thiết.

Nguyên tắc chung của các sửa đổi đối với phương pháp của Newton như sau: tại mỗi lần lặp, một số ma trận xác định dương "có liên quan" được xây dựng trước, và sau đó được tính bằng công thức

Vì nó là xác định dương nên - nhất thiết sẽ là hướng đi xuống. Quy trình xây dựng được tổ chức sao cho nó trùng với ma trận Hessian nếu nó là xác định dương. Các thủ tục này được xây dựng trên cơ sở một số mở rộng ma trận.

Một nhóm phương pháp khác, gần như nhanh như phương pháp Newton, dựa trên tính gần đúng của ma trận Hessian bằng cách sử dụng sự khác biệt hữu hạn, bởi vì không nhất thiết phải sử dụng các giá trị chính xác của các dẫn xuất để tối ưu hóa. Các phương pháp này rất hữu ích khi việc tính toán phân tích các dẫn xuất khó hoặc đơn giản là không thể. Các phương pháp như vậy được gọi là phương pháp Newton rời rạc.

Chìa khóa cho tính hiệu quả của các phương pháp kiểu Newton là tính đến thông tin về độ cong của hàm được tối thiểu hóa, được chứa trong ma trận Hessian và làm cho nó có thể xây dựng các mô hình bậc hai chính xác cục bộ của hàm mục tiêu. Nhưng có thể thu thập và tích lũy thông tin về độ cong của một hàm dựa trên việc quan sát sự thay đổi của gradient trong các lần lặp lại của đường xuống.

Các phương pháp tương ứng dựa trên khả năng xấp xỉ độ cong của một hàm phi tuyến tính mà không cần hình thành rõ ràng ma trận Hessian của nó được gọi là các phương pháp gần như Newton.

Lưu ý rằng khi xây dựng một quy trình tối ưu hóa kiểu Newton (bao gồm cả quy trình chuẩn Newton), cần phải tính đến khả năng xuất hiện điểm yên ngựa. Trong trường hợp này, vectơ của hướng tìm kiếm tốt nhất sẽ luôn hướng đến điểm yên ngựa, thay vì di chuyển khỏi nó theo hướng "xuống".

Phương pháp Newton-Raphson

Phương pháp này bao gồm việc sử dụng lặp lại hướng Newton khi tối ưu hóa các hàm không phải là bậc hai.

Chính công thức lặp lại tối ưu hóa đa biến

được sử dụng trong phương pháp này khi chọn hướng tối ưu hóa từ quan hệ

Độ dài bước thực được ẩn theo hướng Newton không chuẩn hóa.

Vì phương pháp này không yêu cầu giá trị của hàm mục tiêu tại điểm hiện tại, nên đôi khi nó được gọi là gián tiếp hoặc phương pháp phân tích tối ưu hóa. Khả năng xác định điểm cực tiểu của hàm bậc hai trong một phép tính thoạt nhìn cực kỳ hấp dẫn. Tuy nhiên, "phép tính đơn lẻ" này là tốn kém. Trước hết, cần tính n đạo hàm riêng bậc nhất và n (n + 1) / 2 - của bậc hai. Ngoài ra, ma trận Hessian phải được đảo ngược. Điều này đã yêu cầu khoảng n3 hoạt động tính toán. Với cùng một chi phí, các phương pháp hướng liên hợp hoặc phương pháp gradient liên hợp có thể thực hiện khoảng n bước, tức là đạt được kết quả gần như tương tự. Do đó, phép lặp của phương pháp Newton-Raphson không mang lại lợi thế trong trường hợp hàm bậc hai.

Nếu hàm không phải là bậc hai, thì

- hướng ban đầu, nói chung, không chỉ ra điểm cực tiểu thực tế, có nghĩa là các bước lặp phải được lặp lại nhiều lần;
- một bước có độ dài đơn vị có thể dẫn đến một điểm có giá trị tồi tệ nhất chức năng mục tiêu và tìm kiếm có thể đưa ra hướng sai nếu, ví dụ, Hessian không phải là xác định dương;
- Hessian có thể bị bệnh, khiến nó không thể đảo ngược nó, tức là xác định hướng cho lần lặp tiếp theo.

Bản thân chiến lược không phân biệt điểm tĩnh nào (điểm nhỏ nhất, cực đại, điểm yên ngựa) mà việc tìm kiếm đang đến gần và việc tính toán các giá trị hàm mục tiêu, qua đó có thể theo dõi xem hàm có tăng hay không. Vì vậy, tất cả phụ thuộc vào khu vực thu hút điểm dừng là điểm bắt đầu của cuộc tìm kiếm. Chiến lược Newton-Raphson hiếm khi được sử dụng một mình mà không sửa đổi loại này hay loại khác.

Phương pháp Pearson

Pearson đã đề xuất một số phương pháp để tính gần đúng Hessian nghịch đảo mà không tính toán rõ ràng các đạo hàm thứ hai, tức là bằng cách quan sát những thay đổi theo hướng của chất phản truyền tín hiệu. Trong trường hợp này, các hướng liên hợp thu được. Các thuật toán này chỉ khác nhau về chi tiết. Đây là những thứ nhận được nhiều nhất sử dụng rộng rãi trong các lĩnh vực ứng dụng.

Thuật toán Pearson's # 2.

Trong thuật toán này, Hessian nghịch đảo được xấp xỉ bởi ma trận Hk được tính ở mỗi bước bằng công thức

Một ma trận đối xứng xác định dương tùy ý được chọn làm ma trận ban đầu H0.

Thuật toán Pearson này thường dẫn đến các tình huống mà ma trận Hk trở nên không ổn định, cụ thể là nó bắt đầu dao động, dao động giữa xác định dương và xác định không dương, trong khi định thức của ma trận gần bằng không. Để tránh trường hợp này, cần phải thiết lập lại ma trận sau mỗi n bước, tương đương với H0.

Thuật toán Pearson # 3.

Trong thuật toán này, ma trận Hk + 1 được xác định từ công thức

Hk + 1 = Hk +

Đường đi xuống do thuật toán tạo ra tương tự như hành vi của thuật toán Davidon-Fletcher-Powell, nhưng các bước ngắn hơn một chút. Pearson cũng đề xuất một biến thể của thuật toán này với sự sắp xếp lại theo chu kỳ của ma trận.

Thuật toán Projective Newton-Raphson

Pearson đã đề xuất ý tưởng về một thuật toán trong đó ma trận được tính từ mối quan hệ

H0 = R0, trong đó ma trận R0 giống với ma trận ban đầu trong các thuật toán trước.

Khi k là bội của số biến độc lập n, ma trận Hk được thay bằng ma trận Rk + 1 được tính như tổng

Giá trị Hk (f (Xk + 1) - f (Xk)) là hình chiếu của vectơ tăng gradient (f (Xk + 1) -f (Xk)), trực giao với tất cả các vectơ tăng gradient trong các bước trước đó. Sau mỗi n bước, Rk là một xấp xỉ của nghịch đảo Hessian H-1 (Xk), vì vậy về bản chất, một (gần đúng) tìm kiếm Newton được thực hiện.

Phương pháp Davidon-Fletcher-Powell

Phương pháp này có các tên khác - phương pháp số liệu biến đổi, phương pháp gần như Newton, bởi vì anh ta sử dụng cả hai cách tiếp cận này.

Phương pháp Davidon-Fletcher-Powell (DFP) dựa trên việc sử dụng các hướng Newton, nhưng không yêu cầu tính toán Hessian nghịch đảo ở mỗi bước.

Hướng tìm kiếm ở bước k là hướng

trong đó Hi là một ma trận đối xứng xác định dương được cập nhật ở mỗi bước và, trong giới hạn, trở thành bằng Hessian nghịch đảo. Ma trận nhận dạng thường được chọn là ma trận ban đầu H. Thủ tục DFT lặp lại có thể được biểu diễn như sau:

1. Tại bước k, có một điểm Xk và một ma trận xác định dương Hk.
2. Chọn làm hướng tìm kiếm mới

3. Tìm kiếm một chiều (thường bằng nội suy khối) dọc theo hướng xác định k cực tiểu của hàm.

4. Họ hàng.

5. Họ hàng.

6. Được xác định bởi và. Nếu Vk hoặc đủ nhỏ, thủ tục kết thúc.

7. Đặt Uk = f (Xk + 1) - f (Xk).
8. Ma trận Hk được cập nhật theo công thức

9. Tăng k lên một và quay lại bước 2.

Phương pháp này có hiệu quả trong thực tế nếu sai số tính toán gradient nhỏ và ma trận Hk không trở nên vô điều kiện.

Ma trận Ak đảm bảo sự hội tụ của Hk đến G-1, ma trận Bk đảm bảo tính xác định dương của Hk + 1 ở mọi giai đoạn và loại trừ H0 trong giới hạn.

Trong trường hợp của một hàm số bậc hai

những thứ kia. thuật toán DFP sử dụng hướng liên hợp.

Do đó, phương pháp DFT sử dụng cả ý tưởng của phương pháp Newton và các tính chất của hướng liên hợp, và khi tối thiểu hóa hàm bậc hai, nó hội tụ không quá n lần lặp. Nếu hàm đang được tối ưu hóa có dạng gần với hàm bậc hai, thì phương pháp DFP hiệu quả do giá trị gần đúng của G-1 (phương pháp Newton). Nếu hàm mục tiêu có hình thức chung, thì phương pháp DFP hiệu quả do sử dụng các hướng liên hợp.

Chúng ta hãy xem xét vấn đề cực tiểu không điều kiện của một hàm phân biệt của một số biến. Trong phương pháp gradient được xem xét dưới đây, hướng đi xuống từ điểm được chọn trực tiếp. Do đó, theo phương pháp gradient

Hiện hữu nhiều cách khác nhau lựa chọn bước, mỗi bước trong số đó đặt biến thể nhất định phương pháp gradient.

1. Phương pháp xuống dốc nhất.

Hãy xem xét một hàm của một biến vô hướng và chọn làm giá trị mà đẳng thức

Phương pháp này, được đề xuất vào năm 1845 bởi O. Cauchy, ngày nay được gọi là phương pháp dốc nhất.

Trên hình. 10.5 cho thấy một minh họa hình học của phương pháp này để tối thiểu hóa một hàm có hai biến. Từ điểm xuất phát, vuông góc với đường mức theo phương, tiếp tục đi xuống cho đến khi đạt giá trị nhỏ nhất của hàm số dọc theo tia. Tại điểm được tìm thấy, tia này chạm vào đường mức. Sau đó, tia này được tạo ra từ điểm theo phương vuông góc với đường mức cho đến khi tia tương ứng chạm vào đường mức đi qua điểm này tại điểm, v.v.

Chúng tôi lưu ý rằng ở mỗi lần lặp, việc lựa chọn bước ngụ ý giải pháp của bài toán tối thiểu hóa một chiều (10,23). Đôi khi phép toán này có thể được thực hiện một cách phân tích, ví dụ, đối với một hàm bậc hai.

Chúng tôi áp dụng phương pháp dốc nhất để giảm thiểu hàm bậc hai

với một ma trận A xác định dương đối xứng.

Theo công thức (10.8), trong trường hợp này, công thức (10.22) trông như thế này:

thông báo rằng

Hàm này là một hàm bậc hai của tham số a và đạt cực tiểu tại một giá trị mà tại đó

Do đó, như được áp dụng cho việc tối thiểu hóa bậc hai

hàm (10,24), phương pháp giảm độ dốc nhất tương đương với phép tính theo công thức (10,25), trong đó

Nhận xét 1. Vì điểm cực tiểu của hàm số (10,24) trùng với nghiệm của hệ, nên phương pháp dốc nhất (10,25), (10,26) cũng có thể được sử dụng như phương pháp lặp lại giải pháp của hệ thống tuyến tính phương trình đại số với ma trận xác định dương đối xứng.

Nhận xét 2. Lưu ý rằng đâu là quan hệ Rayleigh (xem § 8.1).

Ví dụ 10.1. Chúng tôi áp dụng phương pháp dốc nhất để giảm thiểu hàm bậc hai

Lưu ý rằng Do đó, chúng tôi đã biết trước giá trị chính xác của điểm tối thiểu. Hãy viết ra Chức năng nàyở dạng (10.24), trong đó ma trận và vectơ Như dễ thấy,

Chúng tôi lấy giá trị gần đúng ban đầu và chúng tôi sẽ thực hiện các phép tính bằng công thức (10,25), (10,26).

Tôi lặp lại.

II lần lặp.

Nó có thể được chỉ ra rằng đối với tất cả các lần lặp, các giá trị sẽ nhận được

Lưu ý rằng với Như vậy,

trình tự thu được bằng phương pháp dốc nhất hội tụ với tốc độ cấp số nhân, mẫu số của ai

Trên hình. 10.5 cho thấy chính xác quỹ đạo đi xuống thu được trong ví dụ này.

Đối với trường hợp tối thiểu hóa một hàm bậc hai, điều sau đúng kết quả chung.

Định lý 10.1. Gọi A là ma trận xác định dương đối xứng và hàm số bậc hai (10.24) có cực tiểu. Sau đó, đối với bất kỳ lựa chọn nào về ước lượng ban đầu, phương pháp giảm dần dốc nhất (10,25), (10,26) sẽ hội tụ và ước tính sai số sau là đúng:

Ở đây và Lado là các giá trị riêng nhỏ nhất và lớn nhất của ma trận A.

Lưu ý rằng phương pháp này hội tụ với tốc độ của một cấp tiến hình học, mẫu số của nó, hơn nữa, nếu chúng gần nhau thì nó nhỏ và phương pháp này hội tụ khá nhanh. Ví dụ, trong Ví dụ 10.1, chúng ta có và, do đó, Nếu Asch, thì 1, và chúng ta nên mong đợi phương pháp đi xuống dốc nhất hội tụ chậm.

Ví dụ 10.2. Việc áp dụng phương pháp đi xuống dốc nhất để tối thiểu hóa hàm bậc hai ở giá trị gần đúng ban đầu đưa ra một chuỗi các phép gần đúng trong đó Quỹ đạo của đường đi xuống được thể hiện trong Hình. 10,6.

Chuỗi hội tụ ở đây với tốc độ của một tiến trình hình học, mẫu số của nó, tức là chậm hơn nhiều,

hơn trong ví dụ trước. Vì ở đây kết quả thu được hoàn toàn phù hợp với ước tính (10,27).

Nhận xét 1. Chúng tôi đã xây dựng một định lý về sự hội tụ của phương pháp dốc nhất trong trường hợp hàm mục tiêu là bậc hai. Trong trường hợp tổng quát, nếu hàm cực tiểu là hàm lồi và có điểm cực tiểu x, thì bất kể lựa chọn xấp xỉ ban đầu là bao nhiêu, dãy số thu được bằng phương pháp này hội tụ về x tại. Trong trường hợp này, sau khi rơi vào vùng lân cận đủ nhỏ của điểm cực tiểu, sự hội tụ trở thành tuyến tính và mẫu số của cấp độ hình học tương ứng được ước tính từ trên theo giá trị và ở đó cả giá trị nhỏ nhất và lớn nhất giá trị riêng Ma trận Hessian

Nhận xét 2. Đối với hàm mục tiêu bậc hai (10.24), lời giải của bài toán tối thiểu hóa một chiều (10.23) có thể được tìm thấy dưới dạng một công thức tường minh đơn giản (10.26). Tuy nhiên, đối với hầu hết những người khác chức năng phi tuyếnđiều này không thể được thực hiện và để tính toán theo phương pháp dốc nhất, người ta phải áp dụng phương pháp số các giảm thiểu một chiều của kiểu đã được thảo luận trong chương trước.

2. Vấn đề "khe núi".

Từ cuộc thảo luận ở trên, phương pháp gradient hội tụ khá nhanh nếu các bề mặt mức cho hàm thu nhỏ gần với hình cầu (khi các đường mức gần với các đường tròn). Đối với các hàm như vậy, và 1. Định lý 10.1, Nhận xét 1, và kết quả của Ví dụ 10.2 chỉ ra rằng tốc độ hội tụ giảm mạnh khi giá trị của. Trong trường hợp hai chiều, phần nổi của bề mặt tương ứng giống với địa hình có khe núi (Hình 10.7). Do đó, các chức năng như vậy thường được gọi là gully. Dọc theo các hướng đặc trưng cho "đáy khe núi", chức năng của khe núi thay đổi không đáng kể, trong khi ở các hướng khác đặc trưng cho "độ dốc khe núi", chức năng xảy ra thay đổi rõ rệt.

Nếu điểm bắt đầu rơi trên "độ dốc khe núi", thì hướng của dốc xuống gần như vuông góc với "đáy khe núi" và điểm gần đúng tiếp theo rơi trên "độ dốc khe núi" ngược lại. Bước tiếp theo hướng tới "đáy khe núi" quay trở lại cách tiếp cận "độ dốc khe núi" ban đầu. Kết quả là, thay vì di chuyển dọc theo “đáy khe núi” đến điểm cực tiểu, quỹ đạo đi xuống làm cho cú nhảy ngoằn ngoèo qua “khe núi”, gần như không tiếp cận mục tiêu (Hình 10.7).

Để tăng tốc độ hội tụ của phương pháp gradient trong khi giảm thiểu các chức năng của khe núi, một số phương pháp "khe núi" đặc biệt đã được phát triển. Hãy đưa ra ý tưởng về một trong những phương pháp đơn giản nhất. Từ hai điểm xuất phát gần nhau, một dốc dốc được thực hiện đến "đáy của khe núi". Một đường thẳng được vẽ qua các điểm được tìm thấy, dọc theo đó một bước "khe núi" lớn được thực hiện (Hình 10.8). Từ điểm được tìm thấy theo cách này, một bước của gradient giảm xuống một lần nữa được thực hiện. Sau đó, bước "khe núi" thứ hai được thực hiện dọc theo đường thẳng đi qua các điểm. Kết quả là, sự di chuyển dọc theo "đáy khe núi" đến điểm cực tiểu được tăng tốc đáng kể.

Hơn thông tin chi tiết về vấn đề của phương pháp "khe núi" và "rãnh nước" có thể được tìm thấy, ví dụ, trong,.

3. Các cách tiếp cận khác để xác định bước đi xuống.

Như dễ hiểu, tại mỗi lần lặp, bạn nên chọn một hướng đi xuống gần với hướng mà chuyển động dẫn từ điểm đến điểm x. Thật không may, phản truyền tín hiệu (theo quy luật, là một hướng đi xuống không thành công. Điều này đặc biệt rõ ràng đối với các hàm khe núi. Do đó, có nghi ngờ về khả năng tư vấn của việc tìm kiếm kỹ lưỡng giải pháp cho vấn đề giảm thiểu một chiều (10,23) và có mong muốn chỉ thực hiện một bước như vậy theo hướng có thể cung cấp "sự giảm đáng kể" của chức năng. Hơn nữa, trong thực tế, đôi khi người ta hài lòng với việc xác định một giá trị chỉ đơn giản là làm giảm giá trị của mục tiêu hàm số.

Bạn cũng có thể không tìm kiếm điểm tốt nhất theo hướng của gradient, mà là điểm tốt hơn điểm hiện tại.

Phương pháp dễ thực hiện nhất trong tất cả các phương pháp tối ưu hóa cục bộ. Nó có các điều kiện hội tụ khá yếu, nhưng tốc độ hội tụ khá nhỏ (tuyến tính). Phương pháp gradient bước thường được sử dụng như một phần của các phương pháp tối ưu hóa khác, chẳng hạn như phương pháp Fletcher-Reeves.

Sự mô tả [ | ]

Cải tiến[ | ]

Phương pháp giảm độ dốc hóa ra rất chậm khi di chuyển dọc theo một khe núi và khi số lượng biến hàm mục tiêu tăng lên, hành vi này của phương pháp trở nên điển hình. Để chống lại hiện tượng này được sử dụng, bản chất của nó là rất đơn giản. Sau khi thực hiện hai bước giảm độ dốc và nhận được ba điểm, bước thứ ba nên được thực hiện theo hướng của vectơ nối điểm đầu tiên và điểm thứ ba, dọc theo đáy của khe núi.

Đối với các hàm gần bậc hai, phương pháp gradient liên hợp có hiệu quả.

Ứng dụng trong mạng nơ-ron nhân tạo[ | ]

Phương pháp giảm độ dốc với một số sửa đổi được sử dụng rộng rãi để huấn luyện perceptron và được biết đến trong lý thuyết về mạng nơron nhân tạo như là phương pháp lan truyền ngược. Khi huấn luyện một mạng nơron kiểu perceptron, cần phải thay đổi hệ số trọng số của mạng theo cách để giảm thiểu lỗi trung bìnhở lối ra mạng thần kinh khi áp dụng một chuỗi dữ liệu đầu vào huấn luyện cho đầu vào. Về mặt hình thức, để chỉ thực hiện một bước theo phương pháp giảm dần độ dốc (chỉ thực hiện một thay đổi trong các tham số mạng), cần phải đưa tuần tự toàn bộ tập dữ liệu huấn luyện vào đầu vào mạng, tính toán sai số cho từng dữ liệu huấn luyện. đối tượng và tính toán sự hiệu chỉnh cần thiết của các hệ số mạng (nhưng không thực hiện việc hiệu chỉnh này), và sau khi gửi tất cả dữ liệu, hãy tính tổng trong phần hiệu chỉnh của từng hệ số mạng (tổng độ dốc) và sửa các hệ số "theo một bước" . Rõ ràng, với một tập dữ liệu huấn luyện lớn, thuật toán sẽ hoạt động cực kỳ chậm, do đó, trong thực tế, hệ số mạng thường được điều chỉnh sau mỗi phần tử huấn luyện, trong đó giá trị gradient xấp xỉ với gradient của hàm chi phí chỉ được tính trên một yếu tố đào tạo. Một phương pháp như vậy được gọi là sự giảm dần độ dốc ngẫu nhiên hoặc chuyển xuống dốc hoạt động . Stochastic gradient descent là một dạng của xấp xỉ ngẫu nhiên. Lý thuyết xấp xỉ ngẫu nhiên đưa ra các điều kiện cho sự hội tụ của phương pháp giảm độ dốc ngẫu nhiên.

Liên kết [ | ]

J. Mathews. Mô-đun cho phương pháp dốc hoặc dốc nhất. (liên kết không có sẵn)

Văn chương [ | ]

Akulich I. L. Lập trình toán học trong các ví dụ và nhiệm vụ. - M.: trường cao học, 1986. - S. 298-310.
Gill F., Murray W., Wright M. Practical Optimization = Tối ưu hóa thực tế. - M.: Mir, 1985.
Korshunov Yu. M., Korshunov Yu. M. Cơ sở toán họcđiều khiển học. - M.: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya E. A. Các thuật toán giải các bài toán của lập trình phi tuyến. - M.: MEPhI, 1982.
Maksimov Yu. A. Các thuật toán cho lập trình tuyến tính và rời rạc. - M.: MEPhI, 1980.
Korn G., Korn T. Cẩm nang toán học cho các nhà khoa học và kỹ sư. - M.: Nauka, 1970. - S. 575-576.
S. Yu. Gorodetsky, V. A. Grishagin. Lập trình phi tuyến và tối ưu hóa đa cực. - Nizhny Novgorod: Nhà xuất bản Đại học Nizhny Novgorod, 2007. - S. 357-363.

Cuối cùng, tham số m có thể được đặt không đổi ở tất cả các lần lặp. Tuy nhiên, khi giá trị lớn m quá trình tìm kiếm có thể khác nhau. theo một cách tốt sự lựa chọn của m có thể là định nghĩa của nó tại lần lặp đầu tiên từ điều kiện của một điểm cực trị theo hướng của gradient. Trong các lần lặp tiếp theo, m không đổi. Điều này đơn giản hóa các tính toán hơn nữa.

Ví dụ: đối với một hàm có với các phép chiếu gradient xác định bằng phương pháp dốc nhất. Chúng tôi chấp nhận hằng số tham số ở tất cả các lần lặp.

Tính tọa độ x (1):

Để tính tọa độ của điểm x (2), chúng ta tìm hình chiếu của gradient tại điểm x (1) :, sau đó

vân vân.

Chuỗi này cũng hội tụ.

phương pháp gradient bước

Phương pháp này được phát triển bởi các kỹ sư và nằm ở chỗ, bước cho một trong các biến được coi là không đổi, và đối với các biến khác, nó được chọn dựa trên tỷ lệ của các độ dốc của các điểm. Bởi vì điều này, như nó vốn có, bề mặt cực trị được thu nhỏ, bởi vì sự hội tụ không giống nhau đối với tất cả các biến. Do đó, bằng cách chọn các bước khác nhau cho các tọa độ, họ cố gắng làm cho tốc độ hội tụ xấp xỉ như nhau cho tất cả các biến.

Cho một hàm phân tách và một điểm ban đầu được đưa ra . Hãy thiết lập một bước không đổi dọc theo tọa độ x 1, cho Dx 1 = 0,2. Bước dọc theo tọa độ x 2 được tìm thấy từ tỷ lệ của gradient và số bước.