Tư tưởng cốt lõi của phương phương pháp hàm pê-nan-ti là biến đổi các bài toán quy hoạch phi tuyến có ràng buộc thành một chuỗi các bài toán tối ưu hóa không ràng buộc. Tư tưởng cơ bản của phương pháp này là cộng một hay nhiều hơn các hàm ràng buộc vào hàm mục tiêu để loại bỏ các ràng buộc. Lập luận cơ bản cho cách tiếp cận như vậy là những bài toán không ràng buộc đó dễ dàng giải hơn nhiều. Bằng việc sử dụng một hàm pê-nan-ti một bài toán
quy hoạch phi tuyến có ràng buộc được biến đổi thành một bài toán không ràng buộc.
,
Minimize f x
Minimize L f x g x
với giả thiết g(x)
Trong đó Lf x,g x là một hàm pê-nan-ti. Các dạng khác nhau của hàm pê-nan-ti đã được đưa ra mà có thể tìm thấy trong những tài liệu khác (Gill, Murray và Wright, 1981; Mc Cormick, 1983). Hàm pê-nan-ti được cực tiểu hóa bởi các giai đoạn cho một chuỗi các giá trị của các tham số liên quan tới pê-nan-ti. Thực tế, hàm Lagrange (đã trình bày trong Mục 4.5) là một dạng của hàm pê-nan-ti. Đối với nhiều hàm pê-nan-ti, ma trận Hessian của hàm pê- nan-ti ngày càng trở nên bất lợi (tức là, giá trị hàm là rất nhạy cảm với một thay đổi nhỏ trong giá trị tham số) khi nghiệm tiệm cận tới tối ưu. Mục này trình bày tóm tắt một phương pháp hàm pê-nan-ti là phương pháp số gia Lagrange.
Phương pháp số gia Lagrange bổ xung thêm một dạng hàm pê-nan-ti bậc hai vào hàm Lagrange (Phương trình 4.5.2), để nhận được:
2
1 1
, , 2
m m
i i i
A
i i
L f g g
x x x x
2
T T
f
x g x g x g x (4.7.1) Trong đó là một tham số pê-nan-ti dương. Một số tính chất của phương trình (4.7.1) được thảo luận bởi Gill, Murray và Wright (1981).
Ví dụ 4.7.1. Gill, Murray và Wright (1981), Edgar và Himmelblau (1988) đã sử dụng bài toán cực tiểu hóa sau để minh họa số gia Lagrange.
Minimize f(x) = x3 Với giả thiết
x+1 = 0
Lời giải Số gia Lagrange theo phương trình (4.7.1) là
, , 3 1 12
A 2
L x x x x
Với * 3 và 9, hàm số gia Lagrange là
, 3, 9 3 3 1 9 12
A 2
L x x x x Tại x=-1, gradient của số gia Lagrange là
2
2
, 3, 9 3 3 9 1
3 1 3 9 1 1
3 3 0 0
xLA x x x
và vi phân bậc hai là
2 , 3, 9 6
6 1 9
3
xLA x x
Vi phân bậc hai là xác định dương với 6. Đồ thị của LA(x,-3,9) trong hình 4.7.1 minh họa rằng tại x=-1, lA(x,-3,9) là một cực tiểu địa phương. Cần chú ý rằng hàm số gia Lagrange này không bị chặn dưới với bất kỳ giá trị nào của .
Trong trường hợp lý tưởng, x* có thể được tính bằng một sự cực tiểu hóa không ràng buộc đơn của hàm sai phân (Phương trình 4.7.1). Tuy nhiên, trong trường hợp tổng quát, * không có sẵn cho tới khi nghiệm đã được xác định.
Do đó, một phương pháp số gia Lagrange phải bao gồm một thủ tục để đánh giá các nhân tử Lagrange. Gill, Murray và Wright (1981) đưa ra thuật giải sau:
Bước 0 Chọn các ước lượng ban đầu của các nhân tử Lagrange k 0, tham số pê-nan-ti , một điểm ban đầu xk = 0, Đặt k = k + 1 và
đặt số các bước lặp lớn nhất bằng J.
Bước 1 Kiểm tra để xem liệu xk có thỏa mãn các điều kiện tối ưu không hay liệu k > J không. Nếu thế thì kết thúc thuật giải.
Bước 2 Cực tiểu hóa hàm số gia Lagrange, cực tiểu hóa LA(x, , ), trong phương trình (4.7.1). Các thủ tục để xét tính không bị chặn phải
được xem xét. Nghiệm tốt nhất được biểu thị là xk+1.
Bước 4 Tăng thông số pê-nan-ti nếu sự vi phạm ràng buộc tại xk+1 không giảm xuống đáng kể từ ở xk.
Bước 5 Đặt k = k+1 và quay lại bước 1.
Các phương pháp số gia Lagrange có thể được áp dụng cho các ràng buộc bất đẳng thức. Với tập hợp các ràng buộc bị vi phạm, g(x) tại xk, hàm số gia Lagrange có đạo hàm không liên tục tại điểm nghiệm nếu bất kỳ ràng buộc nào là có hiệu lực (Gill, Murray and Wright, 1981). Buys (1972) và Rockafellar (1973a,b, 1974) đã đưa ra hàm số gia Lagrange cho các bài toán ràng buộc bất đẳng thức
2
2 1
, , 2
2
i
i
m i i i
A
i
i
g g
L f
x x x
x x
x
i
i
nÕu g nÕu g
(4.7.2)
Những ví dụ về việc sử dụng thủ tục số gia Lagrange cho việc kết hợp các ràng buộc biên vào trong các mô hình cho các hệ thống nước ngầm và các hệ thống phân phối nước được trình bày trong Chương 8 và 9.
H×nh 4.7.1
Đường liền nét là đồ thị hàm mục tiêu của Ví dụ 4.7.1 F(x) = x3. Đường các dấu chấm biểu thị đồ thị của hàm Lagrange, và đường nét đứt là đồ thị của số gia Lagrange LA (x,*, 9) (Lấy theo Gill, Murray và Wright, 1981).