tailieunhanh - Phương pháp vượt khe hướng phân giác giải bài toán quy hoạch phi tuyến có ràng buộc

Trong bài báo này, dựa trên cơ sở nguyên lý vượt khe các tác giả xây dựng thuật toán giải bài toán Quy hoạch phi tuyến có ràng buộc: Thuật toán vượt khe hướng phân giác. định lý hội tụ ñược nêu ra và chứng minh. Các ví dụ minh họa ñược trình bày. | TẠP CHÍ KHOA HỌC, ðại học Huế, Số 65, 2011 PHƯƠNG PHÁP VƯỢT KHE HƯỚNG PHÂN GIÁC GIẢI BÀI TOÁN QUY HOẠCH PHI TUYẾN CÓ RÀNG BUỘC Bùi Minh Trí, Trường ðại học Bách khoa Hà Nội Nguyễn Vũ Tiến, ðại học Huế TÓM TẮT Trong bài báo này, dựa trên cơ sở nguyên lý vượt khe chúng tôi xây dựng thuật toán giải bài toán Quy hoạch phi tuyến có ràng buộc: Thuật toán vượt khe hướng phân giác. ðịnh lý hội tụ ñược nêu ra và chứng minh. Các ví dụ minh họa ñược trình bày. 1. Nguyên lý tối ưu hóa vượt khe và hướng tìm kiếm . Nguyên lý tối ưu hóa vượt khe [3] Xét bài toán cực tiểu hóa có ràng buộc: min{J(x)│ gi(x) ≤ 0; i = 1, ,m ; x ∈ Rn} () trong ñó: J(x) là hàm mục tiêu bị chặn dưới và thỏa mãn ñiều kiện: lim J ( x ) = ∞ () x →∞ các hàm gi (x) là các hàm lồi. Thuật toán tối ưu hóa phi tuyến giải bài toán () có phương trình lặp như sau: xk+1 = xk + αk+1 Sk , k = 0, 1, () trong ñó: xk, xk+1 là ñiểm ñầu và ñiểm cuối của bước lặp thứ k+1; αk+1 là ñộ dài bước; Sk là vecto chỉ hướng thay ñổi các biến trong không gian Rn. Nếu αk+1 ñược xác ñịnh theo nguyên lý vượt khe thì ñược gọi là bước vượt khe, còn phương trình () gọi là thuật toán vượt khe [3]. Nguyên lý vượt khe phát biểu rằng ñiểm ñầu và ñiểm cuối của mỗi bước lặp tối ưu hóa luôn luôn nằm về hai phía ñiểm cực tiểu của hàm mục tiêu xét dọc theo hướng chuyển ñộng tại bước ñó. Nói cách khác, nếu tại ñiểm ñầu hàm mục tiêu thay ñổi theo chiều giảm, thì ñến ñiểm cuối nó phải có xu hướng tăng. Quỹ ñạo tìm kiếm tối ưu theo nguyên lý vượt khe tạo ra bức tranh hình học, tựa như ñiểm tìm kiếm tại mỗi lần lặp ñều bước vượt qua lòng khe của hàm mục tiêu. ðể cụ thể hóa nguyên lý vượt khe, ta xét hàm một biến sau ñối với mỗi bước lặp k+1: 241 h(α) = J(xk + αsk) () Giả sử sk là hướng giảm hàm mục tiêu tại ñiểm xk. Theo ñiều kiện () tồn tại một giá trị α* > 0 bé nhất sao cho h(α) ñạt cực tiểu: α* = arg min h(α ) () α >0 Nếu h(α) khả vi liên tục, ta có ñịnh nghĩa bước vượt khe như sau: h ' (α ) α =α v > .

• Toán học
• Phương pháp vượt khe hướng phân giác
• Bài toán quy hoạch phi tuyến
• Nguyên lý tối ưu hóa vượt khe
• Nguyên lý tối ưu hóa vượt khe
• Phương pháp vượt khe